S2T2

Jim Randell 11:22 am on 8 May 2019 Permalink Reply
Tags: by: John Owen ( 33 )   

• 

  Jim Randell 11:23 am on 8 May 2019 Permalink | Reply

  This Python 3 program runs in 415ms.

  Run: [ @repl.it ]

  from itertools import (combinations, permutations)
  from collections import defaultdict
  from enigma import (irange, nconcat, nsplit, join, sprintf as f)
  
  digits = irange(0, 9)
  
  # from transactions <ts> and balance <b> find <k> transactions
  def solve(ts, b, k, s=[]):
    if k == 0:
      yield s
    elif b in ts:
      for (d, a) in ts[b]:
        yield from solve(ts, a, k - 1, s + [(b, d, a)])
  
  # choose 5 different digits for the balance
  for ds in combinations(digits, 5):
  
    # the largest is less than 3x the smallest
    if not (ds[-1] < 3 * ds[0]): continue
  
    # make all possible numbers from the digits
    ns = sorted(nconcat(s) for s in permutations(ds) if s[0] != 0)
  
    # find transactions that make viable debits
    ts = defaultdict(list)
    for (a, b) in combinations(ns, 2):
      d = b - a
      xs = set(nsplit(d))
      if len(xs) == 5 and xs.isdisjoint(ds):
        ts[b].append((d, a))
  
    # find a sequence of 4 transactions
    for b in ts.keys():
      for s in solve(ts, b, 4):
        print(f("final = {f} [{s}]", s=join((f("{b} - {d} = {a}") for (b, d, a) in s), sep=", "), f=s[-1][2]))
  

  Solution: The final balance was £ 347.58.

  There are two possibilities for the initial amount and the first debit amount, which give the same value for the balance:

  (1) 853.47 – 109.62 = 743.85; or:
  (1) 873.45 – 129.60 = 743.85

  After that the next three debits are:

  (2) 743.85 – 169.02 = 574.83
  (3) 574.83 – 120.96 = 453.87
  (4) 453.87 – 106.29 = 347.58

  The condition that “the largest of the digits was less than three times the smallest” reduces the search space, but there are no further solutions without this condition.

  LikeLike

• 

  GeoffR 10:28 am on 9 May 2019 Permalink | Reply

  A brute force approach in MiniZinc uses 45 integer variables and sets to solve this teaser.

  % A Solution in MiniZinc 
  include "globals.mzn"; 
  
  % Balance/Debit Sums - uses 5-digit integers for £ and pence parts
  % ABCDE - abcde == FGHIJ;
  % FGHIJ - fghij == KLMNO;
  % KLMNO - klmno == PQRST;
  % PQRST - pqrst == UVWXY;
  
  % Balances integers
  var 0..9: A; var 0..9: B; var 0..9: C; var 0..9: D; var 0..9: E;
  var 0..9: F; var 0..9: G; var 0..9: H; var 0..9: I; var 0..9: J;
  var 0..9: K; var 0..9: L; var 0..9: M; var 0..9: N; var 0..9: O;
  var 0..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; var 0..9: X; var 0..9: Y;
  
  constraint A != 0 /\ F != 0 /\ K != 0 /\ P != 0 /\ U != 0;
  
  % max balance digit < 3 * min digit for the five balances  
  constraint max([A,B,C,D,E]) < 3 * min([A,B,C,D,E]);
  constraint max([F,G,H,I,J]) < 3 * min([F,G,H,I,J]);
  constraint max([K,L,M,N,O]) < 3 * min([K,L,M,N,O]);
  constraint max([P,Q,R,S,T]) < 3 * min([P,Q,R,S,T]);
  constraint max([U,V,W,X,Y]) < 3 * min([U,V,W,X,Y]);
  
  % Balances - sets of integers
  var set of int: s1 = { A,B,C,D,E };
  var set of int: s2 = { F,G,H,I,J };
  var set of int: s3 = { K,L,M,N,O };
  var set of int: s4 = { P,Q,R,S,T };
  var set of int: s5 = { U,V,W,X,Y };
  
  % Sets s1 to s5 have the same integers
  constraint card (s1 intersect s2 ) == 5;
  constraint card (s1 intersect s3 ) == 5;
  constraint card (s1 intersect s4 ) == 5;
  constraint card (s1 intersect s5 ) == 5;
  
  % Debits integers
  var 0..9: a; var 0..9: b; var 0..9: c; var 0..9: d; var 0..9: e;
  var 0..9: f; var 0..9: g; var 0..9: h; var 0..9: i; var 0..9: j;
  var 0..9: k; var 0..9: l; var 0..9: m; var 0..9: n; var 0..9: o;
  var 0..9: p; var 0..9: q; var 0..9: r; var 0..9: s; var 0..9: t;
  
  constraint a != 0 /\ f != 0 /\ k != 0 /\ p != 0;
  
  % Debits - sets of integers
  var set of int: s6 = { a,b,c,d,e };
  var set of int: s7 = { f,g,h,i,j };
  var set of int: s8 = { k,l,m,n,o };
  var set of int: s9 = { p,q,r,s,t };
  
  % Debit sets s6 to s9 have the same integers
  constraint card (s6 intersect s7 ) == 5;
  constraint card (s6 intersect s8 ) == 5;
  constraint card (s6 intersect s9 ) == 5;
  
  % Sets s1 and s6 have no digits in common
  constraint card(s1 intersect s6) == 0;
  
  % Form all 5-digit integers
  var 10000..99999: ABCDE = 10000*A + 1000*B + 100*C + 10*D + E;
  var 10000..99999: FGHIJ = 10000*F + 1000*G + 100*H + 10*I + J;
  var 10000..99999: KLMNO = 10000*K + 1000*L + 100*M + 10*N + O;
  var 10000..99999: PQRST = 10000*P + 1000*Q + 100*R + 10*S + T;
  var 10000..99999: UVWXY = 10000*U + 1000*V + 100*W + 10*X + Y;
  
  var 10000..99999: abcde = 10000*a + 1000*b + 100*c + 10*d + e;
  var 10000..99999: fghij = 10000*f + 1000*g + 100*h + 10*i + j;
  var 10000..99999: klmno = 10000*k + 1000*l + 100*m + 10*n + o;
  var 10000..99999: pqrst = 10000*p + 1000*q + 100*r + 10*s + t;
  
  % Balance/Debit sums in sequence
  constraint ABCDE - abcde == FGHIJ;
  constraint FGHIJ - fghij == KLMNO;
  constraint KLMNO - klmno == PQRST;
  constraint PQRST - pqrst == UVWXY;
  
  solve satisfy;
  
  output ["Final Balance = " ++ "£"++ show(U),show(V),show(W) ++ "." 
  ++ show(X),show(Y) ] 
  ++ ["\n" ++ show(ABCDE) ++ " - " ++ show(abcde)  ++ " = " ++ show(FGHIJ) ]
  ++ ["\n" ++ show(FGHIJ) ++ " - " ++ show(fghij)  ++ " = " ++ show(KLMNO) ]
  ++ ["\n" ++ show(KLMNO) ++ " - " ++ show(klmno)  ++ " = " ++ show(PQRST) ]
  ++ ["\n" ++ show(PQRST) ++ " - " ++ show(pqrst)  ++ " = " ++ show(UVWXY) ];
  
  % Final Balance = £347.58
  % 85347 - 10962 = 74385 - five digit integer format for £/pence sums
  % 74385 - 16902 = 57483
  % 57483 - 12096 = 45387
  % 45387 - 10629 = 34758
  % % time elapsed: 0.27 s
  % ----------
  % Final Balance = £347.58
  % 87345 - 12960 = 74385
  % 74385 - 16902 = 57483
  % 57483 - 12096 = 45387
  % 45387 - 10629 = 34758
  % % time elapsed: 0.27 s
  % ----------
  % ==========
  % Finished in 666msec
  
  

  LikeLike