S2T2

Jim Randell 8:53 am on 3 September 2020 Permalink Reply
Tags: by: Andrew Skidmore ( 85 )   

• 

  Jim Randell 8:54 am on 3 September 2020 Permalink | Reply

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

  The following run file executes in 249ms.

  Run: [ @replit ]

  #! python -m enigma -rr
  
  SubstitutedExpression "FLORAL + EASTER = BONNET" "N < L < E < T"
  

  Solution: BONNET = 961178.

  ---

  Or for a faster solution we can use a 1-line Python program that uses the [[ SubstitutedSum ]] solver from the enigma.py library:

  from enigma import SubstitutedSum
  
  SubstitutedSum(['FLORAL', 'EASTER'], 'BONNET').go(lambda s: s['N'] < s['L'] < s['E'] < s['T'])
  

  LikeLike

  • 

    Jim Randell 10:05 am on 28 September 2022 Permalink | Reply

    For an even faster solution we can use the [[ SubstitutedExpression.split_sum ]] solver.

    The following run file executes in 72ms. And the internal run time of the generated program is 234µs).

    Run: [ @replit ]

    #! python3 -m enigma -rr
    
    SubstitutedExpression.split_sum
    
    "FLORAL + EASTER = BONNET"
    
    --extra="N < L < E < T"
    --answer="BONNET"
    

    LikeLike

• 

  Frits 7:10 pm on 11 October 2020 Permalink | Reply

  Another Python constraint solver.

  Maybe this is not the most efficient way to do it as it takes 3 seconds.

   
  # https://pypi.org/project/python-constraint/
  
  from constraint import Problem, AllDifferentConstraint
  from functools import reduce
  
  to_num = lambda seq: reduce(lambda x, y: 10 * x + y, seq)
  
  # "FLORAL + EASTER = BONNET" "N < L < E < T"
  
  letters = "FLORAESTBN"
  
  problem = Problem()
  
  for x in letters:
    problem.addVariable(x, range(0,10))
  
  problem.addConstraint(AllDifferentConstraint())
  
  problem.addConstraint(lambda a, b, c, d: a < b and b < c and c < d,
                        ("N", "L", "E", "T"))
                        
  problem.addConstraint(lambda F,L,O,R,A,E,S,T,B,N: to_num([F,L,O,R,A,L]) +
                        to_num([E,A,S,T,E,R]) == to_num([B,O,N,N,E,T]),
                        ("F","L","O","R","A","E","S","T","B","N"))
                        
  for ans in problem.getSolutions():
    print(f"{ans['B']}{ans['O']}{ans['N']}{ans['N']}{ans['E']}{ans['T']}")
  

  LikeLike

  • 

    Frits 11:03 am on 12 October 2020 Permalink | Reply

    A better model to use for future puzzles.

    “N < L" "L < E" "E < T" is a little bit faster than "N < L < E < T"

    # https://pypi.org/project/python-constraint/
    
    from constraint import Problem, AllDifferentConstraint
    from functools import reduce
    from re import findall
    
    # generate numerical expression   inp: A,B,C  output: A*100+B*10+C
    expa = lambda w: ''.join(w[i]+'*'+str(10**(len(w)-i-1))+'+'
                     for i in range(len(w)-1))+w[-1]
    
    # variables in constraint have to be uppercase
    def addC(constraint):
      vars = set(findall('([A-Z])', constraint))
      nbrs = set(findall('([A-Z]+)', constraint))
      
      for n in nbrs:
        constraint = constraint.replace(str(n), expa(n))
      
      parms = "lambda "+', '.join(vars) + ': ' + constraint + \
              ', ("' + '", "'.join(vars) + '")'
      
      exec("p.addConstraint("+parms+")")  
      
    def report(ans, vars):
      print(f"{vars} = ", end="")
      for x in vars:
        print(f"{ans[x]}", end="")
      print()  
     
    p = Problem()
    
    p.addVariables(("LORASTN"), range(0,10))  
    p.addVariables(("FEB"), range(1,10))  
    
    p.addConstraint(AllDifferentConstraint())
    
    addC("N < L") 
    addC("L < E") 
    addC("E < T")         
    addC("FLORAL + EASTER == BONNET")
    
    for ans in p.getSolutions():
      report(ans, "BONNET")
    

    LikeLike

• 

  GeoffR 8:45 am on 12 October 2020 Permalink | Reply

  
  % A Solution in MiniZinc
  include "alldifferent.mzn";
  
  var 0..9: N; var 1..9: E; var 0..9: A;
  var 0..9: T; var 0..9: L; var 0..9: S;
  var 0..9: R; var 1..9: B; var 0..9: O;
  var 1..9: F;
  
  constraint alldifferent ([N,E,A,T,L,S,R,B,O,F]);
  
  constraint 
    (L + A*10 + R*100 + O*1000 + L*10000 + F*100000)
  + (R + E*10 + T*100 + S*1000 + A*10000 + E*100000)
  = (T + E*10 + N*100 + N*1000 + O*10000 + B*100000) ;
  
  solve satisfy;
  
  output["BONNET = " ++ show(T + E*10 + N*100 + N*1000 + O*10000 + B*100000)];
  
  % Answer: 961178
  % time elapsed: 0.05s
  % ----------
  % ==========
  % time elapsed: 0.18 s
  % Finished in 436msec
  
  
  

  A standard MiniZinc solution produced a reasonable run-time, but what is the correct run-time to quote in a posting
  :
  a) time to print first solution?
  b) time elapsed ?
  c) Finished time?

  I like to think it is the time it takes to print out the first time quoted!

  LikeLike

  • 

    Jim Randell 12:43 pm on 12 October 2020 Permalink | Reply

    @GeoffR:

    When I report the timings of my programs I use the complete execution time of the command that runs the program presented.

    So I hardly ever report the time taken to find the first solution, as I am usually more interested in the time taken to exhaustively search the solution space and find all possible solutions. (The exception being if the program is only looking for the first answer it finds, and terminates once it is found).

    I can collect this data using the time builtin of my shell which reports the total runtime of a command. I perform multiple executions, and take the shortest time. I call this the “external runtime”.

    For example comparing my SubstitutedSum() based solution above against a MiniZinc model (I added in a constraint to ensure N < L < E < T) I get:

    % time python3.9 teaser2741.py
    python3.9 teaser2741.py  0.04s user 0.01s system 91% cpu 0.055 total
    
    % time minizinc -a teaser2741geoff.mzn
    minizinc -a teaser2741geoff.mzn  0.07s user 0.02s system 96% cpu 0.095 total
    

    So I would report a runtime of 55ms for the Python program, and 95ms for the MiniZinc model.

    This lets me compare programs using different languages, but makes it less easy to compare programs in the same language that run very quickly. For example on my system run a Python program that consists of the single statement pass, takes between 30ms and 50ms (depending on the version of Python). So to compare Python programs that take less than 50ms I sometimes use the “internal runtime”. I do this by using the [[ Timer ]] class from the enigma.py library, putting a [[ timer.start() ]] statement before the first statement of the program, and a [[ timer.stop() ]] statement at the end. This removes some of the overhead involved in using Python, but means the values are not necessary useful when comparing with non-Python programs, and each language will have a different way of reporting internal runtimes.

    For example, the internal runtime of the Python program above is 13.65ms.

    MiniZinc has a --statistics option which reports: solveTime=0.002176, so it may have an internal runtime of 2.176ms.

    LikeLike

  • 

    Frits 2:27 pm on 12 October 2020 Permalink | Reply

    @GeoffR, I only quote timings if I think the program runs (too) slow. Elapsed times more than one second (PyPy) seem suspicous to me for relatively simple puzzles.

    Normally a) is not important to me for Python programs as you might be lucky to get a solution quickly.

    I use enigma.run(“xxxx.py”, timed=1) for Python programs (normally running with PyPy).

    Unfortunately I was not able to used function toNum in the output statement.

    % A Solution in MiniZinc
    include "alldifferent.mzn";
     
    var 0..9: N; var 1..9: E; var 0..9: A;
    var 0..9: T; var 0..9: L; var 0..9: S;
    var 0..9: R; var 1..9: B; var 0..9: O;
    var 1..9: F;
    
    var 102234..987765: bonnet;
     
    function var int: toNum(array[int] of var int: a) =
              let { int: len = length(a) }
              in
              sum(i in 1..len) (
                ceil(pow(int2float(10), int2float(len-i))) * a[i]
              );
    
    constraint alldifferent ([N,E,A,T,L,S,R,B,O,F]);
    
    constraint bonnet == toNum([B, O, N, N, E, T]);
    constraint toNum([F, L, O, R, A, L]) + toNum([E, A, S, T, E, R]) == bonnet;
       
    solve satisfy;
    output["BONNET = " ++ show(bonnet)];
     
    % Answer: 961178
    

    LikeLike