CODEWITHSUNDEEP
pythonpython-3.xalgorithm
Faheem Azeemi
Faheem Azeemi

Reputation: 33

Solving Canadian Computing Competition: "24"

I am trying to solve the problem above (Here is the link: https://dmoj.ca/problem/ccc08s4) using python but am running into difficulties. The problem asks to determine if 4 number when multiplied, subtracted, added, or divided can yield 24. Parenthesis are also allowed to specify precedence. If such a value is not possible then output the greatest number less than 24.

My solution was to create all permutations of the 4 numbers and then the permutations of all the operations (multiplication, division, subtraction, and addition) in sets of 3 since you can only have 3 operations at one time. Then I would loop over the numbers and apply all the operations yielding all possibilities but this would be incorrect since I did not incorporate parenthesis in the problem. That is where I am struggling. I am not really sure how to incorporate parenthesis.

I feel like I am overcomplicating the problem and the only solution I can think of is finding permutations of multiplication division subtraction, addition, (, and ) but this would still be incorrect since some equations can have more than one set of parenthesis.

I am really new to competitive programming and I feel like I am missing something obvious. I would love some feedback and help.

Upvotes: 0

Views: 135

Answers (1)

Y.T.
Y.T.

Reputation: 2739

One way is to consider the postfix expression instead of the infix expression. E.g, for the infix expression (A+B)*(C-D), we'll consider the postfix expression AB+CD-* instead.

It can be observed that there will be no need for parenthesis in postfix expression, which makes them more friendly to machine.

So you just need to generate all valid postfix expression and evaluate them, for example by using the method here: https://www.geeksforgeeks.org/stack-set-4-evaluation-postfix-expression/

Another more implementation-friendly way is to use recursion to generate all possible order of operation.

Upvotes: 1

Related Questions