A World Without Strings is Chaos

I developed these programming exercises while working at 1010data. Each summer we’d put a batch of half a dozen or so interns through a week-long intensive K training program, including this set of puzzles, and then set them loose on the real codebase.

These problems vary in difficulty from trivial to moderately difficult (in non-escalating order), and are suitable for beginners or anyone wishing to brush a little rust off. A solution is provided for each problem in k3- click and hold on the gray area beneath each IO sample to reveal it. Most problems have at least one elegant solution, but many have multiple valid approaches- see how many ways you can satisfy the requirements!

0 - Multiplicity

Characters are expensive, and the accountants tell me we can’t hand them out willy-nilly anymore. Given a string x and a character y, how many times does y occur in x?


1 - Trapeze Part

Sometimes I try reading sentences right-to-left to make my life more exciting. Results have been mixed. Given a string x, is it identical when read forwards and backwards?

  f "racecar"
  f "wasitaratisaw"
  f "palindrome"

2 - Duplicity

One is the loneliest number. Given a string x, produce a list of characters which appear more than once in x.

  f "applause"
  f "foo"
  f "baz"

3 - Sort Yourself Out

Alphabetical filing systems are passe. It’s far more Zen to organize words by their histograms! Given strings x and y, do both strings contain the same letters, possibly in a different order?


4 - Precious Snowflakes

It’s virtuous to be unique, just like everyone else. Given a string x, find all the characters which occur exactly once, in the order they appear.

  f "somewhat heterogenous"
"mwa rgnu"
  f "aaabccddefffgg"

5 - Musical Chars

Imagine four chars on the edge of a cliff. Say a direct copy of the char nearest the cliff is sent to the back of the line of char and takes the place of the first char. The formerly first char becomes the second, the second becomes the third, and the fourth falls off the cliff. Strings work the same way. Given strings x and y, is x a rotation of the characters in y?


6 - Size Matters

Sometimes small things come first. Given a list of strings x, sort the strings by length, ascending.

  f ("books";"apple";"peanut";"aardvark";"melon";"pie")

7 - Popularity Contest

Sixty-two thousand four hundred repetitions make one truth. Given a string x, identify the character which occurs most frequently. If more than one character occurs the same number of times, you may choose arbitrarily. Is it harder to find all such characters?

  f "abdbbac"

8 - esreveR A ecnetneS

Little-endian encoding is such a brilliant idea I want to try applying it to English. Given a string x consisting of words (one or more non-space characters) which are separated by spaces, reverse the order of the characters in each word.

  f "a few words in a sentence"
"a wef sdrow ni a ecnetnes"
  f "zoop"
  f "one two three four"
"eno owt eerht ruof"
{1_,/|:'(&" "=" ",x)_ x," "}

9 - Compression Session

Let’s cut some text down to size. Given a string x and a boolean vector y of the same length, extract the characters of x corresponding to a 1 in y.

  f["foobar";1 0 0 1 0 1]
  f["embiggener";0 0 1 1 1 1 0 0 1 1]

10 - Expansion Mansion

Wait, strike that- reverse it. Given a string x and a boolean vector y, spread the characters of x to the positions of 1s in y, filling intervening characters with underscores.

  f["fbr";1 0 0 1 0 1]
  f["bigger";0 0 1 1 1 1 0 0 1 1]

11 - C_ns_n_nts

Vowels make prose far too… pronounceable. Given a string x, replace all the vowels (a, e, i, o, u, or y) with underscores.

  f "Several normal words"
"S_v_r_l n_rm_l w_rds"
{(x;"_")x _in "aeiouyAEIOUY"}'

12 - Cnsnnts Rdx

On second thought, I’ve deemed vowels too vile for placeholders. Given a string x, remove all the vowels entirely.

  f "Several normal words"
"Svrl nrml wrds"
{x@&{~x _in "aeiouyAEIOUY"}'x}


Given a string x consisting of words separated by spaces (as above), and a string y, replace all words in x which are the same as y with a series of xes.

  f["a few words in a sentence";"words"]
"a few XXXXX in a sentence"
  f["one fish two fish";"fish"]
"one XXXX two XXXX"
  f["I don't give a care";"care"]
"I don't give a XXXX"
{{x," ",y}/(+(t;(#:'t)#'"X"))@'y~/:t:-1_'(&" "=" ",x)_ x," "}

14 - It’s More Fun to Permute

My ingenious histogram-based filing system has a tiny flaw: some people insist that the order of letters in their names is significant, and now I need to re-file everything. Given a string x, generate a list of all possible reorderings of the characters in x. Can you do this non-recursively?

  f "xyz"
{:[#x;,/x,''_f'x _dv/:x;,x]} / recursive
{x@?<:'+s _vs!_ s^s:#x} / non-recursive