Internet Problem Solving Contest

• C++ program to check submissions
• One possible correct output for M1
• One possible correct output for M2
• Python program solving M1
• Python program solving M2

Easy subproblem

We will start by producing all the digits. Expressions for 0 and 1 were already showed in the example output: +![] and +!![]. In general, as soon as we can construct 1, we can simply add several 1s together. So, 2 is +!![]+!![] (or simply !![]+!![] as the initial cast of a boolean to an integer is no longer needed); 3 is !![]+!![]+!![], and by now the idea should be clear.

The next step is producing multi-digit numbers. Here the big trick is string concatenation – in Javascript, concatenating two strings can be done using the + operator. In fact, + operator will also perform string concatenation if one argument is a string and the other is an integer. For example, "1"+2+3 is "123". But how to create the first string? Well, arrays (or more generally objects) are a good candidate, doing []+1 results in "1". Or similarly, []+[] is "". Don’t ask why.

Now we have only two problems left: The first one is that using + for string concatenation competes with + in our digits and we would end up just concatenating many 1s. Therefore, it would be nice to put the digit sub-expressions into parentheses. Unfortunately, characters () were not allowed in the problem statement. The trick is to use arrays – arrays have a high enough precedence and we can do something like [expression][0] to emulate (expression).

Now we know how to concatenate the digits into a string. The final step is converting this string back into a number. A unary plus is our friend here: +"123" is 123. So, to put all things together, this is one way of writing 123: +[[]+[+!![]][+![]]+[!![]+!![]][+![]]+[!![]+!![]+!![]][+![]]][+![]]

Hard subproblem

The hard subproblem requires more work. We can start by systematically observing what our characters can do. After some experimenting with the javascript console, you could come up with the following set of observations:

• ! always produces a boolean, no matter what value it is applied to.
• binary * and - first convert both arguments to a number and then compute the operation which results in a number (or NaN in case the conversion fails, or +infinity or -infinity in some very special cases)
• binary + is a chameleon. When at least one argument is a string, it concatenates strings. If both arguments are numbers and/or booleans, the result is a number.
• unary + and - always produce a number (or NaN). They can be used to convert string to a number
• as already shown, arrays can be used as parentheses, e.g., (x) is equivalent to [x][0]
• because we have no comma, we cannot create arrays with more than one element. Arrays with a single element are quite interesting though because they can act as strings: [5]+1 is 51 but also [5]*[5] is 25.

We are able to construct expressions of various types. Here’s a list of those:

• a boolean: could be used in binary *, -, and (numerical) +
• a number(-like): an expression which results in a number and behaves as a number regarding to the operator precedence
• a numeric expression: an expression which results a number but does not necessarily follow operator precedence. In particular, any expression which contains binary + or - is of this type.
• a string(-like): an expression which results in a string, or behaves like a string (e.g. [x])
• a string expression: similar to a numeric expression but the result is a string. Again, no operator precedence is guaranteed.

We can formulate the following conversion rules between the types:

• Cast to a number: +boolean/string/number => number
• Cast to a number: -boolean/string/number => number
• Cast to a string: [number/numeric expression/string/string expression] => string
• “Downcast”: number/string => numeric expression/string expression

and we can do the following operations:

• multiplication: boolean/number/string * boolean/number/string => number
• addition: boolean/number/numeric expression + boolean/number/numeric expression => numeric expression
• string concatenation: number/numerical expression + string/string expression => string expression (Note: precedence is left to right so numeric expression would be evaluated first)
• string concatenation: string/string expression + number => string expression (Note: cannot concatenate with numeric expression as it would break it into several terms concatenated together)

• subtraction: boolean/number/numeric expression/string/string expression -

  boolean/number/string => numeric expression

Given all these rules, we can now easily generate a solution for the hard input: We will start with the two booleans ![] and !![] and we will follow all the conversions/operations possible while capping our search to reasonable numbers. (E.g., if the absolute value of the result is > 1100, it probably won’t lead to a short result for numbers 0..1000 and we can cut the search there.)

There is one pitfall along the way: JavaScript does not like ++ and --. These are parsed as a special increment/decrement operator which can only be applied to a variable. Depending on the exact order in which you perform the conversion/operator rules, this might be a problem for the generated result. Our solution was to introduce two additional types: +number and -number which represent a number that might start with + or - respectively. We then disallow all operations that could lead to ++ and --.

But wait, there’s more!

Using the set of rules given above, our solution can solve each of the given test cases in at most 66 characters. Still, it should be noted that there are other ways of producing numbers, and they can even be more efficient. We will give you one tasty example. We can create the number 100000000000000000000 simply as +[1+"e"+2+0]. OK, that would be neat, but where do we get an "e"? Easy: "true"[3] :) Thus, 10²⁰ can be written as +[+!![]+[!![]+[]][+![]][!![]+!![]+!![]]+[!![]+!![]]+[+![]]].