tough program problems

[slinetz]

here is the problems i encountered

give you a random 4 digit #, u will have to some how find a way to make it to 24 by using +,-,*,/

examples: 4362 = > 4*3+6*2

if there is no solution wrote no solution output.

any clever to do it? (if you really want to list all possibility , it is going to be a drag)

 

[warhorse]

I would precompute all possibilities into a 4-D array (also stored on disk to prevent future calculation), then not only will the program work, it will be an O(1) operation!

If you're going to use the program frequently, the essentially free lookups amortizes the cost of the precompute away.

 

[aerialcombat]

didn't he say that listing all the possibilities will be a drag?

The number of possiblities will be *(roughly)

9 x 4 x 10 x 4 x 10 x 4 x 10 = 576,000

Someone calculate how long this will take

 

[Matthias99]

Not very. It's O(1) to test each possibility, and there are only:

10000 * (4 * 4 * 4) * (8) = 5,120,000 possible ways to do it (assuming you can parenthesize the expressions). Shouldn't take very long.

 

[Sahakiel]

Sounds like a HW problem. Very easy, assuming no timing constraints.

Compute all possibilites
Store in chaining hash
list result

 

[warhorse]

Alright, so we haven't actually answered the question because in order to precompute you still have to be able to compute one. We've so far assumed that we have all of the answers already. (I still maintain that precomputing is the best overall solution. I bet you could store each solution in its entirety in 14 bits)

So, to solve any given set of numbers outright, I would do something like this:
Build a tree for every possibility. The root would be all 4 numbers. From there we enumerate every possiblilty of putting one operator between 2 numbers. Prune the tree of repeats (a*b and b*a) and we are left with lots of groups of 3 numbers. Now do the same thing for these 3 numbers, then 2, giving us 1 result. See if it's 24.

This could be done recursively, I guess. The mention a tree because I visualized the solution as an adaptation of minimax (1 player style hehe).


(Edit)
If I claim you can store each solution in 14 bits, then there can only be a maximum of 2^14 different solutions (16384) so it's not too bad. Even if you needed 2 bytes per solution, 10*10*10*10 possible starting positions is just 20,000 bytes. I'm sure you can make it less.

Anyone want to back my claim? I have to double check it then I'll post it in a bit

(Edit)
I change my claim to 16 bits. Also, it isn't 10^4 starting possibilities. It's actually 10 choose 4, I think (my combinatorics is bad) since if my solution works if you sort the numbers you get to eliminate repeats.

 

[blahblah99]

Hmm... sounds like a typical hw problem indeed!

I'm no software programmer, but I did take c++ courses in college and here's my take:

Create a binary tree with the roots being the four digits. Then every parent node of the tree is a mathematical combination of any two digits. I will elaborate more after dinner!

EDIT: Okay, the structure would have to be an inverted binary tree, with the four bases being the four digits. Call this the base level. Then every level up the tree would be a mathematical combination of any two nodes below it. Call it level 2, level 3, level 4, etc etc...

Now, at any given level you will have a result of the mathematical function applied to its two child nodes. If the result is 24, then stop and traverse down the tree and every associated child node and push the value and its operation into a stack and viola, you have the required mathematical combinations.

Not only that, you can change the target value to any number you wish without having to recalculate the combinations since it would only traverse the tree until it finds the target number.

 

[f95toli]

I donät think you can solve this problem without listing all possibilities,.Of course you can make an algorithm that terminates early if it finds the right combination, but I don't think it is possible to conclude that there is NO solution without trying all the possibilities.
I believe this is actually a well-known theorem: There is no way to known if is possible to solve a mathematical problem until you have actually tried solving it.

 

[Peter]

Just do it brute force with the one 4-digit number given as input. If you are not allowed to shuffle the numbers, you have no more than 4^3=64 possible expressions. Even a ZX81 will get that done nice and fast.

If you're really bored and got 10KB of RAM to spare (ditch the ZX81 at this point), then use this piece of code for every possible 4-digit number (there are 9000 or 10000 of them, depending on whether you count those with leading zeros), and store the "right" expression set in a single byte (64 possible expressions fit in 5 bit, plus an extra flag bit for "no solution").

Extra points given for: Add another flag bit for "not computed yet", and fork the pre-calculation into a separate background thread whilst taking input from your user or application program interface.

 

[Peter]

... and all this still isn't Highly Technical, but CS class homework

 

[warhorse]

Peter, how do you get that there are only 4^3 combinations with no number shuffling? With no shuffling, the value can be 0-9 so it should be 4^10. Of course the answer for 1234 is the same as 4321 so I think it's just 10 c 4

 

[Peter]

For each given 4-digit number (!) you have three operator positions, with each being one out of +-*/. Thus, you can make 4^3=64 possible expressions out of each possible 4-digit number.

In total, that makes 64 * 10000 possible expressions. Allowing number shuffles doesn't change that total, since you won't leave the space of 4-digit numbers by shuffling digits around.

 

[blahblah99]

You guys are forgetting an important concept here though... CS homework always involve using object oriented programming such as stacks, queues, trees, linked lists, structures, etc etc. True, the brute force way would be to randomly apply mathematical functions to 4 numbers to see if the result is the desired one, but I don't think that is what the professor is looking for... they're grade mainly on how you apply the concepts in your algorithm.

If your algorithm is just as simple as brute force calculations, what's going to stop the program from recalculating a past sample that didn't achieve the results you wanted? In one pass, it may find the result on the first sample, and in the next pass it'll find the result after trying 10000 possibilities, and it'll depend on how you seed the random number generator.

 

[Sahakiel]

Originally posted by: blahblah99
You guys are forgetting an important concept here though... CS homework always involve using object oriented programming such as stacks, queues, trees, linked lists, structures, etc etc. True, the brute force way would be to randomly apply mathematical functions to 4 numbers to see if the result is the desired one, but I don't think that is what the professor is looking for... they're grade mainly on how you apply the concepts in your algorithm.

I think most psoters are actively avoiding solving the problem specifically and just sticking with concepts. It only took ten seconds to come up with a data structure with O(1) results calculation, O(1) insertion, O(1) output, implicitly sorted, incorporates duplication checking, uses relatively few branches, and needs only a single pass. The structure uses 2-4 simple data structures taught in any intermediate level CS course.

If your algorithm is just as simple as brute force calculations, what's going to stop the program from recalculating a past sample that didn't achieve the results you wanted?

Depends on whether it's faster to check for duplication or just go ahead and calculate the same thing.

In one pass, it may find the result on the first sample, and in the next pass it'll find the result after trying 10000 possibilities, and it'll depend on how you seed the random number generator.

Who said anything about a random number generator?

 

[uart]

Originally posted by: warhorse
Peter, how do you get that there are only 4^3 combinations with no number shuffling? With no shuffling, the value can be 0-9 so it should be 4^10. Of course the answer for 1234 is the same as 4321 so I think it's just 10 c 4

No Warhorse, Peter is not referring to pre-computing every possible outcome for every possible 4 digit number that could be presented. He's simply talking about testing every possible combination of allowable operators for the one number that is actually presented. This is the obvious way to do it and not very difficult at all.

There is no need to impose the constraint of "no digit re-ordering", just test all 3^4 possible operator permutations for all possible factorial(4) digit permutations. Yes it's bute force and some permutations will be redundant due to operator commutivity (a+b = b+a, etc) but what the hell, it's only 1944 total permutations and an entry level home computer could solve it in well under a milli-second. This is really a fairly trivial problem.

 

[uart]

Here's some example Pascal code for enumerating all the possible operator permutations. I'll let you figure out how to traverse the 24 digit permutations.

for o1 := 1 to 4 do
 for o2 := 1 to 4 do
  for o3 := 1 to 4 do
   begin
     case o1 of {1=add, 2=subtract, 3=mult, 4=divide}
        1 : temp:=d1 + d2;
        2 : temp:=d1 - d2;
        3 : temp:=d1 * d2;
        4 : temp:=d1 / d2;	
     end {case}

     case o2 of {1=add, 2=subtract, 3=mult, 4=divide}
        1 : temp:=temp + d3;
        2 : temp:=temp - d3;
        3 : temp:=temp * d3;
        4 : temp:=temp / d3;	
     end {case}

     case o3 of {1=add, 2=subtract, 3=mult, 4=divide}
        1 : temp:=temp + d4;
        2 : temp:=temp - d4;
        3 : temp:=temp * d4;
        4 : temp:=temp / d4;	
     end {case}
    end {for}

 

[Peter]

gnnn ... uart ... your example is computing o1 and o2 in the innermost loop. Be nice to your processor, and move that out

for o1 := 1 to 4 do
 case o1 of {1=add, 2=subtract, 3=mult, 4=divide}
 1 : temp1:=d1 + d2;
 2 : temp1:=d1 - d2;
 3 : temp1:=d1 * d2;
 4 : temp1:=d1 / d2; 
 end {case}

 for o2 := 1 to 4 do
 case o2 of {1=add, 2=subtract, 3=mult, 4=divide}
 1 : temp2:=temp1 + d3;
 2 : temp2:=temp1 - d3;
 3 : temp2:=temp1 * d3;
 4 : temp2:=temp1 / d3; 
 end {case}

 for o3 := 1 to 4 do
 begin
 case o3 of {1=add, 2=subtract, 3=mult, 4=divide}
 1 : temp3:=temp2 + d4;
 2 : temp3:=temp2 - d4;
 3 : temp3:=temp2 * d4;
 4 : temp3:=temp2 / d4; 
 end {case}
 end {for}
 end {for}
 end {for}

 

[uart]

Originally posted by: Peter
gnnn ... uart ... your example is computing o1 and o2 in the innermost loop. Be nice to your processor, and move that out

Actually my code is correct Peter. As you earlier noted there are 3^4 operator permutations, and that's exactly what the three nested 4 iteration "for" loops are doing. If you don't nest the "for" loops then you only get 3 x 4 instead of 3^4 combinations, correct! In other words the entire operator evaluation code (o1, o2 and o2) really should be fully within the inner most loop, as originally shown.

Also you dont need "end" statements for the outer two "for" statements as they have no corresponding begin statements. You could put optional "begin" statements in there but they are not needed as the outer two "for's" execute a single compound statement (the inner "for" loops beings these compound statements).

It's the same as in C when you have code like :

for (k=1, k<10, k++)
if (x<20) {
statement1;
statement2;
statement3;
}

You dont need a "{}" pair for the for loop becauce the entire if statment is considered as one single compount statment and "{}" (or begin end in Pascal) are not needed when you only have one statement.

 

[Peter]

Nevermind the Pascal syntax details. No need to teach me, I've passed those exams (and then forgot )

I'm still doing a three-deep nesting of "for" loops. Sorry it didn't look like it, see below for take 2.

My point is that in your innermost loop, the results of D1xD2 and (D1xD2)xD3 (x being the operator) remain the same for all o3 because o1 and o2 don't change. No need to calculate that four times over. Please notice how I use three "temp" variables to store the intermediate results.

But it's all wrong anyway, because we're doing left-to-right math not proper prioritized */ before +- ... so what we'd actually need to do is build expression strings in that nested loop, and then scan and parse. Shall we?

for o1 := 1 to 4 do begin
 case o1 of {1=add, 2=subtract, 3=mult, 4=divide}
 1 : temp1:=d1 + d2;
 2 : temp1:=d1 - d2;
 3 : temp1:=d1 * d2;
 4 : temp1:=d1 / d2; 
 end {case}

 for o2 := 1 to 4 do begin
 case o2 of {1=add, 2=subtract, 3=mult, 4=divide}
 1 : temp2:=temp1 + d3;
 2 : temp2:=temp1 - d3;
 3 : temp2:=temp1 * d3;
 4 : temp2:=temp1 / d3; 
 end {case}

 for o3 := 1 to 4 do begin
 case o3 of {1=add, 2=subtract, 3=mult, 4=divide}
 1 : temp3:=temp2 + d4;
 2 : temp3:=temp2 - d4;
 3 : temp3:=temp2 * d4;
 4 : temp3:=temp2 / d4; 
 end {case}
 end {for}
 end {for}
 end {for}

 

[uart]

I'm still doing a three-deep nesting of "for" loops. Sorry it didn't look like it, see below for take 2.

Ok Peter, i see your point now. Yes you're still doing three nested loops but your code is more efficient because you're not unnecessarily re-evaluating o1 and o2 on every iteration. So both are correct but yours is more efficient, point well taken!

But it's all wrong anyway, because we're doing left-to-right math not proper prioritized */ before +- ...

Yes that's true. Here's a very rough and ready piece of code (to go in the inner loop) and evaluate the operators (o1, o2, o3) in the correct order (taking 1='+', 2='-', 3='*' and 4='/' as before).


b1:=(o1-1) div 2;
b2:=(o2-1) div 2;
b3:=(o3-1) div 2;
b4:=(o4-1) div 2;
{b1..b4 are binary, 0=low precedence (+ or -) and 1 = high precedence (* or /) }

f1 := b1>=b2;
f2 := b2>=b3;
{f1, f2 are boolean (true/false}


{Test all combinations of f1,f2 to determine correct order of evalution}
if f1 and f2 then {evaluate o1, o2, o3};
if f1 and not(f2) then {evaluate o3, o1, o2};
if not(f1) and f2 then {evaluate o2, o3, o1};
if not(f1) and not(f2) then writeln("Error: Impossible outcome, stop overclocking you lamer");


Crude but it should work. Note that becase b1, b2 and b3 are either zero or one that b3>b2>b1 is impossible).


So the only thing unaccounted for now in the evaluation is the possible use of parentheses. Personally I believe that if the problem was meant to include the possible use of parentheses then this should have been explicitly stated (along with +, -, * , /), so I'd choose to ignore that option. I'm a strong believer that problems should be fully and unambiguously specified.

 

[uart]

Quick note: Though I'd avoid parentheses unless explicitly stated in the problem, they would actually be very simple indeed to implement. The above code for operator precedence would be unnecessary and instead you would simply evaluate all six (actually only five are unique) possible oderings of operators for every iteration. The reason of course is that if parentheses are allowed then there is always a particular combination of digits and of parentheses that will give any possible order of evaluation.

 

[sao123]

this theoretical problem is one use as a common event at national mathematical competitions.
It is officially known as the 24-challenge. Highly unlikely that this is a CSE HW because i think there are provisions against that sort of thing.

There are no parenthesis. Order of operations is essentially the game. There is a selected set of 4 numbers between 0-9. Using these 4 numbers one must find the set of 3 operations (+,-,*,/) involved which when computed gives the value 24. There are 4 difficulty levels, and for every set of numbers, there is exactly 1 method for obtaining 24 with every set having a guaranteed answer.


I believe that after attending one of these competitions and taking part in the event, the best algorithm is reverse engineering the number.
Because of order of operation I recommend starting with finding any added or subtracted number. (this is because there are no parenthesis and order of operations would deem these to be the last operations performed) Then you find the multiplication and division operations. Develop this into a recursive algorithm and you have a fast accurate solution.

 

[uart]

Interesting SAO, I didn't know that it was a widely used "challange". If that's the case then having a program to generate a list of such numbers would be quite useful, perhaps that was the motivation for this question.

Just out of interest is anyone willing to hazzard a guess about just how many 4 digit numbers do infact satisfy this "24" condition.

Challange: Out of all ten thousand four digit numbers, 0000 ... 9999, how many meet "24" condition given that,

1. Parentheses are not allowed.

2. Parentheses are allowed.

PS I wont put my "guess" here as I already know the exact anwsers .

 

[SmoiL]

If parens are not allowed, is 2480 close? I whipped together a quik program but have not carefully gone through the logic which most likely means there are mistakes.

~SmoiL

err #1:changed to 3956 after I found my first mistake, any guesses as to how many more are left? [=
err #2:my results are bloated, as 0+0+3*8 and 0*0+3*8 are counted, etc. new number is 2480
err #3:apparently I have a problem with certain fractions....2480 is also high.

 

[sao123]

Indeed there are not that many possible combinations:

consider this... assuming 1234 was a valid combination making 24...
All of the following values would be recognized as the same problem card, and it would have 1 unique solution
The answer being 1 x 2 x 3 x 4 = 24.

1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321....

note that using probability for any 4 unique digit combination where order isnt important....
4 choose 1 x 3 choose 1 x 2 choose 1 x 1 choose 1 = 24 combinations all being the same problem card.

then u must account for 4 digit numbers having duplicates...
1 set of 4, 1 set of 3, 1 set of 2, 2 sets of 2

There are ________ initial max useable combinations (no duplicates) then I'll leave it up to you to figure how many are valid as having a 24 solution.

---
Oh I may have been wrong about each having only 1 unique solution per your example... I believe that those with 2 or more sulutions have been included and were categorized as level 1 easy. so u dont have to exclude them.