One thing Andrei Alexandrescu mentioned in his recent talk about D that caught my attention in particular, was its inclusion of mixin ; a function that allows code to be invoked at compiletime that defines values, and actually other code as well. In other words, mixin is somewhat like a compiletime eval , that allows a fairly large subset of code to be defined in the code itself, and still be compiled in.
This got me thinking of a script I wrote in Ruby to solve Project Euler Problem 61, a problem which involves chaining together several types of polygonal numbers which share certain digits, so that they form a circular chain. Polygonal numbers are analogous to square numbers, only with polygons other than squares. For instance, the square of 2 is 4, and triangular number 2 is 3.
To solve this problem, I used Ruby's Enumerable Module to iterate through and filter the numbers instead of regular loops, as it's somewhat easy to chain together different filters using that syntax. It's also similar to the IEnumerable interface in C♯. Naturally, I got to wondering if D has a similar device, and it does, after a fashion.
Moreover, as I was solving the problem, the code got more and more repetitive, so I turned it into an exercise in abusing eval to create compact, selfgenerating code. It proved an irresistible challenge to see if this could also be done in D. The answer is below.
There are three versions of the program. At the top of each section is the most readable version, from 061.rb. In the middle is the more compact Ruby version, found in 061compact.rb. Finally, the resulting D version, also found in _061_compact_d.d, is at the bottom.
Starting off gently with the headers.
#!/usr/bin/env ruby
# Solution to Project Euler problem 61
# Author: David J. Oftedal. #!/usr/bin/env ruby
# Solution to Project Euler problem 61
# For a more readable version, see 061.rb
# Author: David J. Oftedal. #!/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; Next up is a helper function for solving quadratic equations. This is useful for computing the inverse of many of the functions below. In the D version, I've restricted the function to integer parameters and return values, as that is what I'm using it for in this program. I've also added a little max function, that makes it convenient to get the maximum element from an array of two elements.
# The ABC formula for solving quadratic equations (where the solutions are real numbers).
def abc(a, b, c)
return (b+Math.sqrt(b**2.0(4.0*a*c)))/(2.0*a),(bMath.sqrt(b**2.0(4.0*a*c)))/(2.0*a)
end # The ABC formula for solving quadratic equations (where the solutions are real numbers).
def abc(a, b, c)
return (b+Math.sqrt(b**2.0(4.0*a*c)))/(2.0*a),(bMath.sqrt(b**2.0(4.0*a*c)))/(2.0*a)
end // 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 = to!real(A), b = to!real(B), c = to!real(C);
return [to!int((b+sqrt((b^^2.0)(4.0*a*c)))/(2.0*a)),to!int((bsqrt((b^^2.0)(4.0*a*c)))/(2.0*a))];
}
int max(int[] ints) {
return std.algorithm.max(ints[0], ints[1]);
} Next come the functions for getting the polygonal numbers. In the Ruby version, I was able to add the methods directly to the Integer class, using what's known as monkey patching, allowing me to make calls like 3.pentagonal . In D, the methods are global instead, so the call would be pentagonal(3) .
Here is where I started noting repetitions in the code. The pentagonal, hexagonal, heptagonal and octagonal functions all follow very similar formulas, and it turns out that all of the functions can be made to use the same one, with one variable inserted in a couple of places. To get the convenience of easy to remember function names without having to type in each one, I used eval to define one function for each number type.
In D, a similar result can be achieved with the mixin compiletime function. Pieces of code that can be executed compiletime can be run to insert values and definitions into the code using this function. There are some limitations on what kinds of code can be run at compiletime – for instance, foreach did not work – But calling a method that calls foreach and returns a value does. I therefore defined methods that constructed code contained in a string, called the methods using mixin , and to get the resulting code defined globally, outside any method, I passed the strings to – you guessed it – mixin . The double mixin was born.
class Integer
# Return triangular number self
def triangular
(self*(1+self))/2
end
# Return pentagonal number self
def pentagonal
((3*self**2)self)/2
end
# Return hexagonal number self
def hexagonal
(2*self**2)self
end
# Return heptagonal number self
def heptagonal
((5*self**2)(3*self))/2
end
# Return octagonal number self
def octagonal
(3*self**2)(2*self)
end $polygonalTypes = ["triangular", "square", "pentagonal", "hexagonal", "heptagonal", "octagonal"]
class Integer
# Return the triangular, square, pentagonal, etc. number self.
# The methods are called triangular, square, etc.
$polygonalTypes.each_with_index do name, i
eval("def #{name}
(((#{i}+1)*self**2)((#{i}1)*self))/2
end")
end 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 ~= "int "~name~"(int n) {
return ((("~to!string(i)~"+1)*n^^2)(("~to!string(i)~"1)*n))/2;
}";
return Polygonals;
}
mixin("mixin(definePolygonals());"); Just as we have squares, we also have square roots, and there are also triangular roots, pentagonal roots, and so on. These functions are the inverse of the ones above, and this gave me another opportunity to make some heavily abbreviated code.
# Return the triangular root of self.
def triangular_root
return 0 if self < 1
abc(1, 1, (2*self)).max
end
# Return the pentagonal root of self.
def pentagonal_root
return 0 if self < 1
((Math.sqrt((24*self)+1)+1)/6)
end
# Return the hexagonal root of self.
def hexagonal_root
return 0 if self < 1
((Math.sqrt((8*self)+1)+1)/4)
end
# Return the heptagonal root of self.
def heptagonal_root
return 0 if self < 1
abc(5, 3, (2*self)).max
end
# Return the octagonal root of self.
def octagonal_root
return 0 if self < 1
abc(3, 2, self).max
end # Return the triangular, square, etc. root of self.
# The methods are called triangular_root, square_root, etc.
$polygonalTypes.each_with_index do name, i
eval("def #{name}_root
return 0 if self < 1
abc(#{i}+1, (#{i}1), (2*self)).max
end")
end // 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 ~= "int "~name~"_root(int n) {
if (n < 1) return 0;
return max(abc("~to!string(i)~"+1, ("~to!string(i)~"1), (2*n)));
}";
return PolygonalRoots;
}
mixin("mixin(definePolygonalRoots());"); These next_ methods return the next square, triangular, pentagonal, etc. number after the one they're called on. For instance, 4.next_square will return 9 .
# Return the next square number after self.
def next_square
((Math.sqrt(self).to_i + 1)**2).to_i
end
# Return the next triangular, pentagonal, etc. number after self.
def next_triangular
(triangular_root.to_i + 1).triangular
end
def next_pentagonal
(pentagonal_root.to_i + 1).pentagonal
end
def next_hexagonal
(hexagonal_root.to_i + 1).hexagonal
end
def next_heptagonal
(heptagonal_root.to_i + 1).heptagonal
end
def next_octagonal
(octagonal_root.to_i + 1).octagonal
end
end # Return the next triangular, square, etc. number after self.
# The methods are called next_triangular, next_square, etc.
$polygonalTypes.each do name
eval("def next_#{name}
(#{name}_root.to_i + 1).#{name}
end")
end
end // 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 ~= "int next_" ~ name ~ "(int n) { return " ~ name ~ "(" ~ name ~ "_root(n) + 1); }\n";
return nextMethods;
}
mixin("mixin(defineNextMethods());"); The generators, called Enumerables in Ruby and .Net parlance, or Ranges in D, yield sequences of the polygonal numbers that can be iterated through and filtered using expressions that are fairly easy to chain together. One generator yielding one type of number can also be swapped for another, allowing different number types to be used in different positions in the chain by swapping the generators around.
The D version was a good deal more awkward to write, as the D library functions for ranges don't have all the bells and whistles as Ruby's Enumerables, and D being a typed language, the different ranges all had to implement a common interface, or alternatively derive from a common base type. But I got there in the end:
# Generators that will yield infinite streams of triangular, square, pentagonal, etc. numbers.
class TriangularGenerator
include Enumerable
# Start at the number equal to or larger than n.
def initialize n
@current = (n1).next_triangular
end
def each
loop do
yield @current
@current = @current.next_triangular
end
end
end
class SquareGenerator
include Enumerable
# Start at the number equal to or larger than n.
def initialize n
@current = (n1).next_square
end
def each
loop do
yield @current
@current = @current.next_square
end
end
end
class PentagonalGenerator
include Enumerable
# Start at the number equal to or larger than n.
def initialize n
@current = (n1).next_pentagonal
end
def each
loop do
yield @current
@current = @current.next_pentagonal
end
end
end
class HexagonalGenerator
include Enumerable
# Start at the number equal to or larger than n.
def initialize n
@current = (n1).next_hexagonal
end
def each
loop do
yield @current
@current = @current.next_hexagonal
end
end
end
class HeptagonalGenerator
include Enumerable
# Start at the number equal to or larger than n.
def initialize n
@current = (n1).next_heptagonal
end
def each
loop do
yield @current
@current = @current.next_heptagonal
end
end
end
class OctagonalGenerator
include Enumerable
# Start at the number equal to or larger than n.
def initialize n
@current = (n1).next_octagonal
end
def each
loop do
yield @current
@current = @current.next_octagonal
end
end
end # Generators that will yield infinite streams of triangular, square, pentagonal, etc. numbers.
$polygonalTypes.each do name
eval("class #{name.capitalize}Generator
include Enumerable
# Start at the number equal to or larger than n.
def initialize n
@current = (n1).next_#{name}
end
def each
loop do
yield @current
@current = @current.next_#{name}
end
end
end")
end // Generators that will yield infinite streams of triangular, square, pentagonal, etc. numbers.
string defineGenerators() {
string generators = "interface NumberGenerator {
@property bool empty();
@property int front();
NumberGenerator set(int);
void popFront();
NumberGenerator takeMax(int);
}
";
foreach(string name; polygonalTypes)
generators ~= "class "~capitalize(name)~"Generator : NumberGenerator {
int current = 1;
int maxValue = int.min;
bool isEmpty = false;
@property bool empty() {
return isEmpty;
}
@property int front() {
return current;
}
"~capitalize(name)~"Generator takeMax(int n) {
maxValue = n;
return this;
}
// Start at the number equal to or larger than n.
"~capitalize(name)~"Generator set(int n) {
current = next_"~name~"(n1);
isEmpty = false;
return this;
}
void popFront() {
current = next_"~name~"(current);
if(maxValue != int.min && current > maxValue) isEmpty = true;
}
}";
return generators;
}
mixin("mixin(defineGenerators());"); Now for the crown jewel. This construction of six generators inside one another is somewhat similar to a loopinsidealoopinsidealoopinsidealoopinsidealoopinsidealoop, generating and filtering square and triangular and pentagonal and other polygonal numbers and passing on those that fit together. The numbers are all supposed to be four digits long and share their first two digits with the previous number and their last two digits with the next one, so that's what all of these filters are looking for.
D doesn't know how to permute arrays of objects it can't sort, so in D I defined one array of generators and one array of indices which D does know how to permute, and then I defined a function which looks for the circular chain of numbers, and which takes the generators, found by using the indices, as parameters. The effect is the same in either case.
# Find a circular chain of six fourdigit numbers, each of a different polygonal type, where the first two digits of each number equal the last two digits of the previous one.
if $0 == __FILE__
# Combine the six streams of numbers in all possible orders.
generators = [TriangularGenerator, SquareGenerator, PentagonalGenerator, HexagonalGenerator, HeptagonalGenerator, OctagonalGenerator]
generators.permutation.each do generator1, generator2, generator3, generator4, generator5, generator6
# Select six fourdigit numbers, each from a separate generator, so that they form a circular chain, where the first two digits of each number equal the last two digits of the previous one.
generator1.new(1010).take_while{n n < 10000}.select{n n.to_s[2] != "0"}.each do num1
generator2.new((num1.to_s[2..3] + "10").to_i).take_while{n n < 10000 && num1.to_s[2..3] == n.to_s[0..1]}.each do num2
generator3.new((num2.to_s[2..3] + "10").to_i).take_while{n n < 10000 && num2.to_s[2..3] == n.to_s[0..1]}.each do num3
generator4.new((num3.to_s[2..3] + "10").to_i).take_while{n n < 10000 && num3.to_s[2..3] == n.to_s[0..1]}.each do num4
generator5.new((num4.to_s[2..3] + "10").to_i).take_while{n n < 10000 && num4.to_s[2..3] == n.to_s[0..1]}.each do num5
generator6.new((num5.to_s[2..3] + "10").to_i).take_while{n n < 10000 && num5.to_s[2..3] == n.to_s[0..1]}.select{n num1.to_s[0..1] == n.to_s[2..3]}.each do num6
# There's only one such chain. Display the result and exit.
puts num1.to_s<<" + "<<num2.to_s<<" + "<<num3.to_s<<" + "<<num4.to_s<<" + "<<num5.to_s<<" + "<<num6.to_s<<" = "<<[num1,num2,num3,num4,num5,num6].inject(:+).to_s
exit
end
end
end
end
end
end
end
end # Find a circular chain of six fourdigit numbers, each of a different polygonal type, where the first two digits of each number equal the last two digits of the previous one.
if $0 == __FILE__
# Chain together the six streams of polygonal numbers in all possible orders.
polygonals = eval("[" << $polygonalTypes.map{name name.capitalize + "Generator"}.join(", ") << "]")
# 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.
code = "num0 = 1010\n"
(1..6).each do i
code += "polygonal#{i.to_s}.new((num#{(i1).to_s}.to_s[2..3] + \"10\").to_i).take_while{n n < 10000 && ("+i.to_s+" == 1 
num#{(i1).to_s}.to_s[2..3] == n.to_s[0..1])}.select{n "+i.to_s+" < 6  num1.to_s[0..1] == n.to_s[2..3]}.each do num#{i.to_s}\n"
end
# There's only one chain of six numbers matching the criteria. As soon as the generators generate one, display the chain and exit.
code += "puts "
(1..6).each {i code += "num"+i.to_s+".to_s+\" "+(i<6 ? "+ \"+" : "= \"+
[num1,num2,num3,num4,num5,num6].inject(:+).to_s\n
exit\n")}
code += ("end\n" * 6)
polygonals.permutation.each do polygonal1, polygonal2, polygonal3, polygonal4, polygonal5, polygonal6
eval(code)
end
end // Find a circular chain of six fourdigit 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(std.algorithm.max(i5, 0))~")[0..2] == to!string(n)[2..4]) && to!string(num"~to!string(i1)~")[2..4] == to!string(n)[0..2]))(polygonal"~to!string(i)~".set(to!int(to!string(num"~to!string(i1)~")[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("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("mixin(defineMain());"); Porting a Ruby script that's so Ruby, it's almost Perl to a statically typed, compiled language is a bit of a challenge. I had to take care when implementing the ranges, as they are somewhat more demanding to implement and use than Ruby's Enumerables. The double mixin s with the method calls also took a while to figure out, after the convenience of eval . On the other hand, D is so expressive and so flexible that it can be done, and as with the previous example with the Python script, the result is not only nearly as concise as the original, and retains the same general structure, but it's also faster.
