Enigmatic Code

Programming Enigma Puzzles

Enigma 1375: Patterns of colour

From New Scientist #2535, 21st January 2006

Pussicato’s latest painting is a 6-by-6 array of small squares, and each square contains just one colour. At the gallery I saw a group of six girl students looking at the painting. Each girl selected a different horizontal row and independently wrote down the pattern of colours in her row, from left to right, by simply giving a different number to each colour in her row.

Talking to the girls I found the patterns in the rows were as follows. First, i.e. top, row 121341, second row 112213, third row 123221, fourth row 121222, fifth row 122113, sixth, i.e. bottom, row 122134.

Later, another group of six girls carried out the same process for the vertical columns of the painting. Again I noted the patterns, from top to bottom, but unfortunately I forgot to note which column is which.

Enigma 1375

The patterns in the columns were as above, in no particular order. Pussicato painted more squares green than any other colour.

How many squares in the painting were green?

[enigma1375]

Advertisements

2 responses to “Enigma 1375: Patterns of colour

  1. Jim Randell 5 November 2013 at 9:28 am

    I found this one quite fun to program a solution for, although once I’d worked out the mechanics of the algorithm it was fairly easy to implement.

    This Python 3 program works by starting with a maximal colouring of the grid (all 36 squares different colours), and then groups together squares that must be the same colour by applying the given patterns. The patterns for the rows are straightforward as were told directly which rows correspond to which patterns. For the columns I implemented a recursive solver which tries columns that don’t break the patterns of the rows. It runs in 57ms.

    from collections import defaultdict, Counter
    from enigma import chunk, irange, diff, printf
    
    # rows of the grid
    rows = (
      ( 0,  1,  2,  3,  4,  5),
      ( 6,  7,  8,  9, 10, 11),
      (12, 13, 14, 15, 16, 17),
      (18, 19, 20, 21, 22, 23),
      (24, 25, 26, 27, 28, 29),
      (30, 31, 32, 33, 34, 35),
    )
    
    # columns of the grid
    columns = (
      ( 0,  6, 12, 18, 24, 30),
      ( 1,  7, 13, 19, 25, 31),
      ( 2,  8, 14, 20, 26, 32),
      ( 3,  9, 15, 21, 27, 33),
      ( 4, 10, 16, 22, 28, 34),
      ( 5, 11, 17, 23, 29, 35),
    )
    
    # patterns for the rows, in order
    prows = ('121341', '112213', '123221', '121222', '122113', '122134')
    
    # patterns for the columns, not in order
    pcols = ('123432', '112324', '123211', '122223', '112343', '122122')
    
    # check a pattern matches
    def match(grid, squares, pattern):
      # map the symbols on the grid to the symbols in the pattern
      r = defaultdict(set)
      for (i, p) in zip(squares, pattern):
        r[grid[i]].add(p)
      # it's a match if the same symbol in the grid maps to the same pattern symbol
      return all(len(v) == 1 for v in r.values())
    
    # coalesce symbols in the grid
    def coalesce(grid, v):
      if len(v) > 1:
        m = min(grid[i] for i in v)
        grid = list(grid)
        for i in v:
          if grid[i] == m: continue
          x = grid[i]
          for (i, y) in enumerate(grid):
            if x == y: grid[i] = m
      return grid
    
    # assign a sequence of squares to a pattern
    def assign(grid, squares, pattern):
      r = defaultdict(list)
      # accumulate squares by symbols in the pattern
      for (i, p) in zip(squares, pattern):
        r[p].append(i)
      # and then coalesce symbols
      for v in r.values():
        grid = coalesce(grid, v)
        if len(v) > 1:
          m = min(grid[i] for i in v)
          grid = coalesce(grid, v)
      return grid
    
    # g - grid
    # i - column we're working on
    # ps - patterns
    def solve(g, i, ps):
      if not ps:
        yield g
      else:
        # assign column i
        c = columns[i]
        for p in ps:
          if match(g, c, p):
            g2 = assign(g, c, p)
            # check the rows still match
            if all(match(g2, r, p2) for (r, p2) in zip(rows, prows)):
              yield from solve(g2, i + 1, diff(ps, [p]))
    
    # start with a maximally coloured grid and apply the row patterns
    g0 = list(irange(1, 36))
    for (r, p) in zip(rows, prows):
      g0 = assign(g0, r, p)
    
    # solve the grid for the column patterns
    for g in solve(g0, 0, pcols):
      # output a solution grid
      symbols = dict(zip(sorted(set(g)), 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'))
      g = list(symbols[x] for x in g)
      for r in chunk(g, 6):
        printf("[{r}]", r=' '.join(r))
      # and count the colours
      for (k, v) in Counter(g).most_common():
        printf("{k}: {v}")
    

    Solution: There are 13 green squares in the painting.

    Enigma 1375

    There are at least 4 colours (as some of the patterns go up to 4), but we can’t determine the exact colouring of the grid. In the diagram above the 13 green squares are shown, along with 11 red squares and 5 blue squares. But the blue squares could be split into up to three different groups of colours, as indicated by the different shades of blue.

  2. arthurvause 6 November 2013 at 2:02 pm

    I found this quite an intricate puzzle to code.

    My approach was to permute the patterns of columns, and for each permutation collect the items from each row matching each colour in each column. Then group together collections that overlap, checking that 2 colours from a row do not become grouped together.

    Finally count the number of cells in each valid grouping found.

    It’s slightly slower than Jim’s version, around 100ms

    from itertools import permutations as perm, combinations as comb
    from collections import defaultdict
    
    rows = ((11,12,11,13,14,11),
            (21,21,22,22,21,23),
            (31,32,33,32,32,31),
            (41,42,41,42,42,42),
            (51,52,52,51,51,53),
            (61,62,62,61,63,64))
    
    
    cols = ((11,12,13,15,13,12),
            (21,21,22,23,22,24),
            (31,32,33,32,31,31),
            (41,42,42,42,42,43),
            (51,51,52,53,54,53),
            (61,62,62,61,62,62))
    
    def Enigma1375():
      for colperm in perm(range(6)):
        agg = []
        for c in xrange(6):
          d = defaultdict(set)
          for r in xrange(6):
            d[cols[colperm[c]][r]].add(rows[r][c])
    
          agg += [d[x] for x in d]
    
        ungrouped,valid = True,True
        while ungrouped and valid:
          ungrouped=False
          for p,q in comb(range(len(agg)),2):
            if len(agg[p]&agg[q])>0:
              agg[p] |= agg[q]
              row = sorted(x//10 for x in agg[p])
              if any(row[i]==row[i+1] for i in xrange(len(row)-1)):
                valid=False
                break
              agg[q] = set()
              ungrouped=True
    
        if valid:
          for a in agg:
            if len(a)>0:
              print sum(1 for i in xrange(6)
                        for j in xrange(6) if rows[i][j] in a),"occurences:", sorted(a)
    
    Enigma1375()
    

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: