S2T2

Jim Randell 4:31 pm on 15 January 2021 Permalink Reply
Tags: by: Victor Bryant ( 139 )   

• 

  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 ]

  #! python3 -m enigma -rr
  
  # 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: The row average is 5159. The column average is 5951.

  There are 56 possible arrangements of digits in the grid. Here is one:

  1 9 7 5
  3 5 1 7
  5 3 9 1
  9 7 5 3

  Row average = (1975 + 3517 + 5391 + 9753) / 4 = 5159.

  Column average = (1359 + 9537 + 7195 + 5713) / 4 = 5951.

  LikeLike

• 

  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)”

  LikeLike

  • 

    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 let clause in Python.

    So a hypothetical:

    let x=<expr1>, y=<expr2>: <expr3>
    

    construct can be implemented as:

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

    or:

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

    This last form is almost exactly the same as the let form, but with a few extra brackets.

    LikeLike

• 

  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.

  LikeLike

  • 

    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.

    LikeLike

• 

  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)];
  
  
  

  LikeLike

  • 

    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));
    

    LikeLike

• 

  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.

  LikeLike