Sunday Times Teaser 3194 – A Proper Lesson


from itertools import count, combinations
from math import gcd

def fout(g):
  fn = lambda f: f'{f[0]}/{f[1]}'
  return f"{fn(g[0])} + {fn(g[1])}, {fn(g[2])} + {fn(g[3])}"

# we need at least eight different numbers
for n_max in count(8):
  # find pairs of fractions (a/b, c/d) that add to 1 using
  # numbers (a, b, c, d) from  1 .. n_max inclusive
  sp = set()
  # the first fraction (a / b)
  for a in range(1, n_max + 1):
    for b in range(a + 1, n_max + 1):
      # compute second fractions equal to 1 -  a / b
      g = gcd(b - a, b)
      c, d = (b - a) // g, b // g
      sp |= set(t for m in range(1, g)
               if len(set(t := (m * c, m * d, a, b))) == 4)
            
  # save groups of four fractions in all pairs of these 
  # fraction pairs that use eight different numbers and
  # record all fractions used
  l_f4, l_fr = list(), list()
  for f1, f2 in combinations(sp, 2):
    f12 = f1 + f2
    if len(set(f12)) == 8:
      # collect the four fractions involved
      f4 = list(((p, q) for p, q in zip(f12[::2], f12[1::2])))
      l_f4 += [f4]
      l_fr += f4
  if not l_f4:
    continue
  for g in l_f4:
    nud = set(range(1, n_max + 1)).difference(a for b in g for a in b)
    b = any(l_fr.count(f) == 1 for f in g)
    print(fout(g), b * f" ==> Solution {sorted(nud)}")
  break

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 count, combinations

from math import gcd

def fout(g):

fn = lambda f: f'{f[0]}/{f[1]}'

return f"{fn(g[0])} + {fn(g[1])}, {fn(g[2])} + {fn(g[3])}"

# we need at least eight different numbers

for n_max in count(8):

# find pairs of fractions (a/b, c/d) that add to 1 using

# numbers (a, b, c, d) from 1 .. n_max inclusive

sp = set()

# the first fraction (a / b)

for a in range(1, n_max + 1):

for b in range(a + 1, n_max + 1):

# compute second fractions equal to 1 - a / b

g = gcd(b - a, b)

c, d = (b - a) // g, b // g

sp |= set(t for m in range(1, g)

if len(set(t := (m * c, m * d, a, b))) == 4)

# save groups of four fractions in all pairs of these

# fraction pairs that use eight different numbers and

# record all fractions used

l_f4, l_fr = list(), list()

for f1, f2 in combinations(sp, 2):

f12 = f1 + f2

if len(set(f12)) == 8:

# collect the four fractions involved

f4 = list(((p, q) for p, q in zip(f12[::2], f12[1::2])))

l_f4 += [f4]

l_fr += f4

if not l_f4:

continue

for g in l_f4:

nud = set(range(1, n_max + 1)).difference(a for b in g for a in b)

b = any(l_fr.count(f) == 1 for f in g)

print(fout(g), b * f" ==> Solution {sorted(nud)}")

break

Reply

John Z permalink


from itertools import count, permutations, combinations
from sys import exit

# get a / b; c / d
for jlo in count(9): # jlo  + 1: just long enough; minimum = 8
  
  # a / b + c / d = 1 -> a * d + c * b = b * d
  pairs = [(a, b, c, d) for a, b, c, d in permutations(range(1, jlo), 4)
            if a < c and a * d + c * b == b * d]
  
  groupsf = list()
  fra = set()

  # group two of the pairs that used eight different numbers from her list
  for gr in combinations(pairs, 2):
    if len(set(gr[0]).union(gr[1])) == 8:
     
    
     # fractions made from pairs
     a, b, c, d, e, f, g, h = gr[0] + gr[1]
     grf = ((a, b), (c, d), (e, f), (g, h))

     groupsf.append((grf, gr[0] + gr[1])) # fractions and their num's and den's

     fra |= set(grf) # set of all fractions encountered
              
  
  if len(groupsf) > 1:
    frat = tuple(fra) # in order to be able to find fractions that occurs once
    
    # number of occurrences of each fraction in group    
    fc = [sum(f in g[0] for g in groupsf) for f in frat]

    # a fraction that occurs once in all groups is not used by only one group.
    if 1 in fc:
      fi = fc.index(1)
      for g in groupsf:
        if frat[fi] in g[0]:
          print('group:', *g[0], '; not used:', set(range(1, jlo)) - set(g[1]))
          exit()

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

from itertools import count, permutations, combinations

from sys import exit

# get a / b; c / d

for jlo in count(9): # jlo + 1: just long enough; minimum = 8

# a / b + c / d = 1 -> a * d + c * b = b * d

pairs = [(a, b, c, d) for a, b, c, d in permutations(range(1, jlo), 4)

if a < c and a * d + c * b == b * d]

groupsf = list()

fra = set()

# group two of the pairs that used eight different numbers from her list

for gr in combinations(pairs, 2):

if len(set(gr[0]).union(gr[1])) == 8:

# fractions made from pairs

a, b, c, d, e, f, g, h = gr[0] + gr[1]

grf = ((a, b), (c, d), (e, f), (g, h))

groupsf.append((grf, gr[0] + gr[1])) # fractions and their num's and den's

fra |= set(grf) # set of all fractions encountered

if len(groupsf) > 1:

frat = tuple(fra) # in order to be able to find fractions that occurs once

# number of occurrences of each fraction in group

fc = [sum(f in g[0] for g in groupsf) for f in frat]

# a fraction that occurs once in all groups is not used by only one group.

if 1 in fc:

fi = fc.index(1)

for g in groupsf:

if frat[fi] in g[0]:

print('group:', *g[0], '; not used:', set(range(1, jlo)) - set(g[1]))

exit()

Reply

John Z permalink

Distilled down to the essentials with more complete printout


from itertools import count, combinations, chain
from sys import exit

# get a / b; c / d
for jlo in count(9): # jlo  + 1: just long enough; minimum = 8

  # a / b + c / d = 1 -> a * d + c * b = b * d
  # generate pairs of positive fractions adding up to 1
  pairs = [(a, b, c, d) for a, b in combinations(range(1, jlo), 2)
           for c, d in combinations(range(a + 1, jlo), 2)
           if b != c and a * d + c * b == b * d]

  # generate groups of pairs of fractions that use 8 digits in four fractions
  #                ((a0 / b0),  (c0 / d0),  ((a1 / b1)  (c1 / d1))  
  groupsf = tuple(((gr[0][:2]),(gr[0][2:]), (gr[1][:2]),(gr[1][2:]))
                  for gr in combinations(pairs, 2)
                  if len(set(gr[0]).union(gr[1])) == 8)

  # tuple of set of all fractions encountered
  fra = tuple(set(chain(*groupsf)))  # 'chain(*' 'flattens' groupsf

  # number of occurrences of each fraction over all the groups    
  fc = [sum(f in g for g in groupsf) for f in fra]

  # a fraction that occurs only once in all groups is used by only one group.
  if 1 in fc:
    print(str([f for i, f in enumerate(fra) if fc[i] == 1])[2: -2].replace
          ('), (','; ').replace(', ','/'), 'fractions used once only\n')
    
    for g in groupsf:      
      print(str(g)[2: -2]. replace('),','').replace(', ','/').
            replace(' (',', '), (fra[fc.index(1)] in g) * ('==> not used: ' +
            str(set(range(1, jlo)) - set(chain(*g)))[1: -1]))
    exit()

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

from itertools import count, combinations, chain

from sys import exit

# get a / b; c / d

for jlo in count(9): # jlo + 1: just long enough; minimum = 8

# a / b + c / d = 1 -> a * d + c * b = b * d

# generate pairs of positive fractions adding up to 1

pairs = [(a, b, c, d) for a, b in combinations(range(1, jlo), 2)

for c, d in combinations(range(a + 1, jlo), 2)

if b != c and a * d + c * b == b * d]

# generate groups of pairs of fractions that use 8 digits in four fractions

# ((a0 / b0), (c0 / d0), ((a1 / b1) (c1 / d1))

groupsf = tuple(((gr[0][:2]),(gr[0][2:]), (gr[1][:2]),(gr[1][2:]))

for gr in combinations(pairs, 2)

if len(set(gr[0]).union(gr[1])) == 8)

# tuple of set of all fractions encountered

fra = tuple(set(chain(*groupsf))) # 'chain(*' 'flattens' groupsf

# number of occurrences of each fraction over all the groups

fc = [sum(f in g for g in groupsf) for f in fra]

# a fraction that occurs only once in all groups is used by only one group.

if 1 in fc:

print(str([f for i, f in enumerate(fra) if fc[i] == 1])[2: -2].replace

('), (','; ').replace(', ','/'), 'fractions used once only\n')

for g in groupsf:

print(str(g)[2: -2]. replace('),','').replace(', ','/').

replace(' (',', '), (fra[fc.index(1)] in g) * ('==> not used: ' +

str(set(range(1, jlo)) - set(chain(*g)))[1: -1]))

exit()

Reply

John Z permalink

The ‘exit()’ in line 35 can be replaced by ‘break’ and line 3 can be deleted as the ‘import’ is no longer required, further simplifying the code.

Reply

BRG permalink

Hi John, I liked your use of a conditional within a print statement to prevent printing ( I adopted it when simplifying my reposted code above). The multiple replace statements are innovative but a bit too difficult to ‘decode’ for my liking!

Reply

John Z permalink

With more staightforward print formatting inspired by your ‘fout’ function, Brian. Plus afew more tweaks


from itertools import count, combinations, permutations, chain

# format tuple of 'fractions' for printout; each 'fraction' is a tuple (a, b)
fmt = lambda x: ', '.join(f'{a}/{b}' for a, b in x)

# get a / b; c / d
for jle in count(9): # jle  + 1: just long enough; minimum = 8

  # a / b + c / d = 1 -> a * d + c * b = b * d
  # generate pairs of positive fractions adding up to 1
  pairs = [(a, b, c, d) for a, b, c, d in permutations(range(1, jle), 4)
           if c > a and a * d + c * b == b * d]

  # generate groups of pairs of fractions that use 8 digits in four fractions
  #                ((a0 / b0),  (c0 / d0),  ((a1 / b1),  (c1 / d1))  
  groupsf = tuple(((gr[0][:2]),(gr[0][2:]), (gr[1][:2]),(gr[1][2:]))
                  for gr in combinations(pairs, 2) if len(set(chain(*gr))) == 8)

  # all of the fractions in all of the groups; 'chain(*' 'flattens' groupsf
  afg = tuple(chain(*groupsf))

  # tuple of set of all fractions encountered
  fra = tuple(set(afg))  

  # number of occurrences of each fraction over all the groups    
  fc = tuple(afg.count(f) for f in fra)
  
  # a fraction that occurs only once in all groups is used by only one group.
  if 1 in fc:
    print(fmt(fr for i, fr in enumerate(fra) if fc[i] == 1),
          'fractions used once only\n')
    
    for gr in groupsf:      
      print(fmt(gr), (fra[fc.index(1)] in gr) * ('==> not used: ' +
            str(sorted(set(range(1, jle)) - set(chain(*gr))))[1: -1]))
    break

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

from itertools import count, combinations, permutations, chain

# format tuple of 'fractions' for printout; each 'fraction' is a tuple (a, b)

fmt = lambda x: ', '.join(f'{a}/{b}' for a, b in x)

# get a / b; c / d

for jle in count(9): # jle + 1: just long enough; minimum = 8

# a / b + c / d = 1 -> a * d + c * b = b * d

# generate pairs of positive fractions adding up to 1

pairs = [(a, b, c, d) for a, b, c, d in permutations(range(1, jle), 4)

if c > a and a * d + c * b == b * d]

# generate groups of pairs of fractions that use 8 digits in four fractions

# ((a0 / b0), (c0 / d0), ((a1 / b1), (c1 / d1))

groupsf = tuple(((gr[0][:2]),(gr[0][2:]), (gr[1][:2]),(gr[1][2:]))

for gr in combinations(pairs, 2) if len(set(chain(*gr))) == 8)

# all of the fractions in all of the groups; 'chain(*' 'flattens' groupsf

afg = tuple(chain(*groupsf))

# tuple of set of all fractions encountered

fra = tuple(set(afg))

# number of occurrences of each fraction over all the groups

fc = tuple(afg.count(f) for f in fra)

# a fraction that occurs only once in all groups is used by only one group.

if 1 in fc:

print(fmt(fr for i, fr in enumerate(fra) if fc[i] == 1),

'fractions used once only\n')

for gr in groupsf:

print(fmt(gr), (fra[fc.index(1)] in gr) * ('==> not used: ' +

str(sorted(set(range(1, jle)) - set(chain(*gr))))[1: -1]))

break

Reply

John Z permalink

The definitive version after clean-up to avoid using indexing


from itertools import count, combinations, permutations, chain

# format tuple of 'fractions' for printout; each 'fraction' is a tuple (a, b)
fmt = lambda x: ', '.join(f'{a}/{b}' for a, b in x)

# get a / b; c / d
for jle in count(9): # jle  + 1: just long enough; minimum = 8

  # a / b + c / d = 1 -> a * d + c * b = b * d
  # generate pairs of positive fractions adding up to 1
  pairs = [((a, b), (c, d)) for a, b, c, d in permutations(range(1, jle), 4)
           if d > c > a and a * d + c * b == b * d]

  # generate pairs of pairs of fractions that use 8 digits in four fractions
  groupsf = tuple(p + q
        for p, q in combinations(pairs, 2) if len(set(chain(*(p + q)))) == 8)
 
  # all of the fractions in all of the groups; 'chain(*' 'flattens' groupsf
  afg = tuple(chain(*groupsf))

  # tuple of set of all fractions encountered
  fra = tuple(set(afg))  

  # number of occurrences of each fraction over all the groups    
  fc = tuple(afg.count(f) for f in fra)
  
  # a fraction that occurs only once in all groups is used by only one group.
  if 1 in fc:
    print(fmt(fr for fr, c in zip(fra, fc) if c == 1),
          'fractions used once only\n')
    
    for gr in groupsf:

      print(fmt(gr), (fra[fc.index(1)] in gr) * ('==> not used: ' +
            str(sorted(set(range(1, jle)) - set(chain(*gr))))[1: -1]))
    break

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

from itertools import count, combinations, permutations, chain

# format tuple of 'fractions' for printout; each 'fraction' is a tuple (a, b)

fmt = lambda x: ', '.join(f'{a}/{b}' for a, b in x)

# get a / b; c / d

for jle in count(9): # jle + 1: just long enough; minimum = 8

# a / b + c / d = 1 -> a * d + c * b = b * d

# generate pairs of positive fractions adding up to 1

pairs = [((a, b), (c, d)) for a, b, c, d in permutations(range(1, jle), 4)

if d > c > a and a * d + c * b == b * d]

# generate pairs of pairs of fractions that use 8 digits in four fractions

groupsf = tuple(p + q

for p, q in combinations(pairs, 2) if len(set(chain(*(p + q)))) == 8)

# all of the fractions in all of the groups; 'chain(*' 'flattens' groupsf

afg = tuple(chain(*groupsf))

# tuple of set of all fractions encountered

fra = tuple(set(afg))

# number of occurrences of each fraction over all the groups

fc = tuple(afg.count(f) for f in fra)

# a fraction that occurs only once in all groups is used by only one group.

if 1 in fc:

print(fmt(fr for fr, c in zip(fra, fc) if c == 1),

'fractions used once only\n')

for gr in groupsf:

print(fmt(gr), (fra[fc.index(1)] in gr) * ('==> not used: ' +

str(sorted(set(range(1, jle)) - set(chain(*gr))))[1: -1]))

break

Reply

Sunday Times Teaser 3194 – A Proper Lesson

by Peter Good

Published Friday December 08 2023 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta