Sunday Times Teaser 3162 – Flash Cordon and Ming


from itertools import combinations, product
from collections import defaultdict

# compile a dictionary of (on, off) periods that give valid duty cycles 
ds = {}
for on, off in combinations(range(10, 41), 2):
  dc, r = divmod(100 * on, on + off)
  if not r and dc < 50:
    ds[(on, off)] = dc

# collect solutions for four timers with consecutive on/off periods 
c4n2n2odc = defaultdict(lambda:defaultdict(list))
c4f2f2odc = defaultdict(lambda:defaultdict(list))
for i in range(10, 38):
  con = tuple(i + j for j in range(4))
  for (on, off), dc in ds.items():
    if on in con:
      c4n2n2odc[con][on].append((off, dc))
    if off in con:
      c4f2f2odc[con][off].append((on, dc))

# for sequences with four consecutive on/off periods, find four valid
# off/on sequences that use only two different periods among them 
c4n2of2dc = defaultdict(lambda:defaultdict(list))
c4f2on2dc = defaultdict(lambda:defaultdict(list))
for d_in, d_out in ((c4n2n2odc, c4n2of2dc), (c4f2f2odc, c4f2on2dc)):
  for con, d_odc in d_in.items():
    # consider all combinations of four off/on periods 
    for odc4 in product(*(d_odc[c] for c in con)):
      onf4, dc4 = zip(*odc4)
      # that have two different periods, each twice
      if set(onf4.count(n) for n in set(onf4)) == {2}:
        d_out[con][onf4].append(dc4)

# output solutions for consecutive on and off period timers
for i, d_in in enumerate((c4n2of2dc, c4f2on2dc)):
  for con, d_onf4 in sorted(d_in.items()):
    for nf4, l_dc4 in d_onf4.items():
      for dc4 in l_dc4:
        t = ' on:', 'off:'
        u = f"{t[i]}{con}", f"{t[1 - i]}{nf4}" 
        mn, mx = min(dc4), max(dc4)
        print(f"{u[i]} {u[1 - i]} dc%:{dc4} (min/max): {mn}/{mx}")

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

from collections import defaultdict

# compile a dictionary of (on, off) periods that give valid duty cycles

ds = {}

for on, off in combinations(range(10, 41), 2):

dc, r = divmod(100 * on, on + off)

if not r and dc < 50:

ds[(on, off)] = dc

# collect solutions for four timers with consecutive on/off periods

c4n2n2odc = defaultdict(lambda:defaultdict(list))

c4f2f2odc = defaultdict(lambda:defaultdict(list))

for i in range(10, 38):

con = tuple(i + j for j in range(4))

for (on, off), dc in ds.items():

if on in con:

c4n2n2odc[con][on].append((off, dc))

if off in con:

c4f2f2odc[con][off].append((on, dc))

# for sequences with four consecutive on/off periods, find four valid

# off/on sequences that use only two different periods among them

c4n2of2dc = defaultdict(lambda:defaultdict(list))

c4f2on2dc = defaultdict(lambda:defaultdict(list))

for d_in, d_out in ((c4n2n2odc, c4n2of2dc), (c4f2f2odc, c4f2on2dc)):

for con, d_odc in d_in.items():

# consider all combinations of four off/on periods

for odc4 in product(*(d_odc[c] for c in con)):

onf4, dc4 = zip(*odc4)

# that have two different periods, each twice

if set(onf4.count(n) for n in set(onf4)) == {2}:

d_out[con][onf4].append(dc4)

# output solutions for consecutive on and off period timers

for i, d_in in enumerate((c4n2of2dc, c4f2on2dc)):

for con, d_onf4 in sorted(d_in.items()):

for nf4, l_dc4 in d_onf4.items():

for dc4 in l_dc4:

t = ' on:', 'off:'

u = f"{t[i]}{con}", f"{t[1 - i]}{nf4}"

mn, mx = min(dc4), max(dc4)

print(f"{u[i]} {u[1 - i]} dc%:{dc4} (min/max): {mn}/{mx}")

Reply

Frits permalink


mn = 10  # (deci-seconds)
mx = 40  # (deci-seconds)

# dictionary of possible ON/OFF pairs (deci-seconds)
d = {(a, b): (100 * a) // (a + b) for a in range(mn, mx)
             for b in range(a + 1, mx + 1) if (100 * a) % (a + b) == 0}

# by choosing OFF values higher then ON values duty cycles will be under 50%

# [1] ON = (A, A+1, A+2, A+3) -> OFF = {B, C, D, E}
for A in range(mn, mx - 3):
  for B in range(A + 1, mx + 1):
    if (A, B) not in d: continue
    for C in range(A + 2, mx + 1):
      if (A + 1, C) not in d: continue
      for D in range(A + 3, mx + 1) if B == C else [B, C]:
        if (A + 2, D) not in d or B == C == D: continue
        E = B if C == D else C if B == D else D
        if (A + 3, E) not in d: continue
        duties = sorted(d[(x, y)] for x, y in zip((A, A+1, A+2, A+3),
                                                  (B, C, D, E)))
        print("1st set:", min(duties), "and", max(duties))

# [2] ON = {F, G, H, I}       -> OFF = (J, J+1, J+2, J+3)
for J in range(mn + 1, mx - 2):
  for F in range(mn, J):
    if (F, J) not in d: continue
    for G in range(mn, J + 1):
      if (G, J + 1) not in d: continue
      for H in range(mn, J + 2) if F == G else [F, G]:
        if (H, J + 2) not in d or F == G == H: continue
        I = F if G == H else G if F == H else H
        if (I, J + 3) not in d: continue
        duties = sorted(d[(x, y)] for x, y in zip((F, G, H, I),
                                                  (J, J+1, J+2, J+3)))
        print("2nd set:", min(duties), "and", max(duties))

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

mn = 10 # (deci-seconds)

mx = 40 # (deci-seconds)

# dictionary of possible ON/OFF pairs (deci-seconds)

d = {(a, b): (100 * a) // (a + b) for a in range(mn, mx)

for b in range(a + 1, mx + 1) if (100 * a) % (a + b) == 0}

# by choosing OFF values higher then ON values duty cycles will be under 50%

# [1] ON = (A, A+1, A+2, A+3) -> OFF = {B, C, D, E}

for A in range(mn, mx - 3):

for B in range(A + 1, mx + 1):

if (A, B) not in d: continue

for C in range(A + 2, mx + 1):

if (A + 1, C) not in d: continue

for D in range(A + 3, mx + 1) if B == C else [B, C]:

if (A + 2, D) not in d or B == C == D: continue

E = B if C == D else C if B == D else D

if (A + 3, E) not in d: continue

duties = sorted(d[(x, y)] for x, y in zip((A, A+1, A+2, A+3),

(B, C, D, E)))

print("1st set:", min(duties), "and", max(duties))

# [2] ON = {F, G, H, I} -> OFF = (J, J+1, J+2, J+3)

for J in range(mn + 1, mx - 2):

for F in range(mn, J):

if (F, J) not in d: continue

for G in range(mn, J + 1):

if (G, J + 1) not in d: continue

for H in range(mn, J + 2) if F == G else [F, G]:

if (H, J + 2) not in d or F == G == H: continue

I = F if G == H else G if F == H else H

if (I, J + 3) not in d: continue

duties = sorted(d[(x, y)] for x, y in zip((F, G, H, I),

(J, J+1, J+2, J+3)))

print("2nd set:", min(duties), "and", max(duties))

or more compact


from itertools import product

mn = 10  # (deci-seconds)
mx = 40  # (deci-seconds)

# dictionary of possible ON/OFF pairs (deci-seconds)
d = {a: [b for b in range(a + 1, mx + 1) if (100 * a) % (a + b) == 0] 
         for a in range(mn, mx)}

# by choosing OFF values higher then ON values duty cycles will be under 50%

# [1] ON = (A, A+1, A+2, A+3) -> OFF = {B, C, D, E} 
# [2] ON = {F, G, H, I}       -> OFF = (J, J+1, J+2, J+3)

for run in ["1st", "2nd"]:
  for V in [x for x in d.keys() if x < mx - 3]:
    for p in product(*[d[V + x] for x in range(4)]):
      if len(set(p)) != 2 or p.count(p[0]) != 2: continue
      Vs = (V, V+1, V+2, V+3)
      duties = sorted((100 * x) // (x + y) for x, y in 
                      (zip(Vs , p) if run == "1st" else zip(p, Vs)))
                       
      print(run, "set:", min(duties), "and", max(duties))
      
  if run == "1st":
    # dictionary of possible OFF/ON pairs (deci-seconds)
    d = {n: [k for k, vs in d.items() if n in vs] for n in range(mn, mx + 1)}

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

from itertools import product

mn = 10 # (deci-seconds)

mx = 40 # (deci-seconds)

# dictionary of possible ON/OFF pairs (deci-seconds)

d = {a: [b for b in range(a + 1, mx + 1) if (100 * a) % (a + b) == 0]

for a in range(mn, mx)}

# by choosing OFF values higher then ON values duty cycles will be under 50%

# [1] ON = (A, A+1, A+2, A+3) -> OFF = {B, C, D, E}

# [2] ON = {F, G, H, I} -> OFF = (J, J+1, J+2, J+3)

for run in ["1st", "2nd"]:

for V in [x for x in d.keys() if x < mx - 3]:

for p in product(*[d[V + x] for x in range(4)]):

if len(set(p)) != 2 or p.count(p[0]) != 2: continue

Vs = (V, V+1, V+2, V+3)

duties = sorted((100 * x) // (x + y) for x, y in

(zip(Vs , p) if run == "1st" else zip(p, Vs)))

print(run, "set:", min(duties), "and", max(duties))

if run == "1st":

# dictionary of possible OFF/ON pairs (deci-seconds)

d = {n: [k for k, vs in d.items() if n in vs] for n in range(mn, mx + 1)}

Reply

BRG permalink

Nice work Frits. Here is my version of your second approach.


from itertools import product

# timer period limits in 0.1 second units
mn, mx = 10, 40

# calculate the duty cycle for (on, off) as tuple (integer, remainder) 
dc = lambda on, off: divmod(100 * on, on + off)

# map valid ON periods to lists of OFF periods for which they are valid
# and vice versa (note: <n> < <f> ensures that duty cycles are below 50%)
n2fs = {n: [f for f in range(n + 1, mx + 1) if not dc(n, f)[1]] for n in range(mn, mx + 1)}
f2ns = {f: [n for n in range(mn, f) if not dc(n, f)[1]] for f in range(mn, mx + 1)}

# look for consecutive solutions in both ON and OFF periods 
for d in (n2fs, f2ns):
  
  # the first period in four consecutive periods
  for i in range(mn, mx - 3):
    # the four consecutive periods
    vs = tuple(i + j for j in range(4))
    
    # for these ON/OFF periods, find four valid OFF/ON 
    # periods that have only two values, each twice
    for ps in product(*[d[v] for v in vs]):
      if set(ps.count(p) for p in set(ps)) == {2}:
        if d == f2ns:
          vs, ps = ps, vs          
        dcs = tuple(dc(x, y)[0] for x, y in zip(vs, ps))
        print(f"on: {vs} -> off: {ps} -> dc%: {dcs} min/max: {min(dcs)}/{max(dcs)}")

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

from itertools import product

# timer period limits in 0.1 second units

mn, mx = 10, 40

# calculate the duty cycle for (on, off) as tuple (integer, remainder)

dc = lambda on, off: divmod(100 * on, on + off)

# map valid ON periods to lists of OFF periods for which they are valid

# and vice versa (note: <n> < <f> ensures that duty cycles are below 50%)

n2fs = {n: [f for f in range(n + 1, mx + 1) if not dc(n, f)[1]] for n in range(mn, mx + 1)}

f2ns = {f: [n for n in range(mn, f) if not dc(n, f)[1]] for f in range(mn, mx + 1)}

# look for consecutive solutions in both ON and OFF periods

for d in (n2fs, f2ns):

# the first period in four consecutive periods

for i in range(mn, mx - 3):

# the four consecutive periods

vs = tuple(i + j for j in range(4))

# for these ON/OFF periods, find four valid OFF/ON

# periods that have only two values, each twice

for ps in product(*[d[v] for v in vs]):

if set(ps.count(p) for p in set(ps)) == {2}:

if d == f2ns:

vs, ps = ps, vs

dcs = tuple(dc(x, y)[0] for x, y in zip(vs, ps))

print(f"on: {vs} -> off: {ps} -> dc%: {dcs} min/max: {min(dcs)}/{max(dcs)}")

Reply

Frits permalink

A Python related question.

I hoped in the first example I could set dictionaries d1 and d2, it didn’t work.

Does someone know how to replace a variable LHS without having to fill all the elements?


d1 = dict()
d2 = dict()
for i, d in enumerate((d1, d2), 1):
  d = {i: i * i}

print(d)
print(d1)
print(d2)
'''
{2: 4}
{}
{}
'''
d1 = dict()
d2 = dict()
for i, d in enumerate((d1, d2), 1):
  d[i] = i * i

print(d)
print(d1)
print(d2)
'''
{2: 4}
{1: 1}
{2: 4}

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

d1 = dict()

d2 = dict()

for i, d in enumerate((d1, d2), 1):

d = {i: i * i}

print(d)

print(d1)

print(d2)

'''

{2: 4}

{}

'''

d1 = dict()

d2 = dict()

for i, d in enumerate((d1, d2), 1):

d[i] = i * i

print(d)

print(d1)

print(d2)

'''

{2: 4}

{1: 1}

{2: 4}

Reply

Frits permalink

I have tested alarm’s flash ON and OFF times settable from 1 second to 1 million seconds.

I needed to rewrite my program for this. The original method to calculate the dictionary of possible ON/OFF pairs becomes horribly slow. For 100,000 seconds it took almost 19 hours to calculate the dictionary (approx 32 seconds with the new method). Also the product function is only called for a few numbers in the todo list.

It has been verified up to 100,000 deconds that the new program calculates the same dictionary as the old program

Only one additional solution is found with 1 million seconds (early on):

((36, 37, 38, 39), (114, 111, 114, 111)) 1st set: 24 and 26


from itertools import product
from number_theory import divisors

mn, mx = 10, 1000000  # (deci-seconds)

# add on/off value to dictionaries
def add(d1, d2, k, v):
  if mn <= k < v <= mx:
    if k not in d1 or v not in d1[k]:
      d1[k] |= {v}
      d2[v] |= {k}

divs100 = divisors(100)[1:]

# formula = lambda ON, OFF: (100 * ON) // (ON + OFF)

d_on =  {a: set() for a in range(mn, mx + 1)}
d_off = {a: set() for a in range(mn, mx + 1)}

for a in range(mn, mx):
  # OFF = p * dv - a > a    --> p > (2 * a) / divs100[-1]
  # OFF = p * dv - a <= mx  --> p <= (mx + a) / divs100[0]
  for p in [x for x in divisors(a) if x * 50 > a]:
    for dv in [x for x in divs100 if 2 * a < (p * x) <= mx + a]:
      # formula is (100 / dv) * (a / p) if ON = a and OFF = p * dv - a
      add(d_on, d_off, a, p * dv - a)

# by choosing OFF values higher then ON values duty cycles will be under 50%

# [1] ON = (A, A+1, A+2, A+3) -> OFF = {B, C, D, E}
# [2] ON = {F, G, H, I}       -> OFF = (J, J+1, J+2, J+3)

d = d_on

for run in ["1st", "2nd"]:
  todo = []
  # does a value in nth entry also occur in n+1, n+2 or n+3 entry?
  for n in range(mn, mx - 2):
    if any(v in d[y] for v in d[n] for y in range(n + 1, n + 4)):
      todo.append(n)

  for V in todo:
    Vs = tuple(V + j for j in range(4))
    # find all possible value combinations of 4 consecutive periods
    # V, V+1, V+2 and V+3
    for p in product(*[d[v] for v in Vs]):
      # we need two pairs
      if len(set(p)) != 2 or p.count(p[0]) != 2: continue
      duties = sorted((100 * x) // (x + y) for x, y in
                      (zip(Vs , p) if run == "1st" else zip(p, Vs)))

      print((Vs, p) if run == "1st" else(p, Vs), end=" ")
      print(run, "set:", min(duties), "and", max(duties))

  if run == "1st":
    # dictionary of possible OFF/ON pairs (deci-seconds)
    d = d_off

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

51

52

53

54

55

56

57

58

59

from itertools import product

from number_theory import divisors

mn, mx = 10, 1000000 # (deci-seconds)

# add on/off value to dictionaries

def add(d1, d2, k, v):

if mn <= k < v <= mx:

if k not in d1 or v not in d1[k]:

d1[k] |= {v}

d2[v] |= {k}

divs100 = divisors(100)[1:]

# formula = lambda ON, OFF: (100 * ON) // (ON + OFF)

d_on = {a: set() for a in range(mn, mx + 1)}

d_off = {a: set() for a in range(mn, mx + 1)}

for a in range(mn, mx):

# OFF = p * dv - a > a --> p > (2 * a) / divs100[-1]

# OFF = p * dv - a <= mx --> p <= (mx + a) / divs100[0]

for p in [x for x in divisors(a) if x * 50 > a]:

for dv in [x for x in divs100 if 2 * a < (p * x) <= mx + a]:

# formula is (100 / dv) * (a / p) if ON = a and OFF = p * dv - a

add(d_on, d_off, a, p * dv - a)

# by choosing OFF values higher then ON values duty cycles will be under 50%

# [1] ON = (A, A+1, A+2, A+3) -> OFF = {B, C, D, E}

# [2] ON = {F, G, H, I} -> OFF = (J, J+1, J+2, J+3)

d = d_on

for run in ["1st", "2nd"]:

todo = []

# does a value in nth entry also occur in n+1, n+2 or n+3 entry?

for n in range(mn, mx - 2):

if any(v in d[y] for v in d[n] for y in range(n + 1, n + 4)):

todo.append(n)

for V in todo:

Vs = tuple(V + j for j in range(4))

# find all possible value combinations of 4 consecutive periods

# V, V+1, V+2 and V+3

for p in product(*[d[v] for v in Vs]):

# we need two pairs

if len(set(p)) != 2 or p.count(p[0]) != 2: continue

duties = sorted((100 * x) // (x + y) for x, y in

(zip(Vs , p) if run == "1st" else zip(p, Vs)))

print((Vs, p) if run == "1st" else(p, Vs), end=" ")

print(run, "set:", min(duties), "and", max(duties))

if run == "1st":

# dictionary of possible OFF/ON pairs (deci-seconds)

d = d_off

Reply

BRG permalink

Nice work Frits. I have not gone through the detail of the calculation of the dictionaries but I like the neat use of the any() clause in the final stage. Getting all the work done in C certainly pays off here!

Reply
- Frits permalink
  
  Another idea would be to build the dictionary at every fourth entry (4-8-12-16 …). A 2nd pass would then only have fill in the gaps k+1, k+2, k+3 if one of d[k] and d[k+4] is non empty.
  Most high d_on numbers are empty for a big mx. The d_off dictionary is more evenly distributed.
  
  Jim Randell told me a more efficient way to build the dictionary: for each ON entry check for each percentage 1-49 which whole number OFF entry can occur.
  
  For very big mx values memory is a problem. This can be solved by working with chunks (1.5M entries use approximately 3GB of memory).
  
  Reply

Sunday Times Teaser 3162 – Flash Cordon and Ming

by Stephen Hogg

Published Sunday April 30 2023 (link)

Leave a comment to Frits Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta