Train Carriage Game Solutions

I'm looking to program a function that can check if you can "make 10" from some 4 digit number (0000 to 9999).

The function should use these rules when performing the check:
https://www.facebook.com/pages/Train-Carriage-Game/108348062559174?sk=info

Does /prog/ know if there's a simple way to perform such a check short of checking every combination individually? I obviously don't want to be writing the following:


boolean makesTen (int a, int b, int c, int d) {
    if (a + b + c + d == 10) {
        return true;
    } else if (-a + b + c + d == 10) {
        return true;
    } else if (a - b + c + d == 10) {
        return true;
    }
    ...
    ...
    } else {
        return false;
    }
}

http://stallman.org/facebook.html

Thats a long ass list

Social networks, for lonely people, may only show them how lonely they are.
dat feel

Generate all the permutations of the four digits, then for each of those permutations generate (you only have to do this once if you really care about efficiency) and test all possible 3-item permutations of the allowed operations. If any pair of permutations gives you 10 when you test it, output it somewhere.

This is very similar to the problem of making change from coin values, which is one of the early SICP exercises, except your search space includes operators and digit combinations as well. E.g. if you have 1, 2, 3, 4 then take { 1, + } and try to find an expression for 9 from { 2, 3, 4 }, { 1, - } and try to find an expression for 11 from { 2, 3, 4 }, etc. You can optimise this process by computing the expressions needed for everything up to 10 and memoising them; look up dynamic programming for more information.

makesTen :: Num a => [a] -> Bool
makesTen nums = makesTen' nums 0
    where makesTen' (x:xs) n = makesTen' xs (n+x) || makesTen' xs (n-x)
          makesTen' [] 10 = True
          makesTen' [] _ = False

The three rules of writing algorithms:
1) Use recursion
2) Use recursion
3) Use recursion

>>6
gotta love haskell

>>6
What about the division, multiplication and exponentiation operators?

>>6
Those are also the three rules of how to blow your stack

>>9
lel
some hairs in my armpit are 10cm long

>>10
Why would you measure their length, JEW?

>>11
fuck off and die, racist faggot

>>1
The rules don't state that you can't reuse the same digit, so as long as the greatest common divisor of the four digits is 1, you can always get 10.

Use Prolog. It's made for problems like this.

>>13
I've never seen someone play the game like that. I think the person who wrote the rules on the Facebook page simply forgot to specify that.

>>14
I've briefly looked into Prolog. While I can't be bothered learning a new language just to solve this one problem, it seems mind-bogglingly powerful. Are my impressions correct?

>>3,11
I see /prog/ is still shit.

>>15
Yes, but use Erlang instead.

Couldn't you just make a recursive function(or even a for loop) that loops from 0 to 9999 which adds all the successful combinations to a list?

>>18
I'm working on a solution right now in Java. It just creates every possible expression and evaluates it. Generating all possible expressions without repeating any is trickier than just generating permutations of operators and operands.

What I'm doing is taking the carriage number and finding the permutations of it. For each one of those permutations I'm then assigning a sign (+ve or -ve) to each digit in every which way I can. Now that I have permutations whose digits have signs, I then add the multiplication, division and exponentiation operators, or no operator if I want to add/subtract numbers from one another. For example, say we start off with carriage number 4832. Then we might have:

4238             (a single permutation)
+4+2-3+8         (one way of giving each digit a sign)
+4/+2^-3 +8      (assigning operators - note the space indicating no operator)
Notice that we have a problem. If we evaluate this expression using the order of operations, we can never raise a number to the power of more than a single digit at a time. For example we will never evaluate an expression like:

+4/+2^(-3 +8)
To get past this, we ignore the order of operations (assume all operators have equal precedence) and evaluate right-to-left. Similarly, to evaluate an expression equivalent to:

(+4/+2)^-3 +8
We give every operator has equal precedence and evaluate left-to-right.

About recursion: I generally shy away from recursion unless I can see an obvious benefit (or have to use it). Although it makes things simpler sometimes, it usually makes it a fucktonne trickier imo.

>>8
Left as a (trivial) exercise for the reader.

>>19
This problem has a very straightforward recursive solution, and one that can be easily memoised too.

Well guys, I've done it.

For anybody interested, Java Code here:
http://pastebin.com/xpmwXHMu
http://pastebin.com/ZExUshBa
http://pastebin.com/ghJ15fFM
http://pastebin.com/G4R8S3Kj
http://pastebin.com/GdhyWQR1

Train game solutions here:
http://tinyurl.com/everyfuckingsolution

>>21
Ignore that, guys. I'm not evaluating stuff in brackets to the power of stuff in brackets. Example:

(+4/+2)^(-3 +8)
is never evaluated.

EVALUATE MY ANUS

>>22
I didn't realize this was an exercise in writing bloated code. Just so you know, no rational number to any rational power is going to give you 10, so leaving that out isn't a problem. It is possible to get 10 by multiplying two sums, though, and it's likely that you left that out too.

>>24
no rational number to any rational power is going to give you 10
10^1.  Haha look at this idiot.

>>24
n^(log(10)/log(n)) = n

>>26
n ≟ 0

Ask 1chan.

some type errors are preventing ^ and / mixing as operators, but this should be enough brute force to cover the possibilities. There's a lot of redundancy that could be optimized away with a better design. I need to implement saving of the expressions so you can actually see its solutions.


collect_1_partitions list = collect_1_partitions' [] list where
  collect_1_partitions' _ [] = []
  collect_1_partitions' behind (x:rest) = (x,(behind ++ rest)):(collect_1_partitions' (behind ++ [x]) rest)

permutations [] = []
permutations [x] = [[x]]
permutations list =
  [ x:rest_perm
  | (x,rest) <- collect_1_partitions list,
    rest_perm <- permutations rest
  ]

collect_splits (x:xs) = collect_splits' [x] xs where
  collect_splits' _ [] = []
  collect_splits' behind (x:xs) = (behind, (x:xs)):(collect_splits' (behind ++ [x]) xs)

associative_reductions [] _ = []
associative_reductions [x] _ = [x]
associative_reductions list ops =
  [ behind_reduction `op` rest_reduction |
    (behind,rest) <- collect_splits list,
    behind_reduction <- associative_reductions behind ops,
    rest_reduction <- associative_reductions rest ops,
    op <- ops ]

all_reductions [] _ = []
all_reductions [x] _ = [x]
all_reductions list ops =
  [ reduction |
    perm <- permutations list,
    reduction <- associative_reductions perm ops ]

can_make_n goal numz ops =
  filter (== goal) (all_reductions numz ops)

Rough check of my solution: Does everybody else here agree that 9195 of 10000 carrage numbers from 0000 to 9999 make 10?

>>29
is this lisp or haskell?

>>31

haskell. I'm just learning it so the conventions might be odd. And lisp would have (((((((((looked))))))))) (((((((((like))))))))))))))))))))))))) ((((((((((((((this)))))))))))))))))))))))) . '())

>>32
And if it did, I would've actually read it.

>>30
0009    (9+((0*0)^0))    = 10
It is not generally agreed upon that 0^0=1.
Most complaints, however, are based on operations that are 0^0 in the limit.

>>34
But! But Google says it's 1!
https://www.google.com/search?q=0%5E0

Does having 0^0 undefined make you more comfortable, anon?

6. Multiple numbers can be used as a basis number, [...]
You guys are bad at reading. 0001 has a perfectly valid solution, i.e. 0+0+10.

>>34
0! = 1 therefore 0 multiplied by itself 0 times equals 1

0! = 1 <==> 0^0 = 1

>>35
>>37
http://www.wolframalpha.com/input/?i=0%5E0

>>30 here.

Changing my code as per >>35's suggestion gives me 9077 carriage numbers that make 10. Can anyone else confirm?

>>35
Google is wrong then, it is undefined and limits that approach the form 0^0 are indeterminate.

It's easy to see why it would undefined, as division can be defined through negative exponents
0^0 = 0^(1 - 1) = 0/0.