A Number Puzzle
July 21, 2015
It is nearly possible to work this out by hand. Obviously the tenth digit is 0, which means the fifth digit is 5. The third and fourth digits taken together must be divisible by 4, so 12, 16, 24, 28, 32, 36, 48, 64, 68, 72, 76, 84, 92 and 96 are the only possibilities. And so on. It makes a fun exercise to solve over a lunch hour.
Since two of the digits are fixed, there are only 8! = 40320 possibilities, so it is easy to iterate over them and check each one. We begin with a function to check one number:
(define (check? digits)
(let loop ((digits digits) (n (length digits)))
(if (= n 1) #t
(if (not (zero? (modulo (undigits digits) n))) #f
(loop (but-last digits) (- n 1))))))
Then we generate all permutations of the digits 1, 2, 3, 4, 6, 7, 8, and 9, insert 5 in the middle, and check each one:
(define (puzzle)
(define (insert5 ds)
(call-with-values
(lambda () (split 4 ds))
(lambda (f b) (append f (list 5) b))))
(filter check?
(map insert5
(permutations
'(1 2 3 4 6 7 8 9))))))
We leave it to you to add the terminal zero by hand:
> (puzzle)
((3 8 1 6 5 4 7 2 9))
This was easy because the Standard Prelude provides many useful functions. It’s slower than it needs to be, because there is much duplication of effort (for instance, the length of the 9-digit list is recalculated for each permutation), but it’s quick and easy to write the program, so there’s a trade-off between computation time and programmer effort. Being lazy, it’s easy for me to make that trade-off.
You can run the program, with all of its helping functions, at http://ideone.com/cRsTSp.
Programming Praxis 
In Python. The first method gives the solution in a flash. The second takes about 5 secs.
from itertools import permutations def solution(n): Q = [(k, 1, {k}) for k in list(range(1, 10))] while Q: k, div, s = Q.pop() if k % div == 0: if div == n: yield k else: Q += [(10 * k + m, div + 1, s | {m}) for m in range(10) if m not in s] def solution2(n): for p in permutations("0123456789"): if all(int("".join(p[:i])) % i == 0 for i in range(1, 11)): print (int("".join(p)))Scala:
object ANumberPuzzle {
def findNext(l: Seq[Long]= (0l to 9l), size: Int=1):Seq[Long]={
if(size==10) l
else findNext( (for(ix*10+i}).flatten filter(x=>x%(size+1)==0 && x.toString().toSet.size==size+1) sorted, size+1)
}
findNext() //> res0: Seq[Long] = Vector(3816547290)
}
I took a different approach of generating numbers that met the division test from left to right using (previous * 10) % place to find possible continuations, and pruning the search tree by testing for unique digits.
http://pastebin.com/embed_iframe.php?i=h9k0qjG0
Python. Basically a recursive depth-first search. At each ply, iterate over the available digits, appending each to the solution so far. Test to see if n % (number of digits of n) == 0. If the test passes, then proceed to the next deeper ply.
def puzzle(n=0, ds=list(range(10))): if ds == []: yield n else: for i in range(len(ds)): nn = 10*n + ds[i] if nn % (10 - (len(ds) - 1)) == 0: yield from dfs(nn, ds[:i]+ds[i+1:]) for solution in puzzle(): print(solution)Actually a little bit of logic narrows the possibilities down to 576. The last digit must be 0, the fifth digit 5, the odd digits 1,3,7,or 9 and the even digits 2,4,6,8.
There are 24 permutations of 1379 and 24 of 2468, giving 576 possibilities.
After making some observations about divisibility, I greatly reduced the needed trials.
Here is a solution in R7RS Scheme. I hand-wrote the permutation procedure.
https://notabug.org/PangolinTurtle/praxis-solutions/raw/master/2015-07-21.scm
I’m telling the sourcecode processor that this is “python” though it’s Scheme. It’s in the family of solutions that prune the search space where the prefix-so-far fails, and otherwise not at all optimized. The time that gsi spends to load and execute it is quite imperceptible.
(let dig ((s "") (n 0)) (case n ((10) (display s) (newline)) (else (for-each (lambda (d) (or (memv d (string->list s)) (let ((t (string-append s (string d))) (u (+ n 1))) (and (zero? (remainder (string->number t) u)) (dig t u))))) (string->list "0123456789")))))This solution is coded in MUMPS (https://en.wikipedia.org/wiki/MUMPS)
01:13:36 PM July 23, 2015
PP2
PP2 ; Programming Praxis #1, Try #2
;
N ENDTIME,STARTTM,TOTAL
S STARTTM=$P($H,”,”,2)
S NUM=1023456789,TOTAL=0
F D PROCESS(NUM,.STOP) Q:STOP
S ENDTIME=$P($H,”,”,2)
W !!,”TOTAL TIME: “,ENDTIME-STARTTM,” seconds”
W !,”TOTAL ENTRIES: “,TOTAL
Q
;
PROCESS(NUM,STOP) ; CYCLE THROUGH PERMUTATIONS
N POINTER
S POINTER=$L(NUM)-1,STOP=0
F D Q:STOP
. I $$DIVIDE(NUM) W !,NUM S TOTAL=TOTAL+1
. D PERMUTAT(.NUM,POINTER,.STOP)
Q
;
PERMUTAT(NUM,POINTER,STOP) ; GET NEXT PERMUTATION
N ARR,I,LEN,NUM2,PTRNUM
S LEN=$L(NUM),PTRNUM=$E(NUM,POINTER)
F I=POINTER+1:1:LEN S NUM2=$E(NUM,I),ARR(NUM2)=””
S NUM2=$O(ARR(PTRNUM))
I NUM2 D
. K ARR(NUM2)
. S $E(NUM,POINTER)=NUM2
. S ARR(PTRNUM)=””
. S NUM2=””
. F I=POINTER+1:1:LEN S NUM2=$O(ARR(NUM2)),$E(NUM,I)=NUM2
E D
. I POINTER=1 S STOP=1
. E D PERMUTAT(.NUM,POINTER-1,.STOP)
Q
;
DIVIDE(NUM) ; INSURE IT DIVIDES CORRECTLY
N FLG,I,NUM2
S FLG=1
F I=1:1:10 D Q:’FLG
. S NUM2=$E(NUM,1,I)/I
. S:NUM2[“.” FLG=0
Q FLG
Great MUMPS solution, I have no idea what is going on but it has a crystalline beauty all of its own, like seeing into the mind of Multivac.
Here is some Haskell that uses the tree pruning approach but also applies the divisibility constraints on tree construction:
import Debug.Trace gen n | n == 5 = [5] | n == 10 = [0] | n `mod` 2 == 0 = [2,4,6,8] | otherwise = [1,3,7,9] solve n k s | n == 11 = [k] | otherwise = -- trace (" -- " ++ show k) $ concatMap (\d -> let j = 10*k+d in if j `mod` n /= 0 || d `elem` s then [] else solve (n+1) j (d:s)) (gen n) main = print(head(solve 1 0 []))Uncommenting the trace reveals that we call solve about 62 times before finding the solution.
Here is my C++ solution. It’s not very elegant and it takes about 5 minutes to compute the answer, but it was the first technique that came to mind and I just started learning C++ a month ago lol.
#include
#include
using namespace std;
int main()
{
int DIGITS[10] = { 0 };
string numString = “A”; int digit = 0; bool hasUniqueDigits = true; long long firstNDigits = 0; int counter = 0;
for (long long i = 1234567880; i <= 9999999999; i += 10)
{
if (i % 100 != 0)
{
// turn i into a string
numString = to_string(i);
for (int j = 0; j < 10; j++)
{
digit = numString[j] – '0';
DIGITS[j] = digit;
}
// check if all digits are unique
for (int j = 0; j < 10; j++)
{
for (int k = j + 1; k = 0; j–)
{
firstNDigits = i / pow(10, j);
if ((firstNDigits % (10 – j)) == 0)
{
counter++;
}
}
if (counter == 10)
{
cout << "ANSWER = " << i << endl;
}
}
// reset variables
counter = 0; hasUniqueDigits = true;
}
}
}
Thought I would add some more comments to flesh out what’s happening in the MUMPS solution.
PP2
PP2 ; Programming Praxis #1, Try #2
;
NEW ENDTIME,STARTTM,TOTAL
SET STARTTM=$P($HOROLOG,”,”,2) ; Starting time
SET NUM=1023456789,TOTAL=0
FOR DO PROCESS(NUM,.STOP) Q:STOP ; Main loop, do PROCESS tag
SET ENDTIME=$PIECE($HOROLOG,”,”,2)
WRITE !!,”TOTAL TIME: “,ENDTIME-STARTTM,” seconds”
WRITE !,”TOTAL ENTRIES: “,TOTAL
QUIT
;
PROCESS(NUM,STOP) ; CYCLE THROUGH PERMUTATIONS
NEW POINTER
SET POINTER=$LENGTH(NUM)-1,STOP=0
FOR DO Q:STOP
. IF $$DIVIDE(NUM) WRITE !,NUM SET TOTAL=TOTAL+1 ; If the number (NUM) divides correctly for each position, write it out and increment the counter (TOTAL)
. DO PERMUTAT(.NUM,POINTER,.STOP) ; Get next permutation. If there are no more, STOP will be set to 1
QUIT
;
PERMUTAT(NUM,POINTER,STOP) ; GET NEXT PERMUTATION
NEW ARR,I,LEN,NUM2,PTRNUM
SET LEN=$LENGTH(NUM),PTRNUM=$EXTRACT(NUM,POINTER) ; NUM is the number to get permutation from
FOR I=POINTER+1:1:LEN SET NUM2=$EXTRACT(NUM,I),ARR(NUM2)=”” ; Go through each digit after the pointer and store in a sparse array (ARR)
SET NUM2=$ORDER(ARR(PTRNUM)) ; Looking in array for larger digit than one at the POINTER position of NUM
IF NUM2 DO ; If it exists do the following
. KILL ARR(NUM2) ; Remove found digit from array (ARR)
. SET $EXTRACT(NUM,POINTER)=NUM2 ; Set the digit at the POINTER position to the newly found digit
. SET ARR(PTRNUM)=”” ; Put previous digit at the POINTER position into the array
. SET NUM2=””
. FOR I=POINTER+1:1:LEN S NUM2=$ORDER(ARR(NUM2)),$EXTRACT(NUM,I)=NUM2 ; Put the digits after the POINTER position into the number (NUM) in ascending order
ELSE DO
. IF POINTER=1 SET STOP=1 ; If there was no larger number, and if we are at the left-most position of the number (NUM), then flag to stop
. ELSE DO PERMUTAT(.NUM,POINTER-1,.STOP) ; Otherwise recurse on the POINTER position to the immediate left of the current pointer position.
QUIT
;
DIVIDE(NUM) ; INSURE IT DIVIDES CORRECTLY
NEW FLG,I,NUM2
SET FLG=1
FOR I=1:1:10 DO QUIT:’FLG ; Check each position of the number
. SET NUM2=$EXTRACT(NUM,1,I)/I ; Get the result of dividing the 1st I position by the position number
. SET:NUM2[“.” FLG=0 ; If it does not divide evenly (has a ‘.’ in the answer), the flag to stop
QUIT FLG
Steve
Instead of checking each of the permutations for validity, I built the number to be tested 1 digit at a time and tested as I went.
I was amazed that instead of taking 2 minutes to run (as the other one did), it took .003 seconds: An improvement of a factor of 40,000!
—
PP3
PP3 ; Programming Praxis #1, Try #3
;
SET START=$PIECE($HOROLOG,”,”,2)
NEW ARR,CTR,DIGIT,FLG,I,NUMBER,POSITION,STOP,SUB
SET CTR=0
SET NUMBER=123,POSITION=4
FOR I=7,9 SET ARR(1,I)=””
FOR I=4,6,8 SET ARR(0,I)=””
SET STOP=0
FOR DO QUIT:STOP
. SET SUB=POSITION#2
. SET FLG=$$GETDIGIT(NUMBER,POSITION,.DIGIT,.ARR,SUB)
. IF FLG DO
. . IF POSITION<9 DO
. . . SET DIGIT2=$EXTRACT(NUMBER,POSITION)
. . . SET:DIGIT2 ARR(SUB,DIGIT2)=""
. . . KILL ARR(SUB,DIGIT)
. . . SET $EXTRACT(NUMBER,POSITION)=DIGIT
. . . IF POSITION=4 SET NUMBER=NUMBER_5,POSITION=6
. . . ELSE SET POSITION=POSITION+1
. . ELSE DO
. . . SET $EXTRACT(NUMBER,9)=DIGIT
. . . WRITE !,NUMBER,0
. . . SET ARR(1,$EXTRACT(NUMBER,9))=""
. . . SET $E(NUMBER,9)=""
. . . SET CTR=CTR+1,POSITION=8
. ELSE DO
. . IF POSITION=1 SET STOP=1
. . ELSE DO
. . . SET DIGIT=$EXTRACT(NUMBER,POSITION)
. . . SET:DIGIT ARR(SUB,DIGIT)=""
. . . IF POSITION=6 DO
. . . . SET $EXTRACT(NUMBER,5,6)=""
. . . . SET POSITION=4
. . . ELSE DO
. . . . SET $EXTRACT(NUMBER,POSITION)=""
. . . . SET POSITION=POSITION-1
SET END=$P($H,",",2)
WRITE !,"TIME: ",$P($HOROLOG,",",2)-START," SECONDS"
WRITE !,"HITS: ",CTR
QUIT
;
GETDIGIT(NUMBER,POSITION,DIGIT,ARR,SUB) ; GET NEXT DIGIT
NEW DIGIT2,FLG
IF POSITION=5 DO
. SET DIGIT=5,FLG=1
ELSE DO
. SET DIGIT2=$EXTRACT(NUMBER,POSITION),FLG=0
. FOR SET DIGIT2=$ORDER(ARR(SUB,DIGIT2)) QUIT:DIGIT2="" DO QUIT:FLG
. . IF ($EXTRACT(NUMBER,1,POSITION-1)_DIGIT2/POSITION)'["." SET FLG=1,DIGIT=DIGIT2
QUIT FLG
It is not actually 40320 combinations, it is just around 163 combinations.
1. All even positions of the ten digit number will consist only even number and odd positions will consist only odd number.
A. 1st, 3rd, 7th, and 9th position will consist either 1 or 3 or 7 or 9 nothing else.
B. 2nd, 4th, 6th, and 8th position will consist either 2 or 4 or 6 or 8 nothing else.
C. 5th position will consist only 5 nothing else.
D. 10th position will consist only 0 nothing else.
2. A number is divisible by 4 if last two digit of the number is divisible by 4.
A. List of two digit numbers which are divisible by 4 are
12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96
B. Actually the two digits are 3rd and 4th digits of the ten digit number, the 3rd digit can not be even number as per 1.A,
and it can not be 5 also, hence the refined list will be 12, 16, 32, 36, 72, 76, 92, 96.
C. In the above list find the 4th digit can be either 2 or 6 nothing else.
3. A number is divisible by 8 if last three digit of the number is divisible by 8.
A. List of three digit numbers which are divisible by 8 are
104, 112, 120, 128, 136, 144, 152, 160, 168, 176, 184, 192, 200, 208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288,
296, 304, 312, 320, 328, 336, 344, 352, 360, 368, 376, 384, 392, 400, 408, 416, 424, 432, 440, 448, 456, 464, 472, 480,
488, 496, 504, 512, 520, 528, 536, 544, 552, 560, 568, 576, 584, 592, 600, 608, 616, 624, 632, 640, 648, 656, 664, 672,
680, 688, 696, 704, 712, 720, 728, 736, 744, 752, 760, 768, 776, 784, 792, 800, 808, 816, 824, 832, 840, 848, 856, 864,
872, 880, 888, 896, 904, 912, 920, 928, 936, 944, 952, 960, 968, 976, 984, 992.
B. These three digits are 6th, 7th and 8th digit of the 10 digit number. the 6th and 8th digit can not be odd number as per 1.B
and the 7th digit can not be other than 1 or 3 or 7 or 9. hence the refined list will be
216, 232, 272, 296, 416, 432, 472, 496, 616, 632, 672, 696, 816, 832, 872, 896.
C. In the abobe list find the 8th digit can be either 2 or 6 nothing else.
4. As per point 3 and 4, 2nd and 6th digits can be 4 or 8 nothing else.
5. Apply all these logic and filter numbers which have unique digits. The following will be the list
JUST 163 combinations.
9496583210, 7876543210, 9876543210, 7896543210, 9476583210, 7496583210, 9496583210, 3836547210,
9836547210, 3896547210, 9436587210, 3496587210, 9496587210, 3836549210, 7836549210, 9836549210,
3876549210, 7876549210, 7436589210, 3476589210, 7872543610, 9872543610, 7892543610, 9472583610,
7492583610, 9492583610, 3832547610, 9832547610, 3892547610, 7892547610, 9432587610, 3492587610,
9492587610, 3832549610, 7832549610, 3872549610, 7872549610, 7432589610, 3472589610, 7876541230,
9876541230, 7896541230, 3476581230, 9476581230, 3496581230, 7496581230, 1816547230, 9816547230,
1896547230, 9416587230, 1816587230, 1496587230, 9496587230, 1816549230, 7816549230, 1876549230,
7876549230, 7416589230, 1816589230, 1476589230, 3872541630, 7872541630, 9872541630, 7892541630,
9472581630, 7492581630, 9492581630, 1812547630, 9812547630, 1892547630, 7892547630, 9412587630,
1432587630, 9432587630, 1492587630, 9492587630, 1812549630, 7812549630, 1872549630, 7872549630,
7412589630, 1472589630, 9836541270, 3876541270, 3896541270, 9436581270, 3496581270, 9496583270,
1816543270, 9816543270, 1896543270, 3416583270, 9416583270, 1816583270, 1496583270, 9496583270,
1816549270, 3816549270, 1836549270, 3836549270, 9836549270, 3416589270, 1816589270, 1436589270,
3832541670, 9832541670, 3892541670, 9432581670, 3492581670, 9492581670, 1812543670, 9812543670,
1892543670, 9412583670, 1492583670, 9492583670, 1812549670, 3812549670, 1832549670, 3832549670,
3412589670, 1432589670, 3836541290, 7836541290, 3876541290, 7876541290, 7436581290, 3476581290,
1816543290, 7816543290, 1876543290, 7876543290, 3416583290, 7416583290, 1816583290, 1476583290,
1816547290, 3816547290, 1836547290, 3836547290, 3416587290, 1816587290, 1436587290, 3832541690,
7832541690, 3872541690, 7872541690, 7892541690, 7432581690, 3472581690, 1812543690, 7812543690,
1872543690, 7872543690, 7412583690, 1472583690, 1812547690, 3812547690, 1832547690, 3832547690,
9832547690, 3412587690, 1432587690.
Python. Quite functional in approach.
@DanBaterisna Something happpened with that one. Let me fix that.
Here: http://codepad.org/bdfeGxRo
[…] A Number Puzzle | Programming Praxis Racket Solution […]
gtent http://clomid-rx.bid
qspokey http://buy-lyrica.bid