Consider how a word could be arranged on an arbitrarily large Boggle grid if the rule about not using the same letter cube more than once is ignored. Also assume that you have an unlimited number of letter cubes (with all letters present), and
Qu is just
MISSISSIPPI could be arranged using only 6 cubes. Here is one possible arrangement:
S MIS PP
Starting at the
M we repeatedly take any step horizontally, vertically, or diagonally until the entire word is spelled out.
Surprisingly, a longer phrase like
AMANAPLANACANALPANAMA also only needs 6 cubes:
However, the minimum number of cubes needed for longer, more complex strings is not always obvious.
Write a program that takes in a string and arranges it in this Boggle-like fashion such that the minimum number of cubes are used. (The dimensions of the resulting grid and the number of empty cells are irrelevant.)
Assume you have have an unlimited number of cubes for each printable ASCII character except space (hex codes 21 to 7E), since it's used as an empty grid cell. Only printable ASCII strings (without spaces) will be input.
Input should be taken from stdin or the command line. Output should go to stdout (or closest alternative).
Leading or trailing newlines and spaces in the output are fine (but hopefully there aren't an inordinate amount).
The search space blows up exponentially as the string gets longer, but you are not required to attempt to make your algorithm efficient (though that would be nice :) ). This is code-golf, so the shortest solution in bytes wins.
If the input were
Oklahoma! (8 character minimum), these would all be valid outputs because the all have exactly 8 filled grid cells and they follow the (revised) Boggle reading pattern:
! Oamo klh
lkO !amo h