Enigmatic Code

Programming Enigma Puzzles

Enigma 1735: A pile of coloured cubes

From New Scientist #2903, 9th February 2013 [link]

I have several boxes, each containing a number of cubes. Each cube has black and white faces (at least one of each colour per cube), and each box contains all possible different cubes, with no duplicates. My three nephews opened the first box and each tried to assemble their own 2×2×2 cube with only one colour on its outer faces, and of course they failed. They then opened further boxes until they were each able to assemble a single-coloured 2×2×2 cube. They then put all the leftover cubes from the open boxes in a pile.

How many cubes were there in the leftover pile?

[enigma1735]

Advertisements

6 responses to “Enigma 1735: A pile of coloured cubes

  1. Jim Randell 6 February 2013 at 11:27 pm

    The following Python program computes the number of different 2-coloured cubes in each box, and which of these can be used as vertices in the 2×2×2 cubes, then — assuming the three nephews construct two 2×2×2 cubes of one colour and one of the other colour — it calculates how many boxes are required, and how many of the smaller cubes remain. It’s not particularly elegant, but it does the job in 35ms.

    from itertools import product, count
    from enigma import printf
    
    # consider a cube with faces - up, down, front, back, left, right
    
    # given a cube we can rotate it so that any of the the faces is U
    # (6 choices) and then can chose any of the 4 adjacent faces can be
    # rotated to F (4 choices), giving 6 x 4 = 24 possible rotations of
    # the cube.
    
    # moves on a cube for each axis
    (u, d, f, b, l, r) = (0, 1, 2, 3, 4, 5)
    
    U = (u, d, r, l, f, b)
    F = (l, r, f, b, d, u)
    L = (b, f, u, d, l, r)
    
    # apply a bunch of moves to a cube
    def move(c, rs):
      for r in rs:
        c = tuple(c[i] for i in r)
      return c
    
    # all rotations of the cube
    def rotations(c0):
      s = set()
      # go through the faces and put each one on U
      rU = [ [], [L, L], [L, L, L], [L], [F, F, F], [F] ]
      # and move each of the 4 adjacent faces to F
      rF = [ [], [U], [U, U], [U, U, U] ]
      for u in rU:
        c = move(c0, u)
        for f in rF:
          s.add(move(c, f))
      return s
    
    # make a box of 2-coloured cubes
    (white, black) = ('W', 'B')
    cubes = set()
    for c in product((white, black), repeat=6):
      if not(white in c and black in c): continue
      cubes.add(min(rotations(c)))
    n = len(cubes)
    printf("[{n} cubes per box]")
    
    # count the number of cubes per box that can form:
    # - the vertex of a 2x2x2 cube of colour 0 (but not colour 1)
    # - the vertex of a 2x2x2 cube of colour 1 (but not colour 0)
    # - the vertex of either colour 2x2x2 cube
    (w, b, wb) = (0, 0, 0)
    for c in cubes:
      vw = any(u == f == l == white for (u, d, f, b, l, r) in rotations(c))
      vb = any(u == f == l == black for (u, d, f, b, l, r) in rotations(c))
      if vw and vb: wb += 1
      elif vw: w += 1
      elif vb: b += 1
    printf("[{w} cubes in the box can be used to make a white 2x2x2 cube]")
    printf("[{b} cubes in the box can be used to make a black 2x2x2 cube]")
    printf("[{wb} cubes in the box can be used to make a 2x2x2 cube of either colour]")  
    
    # we need 8 vertex cubes of the right colour to make a 2x2x2 cube
    
    # assuming we make 2 big cubes of one colour, and 1 of the other...
    
    # open x boxes
    (x0, r) = divmod(24, w + b + wb)
    if r > 0: x0 += 1
    for x in count(x0):
      (nw, nb, nwb) = (w * x, b * x, wb * x)
      printf("[{x} boxes have {nw}x w cubes, {nb}x b cubes, {nwb}x wb cubes]")
      # can we make two white 2x2x2 cubes?
      if 16 > nw + nwb: continue
      # how many of the wb cubes are used?
      u = max(0, 16 - nw)
      # can we make one black 2x2x2 cube from what's left?
      if 8 > nb + nwb - u: continue
    
      printf("[2x 2x2x2 white cubes use {n1} w + {u} wb cubes]", n1=min(nw, 16))
      printf("[1x 2x2x2 black cube uses {n1} b + {n2} wb cubes]", n1=min(nb, 8), n2=max(0, 8 - nb))
    
      printf("{r} cubes left over from {x} boxes", r=x * n - 24)
      break
    

    Solution: There were 24 cubes left over.

  2. mirtouli 17 February 2013 at 4:26 pm

    For sure not very elegant.
    How long did it take to write the program, well written indeed.
    Next time you may not use a nuclear weapon to solve such enigma

    • Jim Randell 18 February 2013 at 9:35 am

      I wrote the program after solving the puzzle by hand, so the program is really just going through the steps I did manually – I didn’t want it to end up on my list of Enigmas that I’ve not solved programatically.

      Once you’ve worked out which of the smaller cubes can be used to construct the larger cubes the solution is straightforward, so I decided to make it a more interesting programming challenge by deriving the rotations of the cube, and the set of different 2-colourings from scratch. I was hoping to come up with a neater way of generating all the rotations of the cube, but in the end – inspired by playing with a Rubik’s cube – I did it mechanically based on the rotations around each axis.

      The program verifies the solution that I did manually, so I’m happy.

      • martin 19 February 2013 at 7:06 am

        Thanks for your comment.
        I downloaded your enigma.py library. Plenty of good tools.
        I had an issue copying your solver for the 2x2x2 cube as some variables were not seen as global. I have still a lot to learn to use Python correctly.
        Have a nice day

        • Jim Randell 19 February 2013 at 3:37 pm

          I’ve verified the code posted above (and the latest enigma.py library) runs on Python 2 and Python 3 (using 2.7.3 and 3.3.0 on OS X, 2.7.3 and 3.2.3 on Linux), so maybe there’s a problem with your Python installation? If you’re still having problems you could drop me an email with the error message your getting, but I’m not sure if I’ll be able to suggest anything as it all looks like it’s working at this end.

          • Martin 20 February 2013 at 6:46 am

            As I said previously, I have still a lot to learn. I was not my intention to suggest your program was wrong but rather to insist on the fact that I probably not run it as it shoul. Enjoy your day.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: