4 ms·

Operator Algebra

5 points by iou 10y ago

CarolineW 10y ago
Really crap code, but here's my 5 minute solution: #!/usr/bin/python from itertools import permutations vs = [ 1, 3, 4, 6 ] def run_tests( rtn, vs ): if len(vs) == 1: print rtn, ':', vs[0] return run_tests( rtn+' +', [ vs[0]+vs[1] ] + vs[2:] ) run_tests( rtn+' -', [ vs[0]-vs[1] ] + vs[2:] ) run_tests( rtn+' r', [-vs[0]+vs[1] ] + vs[2:] ) run_tests( rtn+' *', [ vs[0]*vs[1] ] + vs[2:] ) if vs[1] != 0: run_tests( rtn+' /', [ float(vs[0])/vs[1] ] + vs[2:] ) if vs[0] != 0: run_tests( rtn+' v', [ float(vs[1])/vs[0] ] + vs[2:] ) for p in permutations( vs ): rtn = `p` run_tests( rtn, list(p) ) Run this looking for the desired answer: ./SolverHack.py | grep " 24" It produces: (3, 4, 1, 6) / r v : 24.0 (4, 3, 1, 6) v r v : 24.0 As I say: * crappy code, * complete hack, * done in 5 minutes, * solves the problem.
- iou 10y ago
  Neat! Looks pretty compact. My code was pretty bad too. This is going to probably sound like a dumb question, but what are r and v here? Is that how you're conveying you parentheses? The other extensions of this I was thinking of are: * Can your code identify correct solutions when more numbers are added to the array? * What modifications need to be made to allow it to handle other operators, such as exponents (Right-To-Left associative unlike the LTR associative operators in the first example) I suspect that the cleanest solution would utilize the shunting-yard algorithm (https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm).
  - CarolineW 10y ago
    > ... what are r and v here? The program works by preloading a stack and then applying each permitted operator to the top two recursively until only a single value remains. The operators are, obviously, addition, subtraction, multiplication and division, but we also have to allow reverse subtraction and reverse division to recognise that naive subtraction and division are non-commutative. > Can your code identify correct > solutions when more numbers are > added to the array Yes - easiest for you just to try it. > What modifications need to be > made to allow it to handle other > operators, such as exponents ... Just an extra line for each operator, two if the operator is non-commutative. > ... exponents (Right-To-Left > associative unlike the LTR > associative operators in the > first example) The issue of associativity is already covered as a fundamental part of algorithm. > ... suspect that the cleanest > solution would utilize the > shunting-yard algorithm This effectively is a cut-down version of that. Interleaving the operators into the stack of values has many problems, always having to have enough values above each operator, etc. Instead this externalises the operators from the stack, which is what makes it work.

5 points by iou 10y ago

Really crap code, but here's my 5 minute solution: #!/usr/bin/python from itertools import permutations vs = [ 1, 3, 4, 6 ] def run_tests( rtn, vs ): if len(vs) == 1: print rtn, ':', vs[0] return run_tests( rtn+' +', [ vs[0]+vs[1] ] + vs[2:] ) run_tests( rtn+' -', [ vs[0]-vs[1] ] + vs[2:] ) run_tests( rtn+' r', [-vs[0]+vs[1] ] + vs[2:] ) run_tests( rtn+' *', [ vs[0]*vs[1] ] + vs[2:] ) if vs[1] != 0: run_tests( rtn+' /', [ float(vs[0])/vs[1] ] + vs[2:] ) if vs[0] != 0: run_tests( rtn+' v', [ float(vs[1])/vs[0] ] + vs[2:] ) for p in permutations( vs ): rtn = `p` run_tests( rtn, list(p) ) Run this looking for the desired answer: ./SolverHack.py | grep " 24" It produces: (3, 4, 1, 6) / r v : 24.0 (4, 3, 1, 6) v r v : 24.0 As I say: * crappy code, * complete hack, * done in 5 minutes, * solves the problem.

iou 10y ago
Neat! Looks pretty compact. My code was pretty bad too. This is going to probably sound like a dumb question, but what are r and v here? Is that how you're conveying you parentheses? The other extensions of this I was thinking of are: * Can your code identify correct solutions when more numbers are added to the array? * What modifications need to be made to allow it to handle other operators, such as exponents (Right-To-Left associative unlike the LTR associative operators in the first example) I suspect that the cleanest solution would utilize the shunting-yard algorithm (https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm).
- CarolineW 10y ago
  > ... what are r and v here? The program works by preloading a stack and then applying each permitted operator to the top two recursively until only a single value remains. The operators are, obviously, addition, subtraction, multiplication and division, but we also have to allow reverse subtraction and reverse division to recognise that naive subtraction and division are non-commutative. > Can your code identify correct > solutions when more numbers are > added to the array Yes - easiest for you just to try it. > What modifications need to be > made to allow it to handle other > operators, such as exponents ... Just an extra line for each operator, two if the operator is non-commutative. > ... exponents (Right-To-Left > associative unlike the LTR > associative operators in the > first example) The issue of associativity is already covered as a fundamental part of algorithm. > ... suspect that the cleanest > solution would utilize the > shunting-yard algorithm This effectively is a cut-down version of that. Interleaving the operators into the stack of values has many problems, always having to have enough values above each operator, etc. Instead this externalises the operators from the stack, which is what makes it work.