Project Euler with Befunge


Fork me on GitHub
2014-10-14

Problem 043: Sub-string divisibility

Description:

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4 =406 is divisible by 2
  • d3d4d5 =063 is divisible by 3
  • d4d5d6 =635 is divisible by 5
  • d5d6d7 =357 is divisible by 7
  • d6d7d8 =572 is divisible by 11
  • d7d8d9 =728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.


Solution:
vXXXXXXXXX
vXXXXXXXXX

>902p012p9>:0\1pv
          |\-1: <
>12g55+, #$ " =",, . @                                       vp20<
|`9g20    <                                                  <  <
             >$0v        > v                         >002g0g"0"-1p v
>02g0g"0"-:9`|  >:22p55+-| >22g1g     #v_ 02g0g"9"`!#^_         ## v
             >1+^        >0|-9p22+1:g22<vp20-1g20p0g20+"0"g22p1g221<
v!`g200                                 <             p20+1g20< ##
                           >  02g0g"9"`!#v_                   ^  +
                                         >002g0g"0"-1p"X"02g0p^  1
>#v_002p                   032p0>:0g"0"-32g55v>12p>             ^g
  >02g9-!02g8-!02g7-!++v        |-9\+1:p23+*+<+                  2
  v                    <        >$32g:.55+,12g^                  0
  >02g6-70g"0"-55+*80g"0"-+55+*90g"0"-+89+%+!v>++#^_02g0g"9"`!#v_^
  v!+%+58+-"0"g08*+55+-"0"g07*+55-"0"g06-5g20<+v"X"p1-"0"g0g200<#
  >02g4-50g"0"-55+*60g"0"-+55+*70g"0"-+47+%+!v+>02g0p02g1+02p   ^
  v!+%+70+-"0"g06*+55+-"0"g05*+55-"0"g04-3g20<+
  >02g2-30g"0"-55+*40g"0"-+55+*50g"0"-+05+%+!v+
  v!+%+30+-"0"g04*+55+-"0"g03*+55-"0"g02-1g20<+
  >02g0-10g"0"-55+*20g"0"-+55+*30g"0"-+02+%+!>^
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

While trying to optimize this problem I found that you don't even need a program to solve this. You can easily get the result by calculating it on paper. I have documented my calculations in my Github repo. But I wanted an program to do this (where you could for example change the constraints), so I wrote this.

The code here was a tight fit into the Befunge-93 80x25 grid, not because of some big data structures but because of a lot of code.

Here we generate all combinations from the last digit to the first, we significantly limit the amount of possible combinations by checking the constraints for every number.
For example we are at ???????410, we then don't need to evaluate the first 7 digits because constraint 7 is violated (divisibility of d_789 by 17). This way instead of evaluating 3,628,800 possibilities we only have to look at 1702.

Pen-and-paper solution

We can rule out a lot of combinations by simply looking at our rules. I divided my thought processes into steps:

Step 1:

  • d_1 != d_2 != d_3 != d_4 != d_5 != d_6 != d_7 != d_8 != d_9 (palindromic)
  • d_1 is not 0
  • d_234 is divisible by 2 => d_4 is even
  • d_345 is divisible by 3 => (d_3 + d_4 + d_5) % 3 = 0
  • d_456 is divisible by 5 => d_6 is 0 or 5
  • d_567 is divisible by 7
  • d_678 is divisible by 11
  • d_789 is divisible by 13
  • d_89A is divisible by 17

Step 2:

if d_6 is 0 then d_678 starts with a 0, and because d_678 is divisible by 11: d_7 == d_8. This conflicts with our palindrome rule.

Therefore d_6 = 5.

Step 3:

d_6 is 5 and d_678 is divisible by 11. There are only 8 possibilities for d_678:

506, 517, 528, 539, 561, 572, 583, 594

Step 4:

d_789 is divisible by 13, together with the possibilities for d_78 there are only 4 possibilities left for d_6789:

5286, 5390, 5728, 5832

Step 5:

d_89A is divisible by 17, then we can again - together with the previous result - look at the possibilities for d_6789A:

52867, 53901, 57289

Step 6:

d_567 is divisible by 7, d_6 is 5 and d_7 is 2, 3 or 7. There are now only 2 possible values for d_56789A left:

357289, 952867

Step 7:

Both values contain 2, 5, 7, 8, 9, so d_1 - d_4 can't be any of those

Step 8:

d_345 is divisible by 3. d_5 is 3 or 9 and d_4 is even and the possible digits are 0, 1, 2, 3, 4, 6 and 9 (9 only for d_5).
The possible values for d_345 are therefore:

063, 069, 309, 603, 609

And so the possible values for d_3456789A:

06357289, 06952867, 30952867, 60357289, 60952867

number 2 and 5 are not palindromic, so the numbers left are:

06357289, 30952867, 60357289

Step 9:

The only numbers left are now 1 and 4 and there are no rules left to consider.
We can now list the resulting numbers by using the 3 numbers from before and every combination of 1 and 4:

  • 14 06357289
  • 41 06357289

  • 14 30952867
  • 41 30952867

  • 14 60357289
  • 41 60357289

Step 10:

The final step is now to calculate the sum of these numbers:

   1406357289
+  4106357289
+  1430952867
+  4130952867
+  1460357289
+  4160357289

= 16695334890

Interpreter steps: 821 317
Execution time (BefunExec): 140ms (5.87 MHz)
Program size: 68 x 23 (fully conform befunge-93)
Solution: 16695334890
Solved at: 2014-10-14



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript