Enigmatic Code

Programming Enigma Puzzles

Enigma 1511: Way out

From New Scientist #2673, 13th September 2008

Many years ago, Joe made a 3-foot-wide path from his back door to his garden shed using whole 2-foot by 1-foot paving slabs. Viewed from his back door, he wanted to ensure that the pattern of slabs in any 2- foot-long section of the path was not duplicated.

This limited the length of the path, so he had to move his shed a little nearer to the house!

How long was Joe’s path?

[enigma1511]

Advertisements

4 responses to “Enigma 1511: Way out

  1. Jim Randell 1 October 2012 at 8:09 am

    This was a fun puzzle to solve. Here is a recursive Python program that enumerates all possible paths and determines the maximum length. It runs in 83ms.

    from collections import defaultdict
    from enigma import Accumulator, printf
    
    # accumulate max path length
    max_path = Accumulator(fn = max)
    
    def extend(path, p):
      # find the next empty square
      while True:
        if not(p + 3 < len(path)): path.extend('***')
        if path[p] == '*': break
        p += 1
      # attempt to place a vertical slab at p, p+3
      if path[p + 3] == '*':
        (path[p], path[p + 3]) = ('N', 'S')
        if check(path):
          # try to place another slab
          extend(path, p + 1)
        # remove the slab
        (path[p], path[p + 3]) = ('*', '*')
      # attempt to place a horizontal slab at p, p+1
      if p % 3 < 2 and path[p + 1] == '*':
        (path[p], path[p + 1]) = ('W', 'E')
        if check(path):
          # try to place another slab
          extend(path, p + 2)
        (path[p], path[p + 1]) = ('*', '*')
    
    # check this path is worth continuing with
    # and accumulate length of completed paths
    def check(path):
      # turn path into a string
      path = ''.join(path)
      # remove any wholly unused rows
      while path[-3:] == '***': path = path[:-3]
      # split the path into sections
      sections = list(path[i:i+6] for i in range(0, len(path) - 3, 3))
      # are there repeated sections?
      if len(set(sections)) < len(sections): return False
      # is the path complete?
      if len(sections) < 1 or '*' in sections[-1]: return True
      # length of the path (in ft)
      n = len(path) / 3
      # accumulate path lengths
      max_path.accumulate(n)
      printf("length = {n} [{path}]")
      return True
    
    extend(list('***'), 0)
    printf("max path length = {max_path.value}ft")
    

    Solution: The path is 14 ft long.

    • Hugh Casement 9 October 2014 at 9:42 am

      Jim, thanks for telling me about pre and /pre. One fine day I’m going to teach myself HTML.
      Even so, it’s hard to draw diagrams with text characters, and I’m not confident that Word tables with judiciously merged cells will come across unscathed, so I can’t show you what my tentative 14-foot path looks like. Are you prepared to draw yours for us? Or are there many possible patterns?

      These days the slabs measure 30 cm. Hence the “many years ago”. But one probably uses a quarter inch or so of grouting between them, so the path is still near enough 3 feet wide!

      • Jim Randell 11 October 2014 at 2:55 pm

        My program finds 96 paths of length 14.

        Here’s an example of one of them (for anything sufficiently complicated I tend to upload an image):

        Enigma 1511 - Solution

        In each square (a slab covers two squares) the slab crosses one edge of the square, leaving grey around the other three edges. We can label each square by what the grey area looks like, as they look a bit like stylised letters: N where the slab crosses the bottom edge of the square, U where the slab crosses the top edge of the square, C where the slab crosses the right edge of the square and D where the slab crosses the left edge of the square. (In my program I labelled these N, S, W and E).

        The path above corresponds to:

        NNN UUU NCD UNN NUU UCD NCD UCD CDN NNU UUN CDU CDN CDU

        Taking adjacent pairs we get:

        NNN UUU
        UUU NCD
        NCD UNN
        UNN NUU
        NUU UCD
        UCD NCD
        NCD UCD
        UCD CDN
        CDN NNU
        NNU UUN
        UUN CDU
        CDU CDN
        CDN CDU

        None of which repeat, so they form different patterns. And this path cannot be extended further without causing a repeating pattern.

        • Hugh Casement 12 October 2014 at 9:03 am

          Many thanks, Jim. If you look where the gap between slabs runs right across the path, we have five blocks, alternately two and four slabs long. I found those, but wasn’t sure whether the order I had them in really constituted different patterns. I’s now a bit clearer to me.

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: