Enigmatic Code

Programming Enigma Puzzles

Enigma 166: Water storage

notableFrom New Scientist #1311, 24th June 1982 [link]

Enigma 166

This is a bird’s eye view of my present water store. I got 16 cuboids each 1′×1′, with lengths of 1′, 2′, …, 16′. I stacked them all on end on a level 4′×4′ base and glued them together in that position. As you can see the store’s capacity is 9 (cubic feet). My glue is strong enough to waterproof corner joints, e.g. between 4 and 7 or between 8 and 11. So 3 cu. ft. will stand on number 1, but any more will spill out over 4. And 6 cu. ft. will stand on number 2.

You will notice I could have achieved a bigger capacity with my 16 cuboids. In fact, I could have got 26 cu. ft. But I need something much bigger than that. So I am going to start again with a fresh supply of 64 cuboids, each 1′×1′ again of length 1′, 2′, 3′, …, 64′.

If I stack these on end on an 8′×8′ level base, so that they will hold as much water as possible when glued together, what will be the capacity in cubic feet? I don’t mind if the water is stored in one connected “tank” or (as with my present store) in more than one.

[enigma166]

Advertisements

9 responses to “Enigma 166: Water storage

  1. Jim Randell 4 February 2014 at 8:48 am

    I think this is a tough problem to solve programatically, so I’ve added it to the list of Challenging Puzzles.

    I have coded up a Python program that finds a solution that agrees with the solution published in New Scientist, although I need to clean the program up a bit before putting it up here. I’m interested to hear about any programmatic approaches other people have tried.

    Solution: The maximum capacity achievable on an 8’×8′ base is 946 cu. ft.

    Here is an example of a maximal solution:

    Enigma 166 - Solution

    The deep blue area provides the main tank with a volume of:

    (49 – 1) + (49 – 2) + (49 – 3) + … + (49 – 24) = 876 cu. ft.

    The four light blue areas provide an additional:

    (47 – 25) + (45 – 26) + (43 – 27) + (41 – 28) = 70 cu. ft.

    giving a total volume of 946 cu. ft.

    The 24 deep blue squares can appear in any order, as can the 16 orange squares surrounding them, and the 12 white squares (which play no part in holding the water). The lighter blue and lighter orange squares are arranged to give the largest additional volume in the light blue areas.

    • Jim Randell 6 February 2014 at 12:07 pm

      Here’s my cleaned-up (and tweaked program). Unfortunately one of the tweaks makes it more correct, but means it does a lot more work. So while it displays a minimal solution in about 20 minutes, I think it will take a long time to run to completion and verify that it is indeed the best solution.

      from itertools import product
      from copy import deepcopy
      from enigma import irange, Accumulator, printf
      
      # N is the size of the internal grid, so everything takes place on an (N+2)x(N+2) grid
      import sys
      N = 6 if len(sys.argv) < 2 else int(sys.argv[1])
      
      # mark squares as unassigned, internal, unavailable
      # external squares are marked with the lowest value from that group
      (X, I, U) = (0, -1, -2)
      
      # make an empty grid
      def empty():
        return [[X] * (N + 2) for _ in irange(0, N + 1)]
      
      # make a copy of a grid, keeping external squares and marking current
      # internal squares as unavailable, and new iternal squares from the given list
      def grid(r, ss):
        r2 = deepcopy(r)
        for (j, i) in product(irange(0, N + 1), repeat=2):
          if r[j][i] == I:
            r2[j][i] = U
        for (j, i) in ss:
          r2[j][i] = I
        return r2
      
      # display a region
      def display(r):
        for i in r:
          print(i)
        print()
      
      # find what is connected to a specified square, or if two squares are connected
      def connected(r, p, q=None):
        fs = set([p])
        rs = set()
        while fs:
          (j, i) = fs.pop()
          rs.add((j, i))
          fs.update((j1, i1) for (j1, i1) in ((j - 1, i), (j + 1, i), (j, i - 1), (j, i + 1)) if r[j1][i1] == I)
          fs.difference_update(rs)
          if q and q in fs: return True
        return rs
      
      # generate subregions of a region
      def subregions(r, nI):
        # a breadth first approach
        rs = [r]
        while rs:
          rs2 = []
          for r in rs:
            yield (deepcopy(r), nI)
            # examine the squares
            for (j, i) in product(irange(1, N), repeat=2):
              if r[j][i] == I:
                # find adjacent squares
                adj = list((j1, i1) for (j1, i1) in ((j - 1, i), (j + 1, i), (j, i - 1), (j, i + 1)) if r[j1][i1] == I)
                n = len(adj)
                # can we remove the square?
                if n == 1 or n == 2:
                  s = deepcopy(r)
                  s[j][i] = X
                  # if there are 2 adjacent squares, check they are still connected
                  if n == 2 and not connected(s, *adj): continue
                  if s not in rs2: rs2.append(s)
          rs = rs2
          nI -= 1
      
      # compute maximal volume based on a given region
      def solve(r0, n, values, depth=0):
      
        m = Accumulator(fn=max)
      
        # generate subregions of the region
        for (r, nI) in subregions(r0, n):
      
          # mark the external squares for that region
          (nE, ext) = (0, [])
          for (j, i) in product(irange(0, N + 1), repeat=2):
            if any((j > 0 and r[j - 1][i] == I,
                    i > 0 and r[j][i - 1] == I,
                    j < N + 1 and r[j + 1][i] == I,
                    i < N + 1 and r[j][i + 1] == I)):
              if r[j][i] == X:
                nE += 1
                ext.append((j, i))
              elif r[j][i] > 0:
                ext.append((j, i))
      
          # determine the water level of the region
          if nE > 0:
            w = values[-nE]
            for (j, i) in ext:
              if r[j][i] == X:
                r[j][i] = w
          else:
            w = min(r[j][i] for (j, i) in ext)
      
          # calculate the maximum volume, and remaining values
          v = nI * w - sum(values[:nI])
          values2 = values[nI:len(values) - nE]
          
          # find any remaining unassigned squares in the grid
          rs = set((j, i) for (j, i) in product(irange(1, N), repeat=2) if r[j][i] == X)
          n = len(rs)
          if n > 0:
      
            # compute a theoretical maximum volume for the unassigned squares
            if m.value is not None:
              vm = n * ((N + 2) ** 2 - 3) - sum(values2[:n])
              if not(v + vm > m.value):
                continue
      
            # split the unassigned squares into connected regions
            rs2 = []
            while len(rs) > 0:
              p = rs.pop()
              q = connected(r, p)
              rs2.append(q)
              rs.difference_update(q)
      
            # now find the largest remaining region
            ss = max(rs2, key=len)
            # create a new grid for this region
            r2 = grid(r, ss)
            # and find the maximal volume for that grid
            (v2, values2, r) = solve(r2, len(ss), values2, depth + 1)
            v += v2
      
          # accumulate the volume
          m.accumulate_data(v, (values2, r))
          if depth == 0 and v == m.value:
            printf("volume = {v}")
            display(r)
      
        return (m.value, m.data[0], m.data[1])
      
      
      # create the largest possible NxN region (in an (N+2)x(N+2) grid)
      r0 = empty()
      for (j, i) in product(irange(1, N), repeat=2):
        r0[j][i] = I
      
      # values of the squares
      values = list(irange(1, (N + 2) ** 2))
      
      # determine the maximal possible volume
      (v, _, r) = solve(r0, N ** 2, values)
      
      printf("max = {v}")
      display(r)
      

      The algorithm starts with a specified region of the grid (initially for an 8×8 grid we specify the 6×6 central portion) and generates sub-regions of this initial region and considers each as a water holding tank. Then the procedure is applied recursively to any squares remaining from the initial region to add in the maximal volume made from those squares. The volume of the main tank is added to the maximal volume from the remaining squares to give an overall volume, and the maximum from these overall volumes is selected.

      My original code just tried to fill in the remaining squares, rather than applying the procedure recursively to get a maximal solution. While this was quicker it was a less thorough search. Unfortunately the recursive call means the collection of regions is explored in a depth-first fashion (when a breadth-first search would probably find maximal solutions sooner).

      The sub-regions are generated breadth-first in order of decreasing size. This means that, if a large main tank makes up the lions share of the volume, then a maximal solution will be found sooner, rather than later (but the code will still need to run to completion to make sure that the solution is maximal). A depth-first approach would be easier to program.

      There are also a couple of fairly reasonable (I think) assumptions made:

      The sub-regions are generated by nibbling away at the edges of the region. A square can be removed if it only has one neighbour, or if it has two neighbours and removing it wouldn’t disconnect them.

      The calculation of volumes follows a “greedy” strategy. So the maximum volume of a region is made by using the smallest available values to make the internal squares of the region and the largest available values to make the external “wall” surrounding it. The grid that is output as a solution only contains partial information as to the placement of the blocks, so this strategy needs to be followed to reconstruct a maximal solution.

      Overall this algorithm will work best for large single regions, or large single regions with a few extra tiny regions, it will get hopelessly bogged down on larger grids. Fortunately the solutions seems to follow the pattern that a large “main” tank plus some small extra tanks give a maximal solution.

    • Jim Randell 6 February 2014 at 12:47 pm

      Here are maximal solutions that I found for 3×3 to 7×7 grids:

      Enigma 166 - Solutions

      To maximise the volume we are looking to enclose the maximum possible area with the smallest possible perimeter, so I suppose it makes sense that as the grids get larger the regions approximate to circles.

      • tonysmith 12 February 2014 at 11:57 am

        I derived the general formulae for larger odd and even grids which are the obvious extensions of the7x7 and 8×8 grids given.
        I found that the total volumes in light blue squares are 29 and 70 for ALL odd and even squares respectively.

  2. Brian Gladman 5 February 2014 at 11:08 am

    This is indeed a tough programming challenge, one that I am still thinking about! Congratulations on gettinng a programmmed solution that runs in a reasonable time. My initial thought is to start with the blocks 64 downwards on the outside cells except the corners and 1 upwards on the inside as a starting point and then see if swapping blocks can improve on this. But I haven’t convinced myself that swapping blocks will lead to a solution.

    • Jim Randell 5 February 2014 at 11:18 am

      My program eventually completed after 17h26m (although it finds the solution in a few minutes, it just doesn’t know it’s maximal until it’s finished). I’m not sure if that counts as reasonable, but it reassured me that the published solution was probably correct. I need to tidy my program up a bit before publishing it though.

      For what it’s worth I get a maximum volume of 488 for the 7×7 case in 2m32s. Which is the smallest size for which a single tank is not optimal.

  3. Hugh Casement 17 August 2014 at 6:11 pm

    Can someone please explain this puzzle to me? Surely the water can stand 4 ft deep in compartment no. 1 before it spills, and 8 ft deep in no. 2. Then each of the others can be full, so the total capacity is far greater. Am I just stupid, or is it very badly expressed? I rejected this one as incomprehensible when I found it in a bound volume of NS in the library ten years ago, and it still makes no sense to me after reading the solution and other comments.

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: