Expression that equals its length

Question

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

Answer 1

Javascript, 434 characters

function f(s){return s.replace(/[A-Z]/g,function(t){return{O:'one',T:'two',H:'three',F:'four',I:'five',S:'six',E:'seven',G:'eight',N:'nine',Z:'ten',P:' plus ',M:' minus ',U:' times ',X:'teen',A:'thir',B:'twenty'}[t]})}A='TPAX|GeenMT|EXUO|B FMS|F|GPSUT|ZPHPG|BPFMT|AXPFPS|BPGMF|EUOPGeen|NPT|B GMSPI|GPI|EPE'.split('|');O=26640;function S(n){return n<15&&!(O>>n&1)?'Invalid':f(A[v=n%15])+(new Array(~~(n/15)+(O>>v&1))).join(f('PSPN'))}

Yields a function in the global namespace, S, that accepts any non-negative integer and returns the required string, or "Invalid" if the integer cannot be represented within the specifications.

I would appear to have used the same approach as @optokopper, having made the same observation that "plus six plus nine" is the shortest possible padding string, and that all numbers greater than 27 can be expressed by concatenating one of 15 base strings to repeated copies of the pad.

Having said that, the tables of base strings we use differ, and my solution relies on bit twiddling and the remainder operator (%). It also includes "multiplied by" as a possible operation. And naturally the mechanics of how the strings are constructed are completely different due to the dissimilarity between C and Javascript.

That's my best attempt, at any rate. ;)

Special thanks to @chiru, whose discussion of which numbers were achievable helped prevent fruitless searching.

Answer 2

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

Answer 3

C, 450 characters

Edit: removed zero

Edit: using only plus and minus

I searched for the shortest expression that adds chars and keeps the condition true. I found plus ten plus five is 15 long and adds 15 to the string.

I need only expressions for the first 15 numbers that are not impossible, to express any possible number. 12 is the biggest impossible number, therefore it suffices to hardcode numbers smaller 28.

4 = four
11 = six plus five
13 = eight plus five
14 = twenty minus six
15 = twenty minus five
16 = eighteen minus two
17 = fourteen plus three
18 = twenty two minus four
20 = thirty two minus twelve
21 = twenty plus two minus one
22 = twenty plus four minus two
23 = thirty minus eight plus one
24 = twenty plus eight minus four
25 = twenty plus eight minus three
27 = twenty eight minus six plus five

We can write every number >27 as x*15 + one of the numbers above.

Golfed

#define P" plus "
#define M" minus "
#define U"four"
#define F"five"
#define E"eight"
#define W"twenty"
#define A"ten"P F P
*e[]={0,0,0,0,U,0,0,0,0,0,0,F P"six",0,E P F,W M"six",W M F,E"een"M"two",U"teen"P"three",W" two"M U,A U,"thirty two"M"twelve",W P"two"M"one",W M"two"P U,"thirty"P"one"M E,W P E M U,W M"three"P E,A F P"six",W" "E M"six"P F};main(n){n=atoi(1[(int*)1[&n]]);for(printf("%d: ",n);n>27;n-=15)printf(A);puts(e[n]?e[n]:"impossible");}

Readable Code

#include <stdio.h>
#include <stdlib.h>

// add fifteen to string, both as value and as character count (without spaces)
const char *add_fifteen = "plus ten plus five";

// table with hardcoded expressions
// NOTE: we could calculate 19, 26, 28 and 29 from 4, 11, 13 and 14
// but we would need more logic, so we hardcode those 4 numbers too.
const char *expressions[30]={"impossible", "impossible", "impossible", "impossible",
    "four", "impossible", "impossible", "impossible", "impossible",
    "impossible", "impossible", "five plus six", "impossible",
    "eight plus five", "twenty minus six",
    "fourteen plus one", "eighteen minus two", "fourteen plus three",
    "twenty two minus four", "four plus ten plus five",
    "thirty two minus twelve", "nine plus seven plus five",
    "twenty plus four minus two", "twelve plus seven plus four",
    "twenty plus eight minus four", "twenty plus eight minus three",
    "five plus six plus ten plus five", "twenty eight minus six plus five",
    "eight plus five plus ten plus five", "seven plus seven plus ten plus five"};

int main(int argc,char *argv[])
{
    int n = strtol(argv[1], NULL, 0);
    int fifteens = 0;

    printf("%d: ", n);

    // how many times do we need to add fifteen?
    if(n>29){
        fifteens=(n/15) - 1;
        n -= fifteens*15; // ensure 30 > n >= 15, so we don't get "impossible"
    }

    // look up the expression for n
    printf("%s", expressions[n]);

    // add fifteens till we are done
    while(fifteens-- > 0) {
        printf(" %s", add_fifteen);
    }

    printf("\n");
    return 0;
}