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;
}
}
Social networks, for lonely people, may only show them how lonely they are.
dat feel
Name:
Anonymous2012-08-26 4:10
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.
Name:
Anonymous2012-08-26 6:55
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
>>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.
Name:
Anonymous2012-08-26 20:19
Use Prolog. It's made for problems like this.
Name:
Anonymous2012-08-27 0:56
>>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?
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?
Name:
Anonymous2012-08-27 4:50
>>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.
>>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.
Name:
Anonymous2012-08-27 11:27
EVALUATE MY ANUS
Name:
Anonymous2012-08-27 17:18
>>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.
Name:
Anonymous2012-08-27 17:34
>>24 no rational number to any rational power is going to give you 10
10^1. Haha look at this idiot.
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)
haskell. I'm just learning it so the conventions might be odd. And lisp would have (((((((((looked))))))))) (((((((((like))))))))))))))))))))))))) ((((((((((((((this)))))))))))))))))))))))) . '())
>>39 here
I realised I was making a mistake in evaluating expressions of the form:
-a^b
I was evaluating it as
(-a)^b
instead of
-(a^b)
The latter method allows me to take advantage of the way a carriage number (and it's sign -- +ve or -ve) is permuted, because
(b mod 2)==2
will always be positive.
I now think 9161 of 10000 carrage numbers from 0000 to 9999 make 10. Although (this time) I'm highly confident in my answer, I'd like someone else to confirm. The reason I'm confident in my answer is because the answers in the "cheat sheet" (http://tinyurl.com/everyfuckingsolution) seem reasonable. I also checked that the same 9161 carriage numbers make -10, though this could just mean I'm making the same mistake twice. (If a carriage number can make n, it can also make -n, right?)
Another thing. I was able to check (and show answers to) all 10000 carriage numbers in 4 minutes and a half on an stock i7 950. Can anybody check more than 37 solutions per second?
I ended up changing it so that 0^0 was undefined. The cheat sheet does does contain unsolved games with the solution written "No solution." Unless you wanted me to post a list of numbers separately...
>>46
Well, rule 6 on the Facebook page says you can use multiple digit base numbers, i.e., 0054 has (50-40) as a solution. (It appears I was looking at an old cached version of your answer sheet, so I hadn't noticed you're not using 0^0 anymore; my bad.)
Name:
Anonymous2012-08-30 7:34
If you blocked Facebook in you hosts file
Everyone needs to do this, in all honesty, if people weren't stupid then they would
Name:
Anonymous2012-08-30 7:59
>>54 rule 6
I don't like that rule. I suppose it shouldn't be too hard to solve though.