Sunday Times Teaser 3097 – Crazy Golf

by BRG on January 28, 2022

by Angela Newing

Published Sunday January 30 2022 (link)

Ian was trying to entertain John and Ken, his 2 young nephews, in the local park, which had a 9-hole crazy golf course. He decided to play a round with each of them separately, and gave them money for each hole he lost on a rising scale. He would pay £1 if he lost the first hole (or the first hole after winning one), then £2 if he lost the next consecutive hole, and £3 for the third, and so on.

In the event, Ian won only 5 holes in total between the two rounds, including the first hole against John and the last hole against Ken. There were no ties. At the reckoning after both rounds, both boys received equal amounts of money.

How much did it cost Uncle Ian?

From → Uncategorized

7 Comments Leave one →

Brian Gladman permalink


from collections import defaultdict

# generate sequences of nine holes from Ian's perspective
# summing his losses and his costs from sequential losses
# (since sequences are reversible, we always start with a 
# a win for John and then reverse the sequence for Ken)
#
# number of holes: nh
# hole value: v (0 = loss, 1 = win)
# hole cost: cs
# sequence of results: seq

def round(nh=9, v=1, ls=0, cs=0, seq=()):
  # have we finished?
  if not nh:
    yield ls, cs
  else:
    # the length of the next sequence of wins or losses
    for ln in range(1, nh + 1):
      yield from round(nh - ln, 1 - v,
                # count the losses and their cost 
                ls + (0 if v else ln), 
                cs + (0 if v else ln * (ln + 1) // 2), 
                seq + (v,) * ln)

# map costs to losses
c2l = defaultdict(set)
for ls, cs in round():
  c2l[cs].add(ls)

# consider possible costs
for cost, s_loss in c2l.items():
  # look for 13 losses in total (5 wins)
  if [x for x in s_loss if 13 - x in s_loss]:
    print(f"It cost Uncle Ian £{2 * cost} in total.")

from collections import defaultdict

# generate sequences of nine holes from Ian's perspective

# summing his losses and his costs from sequential losses

# (since sequences are reversible, we always start with a

# a win for John and then reverse the sequence for Ken)

# number of holes: nh

# hole value: v (0 = loss, 1 = win)

# hole cost: cs

# sequence of results: seq

def round(nh=9, v=1, ls=0, cs=0, seq=()):

# have we finished?

if not nh:

yield ls, cs

else:

# the length of the next sequence of wins or losses

for ln in range(1, nh + 1):

yield from round(nh - ln, 1 - v,

# count the losses and their cost

ls + (0 if v else ln),

cs + (0 if v else ln * (ln + 1) // 2),

seq + (v,) * ln)

# map costs to losses

c2l = defaultdict(set)

for ls, cs in round():

c2l[cs].add(ls)

# consider possible costs

for cost, s_loss in c2l.items():

# look for 13 losses in total (5 wins)

if [x for x in s_loss if 13 - x in s_loss]:

print(f"It cost Uncle Ian £{2 * cost} in total.")

This version is slower but outputs the results of the rounds of crazy golf involved.


def round(nh=9, v=1, ls=0, cs=0, seq=()):
  # have we finished?
  if not nh:
    yield ls, cs, seq
  else:
    # the length of the next sequence of wins or losses
    for ln in range(1, nh + 1):
      yield from round(nh - ln, 1 - v,
                # count the losses and their cost 
                ls + (0 if v else ln), 
                cs + (0 if v else ln * (ln + 1) // 2), 
                seq + (v,) * ln)

rounds = list(round())

pseq = lambda s: ''.join('wl'[i] for i in s)

ct = 0
# John's possible sequence of holes starting with a win
for l2j, p2j, s2j in rounds:
  # Ian's possible sequence of holes ending with a
  # win (the sequences are reversible)
  for l2k, p2k, s2k in rounds:
    # look for 13 total losses and equal boys income 
    if l2j + l2k == 13 and p2j == p2k:
      ct += 1
      print(f"{ct:2} John {pseq(s2j)} -> £{p2j}  Ken {pseq(s2k[::-1])} -> £{p2k}")

def round(nh=9, v=1, ls=0, cs=0, seq=()):

# have we finished?

if not nh:

yield ls, cs, seq

else:

# the length of the next sequence of wins or losses

for ln in range(1, nh + 1):

yield from round(nh - ln, 1 - v,

# count the losses and their cost

ls + (0 if v else ln),

cs + (0 if v else ln * (ln + 1) // 2),

seq + (v,) * ln)

rounds = list(round())

pseq = lambda s: ''.join('wl'[i] for i in s)

ct = 0

# John's possible sequence of holes starting with a win

for l2j, p2j, s2j in rounds:

# Ian's possible sequence of holes ending with a

# win (the sequences are reversible)

for l2k, p2k, s2k in rounds:

# look for 13 total losses and equal boys income

if l2j + l2k == 13 and p2j == p2k:

ct += 1

print(f"{ct:2} John {pseq(s2j)} -> £{p2j} Ken {pseq(s2k[::-1])} -> £{p2k}")

John Z permalink

This should be quite fast


from sys import exit

# List of Ian's losses against first nephew indexed by second game won of two
iloss = [0] * 10

# Ian must win two games against one nephew and three against the other
# If Ian wins one game against the first and four against the second, losses
# to each nephew cannot be equal

# Ian wins first game and one other against one nephew
# this is equivalent to Ian wins last game and one other for losses

# Second game Ian wins
for i in range(2, 9):
  iloss[i] = (i - 2) * (i - 1) // 2 + (9 - i) * (10 - i) // 2

# Ian wins first game and two others against the other nephew
# equivalent to Ian wins two games and last game for losses

# Second game Ian wins
for i in range(2, 8):

  # Third game Ian wins:
  for j in range(i + 1, 9):
    # Ian's losses for this configuration of his wins (1, i, j)
    loss2 =  ((i - 2) * (i - 1) // 2 +
              (j - i - 1) * (j - i) // 2 +
              (9 - j) * (10 - j) // 2)
    
    # Are losses to second nephew same as one of the losses against the first?
    if loss2 in iloss:
      print(f'Uncle Ian lost £{loss2 * 2}')
      exit()

from sys import exit

# List of Ian's losses against first nephew indexed by second game won of two

iloss = [0] * 10

# Ian must win two games against one nephew and three against the other

# If Ian wins one game against the first and four against the second, losses

# to each nephew cannot be equal

# Ian wins first game and one other against one nephew

# this is equivalent to Ian wins last game and one other for losses

# Second game Ian wins

for i in range(2, 9):

iloss[i] = (i - 2) * (i - 1) // 2 + (9 - i) * (10 - i) // 2

# Ian wins first game and two others against the other nephew

# equivalent to Ian wins two games and last game for losses

# Second game Ian wins

for i in range(2, 8):

# Third game Ian wins:

for j in range(i + 1, 9):

# Ian's losses for this configuration of his wins (1, i, j)

loss2 = ((i - 2) * (i - 1) // 2 +

(j - i - 1) * (j - i) // 2 +

(9 - j) * (10 - j) // 2)

# Are losses to second nephew same as one of the losses against the first?

if loss2 in iloss:

print(f'Uncle Ian lost £{loss2 * 2}')

exit()

Brian Gladman permalink

Nice to see you back John. You are right that it is fast – too fast to measure with Python’s profile tool.

You could simplify it a little by using a set for ‘iloss’ since you don’t make any use of indexing other than for storage.

Reply

John Z permalink

Taking into account your comment about using a set instead of a list and using combinations instead of nested for loops to avoid using exit.


from itertools import combinations

# Set of Ian's losses against first nephew
iloss = set()
# Ian must win two games against one nephew and three against the other
# If Ian wins one game against the first and four against the second, losses
# to each nephew cannot be equal

# Ian wins first game and one other against one nephew

# This is equivalent to Ian wins last game and one other for losses
# Second game Ian wins
for i in range(2, 9):
  iloss.add((i - 2) * (i - 1) // 2 + (9 - i) * (10 - i) // 2)

# Ian wins first game and two others against the other nephew
# equivalent to Ian wins two games and last game for losses

# Second and third games Ian wins
for i, j in combinations(range(2, 9), 2):

  # Ian's losses for this configuration of his wins (1, i, j)
  loss2 =  ((i - 2) * (i - 1) // 2 +
            (j - i - 1) * (j - i) // 2 +
            (9 - j) * (10 - j) // 2)

  # Are losses to second nephew same as one of the losses against the first?
  if loss2 in iloss:
    print(f'Uncle Ian lost £{loss2 * 2}')
    break

from itertools import combinations

# Set of Ian's losses against first nephew

iloss = set()

# Ian must win two games against one nephew and three against the other

# If Ian wins one game against the first and four against the second, losses

# to each nephew cannot be equal

# Ian wins first game and one other against one nephew

# This is equivalent to Ian wins last game and one other for losses

# Second game Ian wins

for i in range(2, 9):

iloss.add((i - 2) * (i - 1) // 2 + (9 - i) * (10 - i) // 2)

# Ian wins first game and two others against the other nephew

# equivalent to Ian wins two games and last game for losses

# Second and third games Ian wins

for i, j in combinations(range(2, 9), 2):

# Ian's losses for this configuration of his wins (1, i, j)

loss2 = ((i - 2) * (i - 1) // 2 +

(j - i - 1) * (j - i) // 2 +

(9 - j) * (10 - j) // 2)

# Are losses to second nephew same as one of the losses against the first?

if loss2 in iloss:

print(f'Uncle Ian lost £{loss2 * 2}')

break

Brian Gladman permalink

Hi John, Your version can certainly be used to produce a very short and fast solution!


T = lambda x: x * (x + 1) // 2

loss = (set(T(i - 2) + T(9 - i) for i in range(2, 9)) &
        set(T(i - 2) + T(j - i - 1) + T(9 - j) 
          for i in range(2, 9) for j in range(i + 1, 9))).pop()
print(f'Uncle Ian lost £{2 * loss}')

T = lambda x: x * (x + 1) // 2

loss = (set(T(i - 2) + T(9 - i) for i in range(2, 9)) &

set(T(i - 2) + T(j - i - 1) + T(9 - j)

for i in range(2, 9) for j in range(i + 1, 9))).pop()

print(f'Uncle Ian lost £{2 * loss}')

John Z permalink

Indeed! You beat me to it. This is what I was about to post:


print('Uncle Ian loses £',
      * {((i - 2) * (i - 1) + (9 - i) * (10 - i)) for i in range(2, 9)}
      & {((i - 2) * (i - 1) + (j - i - 1) * (j - i) + (9 - j) * (10 - j))
        for i in range(2, 8) for j in range(i + 1, 9)})

print('Uncle Ian loses £',

* {((i - 2) * (i - 1) + (9 - i) * (10 - i)) for i in range(2, 9)}

& {((i - 2) * (i - 1) + (j - i - 1) * (j - i) + (9 - j) * (10 - j))

for i in range(2, 8) for j in range(i + 1, 9)})

Frits permalink

or even


# iloss[i] = iloss[11 - i]
# loss2[i][j] = loss2[11 - j][11 - i]

print('Uncle Ian loses Â£',
      * {((i - 2) * (i - 1) + (9 - i) * (10 - i)) for i in range(2, 6)}
      & {((i - 2) * (i - 1) + (j - i - 1) * (j - i) + (9 - j) * (10 - j))
        for i in range(2, 6) for j in range(i + 1, 12 - i)})

# iloss[i] = iloss[11 - i]

# loss2[i][j] = loss2[11 - j][11 - i]

print('Uncle Ian loses Â£',

* {((i - 2) * (i - 1) + (9 - i) * (10 - i)) for i in range(2, 6)}

& {((i - 2) * (i - 1) + (j - i - 1) * (j - i) + (9 - j) * (10 - j))

for i in range(2, 6) for j in range(i + 1, 12 - i)})

Sunday Times Teaser 3097 – Crazy Golf

by Angela Newing

Published Sunday January 30 2022 (link)

Leave a comment to John Z Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta