Teaser 2947: 55 Divisions
From The Sunday Times, 17th March 2019 [link] [link]
To mark her 55th birthday, Martha, a school teacher, gave each of her nine pupils a sheet of paper with a single different digit from 1 to 9 written on it.
They stood at the front of the classroom in a row and the 9-digit number on display was divisible by 55. Martha then asked the first 3 in the row (from the left) to sit down. The remaining 6-digit number was also divisible by 55. The next 3 then sat down and the remaining 3-digit number was also divisible by 55.
The 9 digit number was the smallest possible. What was it?
[teaser2947]
GeoffR are discussing. 
S2T2 
Jim Randell 6:25 am on 17 March 2019 Permalink |
We can treat the problem as an alphametic puzzle, use the [[
SubstitutedExpression()]] solver from the enigma.py library to find all possible solutions, and then find the smallest of these.This Python program runs in 98ms.
Run: [ @replit ]
from enigma import (SubstitutedExpression, Accumulator, irange, printf) # the alphametic puzzle p = SubstitutedExpression( [ "ABCDEFGHI % 55 = 0", "DEFGHI % 55 = 0", "GHI % 55 = 0" ], answer="ABCDEFGHI", digits=irange(1, 9), ) # find the minimum answer r = Accumulator(fn=min).accumulate_from(p.answers()) # output solution printf("min answer = {r.value} [of {r.count} solutions]")Solution: The number is 143869275.
There are 48 different solutions to the alphametic puzzle.
LikeLike
GeoffR 2:46 pm on 19 March 2019 Permalink |
% A Solution in MiniZinc include "globals.mzn"; enum letters = {A, B, C, D, E, F, G, H, I}; array [letters] of var 1..9: v; constraint all_different(v); var 100000000..999999999: ABCDEFGHI = v[A] * pow(10,8) + v[B] * pow(10,7) + v[C] * pow(10,6) + v[D] * pow(10,5) + v[E] * pow(10,4) + v[F] * 1000 + v[G] * 100 + v[H] * 10 + v[I]; var 100000..999999: DEFGHI = 100000 * v[D] + 10000 * v[E] + 1000 * v[F] + 100 * v[G] + 10 * v[H] + v[I]; var 100..999: GHI = 100 * v[G] + 10 * v[H] + v[I]; constraint ABCDEFGHI mod 55 == 0 /\ DEFGHI mod 55 == 0 /\ GHI mod 55 == 0; solve minimize(ABCDEFGHI); output ["Smallest 9-digit number = " ++ show(ABCDEFGHI) ]; % Smallest 9-digit number = 143869275 % time elapsed: 0.03 s % ---------- % ========== % Finished in 241msecLikeLike
Jim Randell 11:09 am on 20 March 2019 Permalink |
This puzzle is an ideal candidate for using the [[
solve minimize(...)]] target in a MiniZinc model.Also I didn’t know MiniZinc had [[
enum]]. (In fact, in the tutorial I used I seem to remember there was a section on how it didn’t have them and how to emulate them. I suppose they must have come along in a later version).LikeLike
GeoffR 12:14 pm on 20 March 2019 Permalink |
The latest version of MiniZinc( Ver 2.2.3) has much improved documentation and a new menu, including timing for Windows and other features. It seems odd that a solution can be found in 20 -30 msec, but still takes over 200msec to finish.
Here is the link for enums:
https://www.minizinc.org/doc-2.2.3/en/spec.html#enumerated-types
LikeLike
Jim Randell 10:29 am on 29 July 2020 Permalink |
I’ve recently added the [[
accumulate]] parameter to the [[SubstitutedExpression()]] solver, which allows values to be computed from all the solutions.So, my Python program above can be modified to:
from enigma import (SubstitutedExpression, irange, printf) # the alphametic puzzle p = SubstitutedExpression( [ "ABCDEFGHI % 55 = 0", "DEFGHI % 55 = 0", "GHI % 55 = 0" ], digits=irange(1, 9), answer="ABCDEFGHI", accumulate=min, ) # solve the puzzle r = p.run() # output solution printf("min answer = {r.accumulate} [of {r.n} values]")Although the accumulated value will be output twice.
We can also achieve the same result using a run file:
Run: [ @replit ]
Note that changing the [[
--accumulate]] parameter to [[--accumulate="(min, max)"]] allows us to calculate the minimum and maximum values from the answers.This functionality is available in the
2020-07-29version of the enigma.py library.LikeLike