Sunday Times Teaser 3263 – Snakes and Ladders

by BRG on April 6, 2025

by Victor Bryant

Published Sunday April 06 2025 (link)

My “Snakes and Ladders” board has numbers from 1 to 100 — you throw a die repeatedly and work your way up. There are three “snakes”, each taking you down from one perfect square to another, and three “ladders”, each taking you up from one prime to another. The twelve ends of the snakes and ladders are different two-figure numbers. You must go down a snake if you land on its top-end, and up a ladder if you land on its bottom-end.

For any number from 1 to 6, if I throw that same number repeatedly then I eventually land on 100. The number of throws of 4 needed (with first stops 4, 8, …) is one more than when throwing 5s, which is more than when throwing 3s.

What are the three ladders (in the form “p to q”)?

From → Uncategorized

3 Comments Leave one →

BRG permalink

This is a revised version that includes new code and loop reordering from Frits that makes the run-time reasonable using PyPy (it is still quite slow on CPython).


from itertools import combinations

# primes for ladders (lo -> hi)
prms = [n for n in range(11, 100, 2) if all(n % p for p in (3, 5, 7))]
# squares for snakes (hi -> lo)
sqrs = [n * n for n in range(4, 10)]

# make <n> ordered pairs of ends for snakes and ladders
# from values in the ordered sequence <seq>
def pairs(n, seq, prs=()):
  if n == 0:
    yield prs
  else:
    v, rs = seq[0], seq[1:]
    for w in rs:
      yield from pairs(n - 1, [s for s in rs if s != w], prs + ((v, w),))
      
# play Snakes and Ladders always stepping <i> steps with the 
# dictionary <d> holding the snakes and ladders transitions
def play(d, i, sq=()):
  p = i
  while p <= 100 and not p in sq:
    sq += (p,)
    # have we finished correctly?
    if p == 100:
      return sq
    p += i
    # take a snake or ladder if we are on one
    p = d.get(p, p)

# pick six squares for the snakes
for snakes in combinations(sqrs, 6):
  # form pairs for the three snakes
  for sks in pairs(3, snakes):
    t = {b:a for a, b in sks}
    # pick six primes for the ladders
    for ladders in combinations(prms, 6):
      # form pairs for the three ladders
      for lds in pairs(3, ladders):
        # create from -> to dictionary for snakkes/ladders 
        d = t.copy()
        d.update({a:b for a, b in lds})

        # check the results for step sizes 3, 4 and 5
        i2s = dict()
        for i in (4, 5, 3):
          sq = play(d, i)
          i2s[i] = sq
          if not sq or i == 5 and len(i2s[4]) - 1 != len(i2s[5]):
            break
        else:
          if len(i2s) != 3 or len(i2s[5]) <= len(i2s[3]):
            continue
          # check for the remaining step sizes
          i2s.update((i, v) for i in (1, 2, 6) if (v := play(d, i)))
          if len(i2s) == 6:
            for i, s in i2s.items():
              print(f"{i}: {len(s)}: {s}")
            for fr, to in d.items():
              print(f"{fr} -> {to} ({['snake', 'ladder'][bool(fr < to)]})")

from itertools import combinations

# primes for ladders (lo -> hi)

prms = [n for n in range(11, 100, 2) if all(n % p for p in (3, 5, 7))]

# squares for snakes (hi -> lo)

sqrs = [n * n for n in range(4, 10)]

# make <n> ordered pairs of ends for snakes and ladders

# from values in the ordered sequence <seq>

def pairs(n, seq, prs=()):

if n == 0:

yield prs

else:

v, rs = seq[0], seq[1:]

for w in rs:

yield from pairs(n - 1, [s for s in rs if s != w], prs + ((v, w),))

# play Snakes and Ladders always stepping <i> steps with the

# dictionary <d> holding the snakes and ladders transitions

def play(d, i, sq=()):

p = i

while p <= 100 and not p in sq:

sq += (p,)

# have we finished correctly?

if p == 100:

return sq

p += i

# take a snake or ladder if we are on one

p = d.get(p, p)

# pick six squares for the snakes

for snakes in combinations(sqrs, 6):

# form pairs for the three snakes

for sks in pairs(3, snakes):

t = {b:a for a, b in sks}

# pick six primes for the ladders

for ladders in combinations(prms, 6):

# form pairs for the three ladders

for lds in pairs(3, ladders):

# create from -> to dictionary for snakkes/ladders

d = t.copy()

d.update({a:b for a, b in lds})

# check the results for step sizes 3, 4 and 5

i2s = dict()

for i in (4, 5, 3):

sq = play(d, i)

i2s[i] = sq

if not sq or i == 5 and len(i2s[4]) - 1 != len(i2s[5]):

break

else:

if len(i2s) != 3 or len(i2s[5]) <= len(i2s[3]):

continue

# check for the remaining step sizes

i2s.update((i, v) for i in (1, 2, 6) if (v := play(d, i)))

if len(i2s) == 6:

for i, s in i2s.items():

print(f"{i}: {len(s)}: {s}")

for fr, to in d.items():

print(f"{fr} -> {to} ({['snake', 'ladder'][bool(fr < to)]})")

BRG permalink

With some analysis provided by John Crabtree it turns out that it is possible to deduce the form of the three snakes. This makes the run-time more acceptable;


from itertools import combinations

# primes for ladders (lo -> hi)
prms = [n for n in range(11, 100, 2) if all(n % p for p in (3, 5, 7))]
# squares for snakes (hi -> lo)
sqrs = [n * n for n in range(4, 10)]

# make <n> ordered pairs of ends for snakes and ladders
# from values in the ordered sequence <seq>
def pairs(n, seq, prs=()):
  if n == 0:
    yield prs
  else:
    v, rs = seq[0], seq[1:]
    for w in rs:
      yield from pairs(n - 1, [s for s in rs if s != w], prs + ((v, w),))
      
# play Snakes and Ladders always stepping <i> steps with the 
# dictionary <d> holding the snakes and ladders transitions
def play(d, i, sq=()):
  p = i
  while p <= 100 and not p in sq:
    sq += (p,)
    # have we finished correctly?
    if p == 100:
      return sq
    p += i
    # take a snake or ladder if we are on one
    p = d.get(p, p)

# Consider step 6: It will hit 36.  If this isn't the top of a snake 
# it cannot hit 100 or any other snake.  So 36 is the top of a snake
# and the bottom must be 16 or 25.  But it cannot be 16 because step
# 4 would then  get stuck in the 36->16 loop. So one snake is 36->25.
# Now step 6 has to hit another snake from 25 in order to reach 100.
# And the only one that can be hit is 49->16 since 25 and 36 are in
# use. Hence the third snake is 81->64
snakes = {49:16, 36:25, 81:64}
 
# pick six primes for the ladders
for ladders in combinations(prms, 6):
  # form pairs for the three ladders
  for lds in pairs(3, ladders):
    # create from -> to dictionary for snakkes/ladders 
    d = snakes.copy()
    d.update({a:b for a, b in lds})

    # check the results for step sizes 3, 4 and 5
    i2s = dict()
    for i in (4, 5, 3):
      sq = play(d, i)
      i2s[i] = sq
      if not sq or i == 5 and len(i2s[4]) - 1 != len(i2s[5]):
        break
    else:
      if len(i2s) != 3 or len(i2s[5]) <= len(i2s[3]):
        continue
      # check for the remaining step sizes
      i2s.update((i, v) for i in (1, 2, 6) if (v := play(d, i)))
      if len(i2s) == 6:
        for i, s in i2s.items():
          print(f"{i}: {len(s)}: {s}")
        for fr, to in d.items():
          print(f"{fr} -> {to} ({['snake', 'ladder'][bool(fr < to)]})")
        exit()

from itertools import combinations

# primes for ladders (lo -> hi)

prms = [n for n in range(11, 100, 2) if all(n % p for p in (3, 5, 7))]

# squares for snakes (hi -> lo)

sqrs = [n * n for n in range(4, 10)]

# make <n> ordered pairs of ends for snakes and ladders

# from values in the ordered sequence <seq>

def pairs(n, seq, prs=()):

if n == 0:

yield prs

else:

v, rs = seq[0], seq[1:]

for w in rs:

yield from pairs(n - 1, [s for s in rs if s != w], prs + ((v, w),))

# play Snakes and Ladders always stepping <i> steps with the

# dictionary <d> holding the snakes and ladders transitions

def play(d, i, sq=()):

p = i

while p <= 100 and not p in sq:

sq += (p,)

# have we finished correctly?

if p == 100:

return sq

p += i

# take a snake or ladder if we are on one

p = d.get(p, p)

# Consider step 6: It will hit 36. If this isn't the top of a snake

# it cannot hit 100 or any other snake. So 36 is the top of a snake

# and the bottom must be 16 or 25. But it cannot be 16 because step

# 4 would then get stuck in the 36->16 loop. So one snake is 36->25.

# Now step 6 has to hit another snake from 25 in order to reach 100.

# And the only one that can be hit is 49->16 since 25 and 36 are in

# use. Hence the third snake is 81->64

snakes = {49:16, 36:25, 81:64}

# pick six primes for the ladders

for ladders in combinations(prms, 6):

# form pairs for the three ladders

for lds in pairs(3, ladders):

# create from -> to dictionary for snakkes/ladders

d = snakes.copy()

d.update({a:b for a, b in lds})

# check the results for step sizes 3, 4 and 5

i2s = dict()

for i in (4, 5, 3):

sq = play(d, i)

i2s[i] = sq

if not sq or i == 5 and len(i2s[4]) - 1 != len(i2s[5]):

break

else:

if len(i2s) != 3 or len(i2s[5]) <= len(i2s[3]):

continue

# check for the remaining step sizes

i2s.update((i, v) for i in (1, 2, 6) if (v := play(d, i)))

if len(i2s) == 6:

for i, s in i2s.items():

print(f"{i}: {len(s)}: {s}")

for fr, to in d.items():

print(f"{fr} -> {to} ({['snake', 'ladder'][bool(fr < to)]})")

exit()

John Z permalink


from itertools import combinations 

sqs = tuple(x * x for x in range(9, 3, -1))

prms = tuple(x for x in range(11, 100, 2) if all(x % y for y in (3,5,7)))

# returns 3 snakes of form ((top1, top2, top3), (bot1, bot2, bo3))
def snakes(nums):
  # one end of snake must be odd the other even
  s1 = tuple((a, b) for (a, b) in combinations(nums, 2) if (a + b) % 2) 
  for s2 in tuple(combinations(s1, 3)): # 3 possible snakes
    if len(set(sum(s2, ()))) == 6: # all stop and start on different squares
      yield tuple(zip(*s2))

# returns 3 ladders of form ((bot1, bot2, bot3), (top1, top2, top3))
def ladders(nums):
  s1 = tuple(combinations(nums, 2)) 
  for s2 in tuple(combinations(s1, 3)): # 3 possible ladders
    if len(set(sum(s2, ()))) == 6:
      yield tuple(zip(*s2))

def play(s, L):
  tm = [0 for i in range(7)] # total moves for a given throw 1-6

  for throw in range(1, 7):
    cs = 0# cs : current square: start on square of first throw
    st = [0 for i in range(105)] # squares that have been landed upon
    
    while 1:
      tm[throw] += 1 # increment total number of moves      

      cs += throw # add dice value to current square

      if st[cs] == 1 or cs > 100: #is there a loop? or passed 100
        return 0

      elif cs == 100: # reached the end

        break # on to next throw

      st[cs] = 1 # mark current square as having been landed upon

      # landed on the start of a snake or ladder?
      if cs in sL[0]:
        
        cs = sL[1][sL[0].index(cs)] # new current square at end of s or L

        st[cs] = 1
        
  return tm

#---------------------------- main program --------------------------

for s in snakes(sqs):
  print('*') # to indicate that something is happenning
  
  for L in ladders(prms):

    sL = (s[0] + L[0], s[1] + L[1]) #combine snakes and ladders

    # total moves for a given dice throw, 0 if failure
    tm = play(s, L)

    if tm and tm[4] == tm[5] + 1 and tm[5] > tm[3]: # criteria reached
      
      print(*[(i, tm[i]) for i in range(1, 7)])

      for a, b in zip(*L):
        print(f'{a} = > {b} ladder')
      for a, b in zip(*s):
        print(f'{a} = > {b} snake')
      print()

from itertools import combinations

sqs = tuple(x * x for x in range(9, 3, -1))

prms = tuple(x for x in range(11, 100, 2) if all(x % y for y in (3,5,7)))

# returns 3 snakes of form ((top1, top2, top3), (bot1, bot2, bo3))

def snakes(nums):

# one end of snake must be odd the other even

s1 = tuple((a, b) for (a, b) in combinations(nums, 2) if (a + b) % 2)

for s2 in tuple(combinations(s1, 3)): # 3 possible snakes

if len(set(sum(s2, ()))) == 6: # all stop and start on different squares

yield tuple(zip(*s2))

# returns 3 ladders of form ((bot1, bot2, bot3), (top1, top2, top3))

def ladders(nums):

s1 = tuple(combinations(nums, 2))

for s2 in tuple(combinations(s1, 3)): # 3 possible ladders

if len(set(sum(s2, ()))) == 6:

yield tuple(zip(*s2))

def play(s, L):

tm = [0 for i in range(7)] # total moves for a given throw 1-6

for throw in range(1, 7):

cs = 0# cs : current square: start on square of first throw

st = [0 for i in range(105)] # squares that have been landed upon

while 1:

tm[throw] += 1 # increment total number of moves

cs += throw # add dice value to current square

if st[cs] == 1 or cs > 100: #is there a loop? or passed 100

return 0

elif cs == 100: # reached the end

break # on to next throw

st[cs] = 1 # mark current square as having been landed upon

# landed on the start of a snake or ladder?

if cs in sL[0]:

cs = sL[1][sL[0].index(cs)] # new current square at end of s or L

st[cs] = 1

return tm

#---------------------------- main program --------------------------

for s in snakes(sqs):

print('*') # to indicate that something is happenning

for L in ladders(prms):

sL = (s[0] + L[0], s[1] + L[1]) #combine snakes and ladders

# total moves for a given dice throw, 0 if failure

tm = play(s, L)

if tm and tm[4] == tm[5] + 1 and tm[5] > tm[3]: # criteria reached

print(*[(i, tm[i]) for i in range(1, 7)])

for a, b in zip(*L):

print(f'{a} = > {b} ladder')

for a, b in zip(*s):

print(f'{a} = > {b} snake')

print()

Sunday Times Teaser 3263 – Snakes and Ladders

by Victor Bryant

Published Sunday April 06 2025 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta