Operator Algebra | Hacker News Reader

Operator Algebra

josephkirwin.com

5 pointsiou3 comments

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.

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).

  > ... 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.

Reply on news.ycombinator.com