Programming | Geoff Canyon's Appeal to Authority

I have a puzzle called Instant Insanity. It consists of four cubes, with each face one of four colors (each cube has several faces that are colored the same). No one at the office has solved it, despite several of us devising methods to help.

Someone was fiddling with the cubes today, and after talking about the possible combinations, I realized a fairly simple brute force attack wouldn’t be too difficult to write. So I bet I could do it in ten minutes.

I lost. I took twenty minutes to write about sixty lines of code that didn’t find the solution.

Everything looked right, but it didn’t work. I looked at it again later, and after another twenty minutes I noticed my mistake. The problem was in the stringsFrom function. In a repeat, I used the variable I was iterating over instead of the iterator. The correct code was:

repeat for each line L in R2
put rotString(L) after R3

But I had this:

repeat for each line L in R2
put rotString(R2) after R3

And that’s all it takes to put a hurt on you — bad developer, no biscuit.

Updated to add the layout of the four cubes:

G
BGB
R
W

R
RWR
B
G

W
RGW
B
R

B
WWG
R
B

Here’s the correct version, along with all the utility functions that build the strings and check the solutions:

function stringsFrom X
-- Takes a cross-shaped representation of the sides of a cube
-- and returns all the possible unique loops of four sides (could be up to 24)

-- First loop: across the t, and the bottom
  put char 1 to 3 of line 2 of X & char 2 of line 4 of X & cr after R

-- Second loop: the vertical of the t
  repeat with i = 1 to 4
put char 2 of line i of X after R
  end repeat

-- Third loop loop: around the intersection of the t
  put cr after R
  put char 2 of line 3 of X & char 3 of line 2 of X & char 2 of line 1 of X & char 1 of line 2 of X & cr after R

-- add the reverse of the strings
  repeat for each line L in R
  put rString(L) & cr after R2
  end repeat

-- add the rotations of the strings
  repeat for each line L in R2
put rotString(L) after R3
  end repeat

-- de-dupe
   repeat for each line L in R3
put 1 into R4[L]
   end repeat
   return the keys of R4
end stringsFrom

function cube x
-- Returns the data for the requested cube

   return line 5 * x - 4 to 5 * x - 1 of fld 1
end cube

function rString X
-- Takes a 4-character string
-- Returns the string and its reverse

   put cr before X
   repeat with i = 1 to 4
  put char i of line 2 of X before X
   end repeat
   return X
end rString

function rotString X
-- Takes a 4-character string
-- Returns the four rotations of it

   put X after X
   repeat with i = 1 to 4
  put char i to i + 3 of X & cr after R
   end repeat
   return R
end rotString

function checkit X
-- Takes a set of lines in a string, and returns true if they have
-- no columns with duplicate characters
-- Hard-coded to 4-character strings and "RGBW"
-- But will handle 2, 3, or 4 lines

   put the number of lines of X into LC
   repeat with i = 1 to 4
  put "RGBW" into T
  repeat with z = 1 to LC
     replace (char i of line z of X) with empty in T
  end repeat
  if length(T) > 4 - LC then return false
end repeat
   return true
end checkit

I was surprised that checkit was seemingly fast. I tried arrays, which made more intuitive sense than using replace, and found that this was roughly twice as slow:

function checkit X
-- Takes a set of lines in a string, and returns true if they have
-- no columns with duplicate characters
-- Handles arbitrary line length, number of lines, and characters

repeat for each line L in X
  repeat with i = 1 to length(L)
  if T[i] contains char i of L then return false else put char i of L after T[i]
  end repeat
  end repeat
  return true
end checkit

Here’s the too-brute-force code. It builds a list of all the possible combinations, and then parses through them looking for one that works.

on mouseUp
-- Takes four cube definitions in t format
-- And finds any solution to the Instant Insanity puzzle

-- Get the sets of strings for the cubes
repeat with i = 1 to 4
put stringsFrom(cube(i)) into stringList[i]
end repeat

-- Build all the candidate solutions
put 1 into X
  repeat for each line L1 in stringList[1]
  repeat for each line L2 in stringList[2]
  repeat for each line L3 in stringList[3]
  repeat for each line L4 in stringList[4]
  put L1 & cr & L2 & cr & L3 & cr & L4 into T[X]
  add 1 to X
  end repeat
  end repeat
  end repeat
  end repeat

-- Test each candidate to see if it works
repeat for each element E in T
if not checkit(E) then next repeat

   -- Success!
  put E into fld "solution"
exit to top
  end repeat
-- Failure.

put "fail" into fld "solution"
end mouseUp

Here’s a much better version that checks the combinations as it generates them, meaning that it will stop building a combination after two or three cubes if it has duplicate colors, and exits as soon as it finds a solution. Further optimizations are obviously possible, but this reduces the runtime from just under a second to about 30 milliseconds, so I’m done.

on mouseUp
-- Takes four cube definitions in t format
-- And finds any solution to the Instant Insanity puzzle

-- Four nested repeats
-- Each based on the set of strings for one cube

repeat for each line L1 in stringsFrom(cube(1))
repeat for each line L2 in stringsFrom(cube(2))

-- If the first two cubes have duplicate colors,
-- jump to the next option
if not checkit(L1 & cr & L2) then next repeat
repeat for each line L3 in stringsFrom(cube(3))

-- If the first three cubes have duplicate colors,
-- jump to the next option
if not checkit(L1 & cr & L2 & cr & L3) then next repeat
repeat for each line L4 in stringsFrom(cube(4))

-- If the four cubes have duplicate colors,
-- jump to the next option
if not checkit(L1 & cr & L2 & cr & L3 & cr & L4) then next repeat

-- Otherwise, success!
  put L1 & cr & L2 & cr & L3 & cr & L4 into fld "solution"
  exit to top
  end repeat
  end repeat
  end repeat
end repeat
  put "fail" into fld "solution"
end mouseUp

Geoff Canyon's Appeal to Authority

Tag Archives: Programming

Brute Force Insanity