euler61.d

#!/usr/bin/dmd -run

// Solution to Project Euler problem 61
// For a more readable version, see 061.rb
// Author: David J. Oftedal.

import std.stdio, std.math, std.algorithm, std.string, std.conv, std.c.stdlib, std.range;

// The ABC formula for solving quadratic equations (where the solutions are real numbers).
// Restrict to integer solutions.
int[] abc(int A, int B, int C) {
    real a = A, b = B, c = C;
    return map!(to!int)(
          [(-b+sqrt((b^^2.0)-(4.0*a*c)))/(2.0*a),
           (-b-sqrt((b^^2.0)-(4.0*a*c)))/(2.0*a)]).array;
}

immutable string[6] polygonalTypes = ["triangular", "square", "pentagonal", "hexagonal", "heptagonal", "octagonal"];

// Return the triangular, square, pentagonal, etc. number n.
// The methods are called triangular, square, etc.
string definePolygonals() {
    string Polygonals = "";
    foreach(int i, string name; polygonalTypes)
        Polygonals ~= format(q{int %s(int n) {
            return (((%s+1)*n^^2)-((%s-1)*n))/2;
        }}, name, i, i);
    return Polygonals;
}
mixin(definePolygonals());

// Return the triangular, square, etc. root of n.
// The methods are called triangular_root, square_root, etc.
string definePolygonalRoots() {
    string PolygonalRoots = "";
    foreach(int i, string name; polygonalTypes)
        PolygonalRoots ~= format(q{int %s_root(int n) {
            if (n < 1) return 0;
            return reduce!max(abc(%s+1, -(%s-1), -(2*n)));
        }}, name, i, i);
    return PolygonalRoots;
}
mixin(definePolygonalRoots());

// Return the next triangular, square, etc. number after n.
// The methods are called next_triangular, next_square, etc.
string defineNextMethods() {
    string nextMethods = "";
    foreach(string name; polygonalTypes)
        nextMethods ~= format(q{int next_%s(int n) {
                     return %s(%s_root(n) + 1); }}~"\n", name, name, name);
    return nextMethods;
}
mixin(defineNextMethods());

// Generators that will yield infinite streams of triangular, square, pentagonal, etc. numbers.
interface NumberGenerator {
    @property bool empty();
    @property int front();
    NumberGenerator set(int);
    void popFront();
    NumberGenerator takeMax(int);
}

mixin template GenFun(T, alias next) {
    int current = 1;
    int maxValue = int.min;
    bool isEmpty = false;

    @property bool empty() {
        return isEmpty;
    }

    @property int front() {
        return current;
    }

    T takeMax(int n) {
        maxValue = n;
        return this;
    }

    // Start at the number equal to or larger than n.
    T set(int n) {
        current = next(n-1);
        isEmpty = false;
        return this;
    }

    void popFront() {
        current = next(current);
        if(maxValue != int.min && current > maxValue) isEmpty = true;
    }
}
string defineGenerators() {
    string generators;

    foreach(string name; polygonalTypes)
        generators ~= "class "~capitalize(name)~"Generator : NumberGenerator {
            mixin GenFun!("~capitalize(name)~"Generator, next_"~name~");
        }";
    return generators;
}
mixin(defineGenerators());

// Find a circular chain of six four-digit numbers, each of a different polygonal type, where the first two digits of each number equal the last two digits of the previous one.
string defineFindChain() {
    string code = "void findChain(";
    for(int i=1;i<7;i++) code ~= "NumberGenerator polygonal"~to!string(i)~(i<6 ? "," : ") {\nint num0 = 1010;\n");

    // Upon finding a number that may yield a valid chain, create a new generator and search for the second number in that chain, and if found, a third generator, etc.
    // Continue until a chain with six valid numbers is found.
    for(int i=1;i<7;i++)
        code ~= "foreach(int num"~to!string(i)~"; filter!(n => "~to!string(i)~" == 1 || (("~to!string(i)~" < 6 || to!string(num"~to!string(max(i-5, 0))~")[0..2] == to!string(n)[2..4]) && to!string(num"~to!string(i-1)~")[2..4] == to!string(n)[0..2]))(polygonal"~to!string(i)~".set(to!int(to!string(num"~to!string(i-1)~")[2..4] ~ \"10\")).takeMax(9999))) {\n";

    // There's only one chain of six numbers matching the criteria. As soon as the generators generate one, display the chain and exit.
    code ~= "writefln(";
    for(int i=1;i<7;i++) code ~= "to!string(num"~to!string(i)~")~\" "~(i<6 ? "+ \"~" : "= \"\n~to!string(reduce!((a,b) => a+b)(0, [num1,num2,num3,num4,num5,num6])));
    exit(0);");
    for(int i=0;i<7;i++) code ~= "}";

    return code;
}
mixin(defineFindChain());

string defineMain() {
    string main = "int main(string[] argv) {
    // Chain together the six streams of polygonal numbers in all possible orders.
    NumberGenerator[6] polygonals = new NumberGenerator[6];\n";
    foreach(int i, string name; polygonalTypes) main ~= "\tpolygonals["~to!string(i)~"] = new "~capitalize(name)~"Generator();\n";
    main ~= "\tint[] indices = [0, 1, 2, 3, 4, 5];
    do {
        findChain(";
    for(int i=0;i<6;i++) main ~= "polygonals[indices["~to!string(i)~(i<5 ? "]]," : "]]);
    } while(nextPermutation(indices));
    return 0;
    }");
    return main;
}
mixin(defineMain());

unittest {
    // test_nextSquare
    assert(next_square(1) == 4);
    assert(next_square(4) == 9);
    assert(next_square(100) == 121);

    // test_totriangular
    foreach(int n; iota(0, 1001)) assert(triangular(n) == reduce!((a,b) => a+b)(0, iota(1, n+1)));

    // test_fromtriangular
    assert(0 == triangular_root(0));
    foreach(int n; iota(0, 1001)) assert(n == triangular_root(reduce!((a,b) => a+b)(0, iota(1, n+1))));

    // test_triangular_roundtrip
    foreach(int n; iota(0, 1001)) assert(n == triangular_root(triangular(n)));

    // test_nexttriangular
    assert(next_triangular(1) == (1+2));
    assert(next_triangular(reduce!((a,b) => a+b)(0, iota(1, 100))) == reduce!((a,b) => a+b)(0, iota(1, 101)));

    // test_topentagonal
    assert(pentagonal(1) == 1);
    assert(pentagonal(2) == 5);
    assert(pentagonal(3) == 12);
    assert(pentagonal(4) == 22);
    assert(pentagonal(5) == 35);

    // test_frompentagonal
    assert(0 == pentagonal_root(0));
    assert(1 == pentagonal_root(1));
    assert(2 == pentagonal_root(5));
    assert(3 == pentagonal_root(12));
    assert(4 == pentagonal_root(22));
    assert(5 == pentagonal_root(35));
    assert(5 == pentagonal_root(36));
    assert(5 == pentagonal_root(37));

    // test_pentagonal_roundtrip
    foreach(int n; iota(0, 1001)) assert(n == pentagonal_root(pentagonal(n)));

    // test_nextpentagonal
    assert(next_pentagonal(1) == 5);
    assert(next_pentagonal(715) == 782);

    // test_tohexagonal
    assert(hexagonal(1) == 1);
    assert(hexagonal(2) == 6);
    assert(hexagonal(3) == 15);
    assert(hexagonal(4) == 28);
    assert(hexagonal(5) == 45);

    // test_fromhexagonal
    assert(0 == hexagonal_root(0));
    assert(1 == hexagonal_root(1));
    assert(2 == hexagonal_root(6));
    assert(3 == hexagonal_root(15));
    assert(4 == hexagonal_root(28));
    assert(5 == hexagonal_root(45));
    assert(5 == hexagonal_root(46));
    assert(5 == hexagonal_root(47));

    // test_hexagonal_roundtrip
    foreach(int n; iota(0, 1001)) assert(n == hexagonal_root(hexagonal(n)));

    // test_nexthexagonal
    assert(next_hexagonal(1) == 6);
    assert(next_hexagonal(703) == 780);

    // test_toheptagonal
    assert(heptagonal(1) == 1);
    assert(heptagonal(2) == 7);
    assert(heptagonal(3) == 18);
    assert(heptagonal(4) == 34);
    assert(heptagonal(5) == 55);

    // test_fromheptagonal
    assert(0 == heptagonal_root(0));
    assert(1 == heptagonal_root(1));
    assert(2 == heptagonal_root(7));
    assert(3 == heptagonal_root(18));
    assert(4 == heptagonal_root(34));
    assert(5 == heptagonal_root(55));
    assert(5 == heptagonal_root(56));
    assert(5 == heptagonal_root(57));
    assert(27 == heptagonal_root(1782));
    assert(27 == heptagonal_root(1783));
    assert(26 == heptagonal_root(1781));

    // test_heptagonal_roundtrip
    foreach(int n; iota(0, 1001)) assert(n == heptagonal_root(heptagonal(n)));

    // test_nextheptagonal
    assert(next_heptagonal(1) == 7);
    assert(next_heptagonal(783) == 874);
    assert(next_heptagonal(873) == 874);

    // test_tooctagonal
    assert(octagonal(1) == 1);
    assert(octagonal(2) == 8);
    assert(octagonal(3) == 21);
    assert(octagonal(4) == 40);
    assert(octagonal(5) == 65);

    // test_fromoctagonal
    assert(0 == octagonal_root(0));
    assert(1 == octagonal_root(1));
    assert(2 == octagonal_root(8));
    assert(3 == octagonal_root(21));
    assert(4 == octagonal_root(40));
    assert(5 == octagonal_root(65));
    assert(5 == octagonal_root(66));
    assert(5 == octagonal_root(67));
    assert(43 == octagonal_root(5461));
    assert(43 == octagonal_root(5462));
    assert(42 == octagonal_root(5460));

    // test_octagonal_roundtrip
    foreach(int n; iota(0, 1001)) assert(n == octagonal_root(octagonal(n)));

    // test_nextoctagonal
    assert(next_octagonal(1) == 8);
    assert(next_octagonal(736) == 833);
    assert(next_octagonal(4960) == 4961);
    assert(next_octagonal(5460) == 5461);

    // test_sequenceLength
    int length = 0;
    foreach(int element; new SquareGenerator().set(1).takeMax(100)) length++;
    assert(length == 10);
}