my daughter math quiz in APL

[BenoitM]

My daughter had the following math quiz: find the smallest number of the form 2A945B which is a multiple of 18, with A and B 0~9 digits. I though it would fun to solve it with APL and my solution was:
a←(10000×(⍳10)-1)∘.+(209450+(⍳10)-1)
b←100⍴a
⌊/((18|b)=0)/b
but it does not look very elegant, especially the resizing of 'a' and the many parentheses.

What would be a better solution?

Thank you,

Benoit

[Phil Last]

Rather than generating all candidates how about the following.
B must be even as 18 is even.
The recursed digit sum must be 9 as 18 is a multiple of 9.
The digit sum of 2 9 4 5 is 2 so A+B must be 7.
Candidates are therefore

      209450+(7 5 3 1×10*4)+0 2 4 6
279450 259452 239454 219456
      18|279450 259452 239454 219456 ⍝ check
0 0 0 0
      ⌊/279450 259452 239454 219456
219456

The trouble with any obvious APL solution is that without that prior thought it's going to be a sledgehammer approach no matter how terse ∧/∨ elegant.

[StefanoLanzavecchia]

Sledgehammer:

Code: Select all

    ⎕io←0
    ⌊/{⍵/⍨0=18|⍵} {10⊥⍉↑,⊃∘.,/ 2 ⍵ 9 4 5 ⍵}⍳10


[Phil Last]

Sledgehammer:

Nice :)

[Roger|Dyalog]

A bigger sledgehammer:

      (t[;0 2 3 4]∧.='2495') ⌿ t← ⍕⍪18×⍳⌈3e5÷18
214956
234954
254952
274950
284958

[Veli-Matti]

Bludgeon?

      ⍝
      0~⍨{⍵×(0=18|⍵)∧2 9 4 5≡1 3 4 5⊃¨⊂(6⍴10)⊤⍵}¨209450{¯1+⍺+⍳⍵-⍺}299459
219456 239454 259452 279450 289458

-Veli-Matti

[Roger|Dyalog]

When the search space is known to be "small" (at most 1e5 items), it's worthwhile to devise the most direct, most obvious, most ... method to find the answer. Then dream up more elegant solutions. You can use the sledgehammer / bludgeon solution to check the elegant solutions.

An example of such a problem is Krypto, a mathematical card game. (Used by schoolteachers to entice students to practice arithmetic.) The Krypto deck has 56 cards: 3 each of numbers 1-6, 4 each of the numbers 7-10, 2 each of 11-17, 1 each of 18-25.

Six cards are dealt: an objective card and five other cards. A player must use all five of the latter cards' numbers exactly once, using any combination of arithmetic operations (+ , - , × , and ÷) to form the objective card's number. The first player to come up with a correct formula is the winner. The more strict "International Rules" specify the use of positive integers only; fractional and negative intermediate results are not permitted.

[Phil Last]

The inclusion of the number "284958" with its 2 "8"s in Roger's Bigger Sledgehammer and Velli-Matti's Bludgeon both demonstrate that the third statement in my solution was incomplete:
"The digit sum of 2 9 4 5 is 2 so A+B must be 7"
should have been
"The digit sum of 2 9 4 5 is 2 so the digit sum of A+B must be 7"
All in all a cudgel is probably to be recommended most of the time. We can then leave it to people like Roger to speed up the interpreter where it's needed.

[Veli-Matti]

We might try to be slightly clever here.

Knowing that the numbers have to be divisible by 18, we know that it has to be even and the sum of is figures has to be divisible by 9. The given pattern gives the result range from 209450 to 299459.

The following deduction may be done almost without calculating :)
+/2 0 9 4 5 0 equals 20, which is two off 18, i.e. subtracting 2+18 from the lower value gives 209430.
+/2 9 9 4 5 9 equals 38, which is also two off 36 - but now we have to add 9-2 (otherwise the result is not even), to get 299466 for the upper limit.
The difference is 90036 (299466-209430), thus using steps of ten we have to use ~9000 values, 18 is so close to 20 (which needs 4500 values) so supposedly 5000 is enough..

      0~⍨{⍵×2 9 4 5≡1 3 4 5⊃¨⊂(6⍴10)⊤⍵}¨209430+18×⍳5000
219456 239454 259452 279450 289458

Which is approx 20 times quicker than my original one-liner solution.
-wm

[Phil Last]

The point at which we abandon further logical deduction and pick up the shillelagh is fairly arbitrary unless limited by time.

So reiterating and concluding my earlier logic:

B must be even as 18 is even.
The recursed digit sum must be 9 as 18 is a multiple of 9.
The digit sum of 2 9 4 5 is 2 so A+B or its digit sum must be 7.
A is more significant than B so A must take its minimum value.
The lowest digit that added to an even gives a digit sum of 7 is 1.
Therefore A is 1 and B is 6.
The result is therefore 219456.

As with the dyslexic twelve-year-old I taught in school who could barely read but could solve simultaneous equations in his head without being able to explain how, "'sobvious ain' i'", I find some of the above logic transcends my ability to know how I know. Attempting to analyse it into APL leads me into very similar territory to Stef's solution above but the actual thought processes don't feel like that at all. APL may be a "tool of thought", it may be the best, and I'm sure my forty years of it have transformed the way I think but at least outer-products and compressons don't seem to come into it.