K 99: Ninety Nine K Problems

Ryan Gonzalez edited this page Jun 3, 2015 · 15 revisions

K translation of Ninety-Nine Prolog Problems

Problem 1

Find the last element of a list.

Example

  last "abcdef"
"f"

Solution

last : *|:           / reverse, take first
last2: {x@-1+#x}     / index at length-1
last3: {:[1=#x;x;_f 1_ x]}
last4: {-1#x}        / take 1 from end

Problem 2

Find the last but one element of a list.

Example

  butlast "abcdef"
"e"

Solution

butlast : {(|x)@1}
butlast2: {x@-2+#x}
butlast3: {:[2=#x;*x;_f 1_ x]}
butlast4: *-2!

Problem 3

Find the K'th element of a list.

Example

  elementat["abcdef";3]
"c"

Solution

elementat : {x@y-1}
elementat2: {*(y-1)(1_)/x}
elementat2: {:[y=1;*x;_f[1_ x;y-1]]}

Problem 4

Find the number of elements of a list.

Example

  length 1 2 3 4
4

Solution

length : #:
length2: {+/*:'1,'x}

Problem 5

Reverse a list.

Example

  reverse "abcdef"
"fedcba"

Solution

reverse : |:
reverse2: {x@(-1+l)-!l:#x}
reverse3: {:[1=#x;x;_f[1_ x],*x]}

Problem 6

Find out whether a list is a palindrome.

Example

  ispalindrome "aacbcaa"
1

Solution

ispalindrome: {x~|x}

Problem 7

Flatten a nested list structure.

Example

  flatten ((1;2 3);(4;(5;(6;7)));8)
1 2 3 4 5 6 7 8

Solution

flatten: ,//

Problem 8

Eliminate consecutive duplicates of list elements.

Example

  compress "aaaabccaadeeee"
"abcade"

Solution

compress : {x@&1,~=':x}
range : ?    / built in operator

Problem 9

Pack consecutive duplicates of list elements into sublists.

Example

  pack "aaaabccaadeeee"
("aaaa"
 ,"b"
 "cc"
 "aa"
 ,"d"
 "eeee")

Solution

pack: {(&1,~=':x)_ x}

Problem 10

Run-length encoding of a list.

Example

  encode "aaaabccaadeeee"
((4;"a")
 (1;"b")
 (2;"c")
 (2;"a")
 (1;"d")
 (4;"e"))

Solution

encode: {(#:'a),'*:'a:pack x}

Problem 11

Modified run-length encoding.

Example

  encodemod "aaaabccaadeeee"
((4;"a")
 ,"b"
 (2;"c")
 (2;"a")
 ,"d"
 (4;"e"))

Solution

encodemod: {{:[1=l:#x;x;l,?x]}'pack x}

Problem 12

Decode a run-length encoded list.

Example

  decodemod ((4;"a");"b";(2;"c");(2;"a");"d";(4;"e"))
"aaaabccaadeeee"

Solution

decodemod: ,/{:[2=#x;(*x)#x@1;x]}'
decodemod2: ,/#/'

Problem 13

Run-length encoding of a list (direct solution).
Don't explicitly create the sublists containing the duplicates, only count them.

Example

  encodedir "aaaabccaadeeee"
((4;"a")
 ,"b"
 (2;"c")
 (2;"a")
 ,"d"
 (4;"e"))

Solution

encodedir: {(-':a,#x),'x@a:&1,~=':x}

Problem 14

Duplicate the elements of a list.

Example

  dupl "abccd"
"aabbccccdd"

Solution

dupl : ,/2#'
dupl2: ,/{x,x}'

Problem 15

Duplicate the elements of a list a given number of times.

Example

  repl["abccd";3]
"aaabbbccccccddd"

Solution

repl: {,/y#'x}

Problem 16

Drop every N'th element from a list.

Example

  dropevery["abcdefghij";3]
"abdeghj"

Solution

dropevery : {x@&~(#x)#((y-1)#0),1}
dropevery2: {x _di-1+y*1+!(#x)%y}

Problem 17

Split a list into two parts; the length of the first part is given.
Do not use any predefined predicates.

Example

  split["abcdefghij";3]
("abc"
 "defghij")

Solution

split : {(y#x;y _ x)}
split2: {(0,y)_ x}
split3: {(x@!y;x@y+!(#x)-y)}

Problem 18

Extract a slice from a list.

Example

  slice["abcdefghij";3;7]
"cdef"

Solution

slice : {(y-1)_(z-1)#x}
slice2: {x@(y-1)+!z-y}

Problem 19

Rotate a list N places to the left.

Example

  rotate["abcdefghij";3]
"defghijabc"

Solution

rotate : {y!x}
rotate2: {,/(y>0)|:/split[x;y]}

Problem 20

Remove the K'th element from a list.

Example

  removeat["abcdef";3]
("c"
 "abdef")

Solution

removeat : {(x@y;x _di y:y-1)}
removeat2: {(x@i;x@&~x=x@i:y-1)}

Problem 21

Insert an element at a given position into a list.

Example

  insert["abcd";2;"alfa"]
("a"
 "alfa"
 "b"
 "c"
 "d")

Solution

insert : {(l#x),(,z),(l:y-1)_ x}
insert2: {(*s),(,z),,/1_ s:split[x;y]}
insert3: {{x,(,z),y}/split[x;y]}
insert4: {:[y=1;(,z),x;(*x),_f[1_ x;y-1;z]]}

Problem 22

Create a list containing all integers within a given range.

Example

  range[3;7]
3 4 5 6 7
  range[9;3]
9 8 7 6 5 4 3

Solution

range: {x+:[0>y-x;-1;1]*!1+_abs y-x}
range: {:[x>y;|y+!x-y-1;x+!y-x-1]}

Problem 23

Extract a given number of randomly selected elements from a list.

Example

  rndselect["abcdefgh";3]
"bfe"

Solution

rndselect: {x@(-y)?#x}

Problem 24

Lotto: Draw N different random numbers from the set 1..M.

Example

  lotto[6;49]
12 34 15 31 29 22

Solution

lotto : {(-x)?y}
lotto2: {x _draw -y}

Problem 25

Generate a random permutation of the elements of a list.

Example

  rndperm["abcdef"]
"efbadc"

Solution

rndperm: {x@(-l)?l:#x}

Problem 26

Generate the combinations of K distinct objects chosen from the N elements of a list.

Example

  combin["abcdef";3]
("abc"
 "abd"
 "abe"
 "abf"
 ...
 "def")

Solution

combin: {x@<x:x@{&:'y(?,/(1!)\'1,')/,&x-y}[#x;y]}

Problem 27 (Incomplete)

Group the elements of a set into disjoint subsets.

Example

  list:("aldo";"beat";"carla";"david";"evi";"flip";"gary";"hugo";"ida")
  group[list;3]
(("evi"
  "flip"
  "ida")
 ("evi"
  "flip"
  "gary")
 ...)

Solution

group: {combin[x;]'y}

Problem 28

a)

Sorting a list of lists according to length of sublists.

Example

  lsort[("abc";"de";"fgh";"de";"ijkl";"mn";"o")]
("o"
 "de"
 "de"
 "mn"
 "abc"
 "fgh"
 "ijkl")

Solution

lsort: {x@<#:'x}

b)

Sorting a list of lists according to length frequency of sublists.

Example

  lfsort[("abc";"de";"fgh";"de";"ijkl";"mn";"o")]
("ijkl"
 "o"
 "abc"
 "fgh"
 "de"
 "de"
 "mn")

Solution

lfsort: {x@,/f@<f:=#:'x}

Problem 29 (2.01)

Determine whether a given integer number is prime.

Example

  isprime ' 0 1 2 4 5
0 0 1 0 1

Solution

isprime: {2~#&~x!'!1+x}

Problem 30 (2.02)

Determine the prime factors of a given positive integer.

Example

  primefactors 315
3 3 5 7

Solution

primefactors: {{y%x}':({x>1}{x%*{1_ &~(x!)'!1+x}x}\x)}

Problem 31 (2.03)

Construct a list containing the prime factors and their multiplicity.

Example

  multiplicity 315
(2 3
 1 5
 1 7)

Solution

multiplicity: {encode primefactors x}

Problem 32 (2.04)

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

Example

  primes[2;25]
2 3 5 7 11 13 17 19 23

Solution

primes: {x+&isprime'x+!1+y-x}

Problem 33 (2.05)

Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. Find the two prime numbers that sum up to a given even integer.

Example

  goldbach 28
5 23

Solution

ppairs:   {,/t,/:\:t:primes[2;x]}
goldbach: {*t@&{x=+/y}[x]'t:ppairs[x]}

Problem 34 (2.06)

Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.

Example

  goldbachc[9;20]
(10 3 7
 12 5 7
 14 3 11
 16 3 13
 18 5 13
 20 3 17)

Solution

evens:     {2*((x+1)%2)+!(1+y-x)%2}
goldbachc: {{x,goldbach x}'evens[x;y]}

Problem 35 (2.07)

Determine the greatest common divisor of two positive integer numbers.

Example

  gcd[36;63]
9

Solution

gcd: {:[y;_f[y;x!y];x]}

Problem 36 (2.08)

Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.

Example

  coprime[35;64]
1
  coprime[35;63]
0

Solution

coprime: {1=gcd[x;y]}

Problem 37 (2.09)

Calculate Euler's totient function phi(m). Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.

Example

  phi 10
4

Solution

phi: {+/coprime[x]'!x}

Problem 38 (2.10)

Calculate Euler's totient function phi(m)(2). If the list of the prime factors of a number m is known in the form of problem 2.03 then the function phi(m) can be efficiently calculated as follows: Let [[m1,p1],[m2,p2],[m3,p3],...] be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:
phi(m) = (p1 - 1) * p1^(m1 - 1) * (p2 - 1) * p2^(m2 - 1) * (p3 - 1) * p3^(m3 - 1) * ...

Example

  phi2 10
4

Solution

phi2: {*/{(y-1)*y^x-1}.'multiplicity x};

Problem 39 (2.11)

Compare the two methods of calculating Euler's totient function.

Example

  \t phi 10090
806
  \t phi2 10090
7
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.