Sunday Times Teaser 2835 – Jeweller’s Rouge

by Andrew Skidmore

Published: 22 January 2017 (link)

Fabulé’s latest creation consists of a set of equal-sized silver cubes. On each face of each cube there is one diagonal of identical rubies. No two cubes are the same, but had Fabulé made any more such cubes then it would have been necessary to repeat one of the designs.

How many cubes are there in the set?

2 Comments Leave one →

Brian Gladman permalink


from itertools import product
from enum import IntEnum

# The cube vertexes are numbered 0 to 7 according to their positions in
# in the following list of their coordinates (x, y, z) in 3 dimensions:
# ((0,0,0), (1,0,0), (1,1,0), (0,1,0), (0,0,1), (1,0,1), (1,1,1), (0,1,1)

class Axis(IntEnum):
  X = 0
  Y = 1
  Z = 2

# For each index position, the index from which this vertex comes in 90 degree
# clockwise rotations of the cube about the x, y and z axes respectively. 
ri = ( (4, 5, 1, 0, 7, 6, 2, 3), 
       (1, 5, 6, 2, 0, 4, 7, 3),  
       (3, 0, 1, 2, 7, 4, 5, 6) )

# rotate a cube given by the vertex list in <ip> using <cnt> 90 degree
# clockwise rotations about the <ax> axis
def rot(ip, cnt, ax):
  op = tuple(ip)
  for c in range(cnt):
    op = tuple(op[r] for r in ri[ax])
  return op

# The set of (twenty-four) symmetric vertex transformations for a cube
res = set((rot(rot(rot(range(8), i, Axis.X), j, Axis.Y), k, Axis.Z)) 
             for i, j, k in product(range(4), repeat=3))

# list the two diagonal choices for each of the six faces (identified
# by the two linked vertexes, keeping the base face constant) 
faces = ( ((4, 6), (5, 7)), ((0, 2),       ),   #    Up,  Down
          ((0, 7), (3, 4)), ((1, 6), (2, 5)),   #  Left, Right
          ((0, 5), (1, 4)), ((2, 7), (3, 6)) )  # Front,  Back

# for collecting different cubes
cube_set = set()
# consider all combinations of the six cube faces
for p6 in product(*faces):
  
  # check the 24 transformations of this cube configuration 
  # to see if it is new
  if not any(set(tuple(sorted((r[a], r[b]))) for a, b in p6) 
             in cube_set for r in res):
    cube_set.add(frozenset((p6)))

print(f'There are {len(cube_set)} different cubes:')
for c in cube_set:
  print('  ', *sorted(c))

from itertools import product

from enum import IntEnum

# The cube vertexes are numbered 0 to 7 according to their positions in

# in the following list of their coordinates (x, y, z) in 3 dimensions:

# ((0,0,0), (1,0,0), (1,1,0), (0,1,0), (0,0,1), (1,0,1), (1,1,1), (0,1,1)

class Axis(IntEnum):

X = 0

Y = 1

Z = 2

# For each index position, the index from which this vertex comes in 90 degree

# clockwise rotations of the cube about the x, y and z axes respectively.

ri = ( (4, 5, 1, 0, 7, 6, 2, 3),

(1, 5, 6, 2, 0, 4, 7, 3),

(3, 0, 1, 2, 7, 4, 5, 6) )

# rotate a cube given by the vertex list in <ip> using <cnt> 90 degree

# clockwise rotations about the <ax> axis

def rot(ip, cnt, ax):

op = tuple(ip)

for c in range(cnt):

op = tuple(op[r] for r in ri[ax])

return op

# The set of (twenty-four) symmetric vertex transformations for a cube

res = set((rot(rot(rot(range(8), i, Axis.X), j, Axis.Y), k, Axis.Z))

for i, j, k in product(range(4), repeat=3))

# list the two diagonal choices for each of the six faces (identified

# by the two linked vertexes, keeping the base face constant)

faces = ( ((4, 6), (5, 7)), ((0, 2), ), # Up, Down

((0, 7), (3, 4)), ((1, 6), (2, 5)), # Left, Right

((0, 5), (1, 4)), ((2, 7), (3, 6)) ) # Front, Back

# for collecting different cubes

cube_set = set()

# consider all combinations of the six cube faces

for p6 in product(*faces):

# check the 24 transformations of this cube configuration

# to see if it is new

if not any(set(tuple(sorted((r[a], r[b]))) for a, b in p6)

in cube_set for r in res):

cube_set.add(frozenset((p6)))

print(f'There are {len(cube_set)} different cubes:')

for c in cube_set:

print(' ', *sorted(c))

Jim Randell permalink

Here’s the code I used to solve this puzzle.

First I created a generic class to describe the rotations of the cube.


# labels for the faces
(U, D, L, R, F, B) = (0, 1, 2, 3, 4, 5)

# the 24 rotational positions of the cube
# we record the positions of the faces
# and their orientations (in clockwise quarter turns)
ROTATIONS = (
  # the first 6 match up with a rotation of the face U, D, L, R, F, B
  # faces               orientations
  # U  D  L  R  F  B    U  D  L  R  F  B      U F
  ((U, D, F, B, R, L), (1, 3, 0, 0, 0, 0)), # U R - rotate U
  ((U, D, B, F, L, R), (3, 1, 0, 0, 0, 0)), # U L - rotate D = rotate UUU
  ((B, F, L, R, U, D), (2, 0, 1, 3, 0, 2)), # B U - rotate L
  ((F, B, L, R, D, U), (0, 2, 3, 1, 0, 2)), # F D - rotate R = rotate LLL
  ((L, R, D, U, F, B), (1, 1, 1, 1, 1, 3)), # L F - rotate F
  ((R, L, U, D, F, B), (3, 3, 3, 3, 3, 1)), # R F - rotate B = rotate FFF
  # the remaining rotations can be derived from those above
  ((U, D, L, R, F, B), (0, 0, 0, 0, 0, 0)), # U F - rotate []
  ((U, D, R, L, B, F), (2, 2, 0, 0, 0, 0)), # U B - rotate UU
  ((D, U, R, L, F, B), (2, 2, 2, 2, 2, 2)), # D F - rotate FF
  ((D, U, L, R, B, F), (0, 0, 2, 2, 2, 2)), # D B - rotate LL
  ((D, U, F, B, L, R), (3, 1, 2, 2, 2, 2)), # D L - rotate ULL
  ((D, U, B, F, R, L), (1, 3, 2, 2, 2, 2)), # D R - rotate LLU
  ((L, R, F, B, U, D), (2, 0, 1, 3, 1, 1)), # L U - rotate FU
  ((L, R, B, F, D, U), (0, 2, 3, 1, 1, 1)), # L D - rotate FD
  ((L, R, U, D, B, F), (3, 3, 1, 1, 3, 1)), # L B - rotate FUU
  ((R, L, B, F, U, D), (2, 0, 1, 3, 3, 3)), # R U - rotate BD
  ((R, L, F, B, D, U), (0, 2, 3, 1, 3, 3)), # R D - rotate BU
  ((R, L, D, U, B, F), (1, 1, 3, 3, 1, 3)), # R B - rotate BUU
  ((F, B, R, L, U, D), (2, 0, 1, 3, 2, 0)), # F U - rotate RUU
  ((F, B, U, D, L, R), (3, 3, 2, 0, 3, 1)), # F L - rotate RD
  ((F, B, D, U, R, L), (1, 1, 0, 2, 1, 3)), # F R - rotate RU
  ((B, F, R, L, D, U), (0, 2, 3, 1, 2, 0)), # B D - rotate LUU
  ((B, F, D, U, L, R), (1, 1, 2, 0, 1, 3)), # B L - rotate LD
  ((B, F, U, D, R, L), (3, 3, 0, 2, 3, 1)), # B R - rotate LU
)

class Cube(object):

  def __init__(self, faces=None, orientations=None):
    if faces is None: faces = (U, D, L, R, F, B)
    if orientations is None: orientations = (0, 0, 0, 0, 0, 0)
    self.faces = tuple(faces)
    self.orientations = tuple(orientations)

  # a new cube derived from the old one by applying the specified transformation
  def _transform(self, faces, orientations):
    return Cube(
      faces=(self.faces[i] for i in faces),
      orientations=((self.orientations[i] + r) % 4 for (i, r) in zip(faces, orientations))
    )

  # generate all rotations of the cube
  def rotations(self):
    for (faces, orientations) in ROTATIONS:
      yield self._transform(faces, orientations)

# labels for the faces

(U, D, L, R, F, B) = (0, 1, 2, 3, 4, 5)

# the 24 rotational positions of the cube

# we record the positions of the faces

# and their orientations (in clockwise quarter turns)

ROTATIONS = (

# the first 6 match up with a rotation of the face U, D, L, R, F, B

# faces orientations

# U D L R F B U D L R F B U F

((U, D, F, B, R, L), (1, 3, 0, 0, 0, 0)), # U R - rotate U

((U, D, B, F, L, R), (3, 1, 0, 0, 0, 0)), # U L - rotate D = rotate UUU

((B, F, L, R, U, D), (2, 0, 1, 3, 0, 2)), # B U - rotate L

((F, B, L, R, D, U), (0, 2, 3, 1, 0, 2)), # F D - rotate R = rotate LLL

((L, R, D, U, F, B), (1, 1, 1, 1, 1, 3)), # L F - rotate F

((R, L, U, D, F, B), (3, 3, 3, 3, 3, 1)), # R F - rotate B = rotate FFF

# the remaining rotations can be derived from those above

((U, D, L, R, F, B), (0, 0, 0, 0, 0, 0)), # U F - rotate []

((U, D, R, L, B, F), (2, 2, 0, 0, 0, 0)), # U B - rotate UU

((D, U, R, L, F, B), (2, 2, 2, 2, 2, 2)), # D F - rotate FF

((D, U, L, R, B, F), (0, 0, 2, 2, 2, 2)), # D B - rotate LL

((D, U, F, B, L, R), (3, 1, 2, 2, 2, 2)), # D L - rotate ULL

((D, U, B, F, R, L), (1, 3, 2, 2, 2, 2)), # D R - rotate LLU

((L, R, F, B, U, D), (2, 0, 1, 3, 1, 1)), # L U - rotate FU

((L, R, B, F, D, U), (0, 2, 3, 1, 1, 1)), # L D - rotate FD

((L, R, U, D, B, F), (3, 3, 1, 1, 3, 1)), # L B - rotate FUU

((R, L, B, F, U, D), (2, 0, 1, 3, 3, 3)), # R U - rotate BD

((R, L, F, B, D, U), (0, 2, 3, 1, 3, 3)), # R D - rotate BU

((R, L, D, U, B, F), (1, 1, 3, 3, 1, 3)), # R B - rotate BUU

((F, B, R, L, U, D), (2, 0, 1, 3, 2, 0)), # F U - rotate RUU

((F, B, U, D, L, R), (3, 3, 2, 0, 3, 1)), # F L - rotate RD

((F, B, D, U, R, L), (1, 1, 0, 2, 1, 3)), # F R - rotate RU

((B, F, R, L, D, U), (0, 2, 3, 1, 2, 0)), # B D - rotate LUU

((B, F, D, U, L, R), (1, 1, 2, 0, 1, 3)), # B L - rotate LD

((B, F, U, D, R, L), (3, 3, 0, 2, 3, 1)), # B R - rotate LU

)

class Cube(object):

def __init__(self, faces=None, orientations=None):

if faces is None: faces = (U, D, L, R, F, B)

if orientations is None: orientations = (0, 0, 0, 0, 0, 0)

self.faces = tuple(faces)

self.orientations = tuple(orientations)

# a new cube derived from the old one by applying the specified transformation

def _transform(self, faces, orientations):

return Cube(

faces=(self.faces[i] for i in faces),

orientations=((self.orientations[i] + r) % 4 for (i, r) in zip(faces, orientations))

)

# generate all rotations of the cube

def rotations(self):

for (faces, orientations) in ROTATIONS:

yield self._transform(faces, orientations)

Then I used this to find distinct patterns of diagonals:


from itertools import product

# a canonical representation of a pattern of diagonals
# - faces cannot be distinguished
# - diagonals are the same when rotated 180 degrees, so we only need to consider the parity of the orientation
# we choose the minimal value from all possible rotations of the pattern
def canonical(s):
  cube = Cube(orientations=s)
  return min(tuple(x % 2 for x in r.orientations) for r in cube.rotations())

# consider possible diagonals on the faces and record the canonical representations
patterns = set(canonical(s) for s in product((0, 1), repeat=6))

# count the patterns
print("{n} patterns".format(n=len(patterns)))

from itertools import product

# a canonical representation of a pattern of diagonals

# - faces cannot be distinguished

# - diagonals are the same when rotated 180 degrees, so we only need to consider the parity of the orientation

# we choose the minimal value from all possible rotations of the pattern

def canonical(s):

cube = Cube(orientations=s)

return min(tuple(x % 2 for x in r.orientations) for r in cube.rotations())

# consider possible diagonals on the faces and record the canonical representations

patterns = set(canonical(s) for s in product((0, 1), repeat=6))

# count the patterns

print("{n} patterns".format(n=len(patterns)))

Sunday Times Teaser 2835 – Jeweller’s Rouge

by Andrew Skidmore

Published: 22 January 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta