Sunday Times Teaser 3161 – Going Through the Hoops


from itertools import permutations

# map letters to ball colours with 'K' for Black
l2c = {'B':'Blue', 'K':'Black', 'R':'Red', 'Y':'Yellow'}
balls = 'BKRY'

# find all 4-tuples of colours in which Blue preceeds Black (K)
p4t = [''.join(p) for p in permutations(balls) if p.index('B') < p.index('K')]

# create maps for both adjacent and non-adjacent swaps
# of 4-tuples to sets of 4-tuples that can follow them
p2q_adj, p2q_nad = dict(), dict()
for p, q in permutations(p4t, 2):
  # find the indexes of values that swap psoitions between the p and q 4-tuples 
  if len((t := tuple(p.index(b) for a, b in zip(p, q) if a != b))) == 2: 
    d = (p2q_adj if abs(t[0] - t[1]) == 1 else p2q_nad)
    d[p] = d.get(p, set()) | {q}

# generate sequences of 12 different 4-tuples where two colours swap
# their order between successive 4-tuples with non-adjacent colours 
# swapping only on the fifth and tenth hoops; n is the hoop number
def swap(n, seqs):
  if n == 12:
    yield seqs
  else:
    cs = seqs[-1]
    # use non-adjacent map on hoops 5 and 10 only
    for ns in (p2q_nad[cs] if n in {5, 10} else p2q_adj[cs]):
      if ns not in seqs:
        yield from swap(n + 1, seqs + [ns])

# try all initial ball orders where Blue preceds Black
for fs in p4t:
  for seqs in swap(1, [''.join(fs)]):
    # check for a colour for which all times it is before 
    # Yellow occur before all times it is after Yellow
    for b in balls[:-1]:
      bf, af = -1, 12
      for i, s in enumerate(seqs):
        if s.index(b) < s.index('Y'):
          if i > bf:
            bf = i
        elif i < af:
          af = i
      if bf < af:
        cols = ' '.join(l2c[x] for x in seqs[-1])   
        print(f"{cols} (Black=K {' '.join(seqs)})")

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

36

37

38

39

40

41

42

43

44

45

46

47

48

49

from itertools import permutations

# map letters to ball colours with 'K' for Black

l2c = {'B':'Blue', 'K':'Black', 'R':'Red', 'Y':'Yellow'}

balls = 'BKRY'

# find all 4-tuples of colours in which Blue preceeds Black (K)

p4t = [''.join(p) for p in permutations(balls) if p.index('B') < p.index('K')]

# create maps for both adjacent and non-adjacent swaps

# of 4-tuples to sets of 4-tuples that can follow them

p2q_adj, p2q_nad = dict(), dict()

for p, q in permutations(p4t, 2):

# find the indexes of values that swap psoitions between the p and q 4-tuples

if len((t := tuple(p.index(b) for a, b in zip(p, q) if a != b))) == 2:

d = (p2q_adj if abs(t[0] - t[1]) == 1 else p2q_nad)

d[p] = d.get(p, set()) | {q}

# generate sequences of 12 different 4-tuples where two colours swap

# their order between successive 4-tuples with non-adjacent colours

# swapping only on the fifth and tenth hoops; n is the hoop number

def swap(n, seqs):

if n == 12:

yield seqs

else:

cs = seqs[-1]

# use non-adjacent map on hoops 5 and 10 only

for ns in (p2q_nad[cs] if n in {5, 10} else p2q_adj[cs]):

if ns not in seqs:

yield from swap(n + 1, seqs + [ns])

# try all initial ball orders where Blue preceds Black

for fs in p4t:

for seqs in swap(1, [''.join(fs)]):

# check for a colour for which all times it is before

# Yellow occur before all times it is after Yellow

for b in balls[:-1]:

bf, af = -1, 12

for i, s in enumerate(seqs):

if s.index(b) < s.index('Y'):

if i > bf:

bf = i

elif i < af:

af = i

if bf < af:

cols = ' '.join(l2c[x] for x in seqs[-1])

print(f"{cols} (Black=K {' '.join(seqs)})")

Reply

Frits permalink

@Brian, nice solution.

Can you elaborate on the benefits of the new WordPress site?

The only change I see is a new font for the Python code. I hoped with every comment we could see a creation timestamp.

Reply
- BRG permalink
  
  HI Frits,
  
  It was intended to be a cost reduction but it was a disaster since the promised
  site migration didn’t work. So I am now back to my old host. I had to do some
  recovery work and this meant that my Python formatting plug-in has changed. I
  can set the font but I left it on default – is it better or worse? EDIT: I put
  it back to the old font.
  
  Reply
  - Frits permalink
    
    I like the old font better, thanks.
    
    Reply

JohnZ permalink

The teaser is ambiguous about which hoop to hoop transitions have non adjacent swaps. A single solution is reached for transitions from 5 to 6 and 10 to 11.


from itertools import permutations

def croquet(a):
  #a is the solution so far, a tuple of tuples of the four colours
  hoop = len(a) + 1 #next hoop to pass

  if hoop == 13: #all hoops passed
    yield a
  else:
    # consider remaining tuples of four colours to go through next hoop 'nh'
    for nh in bb - set(a):

      # line up colours from previous and next hoops        
      pn = tuple(zip(a[-1], nh))

      # only two colours are allowed to swap places
      if sum(m != n for m, n in pn) != 2:
        continue
      # swap of adjacent 
      sw2 = any(pn[i][0] == pn[i + 1][1] and pn[i][1] == pn[i + 1][0]
                for i in range(3))
      # for non adjacent swap in transition from hoop 5 to hoop 6, 10 to 11?
      h510 = hoop in (6, 11)
      # if adjacent / non-adjacent swap condition is met: to next level
      if (not h510 and sw2) or (h510 and not sw2):
        yield from croquet(a + (nh,))

#main program
balls = ('Blue', 'Black', 'Red', 'Yellow') 

#make the set of different ball orders with Blue before Black
bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

# consider initial hoop out of above set
for b4 in bb:
  for sol in croquet((b4,)):

    # before / after yellow check
    for c in ('Blue', 'Black', 'Red'):
      d, e = 0, 0
      for s in sol:
        if e == 0 and s.index(c) < s.index('Yellow'):
          d += 1
        elif d > 0 and s.index(c) > s.index('Yellow'):
          e += 1      
      if d + e == 12:
        print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))
        print(f'({c} before / after Yellow)')

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

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

from itertools import permutations

def croquet(a):

#a is the solution so far, a tuple of tuples of the four colours

hoop = len(a) + 1 #next hoop to pass

if hoop == 13: #all hoops passed

yield a

else:

# consider remaining tuples of four colours to go through next hoop 'nh'

for nh in bb - set(a):

# line up colours from previous and next hoops

pn = tuple(zip(a[-1], nh))

# only two colours are allowed to swap places

if sum(m != n for m, n in pn) != 2:

continue

# swap of adjacent

sw2 = any(pn[i][0] == pn[i + 1][1] and pn[i][1] == pn[i + 1][0]

for i in range(3))

# for non adjacent swap in transition from hoop 5 to hoop 6, 10 to 11?

h510 = hoop in (6, 11)

# if adjacent / non-adjacent swap condition is met: to next level

if (not h510 and sw2) or (h510 and not sw2):

yield from croquet(a + (nh,))

#main program

balls = ('Blue', 'Black', 'Red', 'Yellow')

#make the set of different ball orders with Blue before Black

bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

# consider initial hoop out of above set

for b4 in bb:

for sol in croquet((b4,)):

# before / after yellow check

for c in ('Blue', 'Black', 'Red'):

d, e = 0, 0

for s in sol:

if e == 0 and s.index(c) < s.index('Yellow'):

d += 1

elif d > 0 and s.index(c) > s.index('Yellow'):

e += 1

if d + e == 12:

print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))

print(f'({c} before / after Yellow)')

Reply

John Z permalink

Line 26 can be written more efficiently as:


if  h510 ^ sw2:

1

2

3

if h510 ^ sw2:

Reply

John Z permalink

A more compact version of my first post


from itertools import permutations

def croquet(a):
  # a is the solution so far, a tuple of tuples of the four colours
  if len(a) == 12: # all hoops passed
    yield a
  else:
    # consider remaining tuples of four colours to go through next hoop 'nh'
    for nh in bb - set(a):

      # only two colours are allowed to swap places
      if (sum(mm := [m != n for m, n in tuple(zip(a[-1], nh))]) == 2 and
      
      # and if adjacent / non-adjacent swap condition is met: to next level
         (len(a) in (5, 10)) ^ (mm[0] & mm[1] or mm[1] & mm[2] or mm[2] & mm[3])):

        yield from croquet(a + (nh,))
                         #
#main program
balls = ('Blue', 'Black', 'Red', 'Yellow') 

#make the set of different ball orders with Blue before Black
bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

# consider initial hoop out of above set
for b4 in bb:
  for sol in croquet((b4,)):
   
    # before / after yellow check
    for c in ('Blue', 'Black', 'Red'):
      d, e = 0, 0 # before and after counters
      for s in sol:
        if e == 0 and s.index(c) < s.index('Yellow'):
          d += 1
        elif d > 0 and s.index(c) > s.index('Yellow'):
          e += 1      
      if d + e == 12:
        print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))
        print(f'({c} before / after Yellow)')

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

36

37

38

39

40

41

from itertools import permutations

def croquet(a):

# a is the solution so far, a tuple of tuples of the four colours

if len(a) == 12: # all hoops passed

yield a

else:

# consider remaining tuples of four colours to go through next hoop 'nh'

for nh in bb - set(a):

# only two colours are allowed to swap places

if (sum(mm := [m != n for m, n in tuple(zip(a[-1], nh))]) == 2 and

# and if adjacent / non-adjacent swap condition is met: to next level

(len(a) in (5, 10)) ^ (mm[0] & mm[1] or mm[1] & mm[2] or mm[2] & mm[3])):

yield from croquet(a + (nh,))

#

#main program

balls = ('Blue', 'Black', 'Red', 'Yellow')

#make the set of different ball orders with Blue before Black

bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

# consider initial hoop out of above set

for b4 in bb:

for sol in croquet((b4,)):

# before / after yellow check

for c in ('Blue', 'Black', 'Red'):

d, e = 0, 0 # before and after counters

for s in sol:

if e == 0 and s.index(c) < s.index('Yellow'):

d += 1

elif d > 0 and s.index(c) > s.index('Yellow'):

e += 1

if d + e == 12:

print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))

print(f'({c} before / after Yellow)')

Reply

John Z permalink

My definitive version:
Variables byt, ayt and cc could be made ‘global’ in hp (if cc is removed from the argument list and from the ‘yield’) which would result in improved run time but would this be considered good style?


from itertools import permutations

balls = ('Blue', 'Black', 'Red', 'Yellow') 

# by, ay: before / after yellow counters; cc: colours ok before & after yellow
def hp(a = (), by = {c: 0 for c in balls}, ay = {c: 0 for c in balls}, cc = 0):
  
  # a is the solution so far, a tuple of tuples of the four colours
  if (la := len(a)) == 12: # all hoops passed
    yield a, cc
    
  else:
    # consider remaining tuples of four colours to go through next hoop 'nh'
    for nh in bb - set(a):
      
      # before yellow count (temporary variable)
      byt = {c: by[c] + (ay[c] == 0 and nh.index(c) < (iy := nh.index('Yellow'))
            ) for c in balls}
      # after yellow count (temporary variable)
      ayt = {c: ay[c] + (nh.index(c) > iy) for c in balls}

      # skip tests for first hoop
      if not la or (
      # only two colours are allowed to swap places in successive hoops
          sum(mm := [m != n for m, n in tuple(zip(a[-1], nh))]) == 2 and
      
      # and if adjacent / non-adjacent swap condition is met: to next hoop
         (la in (5, 10)) ^ (mm[0] & mm[1] or mm[1] & mm[2] or mm[2] & mm[3])
        
      # and set of colours on track for before/after yellow criterion not null 
         and (cc := {c for c in balls if ay[c] + by[c] == la})):

        yield from hp(a + (nh,), byt, ayt, cc)
                         #
# main program

# make the set of different ball orders with Blue before Black
bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

for sol, cc  in hp():

  print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))
  print(f'({cc.pop()} before / after Yellow)')

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

36

37

38

39

40

41

42

43

44

45

from itertools import permutations

balls = ('Blue', 'Black', 'Red', 'Yellow')

# by, ay: before / after yellow counters; cc: colours ok before & after yellow

def hp(a = (), by = {c: 0 for c in balls}, ay = {c: 0 for c in balls}, cc = 0):

# a is the solution so far, a tuple of tuples of the four colours

if (la := len(a)) == 12: # all hoops passed

yield a, cc

else:

# consider remaining tuples of four colours to go through next hoop 'nh'

for nh in bb - set(a):

# before yellow count (temporary variable)

byt = {c: by[c] + (ay[c] == 0 and nh.index(c) < (iy := nh.index('Yellow'))

) for c in balls}

# after yellow count (temporary variable)

ayt = {c: ay[c] + (nh.index(c) > iy) for c in balls}

# skip tests for first hoop

if not la or (

# only two colours are allowed to swap places in successive hoops

sum(mm := [m != n for m, n in tuple(zip(a[-1], nh))]) == 2 and

# and if adjacent / non-adjacent swap condition is met: to next hoop

(la in (5, 10)) ^ (mm[0] & mm[1] or mm[1] & mm[2] or mm[2] & mm[3])

# and set of colours on track for before/after yellow criterion not null

and (cc := {c for c in balls if ay[c] + by[c] == la})):

yield from hp(a + (nh,), byt, ayt, cc)

#

# main program

# make the set of different ball orders with Blue before Black

bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

for sol, cc in hp():

print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))

print(f'({cc.pop()} before / after Yellow)')

Reply

John Z permalink

Never say never; tighter still


from itertools import permutations

balls = ('Blue', 'Black', 'Red', 'Yellow') 

# cy: before / after yellow counters; cc: colours ok before & after yellow
def hoops(a = (), cy = {c: (0, 0) for c in balls[:-1]}, cc = balls[:-1]):
  
  # 'a' is the solution so far, a tuple of tuples of the four colours
  if (la := len(a)) == 12: # all hoops passed
    yield a, *cc
    
  else:
    # consider remaining tuples of four colours to go through next hoop 'nh'
    for nh in bb - set(a):

      iy = nh.index('Yellow')

      # increment before / after yellow counts by colour
      cyt = {c: (cy[c][0] + (nh.index(c) < iy and cy[c][1] == 0),
                 cy[c][1] + (nh.index(c) > iy)) for c in cc}             

      # skip tests for first hoop, do tests for second and successive hoops
      if not la or (
      # only two colours are allowed to swap places in successive hoops
          sum(mm := [m != n for m, n in tuple(zip(a[-1], nh))]) == 2 and
      
      # and if adjacent / non-adjacent swap condition is met
         (la in (5, 10)) ^ (mm[0] & mm[1] or mm[1] & mm[2] or mm[2] & mm[3])
        
      # and there are still colours on track for before/after yellow criterion 
         and (cc := tuple(c for c in cc if sum(cyt[c]) == la + 1))):

        # to next hoop
        yield from hoops(a + (nh,), cyt, cc)
                         #
# main program

# make the set of different ball orders with Blue before Black
bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

for sol, cc  in hoops():

  print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))
  print(f'({cc} before / after Yellow)')

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

36

37

38

39

40

41

42

43

44

45

46

from itertools import permutations

balls = ('Blue', 'Black', 'Red', 'Yellow')

# cy: before / after yellow counters; cc: colours ok before & after yellow

def hoops(a = (), cy = {c: (0, 0) for c in balls[:-1]}, cc = balls[:-1]):

# 'a' is the solution so far, a tuple of tuples of the four colours

if (la := len(a)) == 12: # all hoops passed

yield a, *cc

else:

# consider remaining tuples of four colours to go through next hoop 'nh'

for nh in bb - set(a):

iy = nh.index('Yellow')

# increment before / after yellow counts by colour

cyt = {c: (cy[c][0] + (nh.index(c) < iy and cy[c][1] == 0),

cy[c][1] + (nh.index(c) > iy)) for c in cc}

# skip tests for first hoop, do tests for second and successive hoops

if not la or (

# only two colours are allowed to swap places in successive hoops

sum(mm := [m != n for m, n in tuple(zip(a[-1], nh))]) == 2 and

# and if adjacent / non-adjacent swap condition is met

(la in (5, 10)) ^ (mm[0] & mm[1] or mm[1] & mm[2] or mm[2] & mm[3])

# and there are still colours on track for before/after yellow criterion

and (cc := tuple(c for c in cc if sum(cyt[c]) == la + 1))):

# to next hoop

yield from hoops(a + (nh,), cyt, cc)

#

# main program

# make the set of different ball orders with Blue before Black

bb = set(i for i in permutations(balls) if i.index('Blue') < i.index('Black'))

for sol, cc in hoops():

print(*sol[-1], '\n' + '-' * 21, *tuple('\n' + ' '.join(s) for s in sol))

print(f'({cc} before / after Yellow)')

Reply

Sunday Times Teaser 3161 – Going Through the Hoops

Colin Vout

Published Sunday April 23 2023 (link)

Leave a comment to BRG Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta