New Scientist Enigma 581 – Trail Blazing Cards

by BRG on October 26, 2020

by Keith Austin

From Issue #1734, 15th September 1990

We spent the day camped at the entrance to Apache Pass waiting for the cover of darkness. I passed the time playing cards with a grizzly old prospector, using a pack given him by Billy the Kid.

He took the spades from ace to ten and laid them in a row so:

6 2 9 7 3 10 8 1 4 5

where 1 is the ace.

“That’s the order Wyatt Earp dealt me just before the gunfight at the OK Corral. You can exchange any to cards provided the numbers on them are consecutive but the cards are not next to each other. For example, you can exchange the 7 and the 8, or the 2 and the 3, but not the 4 and the 5”.

“So I can exchange the 7 and 8 and get:

6 2 9 8 3 10 7 1 4 5

and then exchange the 3 and 4 and get:

6 2 9 8 4 10 7 1 3 5

and then exchange the 4 and 5 and get:

6 2 9 8 5 10 7 1 3 4

and so on?” I asked.

“You’ve got it. Now look at this old treasure map I got from Geronimo. It has 6 rows of numbers on it:

A: 7 2 10 9 4 5 3 1 8 6
B: 5 9 2 4 8 1 3 10 7 6
C: 7 4 5 2 1 10 8 3 6 9
D: 4 5 7 8 1 3 2 10 6 9
E: 10 3 4 2 1 9 6 5 7 8
F: 6 10 8 5 3 1 2 4 7 9

“Geronimo said the to discover the treasure it was necessary to find which of these six rows can be obtained from Wyatt’s row by the allowed
operations.”

Find all those of the six rows which can be obtained from Wyatt’s row.

From → Uncategorized

One Comment Leave one →

Brian Gladman permalink


from collections import defaultdict
from itertools import count

# the starting sequence
start = (6, 2, 9, 8, 3, 10, 7, 1, 4, 5)

# the target sequences
ends = dict( 
  A = (7, 2, 10, 9, 4, 5, 3, 1, 8, 6),
  B = (5, 9, 2, 4, 8, 1, 3, 10, 7, 6),
  C = (7, 4, 5, 2, 1, 10, 8, 3, 6, 9),
  D = (4, 5, 7, 8, 1, 3, 2, 10, 6, 9),
  E = (10, 3, 4, 2, 1, 9, 6, 5, 7, 8),
  F = (6, 10, 8, 5, 3, 1, 2, 4, 7, 9))

# given a card sequence (seq) and the swaps (swaps) needed
# to reach it from the start, return a list of the sequences 
# that are reachable from it and the swaps they involve
def swaps(seq, swaps):
  sqn = list()
  for i in range(1, 10):
    p, q = seq.index(i), seq.index(i + 1)
    if abs(p - q) > 1:
      t = list(seq)
      t[p], t[q] = seq[q], seq[p]
      sqn.append((tuple(t), swaps + ((i, i + 1),)))
      
  return sqn              

# list reachable card sequences indexed on the 
# number of swaps they involve 
l2sq = defaultdict(list)
l2sq[0].append((start, ()))
sseq = set(start)
tcnt, zcnt = 0, 0
# the number of swaps involved so far
for lv in count():
  
  # for each sequence reachable in this number of swaps, 
  # list the sequences reachable with one more swap
  for s, t in l2sq[lv]:
    for ss, tt in swaps(s, t):
      if ss not in sseq:
        sseq.add(ss)
        l2sq[lv + 1].append((ss, tt))
  
  # look for and report any target sequences reached
  for s, t in l2sq[lv + 1]:
    for k, v in ends.items():
      if s == v:
        print(f"Sequence {k}: {v} in {lv} swaps:\n  {t}")
        
  # exit if we see no new sequences in three consecutive lengths
  ln = len(l2sq[lv + 1])
  tcnt += ln
  zcnt = 0 if ln else zcnt + 1
  if zcnt == 3:
    print(f"Searched {tcnt} reachable sequences.")
    break

from collections import defaultdict

from itertools import count

# the starting sequence

start = (6, 2, 9, 8, 3, 10, 7, 1, 4, 5)

# the target sequences

ends = dict(

A = (7, 2, 10, 9, 4, 5, 3, 1, 8, 6),

B = (5, 9, 2, 4, 8, 1, 3, 10, 7, 6),

C = (7, 4, 5, 2, 1, 10, 8, 3, 6, 9),

D = (4, 5, 7, 8, 1, 3, 2, 10, 6, 9),

E = (10, 3, 4, 2, 1, 9, 6, 5, 7, 8),

F = (6, 10, 8, 5, 3, 1, 2, 4, 7, 9))

# given a card sequence (seq) and the swaps (swaps) needed

# to reach it from the start, return a list of the sequences

# that are reachable from it and the swaps they involve

def swaps(seq, swaps):

sqn = list()

for i in range(1, 10):

p, q = seq.index(i), seq.index(i + 1)

if abs(p - q) > 1:

t = list(seq)

t[p], t[q] = seq[q], seq[p]

sqn.append((tuple(t), swaps + ((i, i + 1),)))

return sqn

# list reachable card sequences indexed on the

# number of swaps they involve

l2sq = defaultdict(list)

l2sq[0].append((start, ()))

sseq = set(start)

tcnt, zcnt = 0, 0

# the number of swaps involved so far

for lv in count():

# for each sequence reachable in this number of swaps,

# list the sequences reachable with one more swap

for s, t in l2sq[lv]:

for ss, tt in swaps(s, t):

if ss not in sseq:

sseq.add(ss)

l2sq[lv + 1].append((ss, tt))

# look for and report any target sequences reached

for s, t in l2sq[lv + 1]:

for k, v in ends.items():

if s == v:

print(f"Sequence {k}: {v} in {lv} swaps:\n {t}")

# exit if we see no new sequences in three consecutive lengths

ln = len(l2sq[lv + 1])

tcnt += ln

zcnt = 0 if ln else zcnt + 1

if zcnt == 3:

print(f"Searched {tcnt} reachable sequences.")

break

New Scientist Enigma 581 – Trail Blazing Cards

by Keith Austin

From Issue #1734, 15th September 1990

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta