{"id":415,"date":"2007-08-25T16:44:37","date_gmt":"2007-08-25T06:44:37","guid":{"rendered":"http:\/\/www.somethinkodd.com\/oddthinking\/2007\/08\/25\/solving-the-four-fours-puzzle\/"},"modified":"2007-10-07T19:17:56","modified_gmt":"2007-10-07T09:17:56","slug":"solving-the-four-fours-puzzle","status":"publish","type":"post","link":"https:\/\/www.somethinkodd.com\/oddthinking\/2007\/08\/25\/solving-the-four-fours-puzzle\/","title":{"rendered":"Solving the Four Fours Puzzle"},"content":{"rendered":"<p><a href=\"http:\/\/www.mikepope.com\/blog\/DisplayBlog.aspx\">Mike Pope<\/a> published a <a href=\"http:\/\/www.mikepope.com\/blog\/AddComment.aspx?blogid=1804\">little maths puzzle<\/a>.<\/p>\n<blockquote><p>\nThe challenge is to calculate every integer value between 0 and 100 using only the number 4. <\/p>\n<p>Rules:<\/p>\n<ul>\n<li>You may use <strong>only the digit 4<\/strong>.<\/li>\n<p><\/p>\n<li>Important: You may use <strong>no more than four<\/strong> 4&#8217;s. <\/li>\n<p><\/p>\n<li>You may use (only) the following operators:\n<p><b>+<\/b> (addition)<br \/><b>&#8211;<\/b> (subtraction)<br \/><b>x<\/b> or <b>*<\/b> (multiplication)<br \/><b>\/<\/b> (division)<br \/><b>&radic;<\/b> (square root)<br \/><b>!<\/b> (factorial)\n<\/li>\n<li>You can combine the operators to create any (otherwise legal) expression. Parentheses are ok.<\/li>\n<\/ul>\n<p>You can combine the operators to create any (otherwise legal) expression. Parentheses are ok.\n<\/p><\/blockquote>\n<div class=\"aside\">Note: This article describes how I solved this puzzle but does not contain any real spoilers. I reveal the answers to a handful of the easy problems, as explanation of the general principles.<\/div>\n<p>Okay, let&#8217;s start.<\/p>\n<p>I need to write down 101 answers. That will take a lot of paper and rote work. Why don&#8217;t I use a computer to record my progress?<\/p>\n<p>This puzzle is going to take a bit of arithmetic. That&#8217;s going to lead to lots of silly mistakes and rote work. That&#8217;s clumsy and not fun. Why don&#8217;t I get the computer to do the arithmetic?<\/p>\n<p>Using the built-in calculator is just as error prone, and Excel is a bit clumsy for this &#8211; too much rote work. Why don&#8217;t I throw together a little calculator in Python?<\/p>\n<p>Brackets are clumsy to parse. Let&#8217;s use our old friend <a href=\"http:\/\/www.somethinkodd.com\/oddthinking\/2005\/10\/24\/whatever-happened-to-rpn\/\">RPN<\/a>!<\/p>\n<p>Tappity-tap-tap! Look, I&#8217;ve made a stack-based state-machine that handles the operators Four, Add, Substract, Multiply, Divide, Factorial and Square Root. It stores the results on a stack, and each function returns whether there was an error or not. A Result function returns the result when it is required.<\/p>\n<div class=\"aside\">Later, I spend some time optimising factorial to only support 1! to 15! and use a look-up table, for a large increase in speed.<\/div>\n<p>Tappity-tap-tap! A simple parser that reads a string and calls the appropriate functions.<\/p>\n<div class=\"aside\">Later the big &#8216;if&#8217;..&#8217;elif&#8217; statement is replaced with a dictionary of functions, for a threefold increase in speed.<\/div>\n<p>The parser reads in a string containing any of the following characters: &#8220;4&#8221;, &#8220;+&#8221;, &#8220;-&#8220;, &#8220;*&#8221;, &#8220;\/&#8221;, &#8220;!&#8221; and &#8220;R&#8221;. (&#8220;R&#8221; = square root. The &radic; symbol was causing character-encoding issues I couldn&#8217;t be bothered solving.) The parser then calls the appropriate transition on the state-machine.<\/p>\n<p>That leads to ambiguity for &#8220;44&#8221; &#8211; is it forty-four or two fours on the stack. I change the Four operator to remember whether the last operator was a four &#8211; if so, multiply it by 10 and add 4. I also add a &#8220;,&#8221; operator that merely separates fours, so now &#8220;44&#8221; and &#8220;4,4&#8221; are distinguishable.<\/p>\n<p>When the parser gets to the end of the string, it returns the result (if it is an integer between 0 and 100) or an error.<\/p>\n<p>Okay, now I can write <code>parse(\"4,4!+4\/\")<\/code> and get 7 &#8211; i.e. ((4+(4!))\/4) = 7.<\/p>\n<hr \/>\n<p>I can going through the numbers from 0 to 100 and see if I can come up with some formulae.<\/p>\n<p>Let&#8217;s see:<\/p>\n<ul>\n<li>4,4- = 0<\/li>\n<li>4,4\/ = 1<\/li>\n<li>4,4+4\/ = 2<\/li>\n<li>4,4+4+4\/ = 3<\/li>\n<li>4 = 4<\/li>\n<\/ul>\n<p>But wait!  While I am trying to find these expressions, I keep finding solutions for other numbers by mistake. I may as well record these when I think of them for later. Hold on&#8230; that sounds like rote work.<\/p>\n<p>Tappity-tap-tap! Here&#8217;s a simple table that records every expression against the result it gives (so long as it is an integer between 0 and 100).<\/p>\n<div class=\"aside\">A bit later, I add a quick improvement: Where two expressions give the same answer, store the shorter one.<\/div>\n<p>Now, I can blithely guess away &#8211; 4!4*4+ = ? &#8211; and the computer keeps track of the useful solutions I find along the way.<\/p>\n<hr \/>\n<p>I may as well enter all the legal one, two and three character expressions to cover quickly cover the answers to  2, 4, 24 and 44.<\/p>\n<p>What about all the four character ones. Takes me a bit longer &#8211; there are 21 of them, but now I have covered 12 numbers.<\/p>\n<p>Well, wait a minute. I am doing rote work coming up with legal combinations!<\/p>\n<p>Let&#8217;s get Python to generate all the five character strings!<\/p>\n<div class=\"aside\">\nOoh, optimisation time: <\/p>\n<ul>\n<li>The first digit may only be a 4.<\/li>\n<li>The second digit may only be a 4, &#8216;,&#8217;, ! or R.<\/li>\n<li>The remaining digits can only appear if the preceding characters don&#8217;t lead to an error, such as division by zero.<\/li>\n<\/ul>\n<p>Let&#8217;s look at the profile. Ouch, it is all string handling. Let&#8217;s improve that. Try again. Tappity-tap-tap. Factorials? Cache them. Tappity-tap-tap. There, that&#8217;s much faster!\n<\/p><\/div>\n<p>Now I can just set it going, sit back and watch the results! <a href=\"http:\/\/www.somethinkodd.com\/oddthinking\/2005\/05\/21\/puzzling-over-puzzles\/\">That&#8217;s my way of solving a puzzle<\/a>!<\/p>\n<div class=\"aside\">Okay, I admit &#8211; there is too much brute force to call this an elegant solution.<\/div>\n<hr \/>\n<p>This graph shows how many solutions I found as I increased the total legal length of the formula. <\/p>\n<p><a href='http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2007\/08\/fourspuzzle_original_b.png' title='Graph of Success Rate'><img src='http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2007\/08\/fourspuzzle_original_b.thumbnail.png' alt='Graph of Success Rate' \/><\/a><\/p>\n<p>By the time I get to formulae of length 13, I have found 76 of 101 answers, and it is clearly tapering off. <\/p>\n<p>This graph below shows how long each iteration took (wall time, so it isn&#8217;t a very good measure &#8211; it is affected by what else I was doing on my computer at the same time). Note carefully that it uses a logarithmic scale!<\/p>\n<p><a href='http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2007\/08\/fourspuzzle_original_a.png' title='Graph of Time Taken'><img src='http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2007\/08\/fourspuzzle_original_a.thumbnail.png' alt='Graph of Time Taken' \/><\/a><\/p>\n<div class=\"aside\">The dashed yellow line shows the theoreticaly number of combinations of characters. The real lines don&#8217;t follow this curve, because I have optimised away formulae that start out with an error (e.g. there is no point suffixing more operators to a formula that starts by finding the factorial of a negative.)<\/div>\n<p>The next iteration is going to take about 16 hours, and is likely to not add many more solutions. <\/p>\n<p>Hmmm&#8230; This isn&#8217;t going well. It is certainly going to take a long time to find all 101 solutions, and it doesn&#8217;t even look like it is going to be soluble. Have I got a bug?<\/p>\n<hr \/>\n<p>Wait up! Now there is an <a href=\"http:\/\/www.mikepope.com\/blog\/AddComment.aspx?blogid=1804\">update to the original post<\/a>! More operations are permitted!<\/p>\n<p>Exponent? Easy. <\/p>\n<div class=\"aside\">Later, limited the legal range of the result from &plusmn;10<sup>7<\/sup>, to stop time wasting and avoid overflows.<\/div>\n<p>Concatenation? I was already supporting that; I had assumed it was legal from context.<\/p>\n<p>Decimal? I add it as a postfix operation &#8220;.&#8221; that maps 4 to &#8220;0.4&#8221;, 44 to &#8220;0.44&#8221; etc.  So if I write &#8220;444.&#8221;, I will get the result 0.444.<\/p>\n<p>Overbar? This is trickier, and takes a bit more thought.<\/p>\n<p>First, let&#8217;s represent it as an underscore to save dealing with character-encoding issues!<\/p>\n<p>The only legal case I can see for this operator is directly after &#8220;4.&#8221; (which is 0.4, based on the new postfix decimal operator. The overbar would turn that into 0.4444&#8230;) <\/p>\n<p>My point is that you <em>can&#8217;t<\/em> say &#8220;4,4,4+\/_&#8221; and expect the overbar operator to work out as (4\/(4+4)) = 0.5, and then convert that to 0.55555555.<\/p>\n<p>You could use it after &#8220;44._&#8221;. That would also translate to 0.4444&#8230;, but that is longer than &#8220;4._&#8221; so it isn&#8217;t a preferred solution. Let&#8217;s just rule it out.<\/p>\n<p>So really, we just need only symbol that can only take a 4 numeral and convert it to 0.4444&#8230; So &#8220;4_4+&#8221; now equals 4\/9+4. Done.<\/p>\n<div class=\"aside\">I could even be more efficient, and add a new digit (say &#8220;#&#8221;) which is equal to 0.4444&#8230;, but that will interfere with my existing four-counting code. Either way will do, so I just stuck to requiring a 4 to appear first.<\/div>\n<p>This introduces an issue with rounding that I didn&#8217;t properly cover before. Is 25.9999&#8230; equal to 26? Before the software said no. Now, it accepts it if the epsilon error is less than 10<sup>-8<\/sup>.<\/p>\n<hr \/>\n<p>Let&#8217;s start again, with the new rules.<\/p>\n<p><a href='http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2007\/08\/fourspuzzle_newrules_a.png' title='Graph of Success Rate - New Rules'><img src='http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2007\/08\/fourspuzzle_newrules_a.thumbnail.png' alt='Graph of Success Rate - New Rules' \/><\/a><br \/>\nOoh, the success rate is clearly higher, starting when the formula is five characters in length.<\/p>\n<p>I still haven&#8217;t solved it completely, but I am hoping that all is left is the waiting&#8230; (It is running much slower &#8211; not only do the extra operators introduce more combinations, but exponentiation is slow.)<\/p>\n<p>Expect an update later on the progress of this latest run!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The challenge is to calculate every integer value between 0 and 100 using only the number 4. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"","footnotes":""},"categories":[33],"tags":[55,69,54],"class_list":["post-415","post","type-post","status-publish","format-standard","hentry","category-puzzle-solving","tag-puzzle","tag-software","tag-solution"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/415","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=415"}],"version-history":[{"count":0,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/415\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=415"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=415"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=415"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}