Natsumi (2005-04-06)
Synopsis
gcc natsumi.c -o natsumi
./natsumi <integer> [...]
For each command line argument, Natsumi will print out a
representation of it using 120 and basic operators only.
Douglas Adams fans may prefer this instead:
mv natsumi.c deepthought.c
gcc deepthought.c -o deepthought
./deepthought <integer> [...]
... and expressions will be in terms of 42 instead of 120.
Details
Natsumi will reason how everything starts with 120... well, all
integers, at least.
Inspired by Nekoneko Soft's "120en no natsu" (summer of 120 yen).
Source code is meant to resemble Natsumi from the game. For those
who don't know the story:
Two characters met at a vending machine in the summer,
discovered that they have the ability to get free products out
of any vending machine by hitting it together... thus they
toured around the neighborhood and had a great time, even if the
vending machines never give them what they had in mind and never
dispensed more than two products. They found this special
ability to be no longer working at the end of the second day.
Though by then, both realized what they wanted wasn't the this
ability, but merely an excuse to be together. Awkward at first
but regular couple at last... the 1:6 billion chance encounter
that all started with 120 yen.
Most vending machines should still operate at 120 yen per
product...
If anyone else has excess affection for a particular integer and
wants to replace all numeric constants with The One, here is the
program for you ^_^;
Known issues
- Specifying -2147483648 causes a crash.
- Some file names causes output to take a long time to execute.
- Not all outputs are optimal.
- Source is ASCII dependent.
Implementation
Obviously any number can be represented as (120+120+...)/120,
using exactly (n+1) 120s to represent n. Something like this:
#include<stdio.h>
void main(int n,char**a)
{ for(;*++a?sscanf(*a,"%d",&n):0;puts(")/120"))
for(printf("%d = (120",n);--n;printf("+120")); }
... which wouldn't be terribly interesting. Natsumi does much
better in trying to generate expressions with minimal number of
120s, using dynamic programming:
1. Start with a set of known optimal expressions.
2. Combine element pairs from the set using one of four basic
operations. The results are also optimal if they are not in the
optimal set already.
3. Add results to set, go to step 1 and repeat until the number
in question is in the optimal set.
In practice, because the size of integers are finite and the size
of table is finite, some results at step 2 will have to be dropped,
and remaining table entries will have to be filled using less
optimal expressions. Then, because we are not guaranteed to get
all the optimal expressions in every iteration, the entire table
must be filled to get the best expression available for every cell
entry. Natsumi should actually continue to run the steps a few
more times on the full table, but few people have enough patience
for that.
Thus, not all output expressions are optimal... Maybe users can
take it as a challenge to find expressions shorter than Natsumi's
output ^_^; For example, Natsumi outputs 22 120s for 2073600000,
but this can be computed using only 9 120s. Some heuristics might
also apply to eliminating more parentheses...
Because -(-2147483648) == -2147483648 in signed 32bit, specifying
-2147483648 will cause Natsumi to crash. Numbers from -2147483647
to 2147483647 are okay though.
About the output expressions: Natsumi guarantees no divisions where
the denominator is zero or where the quotient is not an integer,
but overflows are something else. Depending on the order of
evaluation, the intermediate result may overflow 32bit signed int.
So then:
- Evaluating them all as doubles should work.
- Evaluating them by hand eventually works.
- Evaluating them with Perl definitely works, something like:
perl -e 'while(<>){print eval;print"\n";}'
About using the file name to select expression base: obviously I
tweaked the numbers such that "natsumi.c" maps to 120 and
"deepthought.c" maps to 42. I wanted to make the number
configurable without adding an extra parameter, without changing
the source, and without wasting any lines for preprocessor. So
source file name it is.
Because of the file name bit, the code becomes ASCII dependent.
Also, it's not so easy to select a number this way, though not
impossible. If user wanted 54, for example (because 42 is six
times nine = 54), they would need some name in l33tspeak like
"de3p7h0ugh7.c". Guessing the right name for the desired number is
left as an exercise to the reader, I only promised 42 and 120.
Well, and 54 too.
The algorithm should work for any number greater than 3 (and
therefore all file names), although some numbers take longer to
generate the table than others, some probably *too* long. This can
be mediated by specifying a smaller table size, by modifying the
"z=46340" bit in line 6. 46340 is the highest value supported on
32bit machines and produces the best results, setting it to a lower
value will make Natsumi run faster, at the cost of losing some
optimal solutions.