14
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ This sounds like a tough optimisation problem. I think it would have made a nice code challenge. \$\endgroup\$ – Martin Ender Sep 17 '14 at 11:31
  • 1
    \$\begingroup\$ I can't edit because there's a pending edit from a low-rep user, but Mississippi has two double-s. \$\endgroup\$ – Peter Taylor Sep 17 '14 at 11:54
  • \$\begingroup\$ What about case sensitivity? \$\endgroup\$ – proud haskeller Sep 17 '14 at 11:56
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Sep 17 '14 at 12:15
  • \$\begingroup\$ @MartinBüttner I think you meant case sensitive \$\endgroup\$ – Ypnypn Sep 17 '14 at 13:40
5
\$\begingroup\$

Python 342 355 398

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 ;)

\$\endgroup\$
  • \$\begingroup\$ Looks good now, just really slow :/ \$\endgroup\$ – Calvin's Hobbies Sep 17 '14 at 19:32
  • 1
    \$\begingroup\$ You can shorten it a bit by removing import sys and replacing sys.argv[1] with raw_input(). \$\endgroup\$ – Calvin's Hobbies Sep 17 '14 at 20:06
  • \$\begingroup\$ @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 \$\endgroup\$ – Will Sep 17 '14 at 20:30
  • 1
    \$\begingroup\$ if "Oklahoma!" is OK input, you could just use input() instead of raw_input(). \$\endgroup\$ – FryAmTheEggman Sep 18 '14 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.