{"id":5421,"date":"2018-03-18T13:00:52","date_gmt":"2018-03-18T13:00:52","guid":{"rendered":"http:\/\/writeasync.net\/?p=5421"},"modified":"2018-04-27T14:58:23","modified_gmt":"2018-04-27T14:58:23","slug":"four-fours","status":"publish","type":"post","link":"https:\/\/writeasync.net\/?p=5421","title":{"rendered":"Four fours"},"content":{"rendered":"

Back in elementary school, I became aware of the four fours<\/a> puzzle. It is a seemingly simple mathematical exercise where you must generate all the integers from 1 to 100 using arithmetic expressions and the digit 4 exactly four times. A few sample solutions:<\/p>\n

    \n
  1. 44 \/ 44<\/li>\n
  2. 4 + 4 – 4 – sqrt(4)<\/li>\n
  3. (4 + 4 + 4)\/4<\/li>\n<\/ol>\n

    (For perhaps more than you ever wanted to know about the puzzle, I recommend David Wheeler’s excellent Definitive Four Fours Answer Key<\/a>.)<\/p>\n

    Over the years, I have solved the puzzle a few times by hand (sometimes assisted by a TI calculator<\/a>) but had never seriously attempted it programmatically. That all changes now. I present to you my Four4Sample project on GitHub<\/a>. The rest of this post describes the design and approach of the code.<\/p>\n

    Before I even wrote a line of code, I spent some time thinking about how to build up the solution expressions. My first instinct was that traditional infix notation<\/a> (e.g. “4 + 4” — the operator “+” appears in between the operands) would be rather complicated to deal with. Thus, I set out to write an RPN<\/a> expression evaluator, using postfix notation (e.g. “4 4 +” — the operator “+” appears after<\/em> the operands). Postfix has the distinct advantage of requiring absolutely no operator precedence handling; any operator can be applied right away.<\/p>\n

    The first couple dozen commits built up the base infrastructure to handle rational number calculations. By that point<\/a>, my calculator could handle the basic arithmetic operators, square root (“R”) and factorial (“!”), along with raw operands for all the numeral 4 expressions (e.g. “4”, “.4”, and “.4_” representing the repeating decimal .4).<\/p>\n

    The next interesting challenge was handling of invalid results. Several commits<\/a> were dedicated to NaN<\/a> propagation (e.g. “4 4 – 4 – R” should result in “NaN” due to the attempt of taking the square root of -4). Given this “NaN hammer,” I chose to treat every error condition as “NaN”. This included too many operands (e.g. “4 4”), too few operands (e.g. “4 +”), division by zero, and so on. Many more commits<\/a> and a few renames later, I had an Expression class with a good enough Eval method.<\/p>\n

    Thinking ahead a few steps, I knew I would need to recursively produce expressions to solve the puzzle. For this reason, I began to make all the data structures immutable<\/a>. This would make it much easier to generate new expressions from old ones without altering previous data, and hence seamlessly allow recursive branching and backtracking. It did make the code a bit weirder, though. (NumberStack as a struct with exactly four item fields?!)<\/p>\n

    The next set of commits<\/a> implemented the append operations and tracking of how many digits were used so far. So for example emptyExpr.Append(\"44\").Append(\"4\").Append(\"+\")<\/code> would produce the result 48<\/code> with digit count of 3.<\/p>\n

    Now in the home stretch, I began to create the ExpressionSearch class<\/a>. This was the core recursive algorithm to generate all the valid expressions. In plain English, it does the following, starting from a completely empty expression:<\/p>\n