Expression that equals its length Given a number, find an expression in words equaling that number, with a length of that number.

Thus, to an input of 15, you might output sixteen minus one, which has fifteen characters (not counting spaces). If multiple solutions exist, print whichever you want. If none exist, print impossible

Use only the operators plus, minus, times, and divided by. Operators are evalutated left to right.

Format 1234 as one thousand two hundred thirty four. Note the absence of "and", and that there are no dashes or commas.

The input and all numbers used in the output must be positive integers less than 10,000.

The input will be given as a command line argument. Print to standard output.

Examples

1: impossible
4: four
7: impossible
13: eight plus five (you could also output "five plus eight")
18: one plus two times six (note that operators are evaluated from left to right)
25: one thousand divided by forty
JS, 1719/1694

Theory

Unfortunately, the rule set that you provide may not be a wise decision from a mathematical point of view. In fact, using a smaller subset of rules, you can find a solution for every number in the given interval


  


except for


  


for which there is no solution.

Reduced rule set

Consider the following subet of rules:


Use only the operators plus, minus and times.
You don't need to implement multiple occurrences of plus or minus in your expressions.
You don't need to implement neither division nor operator associativity (as their solution set is already covered by the first rule).


The reason why this works is that, as you discussed earlier with @Qwix, you allow boring answers, that is, expressions that end in the regular expression
( times one)+$. Allowing this, each number in the given interval will have a solution. 

When you replied in one of your comments,


  @Qwix Yes; boring answers are acceptable, although that one doesn't
  work for 104, 105, 106, 107, 108, 109, 110, or 111. –


you were absolutely right: This does not work when you're trying to build your expression starting with the numbers themselves, i.e. one hundred four times one times one … or any other of those numbers.

If however, your expression starts with an expression whose evaluation equals one of the given numbers, you're out of luck. For example, note that 17 + 87 is indeed 104, so we could write 104 as:

104: seventeen plus eighty seven times one times one times one times one times one times one times one times one times one times one


To see that this subset works, save this file as num.js and make sure that SpiderMonkey, a JavaScript engine for command lines, is installed on your system.

The algorithm


Let us define the property K for positive integers as the state of the number having N letters and having a value of N.
Let us further define the property F for an expression as the state of its word conversion being 8k-times shorter than its evaluation with k ∈ ℕ. F stands for "fillable" and describes whether or not we can fill the word conversion of the expression with expressions of length 8 (i.e. " times one") such that the resulting expression might get the property N.


We then proceed as follows:


Convert the input number to words.
Check if the input number has property K. 


If it does, return the words (4 is the only number with this property, unfortunately).
If it doesn't, proceed. 

For all two-operand expressions (additions, subtractions and multiplications in this order) that result in the input number, check if their evaluation has property K.


If it does, return the words.
If it doesn't, check if the two-operand expression has property N.


If it does, fill the expression with " times one" and check if the evaluation of the resulting expression has property K.


If it does, return the words
If it doesn't, proceed

If it doesn't, proceed


Go drink a coffee


Practice

num.js (for SpiderMonkey / command lines)

function X(e,t){return e+&quot;: &quot;+t}function P(e){var n,t;for(n=1;.5*e+(e%2===0?1:0)&gt;n;++n){if(t=C.s(n)+&quot; plus &quot;+C.s(e-n),t.replace(/\s/g,&quot;&quot;).length===e)return t;if(F(e,t)&amp;&amp;e&gt;t.length)return G(e,t)}return!1}function M(e){var t,n;for(t=L;t&gt;1;--t){if(0&gt;t-e)return!1;if(n=C.s(t)+&quot; minus &quot;+C.s(t-e),n.replace(/\s/g,&quot;&quot;).length===e)return n;if(F(e,n)&amp;&amp;e&gt;n.length)return G(e,n)}return!1}function F(e,t){return(e-t.replace(/\s/g,&quot;&quot;).length)%8===0}function G(r,t){var e,i=(r-t.replace(/\s/g,&quot;&quot;).length)/8,n=&quot;&quot;;for(e=0;i&gt;e;++e)n+=&quot; times one&quot;;return t+n}function T(e){var t,n,r;if(F(e,C.s(e)))return G(e,C.s(e));for(t=1,n=1;t&lt;Math.floor(Math.sqrt(e));++t){for(;e&gt;tn;)++n;if(tn===e&amp;&amp;(r=C.s(t)+&quot; times &quot;+C.s(n),r.replace(/\s/g,&quot;&quot;).length===e))return r}return!1}function Y(e){var n,r,t;return e===C.s(e).length?X(e,C.s(e)):(n=P(e))?X(e,n):(r=M(e))?X(e,r):(t=T(e),t?X(e,t):X(e,&quot;impossible&quot;))}var L=1e4,C=new function(){return this.o=[&quot;&quot;,&quot;one&quot;,&quot;two&quot;,&quot;three&quot;,&quot;four&quot;,&quot;five&quot;,&quot;six&quot;,&quot;seven&quot;,&quot;eight&quot;,&quot;nine&quot;],this.t=[&quot;&quot;,&quot;&quot;,&quot;twenty&quot;,&quot;thirty&quot;,&quot;forty&quot;,&quot;fifty&quot;,&quot;sixty&quot;,&quot;seventy&quot;,&quot;eighty&quot;,&quot;ninety&quot;],this.T=[&quot;ten&quot;,&quot;eleven&quot;,&quot;twelve&quot;,&quot;thirteen&quot;,&quot;fourteen&quot;,&quot;fifteen&quot;,&quot;sixteen&quot;,&quot;seventeen&quot;,&quot;eighteen&quot;,&quot;nineteen&quot;],this.s=function(e){return e?this.m(e):&quot;zero&quot;},this.m=function(e){return e&gt;=1e6?this.m(Math.floor(e/1e6))+&quot; million&quot;+(e%1e6!==0?&quot; &quot;+this.Z(e%1e6):&quot;&quot;):this.Z(e)},this.Z=function(e){return e&gt;=1e3?this.h(Math.floor(e/1e3))+&quot; thousand&quot;+(e%1e3!==0?&quot; &quot;+this.h(e%1e3):&quot;&quot;):this.h(e)},this.h=function(e){return e&gt;99?this.o[Math.floor(e/100)]+&quot; hundred&quot;+(e%100!==0?&quot; &quot;+this.U(e%100):&quot;&quot;):this.U(e)},this.U=function(e){return 10&gt;e?this.o[e]:e&gt;=10&amp;&amp;20&gt;e?this.T[e-10]:this.t[Math.floor(e/10)]+(e%10!==0?&quot; &quot;+this.o[e%10]:&quot;&quot;)},this};print(Y(0|arguments[0]))

num.js (for browsers)

The given code from above can't work for browsers due to its last command, which grabs the command line arguments in order to make a nice command out of the given script.

In order to run the JavaScript code directly from within your browser, select this piece of the above code:


function X(e,t){return e+&quot;: &quot;+t}function P(e){var n,t;for(n=1;.5*e+(e%2===0?1:0)&gt;n;++n){if(t=C.s(n)+&quot; plus &quot;+C.s(e-n),t.replace(/\s/g,&quot;&quot;).length===e)return t;if(F(e,t)&amp;&amp;e&gt;t.length)return G(e,t)}return!1}function M(e){var t,n;for(t=L;t&gt;1;--t){if(0&gt;t-e)return!1;if(n=C.s(t)+&quot; minus &quot;+C.s(t-e),n.replace(/\s/g,&quot;&quot;).length===e)return n;if(F(e,n)&amp;&amp;e&gt;n.length)return G(e,n)}return!1}function F(e,t){return(e-t.replace(/\s/g,&quot;&quot;).length)%8===0}function G(r,t){var e,i=(r-t.replace(/\s/g,&quot;&quot;).length)/8,n=&quot;&quot;;for(e=0;i&gt;e;++e)n+=&quot; times one&quot;;return t+n}function T(e){var t,n,r;if(F(e,C.s(e)))return G(e,C.s(e));for(t=1,n=1;t&lt;Math.floor(Math.sqrt(e));++t){for(;e&gt;tn;)++n;if(tn===e&amp;&amp;(r=C.s(t)+&quot; times &quot;+C.s(n),r.replace(/\s/g,&quot;&quot;).length===e))return r}return!1}function Y(e){var n,r,t;return e===C.s(e).length?X(e,C.s(e)):(n=P(e))?X(e,n):(r=M(e))?X(e,r):(t=T(e),t?X(e,t):X(e,&quot;impossible&quot;))}var L=1e4,C=new function(){return this.o=[&quot;&quot;,&quot;one&quot;,&quot;two&quot;,&quot;three&quot;,&quot;four&quot;,&quot;five&quot;,&quot;six&quot;,&quot;seven&quot;,&quot;eight&quot;,&quot;nine&quot;],this.t=[&quot;&quot;,&quot;&quot;,&quot;twenty&quot;,&quot;thirty&quot;,&quot;forty&quot;,&quot;fifty&quot;,&quot;sixty&quot;,&quot;seventy&quot;,&quot;eighty&quot;,&quot;ninety&quot;],this.T=[&quot;ten&quot;,&quot;eleven&quot;,&quot;twelve&quot;,&quot;thirteen&quot;,&quot;fourteen&quot;,&quot;fifteen&quot;,&quot;sixteen&quot;,&quot;seventeen&quot;,&quot;eighteen&quot;,&quot;nineteen&quot;],this.s=function(e){return e?this.m(e):&quot;zero&quot;},this.m=function(e){return e&gt;=1e6?this.m(Math.floor(e/1e6))+&quot; million&quot;+(e%1e6!==0?&quot; &quot;+this.Z(e%1e6):&quot;&quot;):this.Z(e)},this.Z=function(e){return e&gt;=1e3?this.h(Math.floor(e/1e3))+&quot; thousand&quot;+(e%1e3!==0?&quot; &quot;+this.h(e%1e3):&quot;&quot;):this.h(e)},this.h=function(e){return e&gt;99?this.o[Math.floor(e/100)]+&quot; hundred&quot;+(e%100!==0?&quot; &quot;+this.U(e%100):&quot;&quot;):this.U(e)},this.U=function(e){return 10&gt;e?this.o[e]:e&gt;=10&amp;&amp;20&gt;e?this.T[e-10]:this.t[Math.floor(e/10)]+(e%10!==0?&quot; &quot;+this.o[e%10]:&quot;&quot;)},this}

Now, paste it into your browser's JavaScript console, so you can produce the same results from within your browser with, for example:


Y(1234);


Examples (command line)

chiru@chiru ~ $ js num.js 28
28: fourteen plus fourteen times one
chiru@chiru ~ $ js num.js 7
7: impossible
chiru@chiru ~ $ js num.js 42
42: nine thousand sixty minus nine thousand eighteen


And in order to see the trick with which you can make each number work, just have a look at the boring answer for js num.js 1337:
1337: ten plus one thousand three hundred twenty seven times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one

The provided codes generates valid solutions for the given interval (and probably even above, you'd only have to raise the value of the variable L).

Statistics

I was interested in "how boring" the expressions were (or: how much the substring times one was used per expression within this algorithm), as this part was responsible for finding a solution for every number within the given interval. See for yourselves: 

x: n-th expression (min. 0, max. 10,000)

y: number of occurences of substring " times one" within expression (min. 0, max. 1245)



Conclusions:


The expressions tend to get more and more boring in a linear manner.
Over 99% of solutions are boring.