# Minimal Boggle-like Arrangements

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 Q.

The word 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:

MAN
PLC


However, the minimum number of cubes needed for longer, more complex strings is not always obvious.

# Challenge

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.

# Example

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:

Oklaho
!m


or

  !
Oamo
klh


or

   lkO
!amo
h


etc.

• This sounds like a tough optimisation problem. I think it would have made a nice code challenge. Sep 17 '14 at 11:31
• I can't edit because there's a pending edit from a low-rep user, but Mississippi has two double-s. Sep 17 '14 at 11:54
• What about case sensitivity? Sep 17 '14 at 11:56
• @proudhaskeller I'm sure the input is case insensitive, because: 1) the input is just any printable ASCII 2) the OP didn't mention otherwise 3) The oklahoma example wouldn't be minimal if the input was case insensitive. Sep 17 '14 at 12:15
• @MartinBüttner I think you meant case sensitive Sep 17 '14 at 13:40

## Python 342 355398

R=(-1,0,1)
A=[];b={}
def s(w,x,y):
if w: # not at the end of the word yet?
for I in R: # search adjacent squares
for j in R:
if I|j: # skip the square we are on
i=I+x;j+=y;c=b.get((i,j)) # get square in board
if c==w[0]:s(w[1:],i,j) # square is what we are looking for?
elif not c:b[i,j]=w[0];s(w[1:],i,j);del b[i,j] # we can set square?
else:A.append(dict(b)) # all solutions
s(raw_input(),9,9) # run the search
A=min(A,key=len) # A is now the shortest solution
C=sum(map(list,A),[]) # put all board coords together
C=range(min(C),max(C)+1) # find the board biggest square bound
for r in C:print"".join(A.get((c,r)," ") for c in C)


Indent at four spaces is actually a tab character.

AMANAPLANACANALPANAMA:

MC
NA
PL


MISSISSIPPI:

S
SI
PPM


Oklahoma!:

oh
ma
! l
k
O


Llanfairpwllgwyngyll is lethal ;)

• Looks good now, just really slow :/ Sep 17 '14 at 19:32
• You can shorten it a bit by removing import sys and replacing sys.argv[1] with raw_input(). Sep 17 '14 at 20:06
• @Calvin'sHobbies thx again, neat tip :) To get an early out you can just change the elif to elif not c and (not A or len(b)<len(A[-1])): and it runs a lot faster
– Will
Sep 17 '14 at 20:30
• if "Oklahoma!" is OK input, you could just use input() instead of raw_input(). Sep 18 '14 at 17:14