Internet Problem Solving Contest

IPSC 2015

Solution to Problem M – Make*me-an+[integer!]

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:

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

We can formulate the following conversion rules between the types:

and we can do the following operations:

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, 1020 can be written as +[+!![]+[!![]+[]][+![]][!![]+!![]+!![]]+[!![]+!![]]+[+![]]].