Enigmatic Code

Programming Enigma Puzzles

Enigma 1058: A row of colours

From New Scientist #2214, 27th November 1999 [link]

Pusicatto has been asked by a family to paint a picture consisting of a row of squares, which each square either red or green. Each member of the family has expressed a wish for something they would like to appear in the picture. For example, Mum asked for G??R?G, by which she meant that, somewhere in the row, there should be a green square, then two squares that could be of either colour, then a red square, then a square of either colour, and then a green square, without any other squares coming between them. Dad asked for G?R?R. The children’s requests were:

Kathy: R?G?R
Matthew: RG???G
Janet: G????R
Benjamin: R????R

Pusicatto decided to paint the picture so that it had the smallest number of squares possible.

What was the order of the squares in Pusicatto’s painting?


2 responses to “Enigma 1058: A row of colours

  1. Jim Randell 11 June 2018 at 8:14 am

    This Python program considers possible paintings with increasing numbers of squares until it finds a solution.

    It runs in 83ms.

    Run: [ @repl.it ]

    from itertools import count, product
    from enigma import concat, match, printf
    # patterns to match
    patterns = list( '*' + t + '*' for t in (
      'G??R?G', 'G?R?R', 'R?G?R', 'RG???G', 'G????R', 'R????R'
    for k in count(6):
      n = 0
      for s in product('RG', repeat=k):
        s = concat(s)
        if all(match(s, t) for t in patterns):
          printf("[{k}] {s}")
          n += 1
      if n: break

    Solution: Pussicato’s painting consists of 9 squares: GRRGRRRGG.

    Here’s a diagram showing how the painting meets all of the requirements.

  2. Brian Gladman 11 June 2018 at 4:29 pm
    from itertools import count, product
    from re import compile, search
    # the six templates
    mt = ('G??R?G', 'G?R?R', 'R?G?R', 'RG???G', 'G????R', 'R????R')
    # convert the templates to compiled regular expression search strings
    ms = {compile(''.join('(R|G)' if c == '?' else c for c in s)) for s in mt}
    # try increasing length strings of R's and G's 
    for r in count(6):
      for p in product('RG', repeat=r):
        s = ''.join(p)
        # look for a string that matches all the templates
        if all(m.search(s) for m in ms):
          print(f'Colour Order: {s}')

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: