Enigmatic Code

Programming Enigma Puzzles

Enigma 1257: Boxing clever

From New Scientist #2413, 20th September 2003 [link]

Triangulo, the world-famous Cuban cubist, has created five boxes, each of which contains a number of cubes of the same colour, but with a different colour in each box.

At a master class, he tries to construct a particular size of cube using all the cubes from just two boxes.  But whichever pair he selects, he finds that at least one pair has too many pieces and all the other pairs have too few.

Each different pair of boxes gives a different total of cubes and the largest total is 10 more than the smallest.

With a stoke of genius, using all the cubes together, he creates instead a flat square, multi-coloured masterpiece!

How many cubes (in ascending order) are there in each box?

This puzzle is Enigma 1257 and the previous puzzle I published was Enigma 256, so there are now 1,000 puzzles left to publish (ignoring for the moment that sometimes multiple puzzles are published under the same number, and that I’ve already published Enigma 1095). Which means just under 44% of all Enigma puzzles are now available on the site.

[enigma1257]

Advertisements

8 responses to “Enigma 1257: Boxing clever

  1. Jim Randell 8 February 2015 at 8:48 am

    I think the setter intends for us to assume that the cubes in the boxes are all the same size.

    I originally solved this puzzle by considering increasing square numbers and decomposing them into sets of 5 distinct integers, but it is more efficient to examine the neighbourhoods of the cube numbers.

    This Python program runs in 34ms.

    # There are 5 boxes of unit cubes, pairs of boxes can be chosen in
    # C(5, 2) = 10 different ways.
    #
    # Each of these combinations has a different total number of cubes,
    # and the pair with the most cubes has 10 more cubes than the pair
    # with the lowest number of cubes. So the totals are distributed
    # amongst 11 numbers - there is one unused number somewhere in the
    # middle and this number is a cube number.
    #
    # The sum of the number of cubes for each pair is 4x the sum of the
    # cubes in all the boxes, which is a square number.
    
    from itertools import count
    from enigma import irange, is_square, printf
    
    def generate():
      # consider the target cube
      for i in count(2):
        n = i ** 3
    
        # consider possible totals for the smallest pair
        for k in irange(max(n - 9, 3), n - 1):
          # the totals run from k to k + 10 and exclude n,
          # but n must be interior to the sequence
          ts = tuple(irange(k, k + 10))
          # so t = a + b + c + d + e is...
          (t, r) = divmod(sum(ts) - n, 4)
          if r > 0: continue
          # and this should be a square number
          s = is_square(t)
          if s is None: continue
    
          # now look for the 5 numbers of cubes, a < b < c < d < e
          # (a + b) + 10 == (d + e)
          # so the range of the numbers is (e - a) = 10 - (d - b)
          # and (d - b) is at least 2, so (e - a) is at most 8
          # so (b - a) is at most 5
    
          # a + b == ts[0]
          h = ts[0] // 2
          for a in irange(h - 2, h):
            b = ts[0] - a
            if not(a < b): break
            # d + e == ts[-1]
            for d in irange(b + 1, ts[-1] // 2):
              e = ts[-1] - d
              if not(d < e): continue
              # what pairs have we made?
              ps = set((a + b, a + d, a + e, b + d, b + e, d + e))
              # they should be distinct, and exclude n
              if len(ps) != 6 or n in ps: continue
              # so c is...
              (c, r) = divmod(4 * t - sum(ps) - (a + b + d + e), 4)
              if r > 0: continue
              if not(b < c < d): continue
              # add in the pairs that use box c
              ps.update((a + c, b + c, c + d, c + e))
              # they should all still be distinct
              if len(ps) < 10: continue
              printf("[i={i}, i^3={n}] a={a} b={b} c={c} d={d} e={e}, ps={ps}, t={t} (={s}^2)")
              yield (a, b, c, d, e)
    
    # find the first solution
    for s in generate():
      printf("boxes = {s}")
      break
    

    Solution: The boxes contain 103, 104, 105, 107 and 110 cubes.

    Together the 529 cubes in the five boxes can be used to make a large square with 23 cubes along each edge, but no pair of boxes can make a large cube with 6 cubes along each side, as this requires 216 component cubes, and the number of cubes made by pairing up the boxes are: 207, 208, 209, 210, 211, 212, 213, 214, 215 and 217.

  2. Brian Gladman 10 February 2015 at 5:42 pm

    I didn’t think it was worth speeding this up so I stuck with your original approach.

    from itertools import combinations, count
    
    def is_root(x, n):
      return int(x ** (1 / n) + 0.5) ** n == x
    
    # let the five values be a < b < c < d < e with:
    # 
    # a + b + 10 == d + e -> e - a = 10 - (d - b) -> e <= a + 8
    #
    # min/max of sums of five values from a .. a + 8 are 5.a + 10 and
    # 5.a + 30 so the square satisfies 5.a + 10 <= sq <= 5.a + 30 so
    # a is in the range sq / 5 - 6 to sq / 5 - 2 
    
    def solve():
      for i in count(6):
        # the final square value
        sq = i * i
        # consider the range for a derived above
        for a in range(sq // 5 - 6, sq // 5 - 1):
          
          # pick five values from the nine possibilities
          for c5 in combinations(range(a, a + 9), 5):
            # the sum of all the pairs of five numbers is four times 
            # the sum of the numbers themselves, which is a square
            if is_root(4 * sum(c5), 2):
              
              # check that the ten sums of pairs are distinct
              vals = tuple(sorted(x + y for x, y in combinations(c5, 2)))
              if len(vals) == len(set(vals)) == 10:
              
                # check the missing value is a cube within the range
                val, *r = set(range(vals[0], vals[-1] + 1)) - set(vals)
                if not r and vals[0] < val < vals[-1] and is_root(val, 3):
                  print(c5, val, sq, vals)
                  return
    solve()
    
  3. Jim Randell 12 February 2015 at 9:11 am

    I did try to write a MiniZinc model to solve this one. The model seems quite straightforward, but when I run it it doesn’t seem to enforce the constraint that the total number of cubes is a perfect square, so it produces incorrect answers (along with the correct answer if the -a flag is specified).

    I don’t know if this is a problem with my model, or a problem with MiniZinc itself.

    include "globals.mzn";
    
    % the numbers of cubes in the five boxes
    var int: a;
    var int: b;
    var int: c;
    var int: d;
    var int: e;
    
    % the roots of the square and the cube
    var int: n2;
    var int: n3;
    
    % the numbers of cubes in the boxes are all different
    constraint alldifferent([a, b, c, d, e]);
    constraint increasing([1, a, b, c, d, e]);
    
    % the total number of cubes is a square
    constraint n2 > 0;
    constraint a + b + c + d + e == n2 * n2;
    
    % the pairs (and the cube) are all different
    constraint n3 > 0;
    constraint a + b < n3 * n3 * n3 /\ n3 * n3 * n3 < d + e;
    constraint alldifferent([n3 * n3 * n3, a + b, a + c, a + d, a + e, b + c, b + d, b + e, c + d, c + e, d + e]);
    
    % the difference between the smallest and largest pairs is 10
    constraint a + b + 10 == d + e;
    
    % solve the model
    solve satisfy;
    
    % output the solution (and check the sum constraint on n2)
    output [ "boxes=", show([a, b, c, d, e]), ", n2=", show(n2), ", n3=", show(n3), ": ", show(a + b + c + d + e == n2 * n2) ];
    

    And here’s what happens when I run it…

    % mzn-g12fd enigma1257.mzn
    boxes=[27, 28, 29, 31, 34], n2=12, n3=4: false
    ----------
    
    % mzn-g12fd -a enigma1257.mzn
    boxes=[27, 28, 29, 31, 34], n2=12, n3=4: false
    ----------
    boxes=[30, 33, 35, 36, 37], n2=13, n3=4: false
    ----------
    boxes=[103, 104, 105, 107, 110], n2=23, n3=6: true
    ----------
    boxes=[106, 109, 111, 112, 113], n2=23, n3=6: false
    ----------
    boxes=[167, 169, 170, 171, 175], n2=29, n3=7: false
    ----------
    boxes=[168, 172, 173, 174, 176], n2=29, n3=7: false
    ----------
    boxes=[498, 501, 503, 504, 505], n2=50, n3=10: false
    ----------
    boxes=[3995, 3996, 3997, 3999, 4002], n2=141, n3=20: false
    ----------
    boxes=[3998, 4001, 4003, 4004, 4005], n2=141, n3=20: false
    ----------
    boxes=[5319, 5320, 5321, 5323, 5326], n2=163, n3=22: false
    ----------
    boxes=[5322, 5325, 5327, 5328, 5329], n2=163, n3=22: false
    ----------
    
    
  4. Brian Gladman 12 February 2015 at 4:38 pm

    I am very new to MiniZinc but I can’t see anything wrong with your model. The model compiles but gives no output on the Windows version of MiniZinc, which is different, so it might be a MiniZinc issue of some kind.

  5. hakank 13 February 2015 at 7:59 pm

    I checked Jim’s MiniZinc model and found some issues:

    1) The constraint that doesn’t work seems to be a bug in G12/fd. The Gecode solver (http://gecode.org/) just show the single solution as does most of the other FlatZinc solver I tested. Some solvers throws “integer overflow” error (even when the domains are smaller, see below).

    2) I recommend to use as small domains as possible instead of “var int”. This was one of the problem with Brian running on Windows using the MiniZincIDE: G12/fd throws an integer overflow error with “var int” but the message wasn’t visible in the IDE.

    3) I modified Jim’s model somewhat with smaller domain and a search strategy which makes the model runs faster: 75ms compared to 2.7s with “solve satisfy”. This is the time for a fairly fast Linux Ubuntu machine. Here’s the model: http://hakank.org/minizinc/enigma_1257_boxing_clever_jim_randell2.mzn

    • Brian Gladman 13 February 2015 at 8:37 pm

      Thanks to Hakan for looking at this (and for providing advice on using MiniZinc with other solvers). I installed Gecode x64 on Windows and it solves the problem (with Hakan’s optimisations) as follows:

      Compiling jr2.mzn
      Running jr2.mzn
      boxes=[103, 104, 105, 107, 110], n2=23, n3=6: true
      ———-
      Finished in 69msec

    • Jim Randell 14 February 2015 at 8:19 am

      Thanks for the tips hakank. I downloaded the Gecode solver and using mzn-gecode on my original model does indeed give the right answer.

      % time mzn-gecode enigma1257.mzn
      boxes=[103, 104, 105, 107, 110], n2=23, n3=6: true
      ----------
      mzn-gecode enigma1257.mzn  0.08s user 0.02s system 113% cpu 0.086 total
      

      (This is running on my laptop under OS X 10.10.2).

      I liked that fact that I didn’t have to impose arbitrary limits on the search space in the MiniZinc model.

  6. hakank 14 February 2015 at 10:12 am

    Jim: Yes, sometimes “var int” don’t matter and it’s great feature when writing the first version of the model. But for larger problems or one want to tweak the time, it’s important. As is testing different search strategies (instead of the standard “solve satisfy”).

    A picky note: What I can see you just tested for the first solution. To “prove” that it is a unique solution, add either the “-a” or “-n 0” (or “-n 2”) parameter to mzn-gecode. The solution will presented by a “==========” before the statistics, which is the indication that the solver has checked all solutions. For this problem it took 41ms and 7ms respectively (on my fastest computer).

    Whenever I have a larger problem, I test it with as many FlatZinc solver as possible, and often with Opturion CPX which can be quite fast: http://www.opturion.com/cpx.html . It has an academic license, but what I know it should apply to this kind of recreational programming. One feature of CPX is the “free” (-f parameter) might boost the performance. On this problem it’s a little slower than Gecode: 406ms and 57ms respectively.

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: