# HG changeset patch
# User Jordi Gutiérrez Hermoso <jordigh@octave.org>
# Date 1514742014 18000
# Node ID 8bfcc543f85fedd8eccae6d7c5b61002120dcc67
# Parent  8db386034a68dcb71f7b86beef8c52c7bc457ee1
day 21

diff --git a/2017/day21.d b/2017/day21.d
new file mode 100644
--- /dev/null
+++ b/2017/day21.d
@@ -0,0 +1,156 @@
+import std.stdio;
+import std.array: array;
+import std.algorithm: map, sum, swap;
+import std.range: zip, retro;
+import std.string: split, join;
+import std.conv: to;
+import std.format: format;
+
+immutable dihedralFun =
+"function(ref const Pattern p) {
+  auto n = p.dim;
+  auto output = new int[][](n, n);
+  foreach(i; 0..n) {
+    foreach(j; 0..n) {
+      output[i][j] = p.grid[%s][%s];
+    }
+  }
+  return output;
+}";
+
+immutable dihedralFourGroup = [
+  mixin(format(dihedralFun, "i",     "j")),
+  mixin(format(dihedralFun, "n-i-1", "j")),
+  mixin(format(dihedralFun, "i",     "n-j-1")),
+  mixin(format(dihedralFun, "n-i-1", "n-j-1")),
+  mixin(format(dihedralFun, "j",     "i")),
+  mixin(format(dihedralFun, "n-j-1", "i")),
+  mixin(format(dihedralFun, "j",     "n-i-1")),
+  mixin(format(dihedralFun, "n-j-1", "n-i-1")),
+];
+
+struct Pattern{
+  size_t dim;
+  int[][] grid;
+
+  size_t[2] opSlice(size_t dim)(size_t a,  size_t b)
+  {
+    return [a, b];
+  }
+
+  Pattern opIndex(size_t[2] s1, size_t[2] s2) {
+    auto n = s1[1] - s1[0];
+    Pattern subpat = {
+      n,
+      new int[][](n, n),
+    };
+    foreach(i; 0..n) {
+      foreach(j; 0..n) {
+        subpat.grid[i][j] = this.grid[s1[0]+i][s2[0]+j];
+      }
+    }
+    return subpat;
+  }
+
+  void opIndexAssign(Pattern subpat, size_t[2] s1, size_t[2] s2) {
+    foreach(i; s1[0]..s1[1]) {
+      foreach(j; s2[0]..s2[1]) {
+        this.grid[i][j] = subpat.grid[i-s1[0]][j-s2[0]];
+      }
+    }
+  }
+
+  size_t toHash() const @safe pure nothrow {
+    // Lots of collisions, but input is small.
+    return this.countBits() + this.dim*this.dim;
+  }
+
+  bool opEquals(ref const Pattern other) const @safe pure {
+    if(this.dim != other.dim) {
+      return false;
+    }
+
+    foreach(elt; dihedralFourGroup) {
+      if(this.grid == elt(other)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  auto countBits() const @safe pure nothrow {
+    return this.grid.map!(sum).sum;
+  }
+
+  void applyPatterns(Pattern[Pattern] patterns) {
+    // fractional dimension, step size, new step size
+    size_t fractdim, ss, new_ss;
+    auto newstep = 3;
+    if(this.dim % 2 == 0) {
+      fractdim = this.dim/2;
+      ss = 2;
+      new_ss = 3;
+    }
+    else{
+      fractdim = this.dim/3;
+      ss = 3;
+      new_ss = 4;
+    }
+    auto newdim = fractdim*new_ss;
+    Pattern newpat = {
+      newdim,
+      new int[][](newdim, newdim)
+    };
+    foreach(i; 0..fractdim) {
+      foreach(j; 0..fractdim) {
+        auto subpat = this[ss*i..ss*i+ss, ss*j..ss*j+ss];
+        auto replacement = patterns[subpat];
+        newpat[new_ss*i .. new_ss*i+new_ss, new_ss*j .. new_ss*j+new_ss] = replacement;
+      }
+    }
+    this = newpat;
+  }
+
+}
+
+auto parseGrid(string line) {
+  auto rows = line.split("/");
+  Pattern p =  {
+    rows.length,
+    rows.map!(
+      l => l.map!(
+        x => x == '.' ? 0 : 1
+      ).array
+    ).array
+  };
+  return p;
+}
+
+auto parsePatterns(string[] lines) {
+  Pattern[Pattern] patterns;
+  foreach(parts; lines.map!(l => l.split(" => "))) {
+    patterns[parts[0].parseGrid] = parts[1].parseGrid;
+  }
+  return patterns;
+}
+
+auto runPatterns(Pattern[Pattern] patterns, int numiter = 5) {
+  Pattern image = {
+    3,
+    [
+      [0, 1, 0],
+      [0, 0, 1],
+      [1, 1, 1],
+    ],
+  };
+  foreach(i; 0..numiter) {
+    image.applyPatterns(patterns);
+  }
+  return image.countBits;
+}
+
+void main(string[] args) {
+  auto patterns = File(args[1]).byLineCopy.array.parsePatterns;
+  writeln(patterns.runPatterns(5));
+  writeln(patterns.runPatterns(18));
+}