view 2017/day21.d @ 27:8bfcc543f85f

day 21
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Sun, 31 Dec 2017 12:40:14 -0500
parents
children
line wrap: on
line source

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));
}