# 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.

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]

### 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):
# 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.

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):

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()
```

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