Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 8:11 am on 21 January 2021 Permalink | Reply
    Tags: by: Richard Furner   

    Brain-Teaser 683: Powerless 

    From The Sunday Times, 18th August 1974 [link]

    I have here two positive single figure numbers, each less than 9. Neither is a factor of the other. I add the larger number to the smaller.

    Then, to that total I again add the original larger number, and to the new total I again add the original larger number and may, if I like, continue this process indefinitely, but never shall I obtain a total which is a “power” of any whole number whatsoever.

    What are my two numbers?

    This puzzle was included in the book Brain Teasers (1982, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser683]

     
    • Jim Randell 8:11 am on 21 January 2021 Permalink | Reply

      This Python program narrows down the candidate pairs until there is only one left, so if there is a solution this must be it.

      It runs in 49ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, prime_factor, mgcd, unpack, printf
      
      # check a number is _not_ an exact power
      check = lambda n, gcd=unpack(mgcd): gcd(e for (p, e) in prime_factor(n)) == 1
      
      # record totals and pairs of numbers
      ss = list((A + B, A, B) for (A, B) in subsets(irange(2, 8), size=2) if B % A != 0)
      
      # for each total that is not an exact power, add in B to the total
      while len(ss) > 1:
        ss = list((t + B, A, B) for (t, A, B) in ss if check(t))
      
      # output candidate solutions
      for (t, A, B) in ss:
        printf("A={A} B={B}")
      

      Solution: The two numbers are 6 and 8.

      To show that this is indeed a solution we need to show that (6 + 8k) can never be a non trivial exact power.

      To find a counter example, we are looking for for some positive integers k, a, n, where n ≥ 2, such that:

      6 + 8k = a^n
      2(3 + 4k) = a^n

      Clearly the LHS is a multiple of 2. So the RHS must also be a multiple of 2, so let: a = 2b.

      2(3 + 4k) = (2b)^n
      2(3 + 4k) = (2^n)(b^n)
      3 + 4k = 2^(n – 1)(b^n)

      Clearly the RHS is divisible by 2, but the LHS is not divisible by 2.

      So (6 + 8k) can never be an exact power of an integer.


      Most of the pairs drop out fairly quickly, but (3, 7) hangs in until we get to 2187 = 3 + 312×7 = 3^7.

      Leaving (6, 8) as the only remaining candidate.

      Like

      • Jim Randell 11:06 am on 21 January 2021 Permalink | Reply

        Here is a more efficient program that reuses the code I wrote for Enigma 1777 to generate powers in numerical order.

        Then for each power we remove pairs of numbers that can be used to make that power, until there is only a single pair remaining.

        Run: [ @repl.it ]

        from enigma import Primes, irange, subsets, div, printf
        
        # generate powers in numerical order (starting from 2 ** 2)
        def powers():
          base = { 2: 2 }
          power = { 2: 4 }
          maxp = 2
          primes = Primes(32, expandable=1).generate(maxp + 1)
          while True:
            # find the next power
            n = min(power.values())
            yield n
            # what powers are involved
            ps = list(p for (p, v) in power.items() if v == n)
            # increase the powers
            for p in ps:
              base[p] += 1
              power[p] = pow(base[p], p)
            # do we need to add in a new power?
            if maxp in ps:
              maxp = next(primes)
              base[maxp] = 2
              power[maxp] = pow(2, maxp)
        
        # possible pairs of numbers
        ss = list((A, B) for (A, B) in subsets(irange(2, 8), size=2) if B % A != 0)
        
        # consider increasing powers
        for n in powers():
          # remove any pairs that can make n
          ss = list((A, B) for (A, B) in ss if div(n - A, B) is None)
          if len(ss) < 2:
            printf("solution: {ss}")
            break
        

        Like

      • Frits 8:15 pm on 21 January 2021 Permalink | Reply

        Python 3.9 introduced multiple arguments version of math.gcd.

        Without imports.

        def prime_factors(n):
          i = 2
          factors = []
          while i * i <= n:
            if n % i:
              i = 3 if i == 2 else i + 2
            else:
              n //= i
              factors.append(i)
          if n > 1:
            factors.append(n)
            
          return factors
           
        def is_a_power(n):
          pf = prime_factors(n)
          if len(pf) < 2: 
            return False
            
          # occurences of digits  
          oc = {pf.count(x) for x in set(pf)}
          if mult_gcd(list(oc)) == 1:
            return False
          return True
        
        # calculate greatest common divisor of multiple numbers  
        def mult_gcd(li):
          if len(li) == 1:
            return li[0]
        
          for i in range(len(li) - 1):
            a = li[i]
            b = li[i+1]
            while b:
              (a, b) = (b, a % b)
            
            if a == 1: return a
            
            li[i+1] = a
          return a  
        
        # record totals and pairs of numbers
        ss = [(A + B, A, B) for A in range(2, 8) for B in range(A, 9) if B % A != 0]
         
        # for each total that is not an exact power, add in B to the total
        while len(ss) > 1:
          ss = list((t + B, A, B) for (t, A, B) in ss if not is_a_power(t))
          
        # output candidate solutions
        for (t, A, B) in ss:
          print(f"A={A} B={B}")  
        

        Like

  • Jim Randell 8:10 am on 19 January 2021 Permalink | Reply
    Tags:   

    Teaser 2771: All Saints Day 

    From The Sunday Times, 1st November 2015 [link]

    I have written down three even numbers and then consistently replaced digits by letters with different letters used for different digits. In this way I get:

    ALL
    THE
    SAINTS

    In fact multiplying together the first two of these numbers gives the third.

    What number is my SAINT?

    [teaser2771]

     
    • Jim Randell 8:11 am on 19 January 2021 Permalink | Reply

      We can solve this puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      # all numbers are even
      --invalid="1|3|5|7|9,LES"
      
      "ALL * THE = SAINTS"
      
      --answer="SAINT"
      

      Solution: SAINT = 69357.

      Like

    • GeoffR 10:40 am on 19 January 2021 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 0..9:A; var 0..9:L; var 0..9:T; var 0..9:H; 
      var 0..9:E; var 0..9:S; var 0..9:I; var 0..9:N; 
        
      constraint A != 0 /\ T != 0 /\ S != 0;
      constraint all_different ([A,L,T,H,E,S,I,N]);
      
      var 100..999: ALL = 100*A + 11*L;
      var 100..999: THE = 100*T + 10*H + E;
      var 100000..999999: SAINTS = 100001*S + 10000*A + 1000*I + 100*N + 10*T;
      var 10000..99999: SAINT == 10000*S + 1000*A + 100*I + 10*N + T;
      
      constraint ALL mod 2 == 0 /\ THE mod 2 == 0 /\ SAINTS mod 2 == 0;
      constraint ALL * THE == SAINTS;
      
      solve satisfy;
      
      output ["SAINT = " ++ show(SAINT)
      ++"\nSum is " ++ show(ALL) ++ " x " ++ show(THE) ++ " = " ++ show(SAINTS)];
      
      % SAINT = 69357
      % ----------
      % Sum is 988 x 702 = 693576
      % ==========
      
      
      

      Like

  • Jim Randell 4:31 pm on 15 January 2021 Permalink | Reply
    Tags:   

    Teaser 3043: An odd selection 

    From The Sunday Times, 17th January 2021 [link]

    I wrote an odd digit in each of the sixteen cells of a four-by-four grid, with no repeated digit in any row or column, and with each odd digit appearing three or more times overall. Then I could read four four-figure numbers across the grid and four four-figure numbers down. I calculated the average of the four across numbers and the larger average of the four down numbers. Each was a whole number consisting entirely of odd digits, and each used an odd number of different odd digits.

    What were those two averages?

    [teaser3043]

     
    • Jim Randell 4:54 pm on 15 January 2021 Permalink | Reply

      Here’s a quick (to write) constructive solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 687ms.

      Run: [ @repl.it ]

      # suppose the layout is:
      #
      #  A B C D
      #  E F G H
      #  J K L M
      #  N P Q R
      
      SubstitutedExpression
      
      --digits="1,3,5,7,9"
      
      # no repeated digit in any row or column
      --distinct="ABCD,EFGH,JKLM,NPQR,AEJN,BFKP,CGLQ,DHMR"
      
      # don't reorder the expressions (they all use all 16 symbols)
      --reorder=0
      
      # each average uses an odd number of different odd digits
      --code="avg = lambda *ns: ediv(sum(ns), len(ns))"
      --code="odds = {1, 3, 5, 7, 9}"
      --code="check = lambda s: len(s) in odds and odds.issuperset(s)"
      
      # row average = WXYZ
      "avg(ABCD, EFGH, JKLM, NPQR) = WXYZ"
      "check({W, X, Y, Z})"
      
      # col average = STUV, is greater than row average
      "avg(AEJN, BFKP, CGLQ, DHMR) = STUV"
      "STUV > WXYZ"
      "check({S, T, U, V})"
      
      # each digit appears at least 3 times
      --code="count = lambda s: all(s.count(d) > 2 for d in odds)"
      "count([A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q, R])"
      
      # required answer (row avg, col avg)
      --answer="(WXYZ, STUV)"
      
      # [optional] less verbose output
      --template="({ABCD}, {EFGH}, {JKLM}, {NPQR}) -> {WXYZ}, {STUV}"
      --solution=""
      

      Solution: [To Be Revealed]

      Like

    • Frits 12:31 pm on 16 January 2021 Permalink | Reply

      @Jim,

      First time I see a nested lambda.

      I would have used

      “check({W, X, Y, Z})” etc

      and

      –code=”check = lambda s: len(s) in odds and odds.issuperset(s)”

      Like

      • Jim Randell 1:48 pm on 16 January 2021 Permalink | Reply

        @Frits: Yes, that would probably be clearer. I’ll change it.

        I wrote that bit of code before I was using STUV and WXYZ for the averages, so I didn’t already have them broken out into separate digits.


        You can use a lambda expression to implement a sort of where clause in Python:

        <expr1> where (x=<expr2>, y=<expr3>)
        

        can be implemented as:

        (lambda x, y: <expr1>)(<expr2>, <expr3>)
        

        or:

        (lambda x=<expr2>, y=<expr3>: <expr1>)()
        

        Like

    • Jim Randell 8:18 am on 17 January 2021 Permalink | Reply

      And here is a much faster solution that uses some analysis:

      If we start with the four 4-digit numbers that form the rows, we can construct a fifth 4-digit number using the missing digit from each column.

      When these five numbers are added together, each possible digit now appears in each position, so we get:

      T = 1111 × (1 + 3 + 5 + 7 + 9) = 27775

      We can then make possible actual totals by subtracting a 4-digit number composed of different odd digits from T.

      (Each possible digit appears 4 times in our collection of five 4-digit numbers, and in the actual grid we want each digit to appear at least 3 times, so we can only remove at most 1 copy of each digit).

      A viable total must be divisible by 4 to give the average, which itself must consist of an odd number of different odd digits.

      And for any pair of averages the row average must be less than the column average.

      The following program uses this technique to find possible viable pairs of averages. It turns out there is only one viable pair, so this gives us our solution.

      It runs in 44ms.

      Run: [ @repl.it ]

      from enigma import subsets, nconcat, div, nsplit, printf
      
      # allowable digits
      digits = {1, 3, 5, 7, 9}
      
      # generate possible averages for 4x 4-digit numbers
      # with no digit repeated in the same position
      def avgs():
        # if all digits appeared in each position then 4 copies
        # of each digit would be used, and the sum would be ...
        T = 1111 * sum(digits)
      
        # now delete a digit from each position
        # at least 3 copies of each digit must remain, so we can only
        # delete at most one instance of any digit
        for xs in subsets(digits, size=4, select="P"):
          # calculate the average
          avg = div(T - nconcat(xs), 4)
          if avg is None: continue
          # check it uses an odd number of different odd digits
          s = nsplit(avg, fn=set)
          if not(len(s) in digits and digits.issuperset(s)): continue
          # return the average
          yield avg
      
      # choose possible row and column averages
      for (ravg, cavg) in subsets(sorted(avgs()), size=2):
        printf("row avg = {ravg}, col avg = {cavg}")
      

      All that remains is to show that a grid can be constructed using the required averages. Fortunately my first program (above) finds many possible ways to do this.

      Like

      • Frits 3:39 pm on 17 January 2021 Permalink | Reply

        @Jim, Very clever. I also was thinking to start with the missing digits but would probably not have come up with this solution.

        nconcat(xs) modulo 4 must be 3 but this will not help an already very fast program.

        Like

    • GeoffR 12:36 pm on 17 January 2021 Permalink | Reply

      This programme is a bit verbose and an array type solution might well be shorter.
      Hovever, it gets the same answer as Jim’s first solution and runs in about the same time as that solution – about 0.7 sec.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % four-by-four grid
      %  A B C D
      %  E F G H
      %  J K L M
      %  N P Q R
      
      set of int: odds = {1,3,5,7,9};
      
      var 1..9: A; var 1..9: B; var 1..9: C; var 1..9: D; 
      var 1..9: E; var 1..9: F; var 1..9: G; var 1..9: H; 
      var 1..9: J; var 1..9: K; var 1..9: L; var 1..9: M; 
      var 1..9: N; var 1..9: P; var 1..9: Q; var 1..9: R; 
      
      % Row 1 digits
      constraint A in odds /\ B in odds /\ C in odds /\ D in odds;
      constraint all_different ([A,B,C,D]);
      % Row 2 digits
      constraint E in odds /\ F in odds /\ G in odds /\ H in odds;
      constraint all_different ([E,F,G,H]);
      % Row 3 digits
      constraint J in odds /\ K in odds /\ L in odds /\ M in odds;
      constraint all_different ([J,K,L,M]);
      % Row 4 digits
      constraint N in odds /\ P in odds /\ Q in odds /\ R in odds;
      constraint all_different ([N,P,Q,R]);
      
      % Each odd digit appears three or four times in the grid
      % Row 1 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], A, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], A, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], B, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], B, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], C, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], C, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], D, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], D, 4) ;
      
      % Row 2 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], E, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], E, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], F, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], F, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], G, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], G, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], H, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], H, 4) ;
      
      % Row 3 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], J, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], J, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], K, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], K, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], L, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], L, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], M, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], M, 4) ;
      
      % Row 4 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], N, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], N, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], P, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], P, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], Q, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], Q, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], R, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], R, 4) ;
      
      % Down column digits are all different
      constraint all_different([A,E,J,N]);
      constraint all_different([B,F,K,P]);
      constraint all_different([C,G,L,Q]);
      constraint all_different([D,H,M,R]);
      
      % Across numbers in grid
      var 1000..9999:ABCD = 1000*A + 100*B + 10*C + D;
      var 1000..9999:EFGH = 1000*E + 100*F + 10*G + H;
      var 1000..9999:JKLM = 1000*J + 100*K + 10*L + M;
      var 1000..9999:NPQR = 1000*N + 100*P + 10*Q + R;
      
      % Down numbers in grid
      var 1000..9999:AEJN = 1000*A + 100*E + 10*J + N;
      var 1000..9999:BFKP = 1000*B + 100*F + 10*K + P;
      var 1000..9999:CGLQ = 1000*C + 100*G + 10*L + Q;
      var 1000..9999:DHMR = 1000*D + 100*H + 10*M + R;
      
      % Each average (across and down) is a whole number(see description)
      % Average of across numbers 
      var 1000..9999: Av_Across;
      Av_Across = (ABCD + EFGH + JKLM + NPQR) div 4;
      
      % Across average digits (A1, A2, A3, A4)
      var 1..9:A1; var 1..9:A2; var 1..9:A3; var 1..9:A4;
      
      constraint A1 == Av_Across div 1000 /\ A1 mod 2 == 1;
      
      constraint A2 = Av_Across div 100 mod 10 /\ A2 mod 2 == 1;
      
      constraint A3 = Av_Across div 10 mod 10 /\ A3 mod 2 == 1;
      
      constraint A4 = Av_Across mod 10 /\ A4 mod 2 == 1;
      
      % Average of down numbers
      var 1000..9999: Av_Down;
      Av_Down = (AEJN + BFKP + CGLQ + DHMR) div 4;
      
      % Down average digits (D1, D2, D3, D4)
      var 1..9:D1; var 1..9:D2; var 1..9:D3; var 1..9:D4;
      
      constraint D1 == Av_Down div 1000 /\ D1 mod 2 == 1;
      
      constraint D2 = Av_Down div 100 mod 10 /\ D2 mod 2 == 1;
      
      constraint D3 = Av_Down div 10 mod 10 /\ D3 mod 2 == 1;
      
      constraint D4 = Av_Down mod 10 /\ D4 mod 2 == 1;
      
      % Larger average is down average
      constraint Av_Down > Av_Across;
      
      % Each average used an odd number of digits
      constraint card({A1,A2,A3,A4}) mod 2 == 1 
      /\ card({D1,D2,D3,D4}) mod 2 == 1;
      
      solve satisfy;
      
      output ["Average across = " ++ show(Av_Across)
      ++ "\nAverage down = " ++ show(Av_Down) 
      ++ "\nTypical grid:"
      ++ "\n" ++ show(ABCD) ++ "\n" ++ show(EFGH)
      ++ "\n" ++ show(JKLM) ++ "\n" ++ show(NPQR)];
      
      
      

      Like

      • Frits 1:54 pm on 17 January 2021 Permalink | Reply

        @GeoffR,

        You don’t have to the count for each variable A-R, only for 1,3,5,7,9.
        However, the program doesn’t seem to run faster.

        % Each odd digit appears three or four times in the grid
        array[1..5] of int: nbrs = [1,3,5,7,9];
        constraint forall (i in 1..5) (count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
        N,P,Q,R], nbrs[i], 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
        N,P,Q,R], nbrs[i], 4));
        

        Like

    • GeoffR 3:26 pm on 17 January 2021 Permalink | Reply

      @Frits: Good point. That will shorten the code.
      The original code took 240 ms to print the answer, and 667 msec to complete the search on my I7 laptop.

      Like

  • Jim Randell 8:28 am on 14 January 2021 Permalink | Reply
    Tags:   

    Teaser 2770: Football fans 

    From The Sunday Times, 25th October 2015 [link]

    The clubs Barnet, Exeter, Gillingham, Plymouth, Southend and Walsall need to attract more fans. So each has persuaded one of the players Aguero, Ibrahimovic, Lampard, Neymar, Schweinsteiger and Suarez to join them. Also, each club has persuaded one of the managers Conte, Mourinho, Pellegrini, Terim, Van Gaal and Wenger to take control. For each club, if you look at the club, player and manager, then for any two of the three there are just two different letters of the alphabet that occur in both (with the letters possibly occurring more than once).

    In alphabetical order of the teams, list their new players.

    [teaser2770]

     
    • Jim Randell 8:29 am on 14 January 2021 Permalink | Reply

      The [[ grouping ]] functionality was added to the enigma.py library to solve this kind of puzzle.

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import grouping
      
      clubs = ('Barnet', 'Exeter', 'Gillingham', 'Plymouth', 'Southend', 'Walsall')
      players = ('Aguero',  'Ibrahimovic', 'Lampard', 'Neymar', 'Schweinsteiger', 'Suarez')
      managers = ('Conte', 'Mourinho', 'Pellegrini', 'Terim', 'Van Gaal', 'Wenger')
      
      grouping.solve([clubs, players, managers], grouping.share_letters(2))
      

      Solution: The new players are Lampard (Barnet), Suarez (Exeter), Aguero (Gillingham), Neymar (Plymouth), Ibrahimovic (Southend) and Schweinsteiger (Walsall).

      The groups are:

      Barnet, Lampard, Mourinho
      Exeter, Suarez, Wenger
      Gillingham, Aguero, Terim
      Plymouth, Neymar, Conte
      Southend, Ibrahimovic, Pellegrini
      Walsall, Schweinsteiger, Van Gaal

      Like

  • Jim Randell 9:04 am on 12 January 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 660: An efficient type 

    From The Sunday Times, 3rd March 1974 [link]

    My typewriter had the standard keyboard:

    row 1: QWERTYUIOP
    row 2: ASDFGHJKL
    row 3: ZXCVBNM

    until I was persuaded by a time-and-motion expert to have it “improved”. When it came back I found that none of the letters was in its original row, though the number of letters per row remaining unchanged. The expert assured me that, once I got used to the new system, it would save hours.

    I tested it on various words connected with my occupation — I am a licensed victualler — with the following results. The figures in parentheses indicate how many rows I had to use to produce the word:

    BEER (1)
    STOUT (1)
    SHERRY (2)
    WHISKY (3)
    HOCK (2)
    LAGER (2)
    VODKA (2)
    CAMPARI (2)
    CIDER (3)
    FLAGON (2)
    SQUASH (2, but would have been 1 but for a single letter)

    Despite feeling a trifle MUZZY (a word which I was able to type using two rows) I persevered, next essaying CHAMBERTIN.

    Which rows, in order, did I use?

    This puzzle was included in the book Brain Teasers (1982, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser660]

     
    • Jim Randell 9:05 am on 12 January 2021 Permalink | Reply

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle. Although the program generated does not run under the standard CPython interpreter, as it exceeds the limit on statically nested blocks, but it runs fine with the PyPy interpreter, which does not have this limitation, or we can use the recently added [[ --denest ]] option, which generates code that is not as deeply nested, and allows the program to run under the standard Python interpreter.

      The following run file executes in 93ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      --distinct=""
      --digits="1,2,3"
      
      # no letter is in its original row
      --invalid="1,QWERTYUIOP"
      --invalid="2,ASDFGHJKL"
      --invalid="3,ZXCVBNM"
      
      # number of letters per row remained unchanged
      --code="count = lambda s: tuple(s.count(x) for x in (1, 2, 3))"
      "count([A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z]) == (10, 9, 7)"
      
      # rows used for each word
      "len({B, E, E, R}) = 1"
      "len({S, T, O, U, T}) = 1"
      "len({S, H, E, R, R, Y}) = 2"
      "len({W, H, I, S, K, Y}) = 3"
      "len({H, O, C, K}) = 2"
      "len({L, A, G, E, R}) = 2"
      "len({V, O, D, K, A}) = 2"
      "len({C, A, M, P, A, R, I}) = 2"
      "len({C, I, D, E, R}) = 3"
      "len({F, L, A, G, O, N}) = 2"
      "len({S, Q, U, A, S, H}) = 2"
      "len({M, U, Z, Z, Y}) = 2"
      
      # SQUASH is all in one row, except for a single letter
      "1 in multiset([S, Q, U, A, S, H]).values()"
      
      # answer is the rows involved in typing CHAMBERTIN
      --answer="(C, H, A, M, B, E, R, T, I, N)"
      
      # [optional] less verbose output
      --template=""
      
      # [experimental] work around statically nested block limit
      --denest
      

      Solution: The rows involved in typing CHAMBERTIN are: 1, 3, 1, 2, 2, 2, 2, 3, 2, 1.

      The new assignment of rows to keys is:

      Row 1: A C F G J K L N V X
      Row 2: B E I M P R W Y Z
      Row 3: D H O Q S T U

      Although we don’t know what order the keys are in in a row.

      Liked by 1 person

      • Frits 9:54 am on 12 January 2021 Permalink | Reply

        @Jim, repl.it isn’t working for this puzzle

        Like

        • Jim Randell 10:07 am on 12 January 2021 Permalink | Reply

          @Frits: Odd. It works for me if I’m logged in, but not if I try to run the repl anonymously. You have to jump through some hoops to get PyPy running in repl.it, so it is not surprising the end result is a bit fragile.

          Like

          • Frits 10:21 am on 12 January 2021 Permalink | Reply

            Yesterday I updated PyPy. I didn’t realize repl.it depended on it.

            (error: Makefile:52: recipe for target ‘exec_pip’ failed). I’ll try to reinstall Pip under PyPy.

            Have you already used the 64 bit PyPy nightly build?

            Liked by 1 person

            • Jim Randell 10:49 am on 12 January 2021 Permalink | Reply

              @Frits: I don’t think your local installation of PyPy will affect repl.it. I think the problem is running PyPy under repl.it (which is not directly supported). Maybe the template I used to allow you to do this only works for the owner of the repl. (You could try forking it and see if that works for you).

              Like

            • Frits 10:57 am on 12 January 2021 Permalink | Reply

              I have now installed the latest nightly build of PyPy ([PyPy 7.3.4-alpha0 with MSC v.1927 64 bit (AMD64)] on win32).

              It seems to be a recent error in PyPy.

               
              https://foss.heptapod.net/pypy/pypy/-/issues/3342 
              

              “pypy3 -m ensurepip” doesn’t give errors anymore but repl.it still fails.

              Like

        • Jim Randell 2:09 am on 13 January 2021 Permalink | Reply

          @Frits: It should be working now.

          Like

          • Frits 10:53 am on 13 January 2021 Permalink | Reply

            Thanks, it works but it takes approx 30 seconds.
            The program itself takes 39ms.

            Like

      • Frits 10:14 am on 12 January 2021 Permalink | Reply

        @Jim,

        If the S of SQUASH was the single letter in a different row the multiset line would not recognize it (it depends how you interpret “a single letter”).

        Do you know an easy way how I can execute the run file like a normal py file in a Command Prompt (without creating a main each and every time)?

        Like

        • Jim Randell 10:41 am on 12 January 2021 Permalink | Reply

          @Frits: I would have thought if the S was on a different line then typing SQUASH would involve typing 2 letters that were on a different row. But the puzzle text is open to interpretation there. You can just remove one of the S‘s from the list on line 32 to try the other interpretation. Fortunately it doesn’t change the answer.


          On Unix like operating systems the #! line tells the OS how to execute a file, so the file just needs to be executable. (And a while ago I made a command called run, to make it even easier to run such files).

          Otherwise you can just run the command manually. So for this file:

          % pypy -m enigma -r teaser660.run
          

          Or if you haven’t put enigma.py in your $PYTHONPATH, just put them in the same directory (or specify full paths):

          % pypy enigma.py -r teaser660.run
          

          Alternatively you can run it from the Python shell, using the [[ enigma.run() ]] function:

          % pypy
          >>>> from enigma import run
          >>>> run("teaser660.run")
          A=1 B=2 C=1 D=3 E=2 F=1 G=1 H=3 I=2 J=1 K=1 L=1 M=2 N=1 O=3 P=2 Q=3 R=2 S=3 T=3 U=3 V=1 W=2 X=1 Y=2 Z=2
          (C, H, A, M, B, E, R, T, I, N) = (1, 3, 1, 2, 2, 2, 2, 3, 2, 1) [1 solution]
          

          (I have [[ from enigma import * ]] in my .pythonrc file, so code from enigma.py is always available in interactive Python shells, and I don’t need to import them separately).

          Like

          • Frits 11:08 am on 12 January 2021 Permalink | Reply

            @Jim, thanks.

            It doesn’t work if the filetype is py but that’s OK.

            Like

    • Frits 11:05 am on 13 January 2021 Permalink | Reply

      @Jim, 4th run still takes 15 second, it doesn’t matter.

      I am busy with a program to solve the puzzle without using brute force but am kind of stuck….

      Like

    • Jim Randell 6:18 pm on 13 January 2021 Permalink | Reply

      People who use the [[ SubstitutedExpression ]] solver from the enigma.py library might be interested in the experimental version of enigma.py in this repl [ @repl.it ].

      It adds the denest parameter to [[ SubstitutedExpression]] (which available as --denest or -X from the command line or in run files), that changes the way the code is generated to reduce the amount of nesting in the generated code.

      The upshot of this is, if you are using [[ SubstitutedExpression ]] and you run foul of the "SyntaxError: too many statically nested blocks" issue, you can just use [[ SubstitutedExpression(..., denest=1) ]] (or add the --denest or -X parameter to a run file or on the command line).

      The run file given above, with the additional --denest parameter runs in 93ms using CPython 2.7.

      Assuming no problems show up in further testing, this will be rolled out in the next enigma.py update.

      Update: I have rolled this out in the 2021-01-14 version of enigma.py.

      Like

      • Frits 7:05 pm on 13 January 2021 Permalink | Reply

        @Jim Thanks, it works.

        However, –verbose=256 doesn’t seem to work properly anymore.

        Like

        • Frits 10:55 pm on 16 January 2021 Permalink | Reply

          @Jim, I don’t know if this is caused by your latest update.

          from enigma import SubstitutedExpression
          
          # the alphametic puzzle
          p = SubstitutedExpression(
            [
            "WXYZ = 3713",
            ],
            distinct="",
            digits="1,3,5,7,9",
            answer="W, XYZ",
            d2i={},
            verbose=256
            )   
          
          for (_, ans) in p.solve():  
            print(f"{ans}")
          
          

          No solution is given, see generated code:

           
          [SubstitutedExpression: replacing ({WXYZ} = 3713) -> (3713 = {WXYZ})]
          -- [code language="python"] --
          def _substituted_expression_solver1():
            try:
              _x_ = int(3713)
            except NameError:
              raise
            except:
              raise
            if _x_ >= 0:
              _Z = _x_ % 10
              if _Z != 0 and _Z != 1 and _Z != 2 and _Z != 3 and _Z != 4 and _Z != 5 and _Z != 6 and _Z != 7 and _Z != 8 and _Z != 9:
                _x_ //= 10
                _Y = _x_ % 10
                if _Y != 0 and _Y != 1 and _Y != 2 and _Y != 3 and _Y != 4 and _Y != 5 and _Y != 6 and _Y != 7 and _Y != 8 and _Y != 9:
                  _x_ //= 10
                  _X = _x_ % 10
                  if _X != 0 and _X != 1 and _X != 2 and _X != 3 and _X != 4 and _X != 5 and _X != 6 and _X != 7 and _X != 8 and _X != 9:
                    _x_ //= 10
                    _XYZ = _Z + _Y*10 + _X*100
                    _W = _x_ % 10
                    if _W != 0 and _W != 1 and _W != 2 and _W != 3 and _W != 4 and _W != 5 and _W != 6 and _W != 7 and _W != 8 and _W != 9:
                      _x_ //= 10
                      if _x_ == 0:
                        _WXYZ = _Z + _Y*10 + _X*100 + _W*1000
                        _r_ = (_W), (_XYZ)
                        yield ({ 'W': _W, 'X': _X, 'Y': _Y, 'Z': _Z }, _r_)
          

          Like

          • Jim Randell 11:08 pm on 16 January 2021 Permalink | Reply

            @Frits

            The digits parameter should be a collection of permissible digits (not a string), e.g.:

            digits=(1,3,5,7,9)
            

            Like

            • Frits 11:40 pm on 16 January 2021 Permalink | Reply

              Thanks, I copied it from the run version (something which I normally don’t do).

              Like

    • Frits 6:17 pm on 14 January 2021 Permalink | Reply

      Value 0b110 means letter can reside in row 1 or 2.

      from itertools import combinations as comb
      
      letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
      
      orig = ["QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"]
      sol  = ["ACFGJKLNVX", "BEIMPRWYZ", "DHOQSTU"]     # only used for printing
      
      common1 = [set("BEER"), set("STOUT")]
      common2 = [set("LAGER"), set("CAMPARI"), set("SHERRY"), set("HOCK"), 
                 set("VODKA"), set("FLAGON"), set("SQUASH"), set("MUZZY")]
      common3 = [set("WHISKY"), set("CIDER")]           
      
      r = {4 : "1", 2 : "2", 1 : "3"}   # row number
      
      # return 0 if all letters have been uniquely placed in a row
      def unsolved():
        c = 0
        for let in letters:
          c += d[let]  
          if d[let] not in {1, 2, 4}:
            return c
        return 0
        
      # remove <val> from letter <let> 
      def remove(let, val, text = ""):
        if d[let] & val == 0: return   # already removed
        
        d[let] = d[let] & (7 - val)
        if text != "":
          print(f"remove letter {let} from row {r[val]} {text}")
      
      # one row in common
      def cond1(s):
        # skip if all letters in <s> are known 
        if all(d[x] in {1, 2, 4} for x in s): return
        
        # check if letters in <s> have only one common bit
        common = 7
        for x in s:
          common &= d[x]
        
        if common in {1, 2, 4}:
          print(f"place letters {','.join(s)} in row {r[common]} ", end = "")
          print("(as they have to share 1 row)")
          for x in s:
            d[x] = common   # set all letters to the same value
            
      # two rows in common
      def cond2(s):
        known = [x for x in s if d[x] in {1, 2, 4}]
        rows_used = set(d[x] for x in known)
        
        if len(rows_used) == 2:
          # we have solved letters in 2 rows
          # so all letters in <s> have to be in these 2 rows
          twoRows = sum(rows_used)
          missing_row = 7 - twoRows
          
          for x in s:
            if x in known: continue
            # letter can be in either one of the 2 rows?
            if d[x] == twoRows: continue
            
            rows_used = sorted(list(rows_used), reverse=1)
            text = "(letters "+ ",".join(s) +" must occur in rows " 
            text += ", ".join(r[x] for x in rows_used) + ")"
            remove(x, missing_row, text)
       
      # three rows in common
      def cond3(s):
        # for each row check candidates
        for i in [1, 2, 4]:
          li = [x for x in s if d[x] & i]
           
          if len(li) == 1 and d[li[0]] != i:   # one candidate for row i
            print(f"place letter {li[0]} in row {r[i]} (other ", end = "")
            print(f"letters in {','.join(s)} are not possible in row {r[i]})")
            d[li[0]] = i
            return
      
      # check if all letters in a row are known
      def row_full():
        for i, n in enumerate([4, 2, 1]):
          c = 0
          for let in letters:
            if d[let] == n:
              c += 1
          if c == len(orig[i]):
            # row <i> is full so remove <i> from other candidates
            for let in letters:
              if d[let] == n: continue
              remove(let, n, "(already " + str(len(orig[i])) + 
                     " letters have to be in row " + r[n] +")")
      
      # check whether the number of letters in bottom 2 rows exceeds 16        
      def bottom2(c1 ,c2):  
        common_letters = c1 & c2  
        if len(common_letters) < 2: return False
        
        known = [x for x in common_letters if d[x] in {1, 2, 4}]
        rows_used = list(set(d[x] for x in known))
        if len(rows_used) != 1: return False
        
        bot2 = [x for x in common_letters if x != known[0] and 
                x not in orig[0] and   
                d[x] & d[known[0]] == 0] # different row from known
                
        # known[0] in one bottom row and <bot2> in the other bottom row?       
        if len(bot2) > 0:
          # suppose <bot2> is not in top row, so <bot2> and <known> encompass 
          # 2 rows, this means that all letters in c1 and c2 are in bottom 2 rows
          # check if letters in bottom 2 rows exceeds 16 (9 + 7)
          
          # count entries in 2 bottom rows if <bot2> is not in top row
          li = [x for x in letters 
                if x in orig[0] or        # the 10 QWERTYUIOP entries
                ((d[x] & 4) == 0 or       # not in top row
                  x in (c1 | c2) )]       # in c1 or in c2
                  
          max = len(orig[1]) + len(orig[2])
          if len(li) > max:      
            # put QWERTY... up front
            notTop = {x for x in orig[0]} | {x for x in letters if d[x] & 4 == 0}
            # letter <bot2[0]> can not be in bottom 2 rows
            text = "(assuming letter " + bot2[0] + " in bottom 2 rows leads to\n"
            text += "letters " + ",".join(notTop | c1 | c2) 
            text += " in bottom 2 rows (exceeding total of " + str(max) + "))"
            remove(bot2[0], 1, text)
            remove(bot2[0], 2, text)
            return True
            
        return False   
           
      # print rows  
      def report(li):
        print()
        for i, x in enumerate(li): 
          for y in x: 
            if d[y] == (1 << (2 - i)):  # letter is known
              print(f"{y} = {d[y]:<5}", end=" ")
            else:  
              print(f"{y} = {d[y]:#05b}", end=" ")   
          print()
        print()  
      
      
      d = dict()
      # initialize letters 
      for x in letters:
        d[x] = 7
        
      # remove original row number for each letter
      for i, y in enumerate(orig):
        for x in y:
          remove(x, (1 << (2-i)))
       
      prev = 0
      for loop in range(99):
        for x in common1:
          cond1(x)
        for x in common2:
          cond2(x)
        for x in common3:
          cond3(x)
         
        row_full()         # check if all letters in a row are known
         
        nr_unsolved = unsolved()
        if nr_unsolved == 0:   # are we done?
          report(sol)
          
          squash_rows = sorted(d[x] for x in "SQUASH")
          if squash_rows[0] != squash_rows[1] or \
             squash_rows[-1] != squash_rows[-2]:
            print("letters in SQUASH are all in one row but for a single letter")
          break
        
        report(sol)
       
        if nr_unsolved == prev:    # nothing has been solved in this loop 
          # check all combinations of words which reside on 2 rows
          for c1, c2 in comb(common2, 2):
            # check whether the number of letters in bottom 2 rows exceeds 16
            if bottom2(c1, c2): break
        prev = nr_unsolved
      

      Like

    • John Crabtree 1:04 am on 15 January 2021 Permalink | Reply

      Q, W, E, R, T, Y U, I, O, P (10)
      A, S, D, F, G, H, J, K, L (9)
      Z, X, C, V, B, N, M (7)

      BEER (1) B, E, R -> row 2
      STOUT (1) S, T, O, U -> row 3
      only 3 more letters can go to row 3, and from CIDER, at least one must be D or I
      LAGER (2) A, G, L -> row 1
      SQUASH (2*) Q, H -> row 3 (full except for D or I)
      first row P, W, Y – > row 2
      second row F, J, K -> row 1
      HOCK (2) C -> row 1
      CIDER (3) D -> row 3 (full), I -> row 2
      MUZZY (2) M, Z -> row 2 (full)
      third row N, X, V -> row 1

      CHAMBERTIN comes from rows 1, 3, 1, 2, 2, 2, 2, 3, 2, 1

      In this method WHISKY (3), VODKA (2), CAMPARI (2) and FLAGON (2) are redundant

      Like

      • Jim Randell 5:22 am on 15 January 2021 Permalink | Reply

        If I remove the WHISKY, VODKA, CAMPARI, FLAGON conditions in my program it finds 4 possible solutions. So they can’t all be redundant.

        But adding just CAMPARI back in gets us back to a unique solution.

        Like

        • Frits 9:52 am on 15 January 2021 Permalink | Reply

          True, the problem lies with the CIDER (3) D …. deduction.

          Like

          • John Crabtree 3:33 pm on 15 January 2021 Permalink | Reply

            Jim and Frits, thank you. originally I used CAMPARI. In my incorrect CIDER (3) deduction I thought that E and R were in row 1. 🙂

            Like

    • GeoffR 4:13 pm on 15 January 2021 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      set of int: rows = 1..3;
      
      var rows: A; var rows: B; var rows: C; var rows: D;
      var rows: E; var rows: F; var rows: G; var rows: H;
      var rows: I; var rows: J; var rows: K; var rows: L;
      var rows: M; var rows: N; var rows: O; var rows: P;
      var rows: Q; var rows: R; var rows: S; var rows: T;
      var rows: U; var rows: V; var rows: W; var rows: X;
      var rows: Y; var rows: Z; 
      
      % Standard keyboard layout
      % row1 = Q, W, E, R, T, Y, U, I, O, P (10 letters)
      % row2 = A, S, D, F, G, H, J, K, L  (9 letters)
      % row3 = Z, X, C, V, B, N, M  (7 letters)
      
      % 1st row letters must be in a different row
      constraint Q != 1 /\ W != 1 /\ E != 1 /\ R != 1
      /\ T != 1 /\ Y != 1 /\ U != 1 /\ I != 1
      /\ O != 1 /\ P != 1;
      
      % 2nd row letters must be in a different row
      constraint A != 2 /\ S != 2 /\ D != 2 /\ F != 2
      /\ G != 2 /\ H != 2 /\ J != 2 /\ K != 2 /\ L != 2;
      
      % 3rd row letters must be in a different row
      constraint Z != 3 /\ X != 3 /\ C != 3 /\ V != 3
      /\ B != 3 /\ N != 3 /\ M != 3;
      
      % Letter constraints for three new rows
      % New 1st row
      constraint count_eq ( [A,B,C,D,E,F,G,H,I,J,K,L,M,N,
      O,P,Q,R,S,T,U,V,W,X,Y,Z], 1, 10); 
      
      % New 2nd row
      constraint count_eq ( [A,B,C,D,E,F,G,H,I,J,K,L,M,N,
      O,P,Q,R,S,T,U,V,W,X,Y,Z], 2, 9);
      
      % New 3rd row
      constraint count_eq ( [A,B,C,D,E,F,G,H,I,J,K,L,M,N,
      O,P,Q,R,S,T,U,V,W,X,Y,Z], 3, 7); 
      
      % (Rows) I had to use to produce the words
      % BEER(1)
      constraint card({B,E,E,R}) == 1;
      % STOUT (1)
      constraint card ({S,T,O,U,T}) == 1;
      % SHERRY (2)
      constraint card({S,H,E,R,R,Y}) == 2;
      % WHISKY (3)
      constraint card({W,H,I,S,K,Y}) == 3;
      % HOCK (2)
      constraint card({H,O,C,K}) == 2;
      % LAGER (2)
      constraint card( {L,A,G,E,R}) == 2;
      % VODKA (2)
      constraint card({V,O,D,K,A}) == 2;
      % CAMPARI (2)
      constraint card ({C,A,M,P,A,R,I}) == 2;
      % CIDER (3)
      constraint card ({C,I,D,E,R}) == 3;
      % FLAGON (2)
      constraint card({F,L,A,G,O,N}) == 2;
      
      % SQUASH (2, but would have been 1 but for a single letter)
      
      % There are two rows for these letters. 
      % If four letters in 'QUASH' (i.e. missing first S out)
      % have a cardinality of 1, the other letter one must be
      % in a different row on its own. 
      
      constraint 
           (card ({U,A,S,H}) == 1 \/ card ({Q,A,S,H}) == 1
           \/ card ({Q,U,S,H}) == 1 \/ card ({Q,U,A,H}) == 1
           \/ card ({Q,U,A,S}) == 1);
      
      % MUZZY(2 rows)
      constraint card({M,U,Z,Z,Y}) == 2;
      
      output [ "CHAMBERTIN rows are " ++ 
      show([C,H,A,M,B,E,R,T,I,N]) ++ "\n"
      ++ "\nLETTERS : [A, B, C, D, E, F, G, H, I, J, K, L, M]"
      ++ "\nROWS :    " ++ show( [A, B, C, D, E, F, G, H, I, J, K, L, M])
      
      ++ "\nLETTERS : [N, O, P, Q, R, S, T, U, V, W, X, Y, Z]"
      ++ "\nROWS :    " ++ show([N, O, P, Q, R, S, T, U, V, W, X, Y, Z])
      ++ "\n"
      ++ "\n" ++ "New Row 1 is [A,C,F,G,J,K,L,N,V,X] " 
      ++ "\n" ++ "New Row 2 is [B,E,I,M,P,R,W,Y,Z] " 
      ++ "\n" ++ "New Row 3 is [D,H,O,Q,S,T,U]" ];
      
      % CHAMBERTIN rows are [1, 3, 1, 2, 2, 2, 2, 3, 2, 1]
      
      % LETTERS : [A, B, C, D, E, F, G, H, I, J, K, L, M]
      % ROWS      [1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 1, 1, 2]
      % LETTERS : [N, O, P, Q, R, S, T, U, V, W, X, Y, Z]
      % ROWS      [1, 3, 2, 3, 2, 3, 3, 3, 1, 2, 1, 2, 2]
      % New rows follow from above values
      % New Row 1 is [A,C,F,G,J,K,L,N,V,X] 
      % New Row 2 is [B,E,I,M,P,R,W,Y,Z] 
      % New Row 3 is [D,H,O,Q,S,T,U]
      % ----------
      % ==========
      

      Like

  • Jim Randell 10:25 am on 10 January 2021 Permalink | Reply
    Tags: by: P. R. Scott   

    Brain-Teaser 18 

    From The Sunday Times, 2nd July 1961 [link]

    Mr Simpson, who lives at No. 1453 Long Street, is a keen mathematician, and so he was most interested when, [while delivering a letter], his postman mentioned a strange coincidence. If the numbers of [any] two houses to which he made consecutive deliveries were added together, the result came to the number of the next house to which he delivered a letter.

    Mr Simpson asked him which houses he had visited, but the postman could only remember that some of them had single digits.

    To which house did the postman deliver a letter immediately before delivering Mr Simpson’s letter?

    I have changed the wording of this puzzle slightly for clarity.

    [teaser18]

     
    • Jim Randell 10:26 am on 10 January 2021 Permalink | Reply

      I think the wording in this puzzle could have been made a bit clearer. (I have attempted to clarify the wording from the originally published text).

      Evidently, if we write down the numbers of the houses that the postman delivered to, in the order he delivered, we are told that for every house he visited (after the first two houses), the number of that house is the sum of the numbers of the previous two houses delivered to.

      So the numbers of the houses visited form a Fibonacci sequence. And we are told the sequence starts with two single digit numbers, and the number 1453 is in the sequence.

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, fib, printf
      
      # collect solutions
      r = set()
      
      # choose a single digit number to start the sequence
      for (a, b) in subsets(irange(1, 9), size=2, select="P"):
        ns = list()
        for n in fib(a, b):
          if n > 1453: break
          ns.append(n)
          if n == 1453:
            r.add(ns[-2])
            printf("[({a}, {b}) -> {ns}]")
      
      printf("answer = {r}")
      

      Solution: The postman had just come from house number 898.

      There are in fact three possible starting pairs of house numbers:

      (2, 5) → (7, 12, 19, 31, 50, …)
      (3, 2) → (5, 7, 12, 19, 31, 50, …)
      (5, 7) → (12, 19, 31, 50, …)

      but they all end up settling down to generating the same sequence of higher valued house numbers, which does eventually reach 1453:

      …, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, 898, 1453, …

      And the number immediately preceding 1453 is 898.

      As the ratio of consecutive terms in a Fibonacci sequence approaches the value of the Golden Ratio (φ = (1 + √5) / 2), we can immediately calculate a good guess to the answer:

      % python
      >>> phi = 0.5 + sqrt(5, 4)
      >>> 1453 / phi
      898.0033856535972
      

      Like

    • Hugh Casement 2:02 pm on 11 January 2021 Permalink | Reply

      So for every third house visited, the postman crossed the road and back again.
      That’s not the way our posties (male or female) work.
      I think a better puzzle could have put Simpson in an even-numbered house,
      all houses receiving post that day being on the one side of the street.

      That was a good idea to divide by phi. Repeated division, each time rounding to the nearest integer, would get us most of the way to the start of the sequence, though it would be safer after a while to take S(n) = S(n+2) – S(n+1) .
      Did we need to know that it starts with two single-digit terms? 1453/phi has a unique value!

      Like

    • John Crabtree 4:26 pm on 11 January 2021 Permalink | Reply

      Good question, but I think that the answer is yes. Otherwise you can get shorter sequences which reach 1453, ie:
      1453, 897, 556, 341, 215, 126, 89, 37, 52
      1453, 899, 554, 345, 209, 136, 73, 63, 10
      The ratio of successive terms oscillates about phi, and converges quite slowly.

      Like

    • Hugh Casement 10:24 am on 12 January 2021 Permalink | Reply

      Thanks, John. The best approximations to phi are given by the original Fibonacci sequence.
      So if we double each term we get numbers all on the same side of the street.
      But perhaps the puzzle would then be too easy!

      Like

  • Jim Randell 4:56 pm on 8 January 2021 Permalink | Reply
    Tags:   

    Teaser 3042: A question of scale 

    From The Sunday Times, 10th January 2021 [link]

    The modernist music of Skaredahora eschewed traditional scales; instead he built scales up from strict mathematical rules.

    The familiar major scale uses 7 notes chosen from the 12 pitches forming an octave. The notes are in (1) or out of (0) the scale in the pattern 101011010101, which then repeats. Six of these notes have another note exactly 7 steps above (maybe in the next repeat).

    He wanted a different scale using 6 notes from the 12 pitches, with exactly two notes having another note 1 above, and one having another 5 above. Some notes could be involved in these pairings more than once.

    His favourite scale was the one satisfying these rules that came first numerically when written out with 0s & 1s, starting with a 1.

    What was Skaredahora’s favourite scale?

    [teaser3042]

     
    • Jim Randell 5:14 pm on 8 January 2021 Permalink | Reply

      By choosing the excluded pitches we ensure that the scales are generated in the required order, so we only need to find the first scale that satisfies the specified condition.

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, join, printf
      
      # count notes with an interval of k
      interval = lambda ps, k: sum((p + k) % 12 in ps for p in ps)
      
      # choose six notes to exclude
      for xs in subsets(irange(1, 11), size=6):
        ps = tuple(p for p in irange(0, 11) if p not in xs)
      
        # count notes with an interval of 1 and 5
        if not(interval(ps, 1) == 2 and interval(ps, 5) == 1): continue
      
        # the solution is the first value we find
        printf("{s}", s=join("01"[i in ps] for i in irange(0, 11)))
        break
      

      Solution: Skaredahora’s favourite scale is 100010101110.

      We can consider this as a binary representation of the number 2222.

      There are 12 possible scales starting with 1 that have exactly 2 notes with another note 1 above, and exactly one having another note 5 above.

      There are also 12 possible scales starting with 0.

      Like

      • Jim Randell 11:04 am on 9 January 2021 Permalink | Reply

        Here is another solution that treats the scales as numbers represented in binary.

        We can use the [[ bit_permutations() ]] function from the enigma.py library (described here [link]) to generate patterns with 6 bits set in lexicographic order.

        It runs in 45ms overall, and has an internal runtime of 55µs.

        Run: [ @repl.it ]

        from enigma import bit_permutations, dsum2, printf
        
        # count notes with and interval of k
        def interval(n, k):
          m = n << (12 - k) # notes shifted up an interval of k
          v = n | (n << 12) # wrapped values
          return dsum2(v & m) # count the set bits
          
        # choose a bit pattern with 6 of the 12 digits set
        for n in bit_permutations(0b100000011111, 0b111111111111):
          # count notes with an interval of 1 and 5
          if interval(n, 1) == 2 and interval(n, 5) == 1:
            printf("{n} -> {n:012b}")
            # we only need the first value
            break
        

        And here is an “unrolled” version that has an internal runtime of only 24µs [ link ].

        Like

        • Tony Brooke-Taylor 12:54 pm on 9 January 2021 Permalink | Reply

          I tried the binary approach first and was annoyed that this took more than twice as long as your first solution Jim. Having swapped other bits of my algorithm for yours I think the biggest time difference comes from this: your first approach generates trials with only the 6 notes in; my binary approach generates trials with all 12 positions included, and then I have to use an if statement or similar to test only the 6.

          Like

    • Brian Gladman 10:24 am on 9 January 2021 Permalink | Reply

      You get the speed record this week Jim. And you can gain a few percent more by using a set for in place of a tuple. Maybe I am being stupid but it was not immediately obvious to me why lexically sorted zero digit positions produced numerically sorted values.

      Like

      • Jim Randell 11:02 am on 9 January 2021 Permalink | Reply

        @Brian: The lowest number will have the largest leftmost grouping of 0’s. And fortunately combinations are generated in lexicographic order, so that gives us what we want.

        Like

    • Frits 12:22 pm on 9 January 2021 Permalink | Reply

      As the puzzle is not yet fully clear to me I publish a solution which does the same as Jim’s code.
      I tried to use different and probably less efficient code.

      check1 = lambda s: sum(y == (x + 1) % 12 \
                             for (x, y) in list(zip(s, s[1:] + s[:1])))
      
      check5 = lambda s: sum(y - x == 5 or 12 + x - y == 5 
                             for x in s for y in s if y > x)    
      
      # loop backwards as first found solution will have maximal value
      # and thus the 2nd 1 bit will be as far to the right as possible
      for A in range(7, 0, -1):
        for B in range(8, A, -1):
          for C in range(9, B, -1):
            for D in range(10, C, -1):
               for E in range(11, D, -1):
                 if check1([0, A, B, C, D, E]) != 2: continue
                 if check5([0, A, B, C, D, E]) != 1: continue
                 
                 # print solution
                 for k in range(12):
                   print("1", end="") if k in {0, A, B, C, D, E} \
                                      else print("0", end="")
                 print()  
                 exit()
      

      Like

      • Frits 1:00 pm on 9 January 2021 Permalink | Reply

        check5 can also be written as:

        check5 = lambda s: sum(y - x in {5, 7} for x in s for y in s if y > x)
        

        Like

    • Hugh Casement 1:24 pm on 17 January 2021 Permalink | Reply

      Using Basic (oh horror!) I found the same solution as Jim.
      Five other scales can be found by transposing the scale up or down by appropriate numbers of semitones, always with 1 in first position. Each can be reversed to give the other six.

      I think the solution corresponds to C E F# G# A A#.
      Some of those sharps may be better designated as flats of the note above
      (though in an equitempered scale it makes no difference).

      Five semitones apart is the interval known as a fourth; that leaves seven semitones, known as a fifth, to the octave note. Those are generally considered the most harmonious intervals, so a person with normal hearing would want as many as possible in the scale. I bet S’s so-called music sounds even worse than the stuff they play in the supermarket so that we don’t linger over our shopping a moment longer than necessary. But then I’ve always said that the only good composer is a dead composer — preferably one who’s been dead for a couple of centuries.

      Like

  • Jim Randell 8:47 am on 7 January 2021 Permalink | Reply
    Tags:   

    Teaser 2768: In the bag 

    From The Sunday Times, 11th October 2015 [link]

    A set of snooker balls consists of fifteen reds and seven others. From my set I put some [of the balls] into a bag. I calculated that if I picked three balls out of the bag simultaneously at random, then there was a one in a whole-number chance that they would all be red. It was more likely that none of the three would be red – in fact there was also a one in a whole-number chance of this happening.

    How many balls did I put in the bag, and how many of those were red?

    [teaser2768]

     
    • Jim Randell 8:48 am on 7 January 2021 Permalink | Reply

      (See also: Enigma 1551).

      This Python program runs in 47ms.

      Run: [ @repl.it ]

      from itertools import product
      from enigma import Rational, irange, multiply, printf
      
      F = Rational()
      
      # probability of choosing n balls with the same quality from t
      # where q of the t balls have the quality
      def P(n, t, q):
        return multiply(F(q - i, t - i) for i in irange(0, n - 1))
      
      # choose the number of non-red and red balls
      for (n, r) in product(irange(3, 7), irange(3, 15)):
        # there are r red and n non-red balls
        t = r + n
      
        # probability of 3 being red
        p1 = P(3, t, r)
      
        # probability of 3 being non-red
        p2 = P(3, t, n)
      
        # check the conditions
        if p1.numerator == 1 and p2.numerator == 1 and p1 < p2:
          printf("n={n} r={r}, t={t}, p1={p1} p2={p2}")
      

      Solution: There were 10 balls in the bag, 4 of them were red.

      So, the bag contained 6 red balls, and 4 non-red balls.

      When picking three balls, there is a 1/30 chance that they are all red, and a 1/6 chance of them all being non-red.

      Like

    • Frits 6:37 pm on 7 January 2021 Permalink | Reply

      from enigma import gcd
      
      # pick at least one red
      for R in range(1, 7):
        # pick more others than reds
        for T in range(2 * R + 1, 14):
          den = T * (T - 1) * (T - 2)
         
          num = R * (R - 1) * (R - 2) 
          if num != gcd(num, den): continue
         
          num = (T - R) * (T - R - 1) * (T - R - 2)
          if num != gcd(num, den): continue
      
          print(f"{T} balls in the bag, {R} of them were red ")
          
      # 10 balls in the bag, 4 of them were red   
      

      Like

  • Jim Randell 9:29 am on 5 January 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 658: Fiendish device 

    From The Sunday Times, 17th February 1974 [link]

    “Moriarty speaking”, said the voice on the telephone to the Prime Minister. “As you have rejected my demands, a hidden bomb with destroy London. I’m particularly pleased with the detonating device”, he went on, chuckling fiendishly, “it’s designed to give me time to get away before the explosion. There are 60 switches (all turned OFF at the moment) arranged in a ring so that No. 60 is next to No. 1. Whenever any switch changes from ON to OFF it causes the following switch to change over virtually instantaneously (from OFF to ON or vice-versa). As soon as I put down this phone I’ll activate the device. This will automatically put switch No. 1 to ON, then one minute later to OFF, then one minute later still to ON, carrying on in this way after each minute changing switch No. 1 over. As soon as every switch has remained in the OFF position for 10 seconds simultaneously the bomb explodes. So goodbye now — for ever!”

    The Prime Minister turned anxiously to Professor D. Fuse who had been listening in. “When will the activating device set off the bomb?” he asked.

    What was the Professor’s reply?

    This puzzle was included in the book Brain Teasers (1982, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser658]

     
    • Jim Randell 9:29 am on 5 January 2021 Permalink | Reply

      If there were only 3 switches, this what would happen:

      1 2 3
      1 0 0 (0m)
      0 1 0 (1m)
      1 1 0 (2m)
      0 0 1 (3m)
      1 0 1 (4m)
      0 1 1 (5m)
      1 1 1 (6m)
      1 0 0 (7m)

      If we read the switches backwards we see the system of switches operates as a binary counter starting at 001 (= 1) and counting up to 111 (= 7) after 6 minutes.

      After 7 minutes the counter would reach 8 = (000 + overflow), but the switches are arranged in a circle, so the overflow bit feeds into the least significant bit of the counter, so state 8 corresponds to state 1 (= 001) and we are back where we started.

      The counter cycles through the non-zero states 1-7 every 7 minutes, so never achieves state 0 and the bomb will never go off.

      So, with 60 switches we have a 60-bit counter which cycles through the states 1 – (2^60 – 1) every 1152921504606846975 minutes (= 2.2e+12 years), without ever reaching zero.

      Solution: The Professor’s reply is: “Never”.

      Like

  • Jim Randell 8:39 am on 3 January 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 17 

    From The Sunday Times, 25th June 1961 [link]

    In “Amusements in Mathematics” (Nelson, 1917), the late Henry Ernest Dudeney published a magic knight’s tour of the chessboard. That is to say, a knight placed on the square numbered 1 could, by ordinary knight’s moves, visit every square of the board in the ordered numbered, and the numbers themselves in each row and column added up to 260. Yet it was not a fully magic square, for the diagonals did not add to the same constant. After much trying Dudeney came to the conclusion that it is not possible to devise such a square complete with magic diagonals, but, as he said, a pious opinion is not a proof.

    You are invited to try your skill in devising a magic knight’s tour of a square 7×7, with or without magic diagonals.

    Dudeney’s Amusements in Mathematics is available on Project Gutenberg [link].

    [teaser17]

     
    • Jim Randell 8:39 am on 3 January 2021 Permalink | Reply

      A 7×7 chessboard has 49 squares. So if we colour the corners black there will be 25 black squares and only 24 white squares. So the knight will have to start on a black square, and end on a black square. (So it is not possible for a tour to form a closed loop).

      So, 1 is on a black square. The next square in the tour will be a white square (as a knight always moves to a square of the other colour). So, 2 will be on a white square, 3 on a black square, etc. When the tour is complete all the black squares will be odd numbers and all the white squares will be even numbers.

      The rows/columns alternate between (4 black + 3 white) and (4 white + 3 black) squares, but the total of a row/column consisting of (4 black + 3 white) numbers will be (4 odd + 3 even) = even. And the total of a row/column consisting of (4 white + 3 black) will be (4 even + 3 odd) = odd. And we require the sum of each row and column to be the same (it should be T(49) / 7 = 175),

      So it will not be possible for us to make a magic squares as the sums of the values in the rows and columns will necessarily alternate between even and odd, so they can’t all be the same.

      Hence it is not possible to construct a magic knight’s tour on a 7×7 board.

      Like

    • Hugh Casement 1:35 pm on 3 January 2021 Permalink | Reply

      Dudeney was by no means the first: see
      https://www.mayhematics.com/t/1d.htm
      https://mathworld.wolfram.com/MagicTour.html

      It has been proved (by computer) to be impossible on an 8×8 board,
      though there are many semi-magic tours.

      Like

  • Jim Randell 8:27 pm on 31 December 2020 Permalink | Reply
    Tags:   

    Teaser 3041: The best game played in 1966 

    From The Sunday Times, 3rd January 2021 [link]

    For Christmas 1966 I got 200 Montini building blocks; a World Cup Subbuteo set; and a Johnny Seven multi-gun. I built a battleship on the “Wembley pitch” using every block, then launched seven missiles at it from the gun. The best game ever!

    Each missile blasted a different prime number of blocks off the “pitch” (fewer than remained). After each shot, in order, the number of blocks left on the “pitch” was:

    (1) a prime;
    (2) a square;
    (3) a cube;
    (4) (a square greater than 1) times a prime;
    (5) (a cube greater than 1) times a prime;
    (6) none of the aforementioned; and
    (7) a prime.

    The above would still be valid if the numbers blasted off by the sixth and seventh shots were swapped [with each other].

    How many blocks remained on the “pitch” after the seventh shot?

    [teaser3041]

     
    • Jim Randell 10:14 pm on 31 December 2020 Permalink | Reply

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import Primes, irange, inf, is_square, is_cube, printf
      
      # primes less than 200
      primes = Primes(200)
      
      # test x is of the form (a^k)p where p is prime and a >= m
      def test(x, k, m=2):
        for a in irange(m, inf):
          (p, r) = divmod(x, a ** k)
          if p < 2: return False
          if r == 0 and primes.is_prime(p): return True
      
      # tests
      t1 = primes.is_prime # a prime
      t2 = is_square # a square
      t3 = is_cube # a cube
      t4 = lambda x: test(x, 2) # (a square) times (a prime)
      t5 = lambda x: test(x, 3) # (a cube) times (a prime)
      t6 = lambda x: not any(f(x) for f in (t1, t2, t3, t4, t5)) # none of the above
      t7 = t1 # a prime
      tests = (t1, t2, t3, t4, t5, t6, t7)
      
      # remove different prime amounts from <t>, remaining amounts satisfying <tests>
      # return the amounts removed
      def solve(t, tests, ns=[]):
        # are we done?
        if not tests:
          yield ns
        else:
          # remove less than half of t
          for n in primes:
            t_ = t - n
            if not(n < t_): break
            if n not in ns and tests[0](t_):
              yield from solve(t_, tests[1:], ns + [n])
      
      # find solutions
      for ns in solve(200, tests):
        r = 200 - sum(ns)
        # where the tests still work with the last 2 amounts swapped
        if t6(r + ns[-2]):
          printf("remaining={r} {ns}")
      

      Solution: There were 47 blocks remaining on the pitch after the seventh shot.

      There are six possible sequences that satisfy all the conditions of the puzzle, and they can be grouped into three pairs that give the same total number of blocks remaining:

      [3, 53, 19, 13, 31, 11, 29] → 41
      [3, 53, 19, 13, 31, 23, 17] → 41

      [3, 53, 19, 13, 31, 11, 23] → 47
      [3, 53, 19, 13, 31, 23, 11] → 47

      [3, 53, 19, 13, 31, 11, 17] → 53
      [3, 53, 19, 13, 31, 23, 5] → 53

      Each sequence is the same for the first 5 shots, and only the middle pair consists of sequences where the final two amounts are swapped over, so this gives our solution.

      Like

    • Robert Brown 12:54 pm on 1 January 2021 Permalink | Reply

      Since the sixth & seventh shots can be interchanged, they both take a prime value which doesn’t affect the rest of the puzzle. So I can’t see how we can decide which is which. Surely it would have been better if he had asked for the number of bricks remaining after the fifth shot?

      Like

      • Jim Randell 1:14 pm on 1 January 2021 Permalink | Reply

        @Robert: For any set of numbers chosen for the seven shots the number of blocks remaining after they have all been taken does not depend on the order they were taken in. So there is a unique answer for the number of blocks remaining, even though we don’t know what order the last two shots were taken in.

        Like

    • Robert Brown 6:10 pm on 1 January 2021 Permalink | Reply

      Thanks for that Jim. I realised after I posted my comment that I had misunderstood what the teaser said. The 6th shot prime must be chosen so that the balance remaining isn’t a square, a cube, a square times a prime or a cube times a prime. This gives 3 options, leading to a selection of possible 7th shot values.

      Liked by 1 person

    • Frits 6:11 pm on 2 January 2021 Permalink | Reply

      Things are not necessarily efficient (I didn’t want to copy Jim’s test function or the approach at PuzzlingInPython).

      @Jim, I consider ” (fewer than remained)” also as part of “above would still be valid”, see last 2 checks.

      from enigma import SubstitutedExpression, is_prime, is_square, is_cube, \
                         seq_all_different
      
      # is number product of a prime and a square (k=2) / cube (k=3)
      def is_primeprod(n, k):
        # primes up to (200 / 2^2)
        P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
        if k == 3: # primes up to (200 / 2^3)
          P = P[:9]
        for p in P:
          (d, r) = divmod(n, p)
          if d < 2: return False
          if r == 0 and ((k == 2 and is_square(d)) or (k == 3 and is_cube(d))): 
            return True
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        "is_prime(200 - AB)", 
      
        "is_square(200 - AB - CD)", 
        # fewer than remained
        "2 * CD < 200 - AB",
      
        "is_cube(200 - AB - CD - EF)", 
        # fewer than remained
        "2 * EF < 200 - AB - CD",
      
        # (a square greater than 1) times a prime
        "is_primeprod(200 - AB - CD - EF - GH, 2)", 
        # fewer than remained
        "2 * GH < 200 - AB - CD - EF",
        
        # (a cube greater than 1) times a prime
        "is_primeprod(200 - AB - CD - EF - GH - IJ, 3)", 
        # fewer than remained
        "2 * IJ <  200 - AB - CD - EF - GH",
        
        # none of the aforementioned
        "not is_prime(200 - AB - CD - EF - GH - IJ - KL)",
        "not is_cube(200 - AB - CD - EF - GH - IJ - KL)",
        "not is_square(200 - AB - CD - EF - GH - IJ - KL)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - KL, 2)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - KL, 3)",
        # fewer than remained
        "2 * KL < 200 - AB - CD - EF - GH - IJ", 
        
        
        "is_prime(200 - AB - CD - EF - GH - IJ - KL - MN)",
        # fewer than remained
        "2 * MN < 200 - AB - CD - EF - GH - IJ - KL",
        
        "seq_all_different([AB, CD, EF, GH, IJ, KL, MN])",
        "all(is_prime(x) for x in [AB, CD, EF, GH, IJ, KL, MN])",
      
        
        # rules are still valid if the numbers blasted off by the sixth and 
        # seventh shots were swapped 
        "not is_prime(200 - AB - CD - EF - GH - IJ - MN)",
        "not is_cube(200 - AB - CD - EF - GH - IJ - MN)",
        "not is_square(200 - AB - CD - EF - GH - IJ - MN)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - MN, 2)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - MN, 3)",
        
        # fewer than remained (also after swapping)
        "2 * MN < 200 - AB - CD - EF - GH - IJ", 
        "2 * KL < 200 - AB - CD - EF - GH - IJ - MN", 
        ],
        answer="(AB, CD, EF, GH, IJ, KL, MN), \
                (200 - AB, \
                 200 - AB - CD, \
                 200 - AB - CD - EF, \
                 200 - AB - CD - EF - GH, \
                 200 - AB - CD - EF - GH - IJ, \
                 200 - AB - CD - EF - GH - IJ - KL, \
                 200 - AB - CD - EF - GH - IJ - KL - MN)",
        distinct="",
        d2i={},
        env=dict(is_primeprod=is_primeprod),
        verbose=0)   
      
      for (_, ans) in p.solve():  
        print(f"{ans}")
      

      Like

      • Jim Randell 6:58 pm on 2 January 2021 Permalink | Reply

        @Frits: You’re right. Here is a more rigorous implementation of my original approach.

        We collect all possible solutions, and look for a pair that are the same except the final two values are swapped over:

        from enigma import Primes, irange, inf, is_square, is_cube, group, printf
        
        # primes less than 200
        primes = Primes(200)
        
        # test x is of the form (a^k)p where p is prime and a >= m
        def test(x, k, m=2):
          for a in irange(m, inf):
            (p, r) = divmod(x, a ** k)
            if p < 2: return False
            if r == 0 and primes.is_prime(p): return True
        
        # tests
        t1 = primes.is_prime # a prime
        t2 = is_square # a square
        t3 = is_cube # a cube
        t4 = lambda x: test(x, 2) # (a square) times (a prime)
        t5 = lambda x: test(x, 3) # (a cube) times (a prime)
        t6 = lambda x: not any(f(x) for f in (t1, t2, t3, t4, t5)) # none of the above
        tests = (t1, t2, t3, t4, t5, t6, t1)
        
        # remove different prime amounts from <t>, remaining amounts satisfying <tests>
        # return the amounts removed
        def solve(t, tests, ns=[]):
          # are we done?
          if not tests:
            yield ns
          else:
            # remove less than half of t
            for n in primes:
              t_ = t - n
              if not(n < t_): break
              if n not in ns and tests[0](t_):
                yield from solve(t_, tests[1:], ns + [n])
        
        # collect solutions, with the final two values ordered
        d = group(solve(200, tests), by=(lambda x: tuple(x[:5] + sorted(x[5:]))))
        # find a pair of solution values
        for (k, vs) in d.items():
          if len(vs) > 1:
            printf("remaining={r}; {vs}", r=200 - sum(k))
        

        Like

      • Frits 12:01 pm on 8 January 2021 Permalink | Reply

        Coding the seq_all_different and is_prime clauses for each missile separately will bring the run time down from 1 second to 47ms.

        Like

    • Tony Brooke-Taylor 9:52 am on 7 January 2021 Permalink | Reply

      My original solution looked very messy but I was seeking to reduce the amount of looping over primes by starting in the middle – noting that there are only 4 cubes below 200, I wanted to generate and test cubes rather than primes initially.

      Being a Python novice, I am learning a lot from reviewing solutions on here (Jim’s or others’), so once I had solved the puzzle I came to look at this thread. Then as a test I tried to implement my algorithm using as much of Jim’s code as possible. I have not researched properly the relative time cost of looping through primes and testing other properties, as opposed to engineering the other properties and then testing if prime (which involves at least a look-up which itself must require looping). However, by starting with the square/cube pairs implied by tests 2 and 3, then working back to 200 in one direction and forwards using Jim’s code in the other, I reduced the average run-time on my machine from 0.90ms to 0.38ms.

      I won’t post all my code because I am using a few long-hand functions instead of the Enigma library. However, I think the following chunk should make it clear how I adapted Jim’s code to give a list of possible solutions from which to find the pair with interchangeable d5 and d6:

      convert "power" test into powers generator
      generates (a^k) up to and including x, from a minimum root m
      
      
      
      def powers(x,k,m=2):
          for a in range(m, int(x**(1/k))+1):
              yield a**k
      
      ...
      
      #Control program
      #Store long-list of primes
      n0=200
      primes = list(Primes(n0))
      
      #Start with all possible pairs of squares and cubes separated by a prime
      nsd = {}
      for n3 in powers(n0,3,3):# N3>cube of 2 since we need at least one cube for N5
          for n2 in powers(n0,2):
              d3 = n2 - n3
              if d3>n2/2:continue
              elif is_prime(d3):
                  nsd[(n2,n3)]=d3
      
      #For each of these pairs, run back up to n0 to find possible prime steps
      ns = []
      for n2, n3 in nsd.keys():
          for d2 in primes:
              if d2 > min((n0-n2),n2):break#we don't know n1 yet, so cap d2 as if d1=0
              else:
                  n1=n2+d2
                  d1=n0-n1
                  d3=nsd[(n2,n3)]
                  if is_prime(n1) and is_prime(d1) and len(set([d1,d2,d3]))==3:
      
      #And then run downwards to apply the remaining tests (per JR approach)                 
                      for solution in solve((n0-sum([d1,d2,d3])), (t4, t5, t6, t1)
      , [d1,d2,d3]):
                          ns.append(solution)
      

      Like

      • Frits 12:53 pm on 8 January 2021 Permalink | Reply

        @Tony,

        Interesting idea.

        I am not coding in Python for a very long time.
        I like to use list comprehensions so I would have used something like this:

        nsd1 = [(s2, c3) for s in range(2, 15) for c in range(2, 6) 
                if is_prime(d := (s2 := s*s) - (c3 := c*c*c)) and 2 * d < s2]
        

        As you can calculate d3 from n2 and n3 you don’t need to use a dictionary to store the squares and cubes.

        Like

    • GeoffR 8:21 am on 8 January 2021 Permalink | Reply

      My approach was to simulate the game, finding the blocks left (B1..B7) after firing the missiles in sequence (M1..M7).

      The programme produces outputs for the number of blocks remaining as 53, 41 and 47.

      However, only an output of 47 blocks remaining , after the 7th missile, allows the 6th and 7th missiles (shots) to be interchanged, so this is the answer to the teaser.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      int:blocks = 200;
       
      % list of missiles in sequence fired
      var 2..79:M1; var 2..79:M2; var 2..79:M3; var 2..79:M4; 
      var 2..79:M5; var 2..79:M6; var 2..79:M7;
      
      % all missiles are different (and prime numbers)
      constraint all_different ([M1, M2, M3, M4, M5, M6, M7]);
      
      % list of blocks remaining after each missile (shot)
      var 2..197:B1; var 2..197:B2; var 2..197:B3; var 2..197:B4;
      var 2..197:B5; var 2..197:B6; var 2..197:B7;
      
      % set of primes less than 200
      set of int :primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
      31, 37, 41, 43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
      101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
      163, 167, 173, 179, 181, 191, 193, 197, 199};
      
      % sets of squares and cubes less than 200
      set of int: cubes = { x * x * x | x in 2..5 };
      set of int: squares = { x * x | x in 2..14 };
      
      % set of all integers between 1 and 200
      set of int: all_int = {x | x in 1..200};
      
      % set of squares times primes
      set of int: sq_x_pr = {i * j | i in squares, 
      j in primes where i * j < 200};
      
      % set of cubes times primes
      set of int: cb_x_pr = {i * j | i in cubes, 
      j in primes where i * j < 200};
      
      % set of integers, none of the aforementioned
      set of int : none_of_afore = all_int diff primes 
      diff cubes diff squares diff sq_x_pr diff cb_x_pr;
      
      % 1st Missile M1 leaves Blocks B1, displacing M1 blocks 
      constraint B1 == blocks - M1 /\  M1 < B1 /\ M1 in  primes
      /\ B1 in primes;
      
      % 2nd Missile M2 leaves Blocks B2 
      constraint B2 = blocks - (M1 + M2) /\ M2 < B2 
      /\ M2 in primes /\ B2 in squares;
      
      % 3rd Missile M3 leaves Blocks B3 
      constraint B3 = blocks - (M1 + M2 + M3) /\ 
      M3 < B3 /\ M3 in primes /\ B3 in cubes;
      
      % 4th Missile M4 leaves Blocks B4 
      constraint B4 = blocks - (M1 + M2 + M3 + M4) 
      /\ M4 < B4 /\ M4 in primes /\ B4 in sq_x_pr;
      
      % 5th Missile M5 leaves Blocks B5 
      constraint B5 = blocks - (M1 + M2 + M3 + M4 + M5)
       /\ M5 < B5 /\ M5 in primes /\ B5 in cb_x_pr;
      
      % 6th Missile M6 leaves Blocks B6 
      constraint B6 = blocks - (M1 + M2 + M3 + M4 + M5 + M6)
       /\ M6 < B6 /\ M6 in primes /\ B6 in none_of_afore;
      
      % 7th Missile M7 leaves Blocks B7 
      constraint B7 = blocks - (M1 + M2 + M3 + M4 + M5 + M6 + M7)
      /\ M7 < B7 /\ M7 in primes /\ B7 in primes;
      
      solve satisfy;
      
      output [" Missile sequence: " ++ show(M1),", ", show(M2),
      ", ", show(M3),", ", show(M4),", ", show(M5),", ", show(M6),
      ", ", show(M7) 
      ++ "\n" ++ " Blocks left: " ++ show(B1),", ", show(B2),
      ", ", show(B3),", ", show(B4),", ", show(B5),", ", show(B6),
      ", ", show(B7) ];
      
      %  Missile sequence: 3, 53, 19, 13, 31, 11, 17
      %  Blocks left: 197, 144, 125, 112, 81, 70, 53
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 11, 23 
      %  Blocks left: 197, 144, 125, 112, 81, 70, 47  <<< ans
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 11, 29
      %  Blocks left: 197, 144, 125, 112, 81, 70, 41
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 23, 5
      %  Blocks left: 197, 144, 125, 112, 81, 58, 53
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 23, 11 
      %  Blocks left: 197, 144, 125, 112, 81, 58, 47  <<< ans
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 23, 17
      %  Blocks left: 197, 144, 125, 112, 81, 58, 41
      % ----------
      % ==========
      
      
      
      

      Like

      • Frits 11:13 am on 8 January 2021 Permalink | Reply

        Adding this will only print the 2 solutions

        var 2..197:B6A;
        
        % 7th Missile M7 can be swapped with 6th Missile M6
        constraint B6A = blocks - (M1 + M2 + M3 + M4 + M5 + M7)
         /\ M7 < B6A /\ B6A in none_of_afore;
        

        Like

      • Frits 12:09 pm on 8 January 2021 Permalink | Reply

        @GeoffR, I am not sure if the limit of 79 for missiles is correct.

        The minimum for 6 missiles is 41 (2+3+5+7+11+13) –> (200 – 41) / 2 = 79.5 ???

        I don’t immediately see why the first missile can’t be 83.

        Like

    • Geoff 12:30 pm on 10 January 2021 Permalink | Reply

      I don’t understand. What do the words in brackets mean – (fewer than remained) – I took this to mean that each of the 7 prime numbers where smaller than the number of blocks left on the pitch. So if 53 are kicked off on the second go, don’t we need more than 53 left on the pitch? Or does it mean fewer than remained after that particular shot?

      Like

      • Jim Randell 12:40 pm on 10 January 2021 Permalink | Reply

        @Geoff: I took it to mean that at each stage the number of blocks knocked off is less than the number of blocks remaining after that shot. (So the number knocked off is less than half the number of blocks available).

        So at the beginning there are 200 blocks available, so in the first shot we can knock off between 1 and 99.

        If we knock off 3 with the first shot, there are 197 blocks remaining, so the second shot can knock off between 1 and 98.

        If we knock off 53 with the second shot, there are 144 blocks remaining, so the third shot can knock off between 1 and 71.

        And so on, until all 7 shots are taken.

        Like

  • Jim Randell 8:37 am on 31 December 2020 Permalink | Reply
    Tags: ,   

    Teaser 1995: Pyramid selling 

    From The Sunday Times, 10th December 2000 [link]

    At the fruit stall in our local market the trader built a stack of oranges using the contents of some complete boxes, each containing the same number of oranges.

    He first laid out one box of oranges in a rectangle to form the base of a stack. He then added more oranges layer by layer from the contents of the other boxes. Each layer was a rectangle one orange shorter and narrower than the layer beneath it.

    The top layer should have consisted of a single row of oranges but the trader was one orange short of being able to complete the stack.

    How many oranges were there in each box?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    This completes the 72 puzzles from the 2002 Brainteasers book. In the New Year I will start posting puzzles from the 1982 book “The Sunday Times book of Brain Teasers (50 hard (very hard) master problems)”, compiled by Victor Bryant and Ronald Postill. It is a selection of Teaser puzzles originally published in The Sunday Times between January 1974 and December 1979.

    Happy New Year from S2T2!

    [teaser1995]

     
    • Jim Randell 8:38 am on 31 December 2020 Permalink | Reply

      See: Enigma 1086.

      This Python program runs in 43ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, div, printf
      
      # calculate stacking numbers n <= m
      stack = lambda n, m: sum((n - i) * (m - i) for i in irange(n))
      # or: n * (n + 1) * (3 * m - n + 1) // 6
      
      # generate (n, m) pairs where 1 < n < m
      def pairs():
        for t in irange(5, inf):
          for n in irange(2, (t - 1) // 2):
            yield (n, t - n)
      
      # consider n, m values
      for (n, m) in pairs():
        # number of oranges in a box
        b = n * m
        # number of stacked oranges
        s = stack(n, m) - 1
        # number of boxes required
        k = div(s, b)
        if k is not None:
          printf("n={n} m={m} b={b} s={s} k={k}")
          break
      

      Solution: There were 72 oranges in each box.

      3 boxes were used, making a total of 216 oranges.

      The base layer was 6 × 12 layer, using 72 oranges (= 1 box).

      The remaining layers:

      5 × 11 = 55
      4 × 10 = 40
      3 × 9 = 27
      2 × 8 = 16
      1 × 6 = 6 (the final layer is 1 orange short)

      use 55+40+27+16+6 = 144 oranges (= 2 boxes)


      Manually:

      To complete a structure starting with a base that is n × m where n ≤ m, the number of oranges required is:

      S(n, m) = n(n + 1)(3m – n + 1)/6

      And if we use k boxes we have:

      n(n + 1)(3m – n + 1) / 6 = kmn + 1
      n(n + 1)(3m – n + 1) = 6kmn + 6

      n divides the LHS, so n must divide the RHS, hence n divides 6.

      So: n = 1, 2, 3, 6.

      If n = 6:

      m = 12 / (7 – 2k)

      so: m = 12, k = 3.

      If n = 3:

      m = 5 / (6 – 3k)

      doesn’t work.

      If n = 2:

      m = 2 / (3 – 2k)

      doesn’t work.

      If n = 1:

      m = 1 / (1 – k)

      doesn’t work.

      So: n = 6, m = 12, k = 3 is the only viable solution.

      Like

  • Jim Randell 8:46 am on 29 December 2020 Permalink | Reply
    Tags:   

    Teaser 2508 

    From The Sunday Times, 17th October 2010 [link]

    An Austin was pootling along a country lane at 30mph; behind were a Bentley doing 40mph and a Cortina doing 50mph. The Bentley and the Cortina braked simultaneously, decelerating at constant rates, while the Austin carried on at the same speed. The Bentley just avoided hitting the rear of the Austin, [while, at the same time,] the Cortina just avoided a collision with the Bentley. The Bentley and the Cortina continued to decelerate at the same rates, and stopped with a 45yd gap between them.

    What was the gap between the Bentley and the Cortina at the moment they started to brake?

    The wording in this puzzle has been modified from the published version for clarification.

    [teaser2508]

     
    • Jim Randell 8:46 am on 29 December 2020 Permalink | Reply

      I am assuming that at the time of the “almost collision” the separation between A, B and B, C can be considered to be zero. (And so we can consider the cars to be points, that coincide at the moment of “almost collision”).

      This puzzle can be solved graphically, without the need to resort to equations of motion (although you can solve it that way too).

      If we plot the velocities of the Austin (red), the Bentley (green), and the Cortina (blue) against time we get a graph like this:

      Where red carries on at a steady 30mph, green starts at 40mph and decelerates steadily to 0mph (BB’), and blue starts at 50mph and decelerates steadily to 0mph (CC’).

      At X, all their speeds are 30mph, and this is the point at which the separations between the cars are zero (the almost collision).

      The area under the line XB’ gives the distance travelled by green after the almost collision, and the area under the line XA’ gives the distance travelled by blue after the almost collision.

      And the difference between these distances corresponds to their final separation:

      area(XUB’) – area(XUC’) = 45 yards
      (45 – 45/2) units = 45 yards
      1 unit = 2 yards

      Similarly we can calculate the difference between the areas under the lines CX and BX to get the separation of green and blue at the time they started braking:

      area(CAX) – area(BAX) = (10 – 5) units
      = 10 yards

      Solution: The Bentley and the Cortina were 10 yards apart at the time they started braking.

      Like

  • Jim Randell 8:27 am on 27 December 2020 Permalink | Reply
    Tags:   

    Teaser 1991: Numismathematics 

    From The Sunday Times, 12th November 2000 [link]

    I have three circular medallions that I keep in a rectangular box, as shown. The smallest (of radius 4cm) touches one side of the box, the middle-sized one (of radius 9cm) touches two sides of the blox, the largest touches three sides of the box, and each medallion touches both the others.

    What is the radius of the largest medallion?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1991]

     
    • Jim Randell 8:27 am on 27 December 2020 Permalink | Reply

      Here’s a manual solution:

      Labelling the centres of the medallions (smallest to largest) are A, B, C, and the corresponding radii are 4, 9, R.

      Then the horizontal displacement between B and C, h(B, C), is given by:

      h(B, C)² = (R + 9)² – (R – 9)²
      h(B, C)² = 36R
      h(B, C) = 6r, where: r = √R

      And the horizontal displacement between A and C, h(A, C), is given by:

      h(A, C)² = (R + 4)² – (R – 4)²
      h(A, C)² = 16R
      h(A, C) = 4r

      And the difference in these displacements is the horizontal displacement between A and B, h(A, B):

      h(A, B) = h(B, C) – h(A, C)
      h(A, B) = 2r
      h(A, B)² = 4r² = 4R

      The vertical displacement between A and B, v(A, B), is given by:

      v(A, B) = 2R – 13

      Then we have:

      h(A, B)² + v(A, B)² = 13²
      4R + (2R – 13)² = 13²
      4R + 4R² – 52R = 0
      4R(R – 12) = 0

      So R = 12.

      Solution: The radius of the largest medallion is 12cm.

      Like

  • Jim Randell 10:31 pm on 23 December 2020 Permalink | Reply
    Tags:   

    Teaser 3040: Moving digit 

    From The Sunday Times, 27th December 2020 [link]

    Jonny has opened a new bank account and has set up a telephone PIN. His sort code is comprised of the set of three two-figure numbers with the smallest sum which give his PIN as their product. He was surprised to find that the PIN was also the result of dividing his eight-figure account number by one of the three two-figure numbers in the sort code.

    The PIN has an unusual feature which Jonny describes as a moving digit. If the number is divided by its first digit then the number which results has the same digits in the same order except that first digit is now at the end.

    The account number does not contain the digit which moved.

    What is the account number?

    [teaser3040]

     
    • Jim Randell 10:54 pm on 23 December 2020 Permalink | Reply

      Using a similar analysis to Teaser 3031 we get:

      If the PIN is represented by leading digit a and remaining digits r (a k digit number), then:

      r = a(10^k – a) / (10a – 1)

      The PIN is an 8-digit number divided by a 2-digit number, so it must have 6 or 7 digits. But it is also the product of three 2-digit numbers, so it has at most 6 digits.

      This gives only a few candidates for the PIN (and only one “proper” candidate), which can then be checked against the remaining conditions.

      This Python 3 program runs in 43ms.

      Run: [ @repl.it ]

      from enigma import irange, div, divisors_pairs, catch, ndigits, nsplit, printf
      
      # decompose n into k 2-digit divisors
      def decompose(n, k, m=10, ds=[]):
        if k == 1:
          if 9 < n < 100 and not(n < m):
            yield ds + [n]
        else:
          for (d, r) in divisors_pairs(n):
            if d < m: continue
            if d > 99: break
            yield from decompose(r, k - 1, d, ds + [d])
      
      # consider k digit numbers for r
      k = 5
      m = 10 ** k
      # consider possible leading digits
      for a in irange(1, 9):
        r = div(a * (m - a), 10 * a - 1)
        if r is None: continue
        PIN = a * m + r
        # find the numbers in the sort code
        sc = catch(min, decompose(PIN, 3), key=sum)
        if sc is None: continue
        # find possible account numbers
        ac = list(n for n in (x * PIN for x in set(sc)) if ndigits(n) == 8 and a not in nsplit(n))
        if ac:
          # output solutions
          printf("PIN = {PIN}; sort-code = {sc}; account-number = {ac}")
      

      Solution: The account number is 31589712.

      The 2-digit numbers in the sort code are: 72, 74, 77, so the PIN is 410256.

      And we have:

      31589712 / 77 = 410256
      410256 / 4 = 102564


      If the “two-figure” numbers in the sort code, and the “eight-figure” account number are allowed to have leading zeros, then there are further solutions:

      PIN = 111; sort-code = (01, 03, 37); account-number = 00000333
      PIN = 111111; sort-code = (37, 39, 77); account-number = 08555547
      PIN = 111111; sort-code = (37, 39, 77); account-number = 04333329

      The PIN cannot have a leading zero, as we want to divide by the leading digit.

      Like

      • Frits 1:41 pm on 24 December 2020 Permalink | Reply

        @Jim, Very concise.
        I think you can limit k to 3,4,5 as PIN cannot be a 7 digit number.

        Like

        • Jim Randell 2:50 pm on 24 December 2020 Permalink | Reply

          @Frits: Yes. I’d forgotten PIN is (k + 1) digits.

          And in fact we can see that PIN can only have 6 digits (so k = 5).

          Like

    • Frits 9:58 pm on 24 December 2020 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # smallest 8-digit number divided by biggest 2-digit number:
        # 10,000,000 // 99 = 101,010 so PIN is a 6-digit number
        #
        # PIN = AB * CD * EF = GHIJKL
        # 
        # HIJKL = G * (10^5 - G) / (10G - 1) 
        
        "AB <= CD",
        "CD <= EF",
        
        # PIN is product of three 2-digit numbers
        "AB * CD * EF = GHIJKL",
        
        # moving digit formula
        "G * (100000 - G) == HIJKL * (10 * G - 1)", 
        ],
        answer="(GHIJKL, AB + CD + EF, [GHIJKL * AB, GHIJKL * CD, GHIJKL * EF])",
        distinct="",
        d2i={0: "ACEG"},
        reorder=0,
        verbose=0)   
      
      answs = sorted([y for _, y in p.solve()])
      
      prev = ""
      for ans in answs:  
        if ans[0] != prev:      # only do once for minimal sum
          accounts = [x for x in ans[2] if str(ans[0])[0] not in str(x) 
                      and len(str(x)) == 8]
          if len(accounts) != 1: continue
          print(f"account number {accounts[0]}")
        prev = ans[0]
      

      Like

    • Frits 11:58 am on 25 December 2020 Permalink | Reply

      Framework has been taken from the generated code of the previous program.
      It can’t be run with PyPy yet (due to the walrus operator).

      # product of three 2-digit numbers can't be a 7-digit number
      #
      # smallest 8-digit number divided by biggest 2-digit number:
      # 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number
      #
      # moving digit formula (pin1 = first digit, pin2_6 = the remaining digits):
      #
      # pin1.(100000 - pin1) / (10.pin1 - 1) = pin2_6
      
      sol = []
      
      # increasing sort codes AB, CD and EF 
      for AB in range(10, 100):
        for CD in range(AB, 100):
          mi = max(CD, round(100000 / (AB * CD) + 0.5))
          for EF in range(mi, 100):
            pin = AB * CD * EF
            pin1 = pin // 100000
            pin2_6 = pin % 100000
            # moving digit formula  
            if pin1 * (100000 - pin1) == pin2_6 * (10 * pin1 - 1):
              sol.append([pin, AB + CD + EF, AB, CD, EF])
      
      prev = -1
      for s in sorted(sol):  
        if s[0] != prev:      # only do once for a minimal sum
          # account number has eight digits, none equal to the PIN's first digit
          accounts = [a for x in s[2:] if str(s[0])[0] not in (a := str(x * s[0])) 
                      and len(a) == 8]
                      
          if len(accounts) > 0:
            print(f"account number(s): {', '.join(str(x) for x in accounts)}")
        prev = s[0]
      

      Like

      • Frits 12:15 pm on 25 December 2020 Permalink | Reply

        AB could also have 11 as minimum.

        CD could also have as minimum:

        mi = max(AB, round(round(100000 / 99 + 0.5) / AB + 0.5))
        

        Like

    • GeoffR 2:10 pm on 26 December 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % 6-digit PIN number
      var 100000..999999: PIN;
      
      % 8-digit Account number 
      % Search range reduced to one million to limit run-time
      var 31000000..32000000: ACCNO;
      
      var 1..9:p; var 0..9:q; var 0..9:r;  var 0..9:s; 
      var 0..9:t; var 0..9:u; var 0..9:v;  var 0..9:w; 
      
      constraint ACCNO = 10000000*p + 1000000*q + 100000*r
      + 10000*s + 1000*t + 100*u + 10*v + w;
      
      % Using others similar analysis for the moving digit
      % d = initial digit, n = remaining number and N = power
      var 1..9: d;
      var 3..6: N;
      var 10000..99999:n;
      
      constraint d * pow(10,N) + n == d * (10*n + d);
      constraint PIN = d * pow(10,N) + n;
      
      % Three two digit numbers multiplied to give the PIN
      var 47..99: N1; var 47..99: N2; var 47..99: N3;  
      constraint N1 * N2 * N3 == PIN;
      
      % Find Account Number
      constraint  ACCNO == PIN * N1 \/ ACCNO == PIN * N2 
      \/ ACCNO == PIN * N3;
      
      constraint N3 > N2 /\ N2 > N1;
      
      % Smallest sum of three 2-digit numbers
      solve minimize(N1 + N2 + N3);
      
      % The moved digit 'dig1' is not in the account number
      var 1..9: dig1;
      constraint dig1 == PIN div 100000;
      
      % Set of digits for the account number
      var set of int: s1 = {p, q, r, s, t, u, v, w};
      constraint card(s1 intersect {dig1} ) == 0;
      
      output ["PIN = " ++ show(PIN)
      ++ "\n" ++ "ACC No. = " ++ show(ACCNO)
      ++ "\nThree 2-digit numbers are  " ++ show(N1) ++ 
      ", " ++ show(N2) ++ ", " ++ show(N3) ];
      
      
      

      Like

      • Frits 1:57 pm on 27 December 2020 Permalink | Reply

        Based on GeoffR’s program. I didn’t reduce the account range to limit run-time, runs in half a second.

        Removing lines 56-58 gives the same result but is probably not a good idea in combination with the minimize function.

        % A Solution in MiniZinc
        include "globals.mzn";
        
        % Product of three 2-digit numbers can't be a 7-digit number
        %
        % Smallest 8-digit number divided by biggest 2-digit number:
        % 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number  
        var 101011..922082: PIN;                 % 97*97*98
        
        % Array of sort codes
        array[1..3] of var int: N;  
        
        % Array of possible accounts
        array[1..3, 1..8] of var int: t;  
        
        predicate toNum(array[int] of var int: a, var int: n,  int: base) =
                  let { int: len = length(a) }
                  in
                  n = sum(i in 1..len) (
                    ceil(pow(int2float(base), int2float(len-i))) * a[i]
                  )
                  /\ forall(i in 1..len) (a[i] >= 0 /\ a[i] < base)
        ; 
        
        predicate toNum10(array[int] of var 0..9: a, var int: n) = toNum(a, n, 10);
        
        % Using others similar analysis for the moving digit
        % d = initial digit, n = remaining number and N = power
        var 1..9: d;
        var 10000..99999:n;
        
        constraint d * 100000 + n == d * (10*n + d);
        constraint PIN = d * 100000 + n;
         
        % Three two digit numbers multiplied to give the PIN
        % N[1] <= 97 as 98^3 > 900,000 and 98^4 > 90,000,000, both containing a 9
        % N[2] >= 32 as 31*31*99 < 100,000
        % N[3] >= 47 as 46^3 < 100,000
        constraint N[1] > 10 /\ N[1] < 98;
        constraint N[2] > 31 /\ N[2] < 100;
        constraint N[3] > 46 /\ N[3] < 100;
         
        % Increasing 
        constraint N[3] > N[2] /\ N[2] > N[1];
        
        constraint N[1] * N[2] * N[3] == PIN;
        
        % Smallest sum of three 2-digit numbers
        solve minimize(sum(N));
         
        % The moved digit 'd' is not in the account number
        constraint toNum10(row(t, 1), PIN * N[1]) /\ PIN * N[1] > 9999999;
        constraint toNum10(row(t, 2), PIN * N[2]) /\ PIN * N[2] > 9999999;
        constraint toNum10(row(t, 3), PIN * N[3]) /\ PIN * N[3] > 9999999;
        
        constraint forall( [row(t, 1)[i] != d | i in 1..8] ) \/ 
                   forall( [row(t, 2)[i] != d | i in 1..8] ) \/ 
                   forall( [row(t, 3)[i] != d | i in 1..8] ); 
                   
        output ["PIN = " ++ show(PIN)];
        output ["\nACC No. = " ++ show(N[j] * PIN) ++ " " | j in 1..3 where fix(forall( [row(t, j)[i] != d | i in 1..8]))];
        output ["\nThree 2-digit numbers are  " ++ show(N)];
        output["\nSum = " ++ show(sum(N))];
        

        Like

        • Frits 3:10 pm on 27 December 2020 Permalink | Reply

          A bit easier with div and mod.

          % A Solution in MiniZinc
          include "globals.mzn";
          
          % Product of three 2-digit numbers can't be a 7-digit number
          %
          % Smallest 8-digit number divided by biggest 2-digit number:
          % 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number  
          var 100000..999999: PIN;             
               
          % Array of sort codes
          array[1..3] of var int: N;  
          
          % Array of possible accounts
          array[1..3, 1..8] of var int: t;  
          
          % Using others similar analysis for the moving digit
          % d = initial digit, n = remaining number and N = power
          var 1..9: d;
          var 10000..99999:n;
          
          constraint d * 100000 + n == d * (10*n + d);
          constraint PIN = d * 100000 + n;
           
          % Three two digit numbers multiplied to give the PIN
          % N[1] <= 97 as 98^3 > 900,000 and 98^4 > 90,000,000, both containing a 9
          % N[2] >= 32 as 31*31*99 < 100,000
          % N[3] >= 47 as 46^3 < 100,000
          constraint N[1] > 10 /\ N[1] < 98;
          constraint N[2] > 31 /\ N[2] < 100;
          constraint N[3] > 46 /\ N[3] < 100;
           
          % Increasing 
          constraint N[3] > N[2] /\ N[2] > N[1];
          
          constraint N[1] * N[2] * N[3] == PIN;
          
          % Smallest sum of three 2-digit numbers
          solve minimize(sum(N));
           
          % The moved digit 'd' is not in the account number
          constraint forall( [(PIN * N[1] div pow(10,i-1) mod 10) != d | i in 1..8] ) \/ 
                     forall( [(PIN * N[2] div pow(10,i-1) mod 10) != d | i in 1..8] ) \/ 
                     forall( [(PIN * N[3] div pow(10,i-1) mod 10) != d | i in 1..8] ); 
          
          % Account consists of 8 digits          
          constraint forall( [PIN * N[i] > 9999999 | i in 1..3] );          
                     
          output ["PIN = " ++ show(PIN)];
          output ["\nACC No. = " ++ show(N[j] * PIN) ++ " " | j in 1..3 
                  where fix(forall( [(PIN * N[j] div pow(10,i-1) mod 10) != d 
                  | i in 1..8]))];
          output ["\nThree 2-digit numbers are  " ++ show(N)];
          output["\nSum = " ++ show(sum(N))];
          

          Like

    • GeoffR 7:35 pm on 27 December 2020 Permalink | Reply

      @Frits:
      On running your latest two MiniZinc postings, I found that they both give three solutions as output.

      From my own experience in MinZinc, I also know this is possible and the correct solution can easily be found as one of the output solutions. However, for this teaser, my code produced a single solution. Maybe, with some minor amendment, this also might be possible for your code, but I am not sure why our outputs vary.

      I also try to generally try to make most of my code visible in the available posting space. However, I have not found any guidance/ recommendations on this matter and opinions vary. I did achieve this aim for my MiniZinc posting, but it gets increasingly difficult to achieve when page widths for posting decrease with replies to postings.

      I noticed there was quite a lot of your output code hidden from the available posting window on your first posting after my posting. I reformatted this last section of code to show that some simple adjustments to code can keep code readable in the window – please don’t mind me doing this as I am just making a comment.

      % Frits part teaser code only - formatting comment
        
      % The moved digit 'd' is not in the account number
      constraint toNum10(row(t, 1), PIN * N[1])
      /\ PIN * N[1] > 9999999;
      
      constraint toNum10(row(t, 2), PIN * N[2]) 
      /\ PIN * N[2] > 9999999;
      
      constraint toNum10(row(t, 3), PIN * N[3]) 
      /\ PIN * N[3] > 9999999;
       
      constraint forall( [row(t, 1)[i] != d | i in 1..8] ) 
      \/ forall( [row(t, 2)[i] != d | i in 1..8] ) 
      \/ forall( [row(t, 3)[i] != d | i in 1..8] ); 
                  
      output ["PIN = " ++ show(PIN)];
      output ["\nACC No. = " ++ show(N[j] * PIN) 
      ++ " " | j in 1..3 
      where fix(forall( [row(t, j)[i] != d | i in 1..8]))];
      output ["\nThree 2-digit numbers are  " ++ show(N)];
      output["\nSum = " ++ show(sum(N))];
      
      
      

      @Jim: Any comments about maximising available windows for posting code?

      Like

      • Jim Randell 7:24 pm on 31 December 2020 Permalink | Reply

        When running MiniZinc on a model with a maximise()/minimise() target you only expect to get one answer, but I think some solvers will output “best so far” solutions as they work if the “all solutions” parameter is selected.

        Replies on the site are indented, so there is less horizontal space. I like replies, rather than making new comment threads, but this is an issue for code. Unfortunately there doesn’t seem to be a documented option to allow code blocks to wrap long lines. (Although there is a [[ collapse="true" ]] option which means you have to click on it to view the code, which might be useful for long programs).

        Personally I’m not bothered that much by horizontal scrolling (I prefer it to lots of wrapped lines). If I really want to look at (or run) a program I will copy it into an editor.

        Like

    • GeoffR 8:22 am on 28 December 2020 Permalink | Reply

      @Frits:
      Looking at the three solutions in the output, the first two solutions are not the minimum sum of the three two-digit numbers (224 and 225). The third solution is the answer and has a minimum sum of 223. Should have seen that earlier!

      Like

      • Frits 10:36 am on 28 December 2020 Permalink | Reply

        @GeoffR, Yes, per default Minizinc will print intermediate solutions. In the configuration editor you have to use “user-defined behavior”.

        I normally try to keep code within lines of 80 bytes. I will not correct for indentations within WordPress itself.

        In your program “d” and “dig1” always seem to be the same as you have fixed PIN to 6 digits. Also N always have to be 5 in that case.

        Like

  • Jim Randell 10:37 am on 22 December 2020 Permalink | Reply
    Tags: by: Sgt. Tellis   

    Brain-Teaser 16 

    From The Sunday Times, 18th June 1961 [link]

    My army number has eight digits, the third being the same as the sixth, all the others occurring only once. The sum of the digits is 33, and the difference between the sum of the first four and the sum of last four is 3. The first four digits have irregular ascending values. When out of their correct order, three only of my last four digits have consecutive numerical value; in correct order there is a difference of at least 2 between consecutive digits. The highest digit is 7 and army numbers never start with zero.

    What is my number?

    [teaser16]

     
    • Jim Randell 10:37 am on 22 December 2020 Permalink | Reply

      Alphametically, we can consider the number to be: ABCDECFG (the 3rd and 6th digits are the same).

      And we can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve the puzzle.

      The following run file executes in 96ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      # number is ABCDECFG (3rd and 6th digits the same)
      --answer="ABCDECFG"
      
      # use digits 0-7, no leading zero
      --digits="0-7"
      --invalid="0,A"
      
      # digit sum is 33
      "A + B + C + D + E + C + F + G = 33"
      
      # difference between sum of first 4 and last 4 is 3
      "abs((A + B + D) - (E + F + G)) = 3"
      
      # first 4 digits are ascending
      "A < B < C < D"
      # but not in arithmetic progression
      "not all_same(B - A, C - B, D - C)"
      
      # last 4 digits have no consecutive pairs
      "abs(C - E) > 1"
      "abs(F - C) > 1"
      "abs(G - F) > 1"
      
      # but exactly three of the digits are consecutive (when ordered)
      --code="check = unpack(lambda a, b, c, d: (c - a == 2) != (d - b == 2))"
      "check(sorted((E, C, F, G)))"
      
      # [optional]
      --verbose=16
      

      Solution: The number is 23674605.

      Like

      • Frits 2:34 pm on 22 December 2020 Permalink | Reply

        @Jim: “When out of their correct order, three only of my last four digits have consecutive numerical value”.

        You seem to have interpreted it as “at least three”.

        Like

        • Jim Randell 4:30 pm on 22 December 2020 Permalink | Reply

          @Frits: Yes, this would be a more accurate (and specific) test:

          --code="check = unpack(lambda a, b, c, d: (c - a == 2) != (d - b == 2))"
          "check(sorted((E, C, F, G)))"
          

          It doesn’t change the solutions found. But I’ll update my code.

          Like

    • Frits 12:59 pm on 22 December 2020 Permalink | Reply

      “three of the digits are consecutive (in some order)” could (probably) also be achieved by:

      # ^ is bitwise XOR operator
      check = lambda li: li[2] == li[1] + 1 and \
                                  ((li[3] == li[2] + 1) ^ (li[1] == li[0] + 1))
      
      "check(sorted([E, C, F, G])"
      

      Like

  • Jim Randell 9:04 am on 20 December 2020 Permalink | Reply
    Tags:   

    Teaser 2570: Christmas Teaser 

    From The Sunday Times, 25th December 2011 [link]

    I asked my nine-year-old grandson Sam to set a Teaser for today’s special edition and the result was:

    SAM
    SET
    NICE
    CHRISTMAS
    TEASER

    Those words are the result of taking five odd multiples of nine and consistently replacing digits by letters.

    Given that THREE is divisible by 3; What is the 9-digit number CHRISTMAS?

    This was not a prize puzzle.

    [teaser2570]

     
    • Jim Randell 9:04 am on 20 December 2020 Permalink | Reply

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 95ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      # all words are odd multiples of 9
      --code="f = lambda x: x % 18 == 9"
      "f(SAM)"
      "f(SET)"
      "f(NICE)"
      "f(CHRISTMAS)"
      "f(TEASER)"
      
      # and THREE is a multiple of 3
      "THREE % 3 = 0"
      
      --answer="CHRISTMAS"
      

      Solution: CHRISTMAS = 489051765.

      Like

    • GeoffR 9:16 am on 20 December 2020 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:S; var 0..9:A; var 1..9:M; var 0..9:E;
      var 1..9:T; var 1..9:N; var 0..9:I; var 1..9:C;
      var 0..9:H; var 0..9:R;
      
      constraint all_different ([S,A,M,E,T,N,I,C,H,R]);
      
      var 100..999: SAM = 100*S + 10*A + M;
      var 100..999: SET = 100*S + 10*E + T;
      var 1000..9999: NICE = 1000*N + 100*I + 10*C + E;
      
      var 100000000..999999999: CHRISTMAS = S + 10*A
       + 100*M + 1000*T + 10000*S + 100000*I + 1000000*R
        + 10000000*H + 100000000*C;
      
      var 100000..999999: TEASER = 100000*T + 10000*E
       + 1000*A + 100*S + 10*E + R;
       
      var 10000..99999:THREE = 10000*T + 1000*H + 100*R + 11*E;
      
      constraint THREE mod 3 == 0;
      
      % five odd multiples of nine 
      constraint SAM mod 2 == 1 /\ SAM mod 9 == 0;
      constraint SET mod 2 == 1 /\ SET mod 9 == 0;
      constraint NICE mod 2 == 1 /\ NICE mod 9 == 0;
      constraint CHRISTMAS mod 2 == 1 /\  CHRISTMAS mod 9 == 0;
      constraint TEASER mod 2 == 1 /\ TEASER mod 9 == 0;
      
      solve satisfy;
      
      output["CHRISTMAS = " ++ show(CHRISTMAS)  ++
      "\nSAM = " ++ show(SAM) ++ ", SET = " ++ show(SET) ++
      "\nNICE = " ++ show(NICE) ++ ",  TEASER = " ++ show(TEASER) ];
      
      % CHRISTMAS = 489051765
      % SAM = 567, SET = 531
      % NICE = 2043,  TEASER = 136539
      % ----------
      % ==========
      
      
      

      Like

    • GeoffR 10:57 am on 20 December 2020 Permalink | Reply

      Another solution using the digits only in the multiple numbers.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:S; var 0..9:A; var 1..9:M; var 0..9:E;
      var 1..9:T; var 1..9:N; var 0..9:I; var 1..9:C;
      var 0..9:H; var 0..9:R;
      
      constraint all_different ([S,A,M,E,T,N,I,C,H,R]);
      
      % last digits for 5 odd numbers
      constraint M==1 \/ M==3 \/ M==5 \/ M==7 \/ M==9;
      constraint T==1 \/ T==3 \/ T==5 \/ T==7 \/ T==9;
      constraint E==1 \/ E==3 \/ E==5 \/ E==7 \/ E==9;
      constraint S==1 \/ S==3 \/ S==5 \/ S==7 \/ S==9;
      constraint R==1 \/ R==3 \/ R==5 \/ R==7 \/ R==9;
      
      % THREE is divisible by 3, as are the sum of its digits
      constraint (T + H + R + E + E) mod 3 == 0;
      
      % five multiples of nine
      % sum of digits  of each nmber is also divisible by 9
      constraint (S + A + M) mod 9 == 0 ;
      constraint (S + E + T) mod 9 == 0 ;
      constraint (N + I + C + E) mod 9 == 0;
      constraint (C + H + R + I + S + T + M + A + S) mod 9 == 0;
      constraint (T + E + A + S + E + R) mod 9 == 0;
      
      solve satisfy;
      
      output ["CHRISTMAS = " ++ show(C),show(H),show(R),
      show(I),show(S),show(T),show(M),show(A),show(S) ];
      
      % CHRISTMAS = 489051765
      % ----------
      % ==========
      
      

      Like

    • Frits 2:26 pm on 20 December 2020 Permalink | Reply

      Without using modulo and with the Walrus assignment (not possible to run with PyPy).

      from enigma import SubstitutedExpression 
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # all words are odd multiples of 9 (and don't start with zero)
        # digits M,E,S,T,R are odd and A,N,I,C,H are even
        
        # SAM digits: one odd, 2 even; so sum is even and multiple of 18
        # so A >= 2 (max(S+M) is 16), max(A) is 8 so M + S >= 10
        "M + S > 9",
        "S+A+M = 18",                # even
        "S+E+T = 9",                 # odd (9 or 27)
        "N+I+C+E = 9",               # odd, 27 not possible as 
                                     # max(N+I+C) = 14) and A is 6 or 8 (see below)
        
        # C+H+R+I+S+T+M+A+S equals C+H+R+I+S+T plus S+A+M
        "C+H+R+I+S+T == 27",          # odd (9, 27 or 45) 
        
        # T+E+A+S+E+R equals S+E+T plus A+E+R (so A+E+R is even)
        # max(A) is 8 so E + R >= 10
        "E+R > 9",
        "A+E+R = 18",                # even
        # E + R >= 10 and M + S >= 10 so T <= 5 
        
        # (A + E + R) mod 18 == 0 and (S + A + M) mod 18 == 0
        #  so E + R must be equal to M + S --> T is 1 or 5 and A is 6 or 8
         
        # and THREE is a multiple of 3
        # THREE contains one even digit and 4 odd digits 
        # so sum must be even and a multiple of 6
        "(tot := T+H+R+E+E) == 18 or tot == 24",   
        ],
        answer="(C,H,R,I,S,T,M,A,S), E,N",
        # A is 6 or 8, T is 1 or 5
        d2i=dict([(0, "MTESRACN")] + \
                 [(2, "MTESRA")] + \
                 [(3, "ANICHT")] + \
                 [(4, "MTESRA")] + \
                 [(7, "ANICHT")] + \
                 [(9, "ANICHT")] + \
                 [(k, "ANICH") for k in {1, 5}] + \
                 [(k, "MTESR") for k in {6, 8}]),
        distinct="CHRISTMAEN",
        reorder=0,
        verbose=0)   
      
      # print answers 
      for (_, ans) in p.solve():
        print(f"{ans}")
        
      # ((4, 8, 9, 0, 5, 1, 7, 6, 5), 3, 2)
      

      Like

      • Jim Randell 11:17 pm on 20 December 2020 Permalink | Reply

        @Frits: You could just use [[ "T+H+R+E+E in (18, 24)" ]] to eliminate the “walrus” operator.

        Like

        • Frits 11:26 am on 21 December 2020 Permalink | Reply

          @Jim: Thanks. “T+H+R+E+E in {18, 24}” doesn’t work in combination with SubstitutedExpression. However, “T+H+R+E+E in set((18, 24))” works.

          As N+I+C+E = 9 we can also further analyze that I = 0.

          Some benchmark tests on lists, sets and tuples. In one case an in_test for sets is slower than for lists and tuples.

          import time
          from timeit import timeit
          from datetime import datetime
          
          # See https://stackoverflow.com/questions/2831212/python-sets-vs-lists
          # https://www.nuomiphp.com/eplan/en/92679.html
           
          # Determine if an object is present
          def in_test(iterable):
            for i in range(1000):
              if i in iterable:
                pass
          
          # Iterating
          def iter_test(iterable):
            for i in iterable:
              pass
          
          # Determine if an object is present
          print("# in_test")
          print("# set   ", timeit(
          "in_test(iterable)",
          setup="from __main__ import in_test; iterable = set(range(1000))",
          number=10000))
           
          print("# list  ",timeit(
          "in_test(iterable)",
          setup="from __main__ import in_test; iterable = list(range(1000))",
          number=10000))
          
          print("# tuple ", timeit(
          "in_test(iterable)",
          setup="from __main__ import in_test; iterable = tuple(range(1000))",
          number=10000))
          print()
          
          # Iterating
          print("# iter_test")
          print("# set   ", timeit(
          "iter_test(iterable)",
          setup="from __main__ import iter_test; iterable = set(range(10000))",
          number=100000))
          
          print("# list  ", timeit(
          "iter_test(iterable)",
          setup="from __main__ import iter_test; iterable = list(range(10000))",
          number=100000))
          
          print("# tuple ", timeit(
          "iter_test(iterable)",
          setup="from __main__ import iter_test; iterable = tuple(range(10000))",
          number=100000))
          print()
          
          
          
          def in_test1():
            for i in range(1000):
              if i in (314, 628):
                pass
          
          def in_test2():
            for i in range(1000):
              if i in [314, 628]:
                pass
          
          def in_test3():
            for i in range(1000):
              if i in {314, 628}:
                pass
          
          def in_test4():
            for i in range(1000):
              if i == 314 or i == 628:
                pass
          print("# Another in_test")
          print("# tuple", end=" ")
          print(timeit("in_test1()", setup="from __main__ import in_test1", 
                number=100000))
          print("# list ", end=" ")
          print(timeit("in_test2()", setup="from __main__ import in_test2", 
                number=100000))
          print("# set  ", end=" ")
          print(timeit("in_test3()", setup="from __main__ import in_test3", 
                number=100000))
          print("# or   ", end=" ")
          print(timeit("in_test4()", setup="from __main__ import in_test4", 
                number=100000))
          print()
          
          
          l = list(range(10000000))
          t = tuple(range(10000000))
          s = set(range(10000000))
          
          start = time.perf_counter()  
          -1 in l
          elapsed = time.perf_counter() 
          e = elapsed - start 
          print("# Time spent in list is: ", e)
          
          start = time.perf_counter()  
          -1 in s
          elapsed = time.perf_counter() 
          e = elapsed - start 
          print("# Time spent in set is: ", e)
          
          
          start = time.perf_counter()  
          -1 in t
          elapsed = time.perf_counter() 
          e = elapsed - start 
          print("# Time spent in tuple is: ", e)
          print()
          
          
          # Running with PyPy
          #
          # in_test
          # set    0.081273
          # list   1.5676623
          # tuple  4.0899722
          
          # iter_test
          # set    3.432239
          # list   3.486127399999999
          # tuple  2.8504029000000006
          
          # Another in_test
          # tuple 0.1158544999999993
          # list  0.11811669999999985
          # set   0.8540392000000008
          # or    0.12334350000000072
          
          # Time spent in list is:  0.0029356000000007043
          # Time spent in set is:  4.600000000465343e-06
          # Time spent in tuple is:  0.014147899999997549
          #
          # Running with Python 3.9.0
          #
          # in_test
          # set    0.4714717
          # list   51.8807992
          # tuple  48.01474160000001
          
          # iter_test
          # set    11.122311100000005
          # list   7.8272695
          # tuple  8.692177200000003
          
          # Another in_test
          # tuple 4.704576400000008
          # list  4.779769200000004
          # set   3.6342248999999924
          # or    4.508794999999992
          
          # Time spent in list is:  0.09308849999999325
          # Time spent in set is:  3.800000001774606e-06
          # Time spent in tuple is:  0.09272150000001034
          

          Like

    • GeoffR 9:05 am on 22 December 2020 Permalink | Reply

      A Python 3 permutation solution.

      from itertools import permutations
      
      digits = set('0123456789')
      
      for P1 in permutations(digits, 4):
          T, H, R, E = P1
          if T == '0':
              continue
          if int(T) % 2 != 1:
              continue
          if int(E) % 2 != 1:
              continue
          THREE = int(T + H + R + E + E)
          if THREE % 3 != 0:
              continue
          Q1 = digits.difference(P1)
          # permute remaining digits
          for P2 in permutations(Q1):
              C, I, S, M, A, N = P2
              if '0' in (C, S, N):
                  continue
              if (int(M) % 2 != 1 or int(S) % 2 != 1
                      or int(R) % 2 != 1):
                  continue
              SAM, SET = int(S + A + M), int(S + E + T)
              if SAM % 9 != 0 or SET % 9 != 0:
                  continue
              NICE = int(N + I + C + E)
              TEASER = int(T + E + A + S + E + R)
              if NICE % 9 != 0 or TEASER % 9 != 0:
                  continue
              CHRISTMAS = int(C + H + R + I + S + T + M + A + S)
              if CHRISTMAS % 9 == 0:
                  print(f"CHRISTMAS = {CHRISTMAS}")
      
      
      

      Like

    • John Crabtree 3:16 am on 24 December 2020 Permalink | Reply

      E, M, R, S and T are odd, and A, C, H, I and N are even
      S+E+T is odd, = 9 = (1, 3, 5), and so M, R = (7, 9)
      N+I+C+E is odd, = 9 = (0, 2, 4, 3) or (0, 2, 6, 1)

      T+E+A+S+E+R is odd, = 27 and so A+E+R = 18
      C+H+R+I+S+T is odd, = 27, and so N+A+M+E (remaining letters) = 18 = A+E+R, and so R = M+N
      And so R = 9, M = 7, N = 2, and as C > 0, I = 0 and C + E = 7

      From N+A+M+E = 18 = S+A+M, S = E + 2, and so C + S = 9
      (C+H+R+I+S+T) – (T+H+R+E+E) = C + S – 2E = E mod 3 = 0 mod 3
      And so E = 3, A = 6; C = 4, S = 5; and T = 1, H = 8.

      CHRISTMAS = 489051765

      Like

  • Jim Randell 4:36 pm on 18 December 2020 Permalink | Reply
    Tags:   

    Teaser 3039: Three patterned paving 

    From The Sunday Times, 20th December 2020 [link]

    James is laying foot-square stones in a rectangular block whose short side is less than 25 feet. He divides this area into three rectangles by drawing two parallel lines between the longest sides and into each of these three areas he lays a similar pattern.

    The pattern consists of a band or bands of red stones laid concentrically around the outside of the rectangles with the centre filled with white stones. The number of red stone bands is different in each of the rectangles but in each of them the number of white stones used equals the number of outer red stones used.

    The total number of stones required for each colour is a triangular number (i.e., one of the form 1+2+3+…).

    What is the total area in square feet of the block?

    [teaser3039]

     
    • Jim Randell 5:51 pm on 18 December 2020 Permalink | Reply

      (See also: Teaser 3007).

      After some head scratching I realised that the parallel lines are parallel to the short sides of the rectangular block, not the long sides.

      Considering a section of paving that is n stones wide and h stones long.

      If we count the number of border layers on both sides of the central area, we get an even number b, such that b < n.

      And if the border area is the same as the central area we have:

      (n – b)(h – b) = nh/2
      h = 2b(n – b) / (n – 2b)

      So for any (n, b) pair we can calculate a value for h, and accept values where b < h.

      The following Python program runs in 44ms.

      Run: [ @repl.it ]

      from enigma import irange, div, subsets, all_different, is_triangular, printf
      
      # consider values for the short side of the rectangle
      for n in irange(3, 24):
        # collect sets of (<section-length>, <border-width>)
        ss = list()
        # consider possible border values
        for b in irange(2, (n - 1) // 2, step=2):
          # calculate section length
          h = div(2 * b * (n - b), n - 2 * b)
          if h is None or not(b < h): continue
          printf("[n={n} b={b} -> h={h}]")
          ss.append((h, b))
        # choose the 3 sections
        for ((h1, b1), (h2, b2), (h3, b3)) in subsets(ss, size=3):
          # the borders are all different
          if not all_different(b1, b2, b3): continue
          # total length of the sections
          h = h1 + h2 + h3
          if not(h > n): continue
          # total number of stones for each colour
          t = div(n * h, 2)
          if t is None or not is_triangular(t): continue
      
          # output solution
          printf("{n} x {h} -> A={A} (t={t}); sections = (h={h1}, b={b1}) (h={h2}, b={b2}) (h={h3}, b={b3})", A=2 * t)
      

      Solution: The total area of the block is 2352 square feet.

      The block is 24 feet wide and 98 feet long, and is split into three sections:

      24 feet × 10 feet, border 2 deep. (120 slabs of each colour).

      24 feet × 18 feet, border 3 deep. (216 slabs of each colour).

      24 feet × 70 feet, border 5 deep. (840 slabs of each colour).

      In total 1176 slabs of each colour are required, and 1176 = T(48).

      Here’s a diagram of the three sections, with the longest one in the middle:

      Like

    • Frits 6:37 pm on 19 December 2020 Permalink | Reply

      I tried pythagorean_triples in combination with SubstitutedExpression (as n^2 + h^2 must be square) but that was too slow.

      from enigma import SubstitutedExpression, is_square
      
      # number of red stones: (n - b)(h - b)
      # number of white stones: nh/2
      # b^2 - (n + h)b + nh/2 = 0 
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ 
        # AB = number of border layers on both sides of the central area
        # CDE = long side
        # FG = short side
        # FG is at least 15, 2+4+6 = 12, sum 3 different numbers of border layers
        #                    plus 3 whites
        "FG > 14",
        "FG < 25",
        "AB * AB - (CDE + FG) * AB + CDE * FG / 2 == 0",
        "AB > 0",
        "AB < CDE",
        "CDE > 0",
       
        # IJ = number of border layers on both sides of the central area
        # KLM = long side
        "IJ * IJ - (KLM + FG) * IJ + KLM * FG / 2 == 0",
        "IJ > 0",
        "KLM > 0",
        "IJ < KLM",
        "KLM > CDE", 
        
        # QR = number of border layers on both sides of the central area
        # STU = long side
        "QR * QR - (STU + FG) * QR + STU * FG / 2 == 0",
        "QR > 0",
        "STU > 0",
        "QR < STU",
        "STU > KLM",
        
        # the numbers of border layers are all different
        "len([AB, IJ, QR]) == len(set([AB, IJ, QR]))",
        
        # total number of stones for each colour must be triangular
        # if t is the nth triangular number, then t = n*(n+1)/2
        # and n = (sqrt(8t+1) - 1) / 2
      
        "is_square(4* FG * (CDE + KLM + STU) + 1)"
        ],
        answer="FG * (CDE + KLM + STU), FG, CDE, AB, KLM, IJ, STU, QR",
        # short side is even and < 25
        d2i=dict([(0, "F")] + \
                 [(1, "GBJR")] + \
                 [(k, "FGBJR") for k in {3, 5, 7, 9}] + \
                 [(k, "F") for k in {4, 6, 8}]),
        distinct="",
        reorder=0,
        verbose=0)   
      
      # collect and print answers 
      answs = sorted([y for _, y in p.solve()])
      print(" area,  n  h1  b1 h2  b1 h3  b3")
      for a in answs:
        print(f"{a}")
      

      Like

  • Jim Randell 8:07 am on 17 December 2020 Permalink | Reply
    Tags:   

    Teaser 2767: Cutting corners 

    From The Sunday Times, 4th October 2015 [link]

    To make an unusual paperweight a craftsman started with a cuboidal block of marble whose sides were whole numbers of centimetres, the smallest sides being 5cm and 10cm long. From this block he cut off a corner to create a triangular face; in fact each side of this triangle was the diagonal of a face of the original block. The area of the triangle was a whole number of square centimetres.

    What was the length of the longest side of the original block?

    [teaser2767]

     
    • Jim Randell 8:08 am on 17 December 2020 Permalink | Reply

      Assuming the block is a rectangular cuboid (like a brick), lets us calculate the diagonals of the faces using Pythoagoras’ Theorem. (But this isn’t the only type of cuboid, see: [ @wikipedia ]).

      Suppose the sides of the block are (a, b, c).

      Then the lengths of the diagonals are: (x, y, z) = (√(a² + b²), √(a² + c²), √(b² + c²)).

      Using the following variant of Heron’s Formula [ @wikipedia ] for the area of a triangle with sides (x, y, z)

      4A = √(4x²y² – (x² + y² – z²)²)

      We can simplify this to calculate the area of a triangle formed by the diagonals as:

      4A = √(4(a² + b²)(a² + c²) – (2a²)²)
      2A = √(a²b² + a²c² + b²c²)

      And we are interested in when the area A is an integer, for given values of a and b.

      A = (1/2)√(a²b² + a²c² + b²c²)

      This Python program looks for the smallest solution for side c. It runs in 44ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, is_square, div, printf
      
      # the smallest 2 sides are give
      (a, b) = (5, 10)
      (a2, b2) = (a * a, b * b)
      
      # consider values for the longest side
      for c in irange(b + 1, inf):
        c2 = c * c
      
        # calculate the area of the triangle
        r = is_square(a2 * b2 + a2 * c2 + b2 * c2)
        if r is None: continue
        A = div(r, 2)
        if A is None: continue
      
        # output solution
        printf("a={a} b={b} c={c}; A={A}")
        break # only need the first solution
      

      Solution: The longest side of the original block was 40 cm.


      In this case we are given a = 5, b= 10, so we have:

      4A² = 2500 + 125c²
      4A² = 125(20 + c²)
      c² = 4A²/125 – 4.5
      c = √(4A²/125 – 20)

      For c to be an integer, it follows the 4A² is divisible by 125 = 5³. So A is some multiple of 25, larger than 25.

      And we quickly find a solution, either manually, or using a program:

      from enigma import irange, inf, is_square, div, printf
      
      # consider values for the longest side
      for A in irange(50, inf, step=25):
        c = is_square(div(4 * A * A, 125) - 20)
        if c is not None:
          # output solution
          printf("a={a} b={b} c={c}; A={A}", a=5, b=10)
          break # only need the first solution
      

      However, this is not the only solution. If we leave the program running we find larger solutions:

      a=5 b=10 c=40; A=225
      a=5 b=10 c=720; A=4025
      a=5 b=10 c=12920; A=72225
      a=5 b=10 c=231840; A=1296025
      a=5 b=10 c=4160200; A=23256225
      a=5 b=10 c=74651760; A=417316025
      a=5 b=10 c=1339571480; A=7488432225

      These further solutions could have been eliminated by putting a limit on the size of the block (e.g. if the longest side was less than 7m long, which it probably would be for a desk paperweight).

      But we can generate these larger solutions more efficiently by noting that we have a form of Pell’s equation:

      4A² = a²b² + a²c² + b²c²
      (2A)² – (a² + b²)c² = a²b²

      writing:

      X = 2A
      D = a² + b²
      Y = c
      N = a²b²

      we get:

      X² – D.Y² = N

      And we are interested in solutions to the equation where X is even, and Y > b.

      We can use the pells.py code given in Teaser 2994 to efficiently generate solutions:

      from pells import pells
      from enigma import div, first, unpack, arg, printf
      
      (a, b) = (5, 10)
      
      # given (a, b) generate solutions for (c, A)
      def solve(a, b):
        (a2, b2) = (a * a, b * b)
        for (D, N, k, c) in pells((a2 + b2, a2 * b2)):
          A = div(k, 2)
          if A is not None and b < c:
            yield (c, A)
      
      # output n solutions ordered by c
      n = arg(20, 0, int)
      for (c, A) in sorted(first(solve(a, b), n), key=unpack(lambda c, A: c)):
        printf("a={a} b={b} c={c}; A={A}")
      

      Which gives the following output:

      a=5 b=10 c=40; A=225
      a=5 b=10 c=720; A=4025
      a=5 b=10 c=12920; A=72225
      a=5 b=10 c=231840; A=1296025
      a=5 b=10 c=4160200; A=23256225
      a=5 b=10 c=74651760; A=417316025
      a=5 b=10 c=1339571480; A=7488432225
      a=5 b=10 c=24037634880; A=134374464025
      a=5 b=10 c=431337856360; A=2411251920225
      a=5 b=10 c=7740043779600; A=43268160100025
      a=5 b=10 c=138889450176440; A=776415629880225
      a=5 b=10 c=2492270059396320; A=13932213177744025
      a=5 b=10 c=44721971618957320; A=250003421569512225
      a=5 b=10 c=802503219081835440; A=4486129375073476025
      a=5 b=10 c=14400335971854080600; A=80500325329753056225
      a=5 b=10 c=258403544274291615360; A=1444519726560481536025
      a=5 b=10 c=4636863460965394995880; A=25920854752758914592225
      a=5 b=10 c=83205138753102818310480; A=465130865823099981124025
      a=5 b=10 c=1493055634094885334592760; A=8346434730063040745640225
      a=5 b=10 c=26791796274954833204359200; A=149770694275311633440400025
      ...
      

      Solutions for the longest side (c) and area (A) can be calculated by the following recurrence relation:

      (c, A) → (40, 225)
      (c, A) → (9c + 8A/5, 50c + 9A)

      Like

  • Jim Randell 9:20 am on 15 December 2020 Permalink | Reply
    Tags:   

    Teaser 1967: Domino effect 

    From The Sunday Times, 28th May 2000 [link]

    I have placed a full set of 28 dominoes on an eight-by-seven grid, with some of the dominoes horizontal and some vertical. The array is shown above with numbers from 0 to 6 replacing the spots at each end of the dominoes.

    Fill in the outlines of the dominoes.

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1967]

     
    • Jim Randell 9:20 am on 15 December 2020 Permalink | Reply

      We can use the [[ DominoGrid() ]] solver from the enigma.py library to solve this puzzle.

      Run: [ @repl.it ]

      from enigma import DominoGrid
      
      DominoGrid(8, 7, [
        1, 6, 3, 3, 5, 6, 6, 0,
        2, 6, 2, 5, 4, 4, 3, 3,
        3, 6, 6, 5, 0, 4, 1, 3,
        2, 4, 5, 0, 0, 1, 1, 4,
        4, 4, 1, 1, 0, 2, 0, 6,
        0, 4, 3, 2, 0, 2, 2, 6,
        2, 1, 5, 5, 5, 5, 1, 3,
      ]).run()
      

      Solution: The completed grid is shown below:

      Like

    • Frits 2:00 pm on 19 December 2020 Permalink | Reply

      You have to press a key each time for finding new dominoes/stones.

      import os
      from collections import defaultdict
        
      # grid dimensions (rows, columns)
      (R, C) = (7 ,8)
       
      g = [
          1, 6, 3, 3, 5, 6, 6, 0,
          2, 6, 2, 5, 4, 4, 3, 3,
          3, 6, 6, 5, 0, 4, 1, 3,
          2, 4, 5, 0, 0, 1, 1, 4,
          4, 4, 1, 1, 0, 2, 0, 6,
          0, 4, 3, 2, 0, 2, 2, 6,
          2, 1, 5, 5, 5, 5, 1, 3,
          ]
      
      # return coordinates of index number <n> in list <g>
      coord = lambda n: (n // C, n % C)
      
      # return index number in list <g>
      gnum = lambda x, y: x * C + y
      
      # return set of stone numbers in list <li>, like {'13', '15', '12'}
      domnums = lambda li: set("".join(sorted(str(li[i][1]) + str(li[i+1][1]))) 
                           for i in range(0, len(li), 2))
      
      # build dictionary of coordinates per stone
      def collect_coords_per_stone()  : 
        # empty the dictionary
        for k in coords_per_stone: coords_per_stone[k] = []
        
        for (i, d) in enumerate(g):
          if d < 0: continue           # already placed?
          # (x, y) are the coordinates in the 2 dimensional matrix
          (x, y) = divmod(i, C) 
          js = list()
          # horizontally
          if y < C - 1 and not(g[i + 1] < 0): js.append(i + 1)
          # vertically
          if x < R - 1 and not(g[i + C] < 0): js.append(i + C)
          
          # try possible placements
          for j in js:
            stone = tuple(sorted((g[i], g[j])))
            if ((coord(i), coord(j))) in ex: continue
           
            if not stone in done:
              coords_per_stone[stone] += [[coord(i), coord(j)]]
           
      # coordinate <mand> has to use stone {mandstone> so remove other possibilities
      def remove_others(mand, mandstone, reason):  
        global stop
        mandval = g[gnum(mand[0], mand[1])]
        stones = stones_per_coord[mand]
        for i in range(0, len(stones), 2):
          otherval = stones[i+1][1] if stones[i][0] == mand else stones[i][1]
          stone = sorted([mandval, otherval])
          # stone at pos <mand> unequal to <mandstone> ?
          if stone != mandstone:
            otherco = stones[i+1][0] if stones[i][0] == mand else stones[i][0]
            tup = tuple(sorted([mand, otherco]))
            if tup in ex: continue
            print(f"stone at {yellow}{str(tup)[1:-1]}{endc} "
                  f"cannot be {stone} {reason}")
            ex[tup] = stone
            stop = 0
      
      # check for unique stones and for a coordinate occurring in all entries 
      def analyze_coords_per_stone():
        global step, stop
        for k, vs in sorted(coords_per_stone.items()): 
          k_stone = tuple(sorted(k))
          if len(vs) == 1:
            pair = vs[0]
            x = gnum(pair[0][0], pair[0][1])
            y = gnum(pair[1][0], pair[1][1])
            if list(k_stone) in done: continue
      
            print(f"----  place stone {green}{k_stone}{endc} at coordinates "
                  f"{yellow}{pair[0]}, {pair[1]}{endc} (stone occurs only once)")
            done.append(k_stone)
            g[x] = g[y] = step
            step -= 1
            stop = 0
          elif len(vs) != 0:
            # look for a coordinate occurring in all entries
            common = [x for x in vs[0] if all(x in y for y in vs[1:])]
            if len(common) != 1: continue
            reason = " (coordinate " + yellow + str(common)[1:-1] + \
                     endc + " has to use stone " + str(k) + ")"
            # so remove <common> from other combinations
            remove_others(common[0], sorted(k), reason)
      
      # build dictionary of stones per coordinate
      def collect_stones_per_coord():
        stones = defaultdict(list)
        # collect stones_per_coord per cell
        for (i, d) in enumerate(g):
          if d < 0: continue      # already placed?
          # (x, y) are the coordinates in the 2 dimensional matrix
          (x, y) = divmod(i, C) 
          
          js = list()
          # horizontally
          if y < C - 1 and not(g[i + 1] < 0): js.append(i + 1)
          if y > 0     and not(g[i - 1] < 0): js.append(i - 1)
          # vertically
          if x < R - 1 and not(g[i + C] < 0): js.append(i + C)
          if x > 0     and not(g[i - C] < 0): js.append(i - C)
          # try possible placements
          for j in js:
            t = [[coord(i), g[i]], [coord(j), g[j]]]
            t2 = tuple(sorted((coord(i), coord(j))))
            if t2 not in ex:
              stones[(x, y)] += t
              
        return stones
        
      # check if only one stone is possible for a coordinate  
      def one_stone_left():
        global step, stop
        for k, vs in sorted(stones_per_coord.items()): 
          if len(vs) != 2: continue  
      
          pair = vs
          x = gnum(pair[0][0][0], pair[0][0][1])
          y = gnum(pair[1][0][0], pair[1][0][1])
          if g[x] < 0 or g[y] < 0: return
          
          stone = sorted([g[x], g[y]])  
          if stone in done: continue
      
          print(f"----  place stone {green}{tuple(stone)}{endc} at coordinates "
                f"{yellow}{str(sorted((pair[0][0], pair[1][0])))[1:-1]}{endc}, "
                f"(only one possible stone left)")
          done.append(stone)
          g[x] = g[y] = step
          step -= 1
          stop = 0
      
      
      # if n fields only allow for n stones we have a group
      def look_for_groups():
        global stop
        for n in range(2, 5):
          for group in findGroups(n, n, list(stones_per_coord.items())):
            # skip for adjacent fields 
            a1 = any(x[0] == y[0] and abs(x[1] - y[1]) == 1 
                     for x in group[1] for y in group[1])
            if a1: continue
            a2 = any(x[1] == y[1] and abs(x[0] - y[0]) == 1 
                     for x in group[1] for y in group[1])
            if a2: continue
      
            for d in group[0]:
              # get stone number
              tup = tuple(int(x) for x in d)
              for c in coords_per_stone[tup]:
                # skip coordinates in our group 
                if len(set(c) & set(group[1])) > 0: continue
                
                tup2 = tuple(c)
                if g[gnum(tup2[0][0], tup2[0][1])] < 0: continue
                if g[gnum(tup2[1][0], tup2[1][1])] < 0: continue
                if tup2 in ex: continue
                print(f"stone at {yellow}{str(tup2)[1:-1]}{endc} cannot be "
                      f"{list(tup)}, group ({', '.join(group[0])}) "
                      f"exists at coordinates {yellow}{str(group[1])[1:-1]}{endc}")
                ex[tup2] = list(tup)
                stop = 0
          if stop == 0: return    # skip the bigger groups
      
      # pick <k> elements from list <li> so that all picked elements use <n> values
      def findGroups(n, k, li, s=set(), f=[]):
        if k == 0:
          yield (list(s), f)
        else:
          for i in range(len(li)):
            # get set of stone numbers
            vals = domnums(li[i][1])
            if len(s | vals) <= n:
              yield from findGroups(n, k - 1, li[i+1:], s | vals, f + [li[i][0]])  
      
      def print_matrix(mat, orig):
        # https://en.wikipedia.org/wiki/Box-drawing_character
        global g_save
        nw = '\u250c'    #   N
        ne = '\u2510'    # W   E
        ho = '\u2500'    #   S
        ve = '\u2502' 
        sw = '\u2514' 
        se = '\u2518'
        
        numlist = "".join(["    " + str(i) for i in range(C)]) + "   "
        print("\n\x1b[6;30;42m" + numlist + "\x1b[0m")
        for i in range(R):
          top = ""
          txt = ""
          bot = ""
          prt = 0
          for j in range(C):
            v = mat[i*C + j]
            # original value
            ov = orig[i*C + j] if orig[i*C + j] > -1 else " "
            
            cb = green if v != g_save[i*C + j] else ""
            ce = endc if v != g_save[i*C + j] else ""
            
            o = orientation(mat, i*C + j, v)
            
            if o == 'N': 
              top += nw+ho+ho+ho+ne
              txt += ve+cb+ " " + str(ov) + " " + ce+ve
              bot += ve+ "   " + ve
            if o == 'S': 
              top += ve+ "   " + ve
              txt += ve+cb+ " " + str(ov) + " " + ce+ve
              bot += sw+ho+ho+ho+se  
            if o == 'W':   # already handle East as well
              top += nw+ho+ho+ho+ho+ho+ho+ho+ho+ne
              txt += ve+cb+ " " + str(ov) + "    " + str(orig[i*C + j + 1]) + " " + ce+ve
              bot += sw+ho+ho+ho+ho+ho+ho+ho+ho+se
            if o == '':  
              top += "     "
              txt += "  " + str(ov) + "  " 
              bot += "     "
          print("\x1b[6;30;42m \x1b[0m " + top + "\x1b[6;30;42m \x1b[0m")  
          print("\x1b[6;30;42m" + str(i) + "\x1b[0m " + txt + "\x1b[6;30;42m" + str(i) + "\x1b[0m")
          print("\x1b[6;30;42m \x1b[0m " + bot + "\x1b[6;30;42m \x1b[0m")  
        print("\x1b[6;30;42m" + numlist + "\x1b[0m")  
          
        g_save = list(g)
          
      def orientation(mat, n, v):
        if v > -1: return ""
        
        # (x, y) are the coordinates in the 2 dimensional matrix
        (x, y) = divmod(n, C) 
        # horizontally
        if y < C - 1 and mat[n + 1] == v: return "W"
        if y > 0     and mat[n - 1] == v: return "E"
        # vertically
        if x < R - 1 and mat[n + C] == v: return "N"
        if x > 0     and mat[n - C] == v: return "S"
        
        return ""
                     
       
      coords_per_stone = defaultdict(list)
      
      stop = 0
      step = -1
      green = "\033[92m"    
      yellow = "\033[93m"   
      endc = "\033[0m"    # end color
       
       
      done = []
      ex = defaultdict(list)
      
      os.system('cls||clear')
      
      g_orig = list(g)
      g_save = list(g)
      
      for loop in range(222):
        stop = 1
        prevstep = step
        
        stones_per_coord = collect_stones_per_coord()
        
        one_stone_left()
        
        if step == prevstep:
          collect_coords_per_stone()    
          analyze_coords_per_stone()
      
        if step < prevstep:
          print_matrix(g, g_orig) 
          if all(y < 0 for y in g):
            exit(0)
          letter = input('Press any key: ')
          os.system('cls||clear')
          print()
          continue
      
        # collect again as some possible placements may have been ruled out
        stones_per_coord = collect_stones_per_coord()
        look_for_groups()
      
        if stop: break
      
      
      print("----------------------- NOT SOLVED -----------------------------")
      
      print_matrix(g, g_orig) 
      

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Create your website at WordPress.com
Get started
%d bloggers like this: