SDPS_Brute

seednum

This is a small console application built to solve the puzzles presented by a fellow student’s mobile math game. It gives you access to 7 basic arithmetic functions and a single digit. The goal is to reach a target value, using only those tools. The secondary goal is to complete the task with the fewest instances of the given digit.

I first solved a few puzzles by hand. With advice by the student (who had played the game more than any sane man should) I started to develop a basic strategy for how to quickly solve puzzles. The functions given are +, -, *, /, ^, square root, and factorial. Two of these take in a single value, square root and factorial. The other five take in two.

For n digits:

I decided to only allow for factorial and square root to be used on the given digit, and build up a set of constants from the 5 possible combinations of these two. Being x, sqrt(x), x!, sqrt(x!), and (sqrt(x))!. I throw out any of the ones resulting in non-integers. So we have a list of n choices from these constants.

Next is the function application and order of operations. I create a binary tree of n-1 digits, initialized so that it is only left descending. This tree represents the order of operations. It uses a solver function recursively downward that ends in the root reaching the statement value. I also create a list of n-1 s choices from the functions between any 2 digits.

We then iterate through every combination of functions and digits, stopping if we reach the target value. If not, we move the left-most leaf of the tree directly right of the leaf directly right of it, and reset the lists to iterate again.

This method is entirely unwieldy, and STILL does not cover the entire search space.

It has a worst case step count of… (25^n)/5 * (2(n-1) choose (n-1))

Dear god why did I do this. Source

Thoughts:

  • If a solving tree member returns a non-integer, quit the solution process and iterate.
  • Some function combinations are useless. Scan for these ( find …*(x/x) structures)
  • Perhaps use an exploratory method using factor similarity as a metric for shortest path.
  • Tree members ALSO need a state, as a factorial/ square root could also be applied to a statement fragment. This is a bit of a problem though as factorial could be applied recursively…
  • Half the order permutations are identical, so after the symmetric case I can stop