Sunday Times Teaser 2673 – Footprints

by Nick MacKinnon

Each of the faces of a six sided cubical die are numbered one to six as usual and have dimensions that exactly match the dimensions of each of the nine cells in a three by three grid.

The die is placed on one of these cells and is then ‘rolled’ on one of its lower edges in such a way that it moves onto another grid cell. This move is repeated a total of eight times and in such a way that the die occupies every grid cell exactly once.

The score for such a sequence of moves is the sum of the nine die faces that have been in contact with the grid (some added more than once).

What are the minimum and maximum possible scores and what scores between these two values are impossible?

6 Comments Leave one →

brian gladman permalink

This is my first attempt at this, one which I may improve later.


# the six dice faces will be enumerated in the order 
# Left, Front, Up, Right, Back, Down (X = illegal)
L, F, U, R, B, D, X = range(7)

# sides that become L, F, U, R, B, D after rolling a die on a
# lower left, right, forward and backward edge respectively
rolls = ((U, F, R, D, B, L), (D, F, L, U, B, R), 
         (L, U, B, R, D, F), (L, D, F, R, U, B))

# possible die moves for each or the nine grid cells - positions
# in the three grid rows are  (0, 1, 2), (3, 4, 5) and (6, 7, 8) 
moves = ( (R, F), (L, R, F), (L, F),  (B, R, F), (B, L, R, F), 
          (B, L, F), (B, R), (B, L, R), (B, L) )

# the distance moved in the grid array for moves L, F, R and B
dis = (-1, 3, X, 1, -3, X)
# and the die roll data involved
rol = ( rolls[0], rolls[2], X, rolls[1],  rolls[3], X)

# roll a die onto the nine grid squares in turn
def run(path, fp, d):
  # if we have finished, return the score for the sequence
  if len(path) == 9:
    yield fp
  else:
    # the current position of the die on the grid
    cp = path[-1]
    # for each of the possible moves from this position
    for m in moves[cp]:
      # find the next die position on the grid
      np = cp + dis[m]
      # if this has not yet been visited
      if np not in path:
        # roll the die to move to the new position, add the score 
        # to the running total and proceed to the next move
        nd = tuple(d[i] for i in rol[m])
        yield from run(path + [np], fp + nd[D], nd)

# given two dice faces anti-clockwise at a vertex, find the third
# face at this vertex (using a western die if 'same' is True)
def die_third_face(first, second, same=True):
  if second in (first, 7 - first):
    raise ValueError
  t, f = min(first, 7 - first), min(second, 7 - second)
  c1 = ((f - t) % 3 == (1 if same else 2))
  c2 = (first < 4) == (second < 4)
  return 6 - t - f if c1 == c2 else t + f + 1

# permute a die into its 24 spatial orientations
# (e.g. any of the six faces on top and then any
# of the four side faces at the front)
def permute_die():
  for left in range(1, 7):
    for front in set(range(1, 7)) - set((left, 7 - left)):
      up = die_third_face(left, front)
      yield (left, front, up, 7 - left, 7 - front, 7 - up)

# a set to hold the scores
scores = set()
# for each essentially different grid starting position
for pos in (0, 1, 4):
  # and for each starting die orientation
  for die in permute_die():
    # generate all sequences and add their scores to our set
    scores |= set(fp for fp in run([pos], die[D], die))

# find the minimum and maximum possible scores
min_s, max_s = min(scores), max(scores)
# find any scores that are missing between these two values
missing = set(range(min_s, max_s + 1)) - scores
fs = 'Scores: minimum = {}, maximum = {}, impossible: {}.'
print(fs.format(min_s, max_s, tuple(sorted(missing))))

# the six dice faces will be enumerated in the order

# Left, Front, Up, Right, Back, Down (X = illegal)

L, F, U, R, B, D, X = range(7)

# sides that become L, F, U, R, B, D after rolling a die on a

# lower left, right, forward and backward edge respectively

rolls = ((U, F, R, D, B, L), (D, F, L, U, B, R),

(L, U, B, R, D, F), (L, D, F, R, U, B))

# possible die moves for each or the nine grid cells - positions

# in the three grid rows are (0, 1, 2), (3, 4, 5) and (6, 7, 8)

moves = ( (R, F), (L, R, F), (L, F), (B, R, F), (B, L, R, F),

(B, L, F), (B, R), (B, L, R), (B, L) )

# the distance moved in the grid array for moves L, F, R and B

dis = (-1, 3, X, 1, -3, X)

# and the die roll data involved

rol = ( rolls[0], rolls[2], X, rolls[1], rolls[3], X)

# roll a die onto the nine grid squares in turn

def run(path, fp, d):

# if we have finished, return the score for the sequence

if len(path) == 9:

yield fp

else:

# the current position of the die on the grid

cp = path[-1]

# for each of the possible moves from this position

for m in moves[cp]:

# find the next die position on the grid

np = cp + dis[m]

# if this has not yet been visited

if np not in path:

# roll the die to move to the new position, add the score

# to the running total and proceed to the next move

nd = tuple(d[i] for i in rol[m])

yield from run(path + [np], fp + nd[D], nd)

# given two dice faces anti-clockwise at a vertex, find the third

# face at this vertex (using a western die if 'same' is True)

def die_third_face(first, second, same=True):

if second in (first, 7 - first):

raise ValueError

t, f = min(first, 7 - first), min(second, 7 - second)

c1 = ((f - t) % 3 == (1 if same else 2))

c2 = (first < 4) == (second < 4)

return 6 - t - f if c1 == c2 else t + f + 1

# permute a die into its 24 spatial orientations

# (e.g. any of the six faces on top and then any

# of the four side faces at the front)

def permute_die():

for left in range(1, 7):

for front in set(range(1, 7)) - set((left, 7 - left)):

up = die_third_face(left, front)

yield (left, front, up, 7 - left, 7 - front, 7 - up)

# a set to hold the scores

scores = set()

# for each essentially different grid starting position

for pos in (0, 1, 4):

# and for each starting die orientation

for die in permute_die():

# generate all sequences and add their scores to our set

scores |= set(fp for fp in run([pos], die[D], die))

# find the minimum and maximum possible scores

min_s, max_s = min(scores), max(scores)

# find any scores that are missing between these two values

missing = set(range(min_s, max_s + 1)) - scores

fs = 'Scores: minimum = {}, maximum = {}, impossible: {}.'

print(fs.format(min_s, max_s, tuple(sorted(missing))))

Frits permalink

Later is now?

This version also seems to work


def die_third_face(f, s, same=False):
  if s in {f, 7 - f}:
    raise ValueError
  oth = [i for i in range(1, 7) if i not in {f, s, 7 - f, 7 - s}]
  t = oth[(f < s) == ((s - f) % 2)]
  return 7 - t if (same == (s + f < 7)) else t

def die_third_face(f, s, same=False):

if s in {f, 7 - f}:

raise ValueError

oth = [i for i in range(1, 7) if i not in {f, s, 7 - f, 7 - s}]

t = oth[(f < s) == ((s - f) % 2)]

return 7 - t if (same == (s + f < 7)) else t

Frits permalink

or even shorter:

Python

return oth[((f < s) == ((s - f) % 2)) == (same == (s + f > 7))]

1
2
3

return oth[((f < s) == ((s - f) % 2)) == (same == (s + f > 7))]

Reply
BRG permalink

Hi Frits, Clearly I never returned to it. In retrospect it seems quite long.

Reply

ahmet cetinbudaklar permalink

3×3 grid gives us the central and the four corners as starting points as a result of which 21 and 42 being the minimum and the maximum scores which can be scored respectively with 29 and 34 being impossible scores to reach.
There are 40 distinct ways of letting the die to touch each cell only once and each way having 24 different possibilities to apply.

Reply

Frits permalink

Using the same structure but with less hard coded moves/rolls.


# possible moves:
#
#  0 1 2
#  3 4 5
#  6 7 8

row, col = lambda i: i // 3, lambda i: i % 3

# adjacent fields to field <i>
adj = {i: [(j, (col(j) - col(i), row(i) - row(j))) for j in range(9) 
          if sum(abs(tp(j) - tp(i)) for tp in (row, col)) == 1] 
          for i in range(9)} 
        
# given two dice faces anti-clockwise at a vertex, find the third
# face at this vertex (using a western die if 'same' is True)
def die_third_face(f, s, same=True):
  if s in {f, 7 - f}:
    raise ValueError
  oth = [i for i in range(1, 7) if i not in {f, s, 7 - f, 7 - s}]
  return oth[((f < s) == ((s - f) % 2)) == (same == (s + f > 7))]

# permute a die into its 24 spatial orientations
dice24 = [(l, f, die_third_face(l, f)) for l in range(1, 7) 
           for f in range(1, 7) if f not in {l, 7 - l}]

# roll a die (depending on direction), always the "up" face should change
def roll(die, direction): 
  (l, f, u), (dx, dy) = die, direction
  if dy: # to the front or to the back  (-1, 1)
    nd = (l, 7 - u, f) if dy > 0 else (l, u, 7 - f) 
  else:  # to the left or to the right  (-1, 1)
    nd = (7 - u, f, l) if dx > 0 else (u, f, 7 - l) 
  return nd  # return new die
  
# keep rolling a die until the nine grid squares have been visited
def run(path, k, t, d):
  # if we have finished, return the score for the sequence
  if k == 0:
    # total of the nine faces that are in contact with the grid
    # is 63 - sum top faces  
    yield 63 - t
  else:
    # next possible positions from the current position
    for np, dxdy in adj[path[-1]]:
      # if this square has not yet been visited
      if np in path: continue
      # find the next die position on the grid
      nd = roll(d, dxdy)
      # find the next position for the die on the grid
      yield from run(path + [np], k - 1, t + nd[-1], nd)      
      
# a set to hold the scores
scores = set()
# for each starting die orientation
for die in dice24:
  # and for each essentially different grid starting position
  for pos in (0, 1, 4):
    # generate all sequences and add their scores to our set
    scores |= set(fp for fp in run([pos], 8, die[-1], die))          

print(f"(a): {(mn := min(scores))}")
print(f"(b): {(mx := max(scores))}")
print(f"(c): {' and '.join(str(s) for s in range(mn, mx + 1) 
              if s not in scores)}")

# possible moves:

# 0 1 2

# 3 4 5

# 6 7 8

row, col = lambda i: i // 3, lambda i: i % 3

# adjacent fields to field <i>

adj = {i: [(j, (col(j) - col(i), row(i) - row(j))) for j in range(9)

if sum(abs(tp(j) - tp(i)) for tp in (row, col)) == 1]

for i in range(9)}

# given two dice faces anti-clockwise at a vertex, find the third

# face at this vertex (using a western die if 'same' is True)

def die_third_face(f, s, same=True):

if s in {f, 7 - f}:

raise ValueError

oth = [i for i in range(1, 7) if i not in {f, s, 7 - f, 7 - s}]

return oth[((f < s) == ((s - f) % 2)) == (same == (s + f > 7))]

# permute a die into its 24 spatial orientations

dice24 = [(l, f, die_third_face(l, f)) for l in range(1, 7)

for f in range(1, 7) if f not in {l, 7 - l}]

# roll a die (depending on direction), always the "up" face should change

def roll(die, direction):

(l, f, u), (dx, dy) = die, direction

if dy: # to the front or to the back (-1, 1)

nd = (l, 7 - u, f) if dy > 0 else (l, u, 7 - f)

else: # to the left or to the right (-1, 1)

nd = (7 - u, f, l) if dx > 0 else (u, f, 7 - l)

return nd # return new die

# keep rolling a die until the nine grid squares have been visited

def run(path, k, t, d):

# if we have finished, return the score for the sequence

if k == 0:

# total of the nine faces that are in contact with the grid

# is 63 - sum top faces

yield 63 - t

else:

# next possible positions from the current position

for np, dxdy in adj[path[-1]]:

# if this square has not yet been visited

if np in path: continue

# find the next die position on the grid

nd = roll(d, dxdy)

# find the next position for the die on the grid

yield from run(path + [np], k - 1, t + nd[-1], nd)

# a set to hold the scores

scores = set()

# for each starting die orientation

for die in dice24:

# and for each essentially different grid starting position

for pos in (0, 1, 4):

# generate all sequences and add their scores to our set

scores |= set(fp for fp in run([pos], 8, die[-1], die))

print(f"(a): {(mn := min(scores))}")

print(f"(b): {(mx := max(scores))}")

print(f"(c): {' and '.join(str(s) for s in range(mn, mx + 1)

if s not in scores)}")

Sunday Times Teaser 2673 – Footprints

by Nick MacKinnon

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta