collatz.d

/**
 * Collatz graph generator (inspired by http://www.xkcd.com/710/)
 * Written by Daniel Keep; released to the Public Domain.
 *
 * To use this, compile and either dump the output to a file, or feed it
 * directly into GraphViz like so:
 *
 * -----
 *  collatz 100 | dot -Ocollatz_100.svg -Tsvg
 * -----
 */
module collatz;

import tango.io.Stdout;
import tango.util.Convert;

int main(char[][] args)
{
    if( args.length != 2 )
    {
        Stderr
            .formatln("Usage: {} N", args[0])
            .formatln("Produces directed Collatz graph of the first N positive integers.");
        return 1;
    }

    auto n = to!(ulong)(args[1]);
    bool[ulong] highmap;

    Stdout
        .formatln("digraph collatz_{}", n)
        .formatln("{{")
        .formatln("  _1[label=\"1\"];");

    for( ulong i=2 ; i<=n ; ++i )
    {
        // Should probably refactor into a do...while loop, but can't be
        // arsed.
        ulong j;
        
        if( i % 2 == 0 )
            j = i / 2;

        else
            j = 3*i + 1;

        Stdout.formatln("  _{0}[label=\"{0}\"];", i);
        Stdout.formatln("  _{} -> _{};", i, j);

        while( j > n )
        {
            if( j in highmap ) break;

            ulong k;
            if( j % 2 == 0 )    k = j / 2;
            else                k = 3*j + 1;

            Stdout.formatln("  _{0}[label=\"{0}\"];", j);
            Stdout.formatln("  _{} -> _{};", j, k);
            highmap[j] = true;
            j = k;
        }
    }

    Stdout
        .formatln("}");

    return 0;
}