Arithmetic expressions
Problem 093: Arithmetic expressions
By using each of the digits from the set, {1, 2, 3, 4}, exactly once,
and making use of the four arithmetic operations (+, ?, *, /) and brackets/parentheses,
it is possible to form different positive integer targets.
For example,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) ? 1
36 = 3 * 4 * (2 + 1)Note that concatenations of the digits, like 12 + 34, are not allowed.
Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.
Find the set of four distinct digits, a < b < c < d, for which the
longest set of consecutive positive integers, 1 to n, can be obtained,
giving your answer as a string: abcd.
Solution:
XX ####################################################################################################
####################################################################################################
C ####################################################################################################
OOOO ####################################################################################################
####################################################################################################
OOOO O ####################################################################################################
OOOO O ####################################################################################################
OOOO O ####################################################################################################
OOOO O ####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
################ #### #### ##################################################
################ #### #### ##################################################
################ #### #### ##################################################
################ ##################################################
################ ##################################################
################ ##################################################
################ ############################## ###########
################ ############################## ###########
################ ############################## ###########
############ #### ##### ############################## ###########
############ #### ##### ############################## ###########
############ #### ##### ############################## ###########
############ ###################### ###########
############ ###################### ###########
############ ######### ############# ###########
############ ######### ############# ###########
############ ######### ############# ###########
############ #### ##### #### ###########
############ #### #### #### ###########
############ #### #### #### ###########
############ ################## ###########
############ ################## ###########
############ ################## ###########
############ ###########
############ ###########
############ ###########
############ ###########
############ ###########
############ ###########
############ ###############
############ ###############
############ ###############
############ ###############
############ ###############
################ ###############
################ ###############
################ ###############
################ ###############
################ ######### ################# ######### ###############
################ ######### ################# ######### ###############
################ ######### ################# ######### ###############
################ ######### ################# ######### ###############
################ ######### ################# ######### ###############
################ ############# ##################### ############## ###################
################ ############# ##################### ############## ###################
################ ############# ##################### ############## ###################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
0 ####################################################################################################
2 ####################################################################################################
1 ####################################################################################################
p ####################################################################################################
" ####################################################################################################
H ####################################################################################################
# ####################################################################################################
" ####################################################################################################
* ####################################################################################################
2 ####################################################################################################
3 ####################################################################################################
p ####################################################################################################
0 ####################################################################################################
3 ####################################################################################################
1 ####################################################################################################
p ####################################################################################################
>"}P"*>1-:" "\:"d"v
|:p/"d"\+9% <
v $< >4g.24g.34g.44g.@
>120p>20g1+30p >30g1+40p >40g1+50p > "X" 20g55+*30g+50g55+*40v
|-7p02:+1g02<|-8p03:+1g03<|-9p04:+1g04<|-5-5p05:+1g05p13+1g13p+g <
v < # ^< ^< ^<
> 31g1-!#^_21g1+21p031p>120p>20g1+30p >30g1+40p >40g1+50p >20g55+*30g+50g55+*40g+g"X"-v
|-7p02:+1g02<|-8p03:+1g03<|-9p04:+1g04<|-5-5p05:+1g05< _v
^ < ^< ^< ^< >^
vp670p64*g32g05p63*g32g04p62*g32g03p61*g32g02 ># ^# <
v <v <v <
>76g:1+76pv >77g:1+77pv >78g:1+78pv ^
> #v #: #< #v #: #< ^ v: <
v-1_$077p16g26g+17p36g27p46g37p ^v-1_$078p17g27g+18p37g28p ^v-1_$18g28g+19p v
>: v >: v >: v
v-1_$077p16g36g+17p26g27p46g37p ^v-1_$078p17g37g+18p27g28p ^v-1_$18g28g-19p v
>: v >: v >: v
v-1_$077p16g46g+17p26g27p36g37p ^v-1_$078p37g18p27g17g+28p ^v-1_$28g18g-19p v
>: v >: v >: v
v-1_$077p46g17p26g16g+27p36g37p ^v-1_$078p17g18p27g37g+28p ^v-1_$18g28g*23g/19p v
>: v >: v >: v
v-1_$077p16g17p26g36g+27p46g37p ^v-1_$078p27g18p37g17g+28p ^v-1_$28g!#v_18g23g*28g/19p v
>: v >: v >: v > ^
v-1_$077p16g17p26g46g+27p36g37p ^v-1_$078p17g18p37g27g+28p ^v $_$18g!#v_28g23g*18g/19p v
>: v >: v ^ < > ^
v-1_$077p46g17p26g27p36g16g+37p ^v-1_$078p17g27g-18p37g28p ^ <
>: v >: v |+!!%g32g91!!-g12/g32g91<
v-1_$077p16g17p46g27p36g26g+37p ^v-1_$078p17g37g-18p27g28p ^ 3
>: v >: v 1
v-1_$077p16g17p26g27p36g46g+37p ^v-1_$078p37g18p27g17g-28p ^ g
>: v >: v 1
v-1_$077p36g17p26g27p46g16g+37p ^v-1_$078p17g18p27g37g-28p ^ +
>: v >: v 3
v-1_$077p16g17p36g27p46g26g+37p ^v-1_$078p27g18p37g17g-28p ^ 1
>: v >: v p
v-1_$077p16g17p26g27p46g36g+37p ^v-1_$078p17g18p37g27g-28p ^ 2
>: v >: v 0
v-1_$077p16g26g-17p36g27p46g37p ^v-1_$078p17g27g*23g/18p37g28p ^ g
>: v >: v 1
v-1_$077p16g36g-17p26g27p46g37p ^v-1_$078p17g37g*23g/18p27g28p ^ 4
>: v >: v p
v-1_$077p16g46g-17p26g27p36g37p ^v-1_$078p37g18p27g17g*23g/28p ^ 3
>: v >: v 0
v-1_$077p46g17p26g16g-27p36g37p ^v-1_$078p17g18p27g37g*23g/28p ^ g
>: v >: v 2
v-1_$077p16g17p26g36g-27p46g37p ^v-1_$078p27g18p37g17g*23g/28p ^ 4
>: v >: v p p
v-1_$077p16g17p26g46g-27p36g37p ^v-1_$078p17g18p37g27g*23g/28p ^ 4
>: v >: v ^44g05p4 3g0<
v-1_$077p46g17p26g27p36g16g-37p ^v-1_$27g!#v_078p17g23g*27g/18p37g28p ^
>: v >: v > ^
v-1_$077p16g17p46g27p36g26g-37p ^v-1_$27g!#v_078p17g23g*37g/18p27g28p ^
>: v >: v > ^
v-1_$077p16g17p26g27p36g46g-37p ^v-1_$27g!#v_078p37g18p27g23g*17g/28p ^
>: v >: v > ^
v-1_$077p36g17p26g27p46g16g-37p ^v-1_$27g!#v_078p17g18p27g23g*37g/28p ^
>: v >: v > ^
v-1_$077p16g17p36g27p46g26g-37p ^v-1_$27g!#v_078p27g18p37g23g*17g/28p ^
>: v >: v > ^
v-1_$077p16g17p26g27p46g36g-37p ^v $_$27g!#v_078p17g18p37g23g*27g/28p ^
>: v ^ < > ^
v-1_$077p16g26g*23g/17p36g27p46g37p ^
>: v
v-1_$077p16g36g*23g/17p26g27p46g37p ^
>: v
v-1_$077p16g46g*23g/17p26g27p36g37p ^
>: v
v-1_$077p46g17p26g16g*23g/27p36g37p ^
>: v
v-1_$077p16g17p26g36g*23g/27p46g37p ^
>: v
v-1_$077p16g17p26g46g*23g/27p36g37p ^
>: v
v-1_$077p46g17p26g27p36g16g*23g/37p ^
>: v
v-1_$077p16g17p46g27p36g26g*23g/37p ^
>: v
v-1_$077p16g17p26g27p36g46g*23g/37p ^
>: v
v-1_$077p36g17p26g27p46g16g*23g/37p ^
>: v
v-1_$077p16g17p36g27p46g26g*23g/37p ^
>: v
v-1_$077p16g17p26g27p46g36g*23g/37p ^
>: v
v-1_$26g!#v_077p16g23g*26g/17p36g27p46g37p ^
>: v > ^
v-1_$36g!#v_077p16g23g*36g/17p26g27p46g37p ^
>: v > ^
v-1_$46g!#v_077p16g23g*46g/17p26g27p36g37p ^
>: v > ^
v-1_$16g!#v_077p46g17p26g23g*16g/27p36g37p ^
>: v > ^
v-1_$36g!#v_077p16g17p26g23g*36g/27p46g37p ^
>: v > ^
v-1_$46g!#v_077p16g17p26g23g*46g/27p36g37p ^
>: v > ^
v-1_$16g!#v_077p46g17p26g27p36g23g*16g/37p ^
>: v > ^
v-1_$26g!#v_077p16g17p46g27p36g23g*26g/37p ^
>: v > ^
v-1_$46g!#v_077p16g17p26g27p36g23g*46g/37p ^
>: v > ^
v-1_$16g!#v_077p36g17p26g27p46g23g*16g/37p ^
>: v > ^
v-1_$26g!#v_077p16g17p36g27p46g23g*26g/37p ^
>: v > ^
v $_$36g!#v_077p16g17p26g27p46g23g*36g/37p ^
^ ># #< ^
>" "20g55+*30g+50g55+*40g+p^
Explanation:
This one needs a little bit of a bigger explanation:
First let me say that I'm aware that this is neither the fastest algorithm nor the best algorithm to represent in funge-space. But its reasonable fast and I liked the challenge of doing such a big program (in terms of raw code size) in befunge.
First we take a 4-dimensional cache of all possible number combinations (so an bool[10][10][10][10] array) where we remember if a combination is valid.
In our program we represent it as an 2D-field with X=s1*10+s2 and Y=s4*10+s3.
Initially we set all fields to true where 0<s1<s2<s3<s4<10
Now we first test all combinations if they can produce 1 and remove the ones from our cache that can't.
Then we do 2, then 3 and so on until only one combination is left. This combination will be our solution.
The interesting part (with an quite bad algorithm) is determining if a combination can produce a specific target number. (For better understanding it could be good to look at the C# version of this problem in this git repo)
In the first step we combine all possible two numbers together (with all 4 possible operators) so we get the same problem with three numbers and a target value. There are in total 48 unique ways of trimming the combination down to three numbers:
[s1+s2, s3, s4]
[s1-s2, s3, s4]
[s1*s2, s3, s4]
[s1/s2, s3, s4] if s2 != 0
[s1+s3, s2, s4]
[s1-s3, s2, s4]
[s1*s3, s2, s4]
[s1/s3, s2, s4] if s3 != 0
[s1+s4, s2, s3]
[s1-s4, s2, s3]
[s1*s4, s2, s3]
[s1/s4, s2, s3] if s4 != 0
...This is more or less a divide and conquer algorithm (but the divide part is kinda missing :D )
Next we do the same for now three numbers and a target value (now there are only 24 ways of combining the numbers) to get only two values
Then (as you could have guessed) we do the same for two value (8 combinations, but only 6 unique ones)
And in the last step we only have to test if the number equals the target.
In our top-most method (let's call it test_0() ) there are then two possibilities: Either all 48 code paths failed and we can scratch that combination from our cache, or one succeeded and we keep it.
This algorithm makes (heavy) use of the callstack. One method is calling another one many times with different parameter and this one is calling the next (up until four layers deep). In befunge we have nothing like a callstack so we need to do all the management of parameters, state and return position by hand. But one thing works in our favor: At each time every method is at most one type on the callstack (no recursion or similar stuff here). Because of that we can write the parameter and program-counter to fixed position on the funge grid for each method. It will never be the case that two calls override each others state.
Up until here everything sounds nice and friendly. The problem stems from the division operation.
Befunge only understands integer numbers, but in this program it is possible that a intermediate value is a fraction (but the end result still is an integer).
I was not that far away from implementing fractions into this program, but fortunately (the runtime is thanking me :D ) there is another way.
We pre-multiply all numbers by a fixed value (this is called fixed-point arithmetic).
The challenge was to find the correct factor.
It should be an integer that is divisible by all numbers from one to ten, so no single division can introduce errors.
And the smallest number is 2520, this magic number will be the factor for our fixed-point arithmetic.
When doing fixed-point arithmetic addition and subtraction are straight-forward:
C = A+B => n*C = n*A + n*BA little more attention is needed when doint multiplication and division, for the first we have to divide by the factor after the operation and for the second we have to multiply it:
C = A*B => n*C = (n*A * n*B) / n
C = A/B => n*C = ((n*A)*n / (n*B)It is important that we multiply the dividend by the factor and not the result of the division, otherwise the decimal places will get lost.
As usual a final note from me: Nice problem. 10/10 would solve again
| Interpreter steps: | 305 514 916 |
| Execution time (BefunExec): | 42s (7.25 MHz) |
| Program size: | 111 x 211 |
| Solution: | 1258 |
| Solved at: | 2016-08-26 |