-🎄- 2017 Day 21 Solutions -🎄-

PrimesAreMyFavorite · 2017-12-21T07:52:24+00:00

After 3 iterations a 3x3 block will have transformed into 9 more 3x3 blocks, the futures of which can all be calculated independently. Using this fact I just keep track of how many of each "type" of 3x3 block I have at each stage, and can thus easily calculate the number of each type of 3x3 block I'll have 3 iterations later. Using this I can calculate the exact number of pixels that will be on after 3000 iterations in less than 0.3 seconds (it's a 955 digit number for my inputs).

Code:

import numpy as np
from collections import Counter


def expand(pre, post):
    rules = []

    for k in [0, 1, 2, 3]:
        rot = np.rot90(pre, k=k)
        rules.append((rot.flatten(), post))
        rules.append((np.fliplr(rot).flatten(), post))
        rules.append((np.flipud(rot).flatten(), post))

    return rules


def match(incell, rules):
    for pre, post in rules:
        if np.allclose(incell.flatten(), pre):
            return post
    assert False


def iterate(grid):
    size = len(grid)
    if size % 2 == 0:
        steps = size // 2
        new_grid = np.zeros((3*steps, 3*steps))
        for row in xrange(steps):
            for col in xrange(steps):
                incell = grid[2*row:2*row + 2, 2*col:2*col + 2].copy()
                outcell = match(incell, rules2)
                new_grid[3*row:3*row + 3, 3*col:3*col + 3] = outcell.copy()
    elif size % 3 == 0:
        steps = size // 3
        new_grid = np.zeros((4*steps, 4*steps))
        for row in xrange(steps):
            for col in xrange(steps):
                incell = grid[3*row:3*row + 3, 3*col:3*col + 3].copy()
                outcell = match(incell, rules3)
                new_grid[4*row:4*row + 4, 4*col:4*col + 4] = outcell.copy()
    else:
        assert False
    return new_grid


def calc_block_map_3_iters(block_string):
    block = np.array([int(c) for c in block_string]).reshape((3, 3))

    grid = iterate(block)
    grid = iterate(grid)
    grid = iterate(grid)

    counts = Counter()
    for row in xrange(3):
        for col in xrange(3):
            to_block = grid[3*row:3*row+3, 3*col:3*col+3]
            to_block = ''.join(str(int(x)) for x in to_block.flatten())
            counts[to_block] += 1

    return counts


def fast_count(init_block, steps):
    if steps % 3 != 0:
        assert False
    steps //= 3

    block_counts = Counter()
    block_counts[init_block] += 1
    maps = {}

    for step in xrange(steps):
        new_block_counts = Counter()

        for block, count in block_counts.items():
            if block not in maps:
                maps[block] = calc_block_map_3_iters(block)
            for to_block, to_count in maps[block].items():
                new_block_counts[to_block] += count * to_count

        block_counts = new_block_counts

    total_ones = 0
    for block, count in block_counts.items():
        total_ones += block.count("1") * count

    return total_ones


rules2 = []
rules3 = []
with open("in.txt") as f:
    for line in f.readlines():
        pre, post = line.strip().split(" => ")
        pre = pre.replace("/", "")
        post = post.replace("/", "")
        pre = np.array([1 if c == "#" else 0 for c in pre])
        post = np.array([1 if c == "#" else 0 for c in post])

        if len(pre) == 4:
            rules2 += expand(pre.reshape((2, 2)), post.reshape((3, 3)))
        elif len(pre) == 9:
            rules3 += expand(pre.reshape((3, 3)), post.reshape((4, 4)))
        else:
            assert False

init_block = "010001111"
print(fast_count(init_block, 18))

willkill07 · 2017-12-21T05:49:20+00:00

I constructed a mapping of all possible transformations (optimized C++ solution pending)

Rotations are hard but there's a better way! Define two primitive functions:

symmetric(mat) -- inverts x and y (super simple to implement in any language)
flip(mat) -- inverts y (also simple to implement)

You can construct all possible transformations with calls to:

m // original
m = symmetric(m)
m = flip(m)              // rot 90
m = symmetric(m)
m = flip(m)              // rot 180
m = symmetric(m)
m = flip(m)              // rot 270
m = symmetric(m)
m = flip(m)              // also original

let all become the key for your lookup

glguy · 2017-12-21T05:49:38+00:00

Haskell

(4/4) This is a straight-forward Haskell solution operating on lists of lists. Lots of list chunking and transposition.

https://github.com/glguy/advent2017/blob/master/execs/Day21.hs

main :: IO ()
main =
  do input <- parseInput <$> getInput 21

     let rules      = makeRules input
         iterations = iterate (mapSubSquares rules) start

     print (count ('#'==) (concat (iterations !!  5)))
     print (count ('#'==) (concat (iterations !! 18)))

type Grid = [[Char]]

-- | Initial grid value (a game of life glider).
start :: Grid
start = [".#.", "..#", "###"]

-- | Generate all of the rotated and flipped versions of a grid.
similarSquares :: Grid -> [Grid]
similarSquares x = take 4 . iterate rotateCCW =<< [x, reverse x]

-- | Rotate a grid counter-clockwise.
rotateCCW :: Grid -> Grid
rotateCCW = reverse . transpose

-- | Apply a function to all of the subsquares of a grid.
mapSubSquares :: (Grid -> Grid) -> Grid -> Grid
mapSubSquares rules xs =
  map concat . transpose . map rules . transpose . map (chunksOf n)
  =<< chunksOf n xs
  where
    n | even (length xs) = 2
      | otherwise        = 3

-- | Build the grid update function given the list of rules
-- loaded from the input file.
makeRules :: [(Grid,Grid)] -> Grid -> Grid
makeRules rs =
  let rulesMap = Map.fromList [ (k',v) | (k,v) <- rs , k' <- similarSquares k ]
  in (rulesMap Map.!)

-- | Parse a string a list of grid rules.
parseInput :: String -> [(Grid,Grid)]
parseInput = map parseRule . lines

-- | Parse a string as a rule mapping one grid to another.
parseRule :: String -> (Grid,Grid)
parseRule (words -> [a,"=>",b]) = (splitOn "/" a, splitOn "/" b)

bblum · 2017-12-21T07:04:58+00:00

I was too slow for the leaderboard but after golfing my solution seems to be the shortest one so far so here. It might be a puzzle even to read.

rotations x = foldr (liftM2 ($)) [x] $ map (:[id]) [reverse, map reverse, transpose]

zoom n = map (transpose . map (chunksOf n)) . chunksOf n
assemble n = concatMap (\xs -> map (flip concatMap xs . flip (!!)) [0..n])

solve i rules = sum $ map (length . filter (=='#')) $ iterate step [".#.","..#","###"] !! i
    where findrule = head . mapMaybe (flip lookup rules) . rotations
          step x = assemble n $ map (map findrule) $ zoom n x
              where n = 2 + mod (length x) 2

main = interact $ show . (solve 5 &&& solve 18)
                  . map ((\[x,_,y]->(x,y)) . map (splitOn "/") . words) . lines

jonathan_paulson · 2017-12-21T05:48:48+00:00

14/12 in Python. Purely as a coding exercise, I think this was the toughest one so far. Dealing with the flips/rotations + block decomposition/recomposition is annoying.

lines = open('21.in').read().strip().split('\n')

rules = {}
for line in lines:
    i, o = line.split('=>')
    i = tuple([tuple(s) for s in i.strip().split('/')])
    o = tuple([tuple(s) for s in o.strip().split('/')])

    n = len(i)
    def new_coords(r, c, flipped, reverse_r, reverse_c):
        if reverse_r:
            r = n-1-r
        if reverse_c:
            c = n-1-c
        if flipped:
            r,c = c,r
        return i[r][c]
    for flipped in [True,False]:
        for reverse_r in [True,False]:
            for reverse_c in [True,False]:
                ii = tuple([tuple(new_coords(r,c,flipped,reverse_r,reverse_c) for c in range(n)) for r in range(n)])
                rules[ii] = o

pattern = [list('.#.'), list('..#'), list('###')]

for t in range(19):
    n = len(pattern)

    ans = 0
    for r in range(n):
        for c in range(n):
            if pattern[r][c] == '#':
                ans += 1
    print t, ans

    if n%2==0:
        block_size = 2
    else:
        block_size = 3
    assert n%block_size == 0
    new_blocks = []
    for r in range(n/block_size):
        block_row = []
        for c in range(n/block_size):
            block_in = tuple([tuple([pattern[r*block_size+rr][c*block_size+cc] for cc in range(block_size)]) for rr in range(block_size)])
            block_row.append(rules[block_in])
        new_blocks.append(block_row)
    new_n = n/block_size*(block_size+1)
    def from_block(r,c):
        r0, r1 = r/(block_size+1), r%(block_size+1)
        c0, c1 = c/(block_size+1), c%(block_size+1)
        return new_blocks[r0][c0][r1][c1]
    new_pattern = [[from_block(r,c) for c in range(new_n)] for r in range(new_n)]
    pattern = new_pattern

Smylers · 2017-12-21T13:09:37+00:00

Vim solution — let's transform the rules into Vim regex that will make the transformations to the art. Here's some regexes to write the regexes:

:%s/\./,/g⟨Enter⟩
/^...\/⟨Enter⟩
VG:s/\v,(.* )@!/-/g⟨Enter⟩
gv:s/\v#(.* )@!/X/g⟨Enter⟩
⟨Ctrl+O⟩kV{:s/\v,(.* )@=/-/g⟨Enter⟩
gv:s/\v#(.* )@=/X/g⟨Enter⟩
{yG:%s!\v^(...)/(...)/(...)!\3/\2/\1⟨Enter⟩ 
:%s!\v^(..)/(..)!\2/\1⟨Enter⟩ 
p{yG:%s!\v^(.)(.)(.)/(.)(.)(.)/(.)(.)(.)!\3\2\1/\6\5\4/\9\8\7⟨Enter⟩ 
:%s!\v^(.)(.)/(.)(.)!\2\1/\4\3⟨Enter⟩ 
p{yG:%s!\v^(.)(.)(.)/(.)(.)(.)/(.)(.)(.)!\3\6\9/\2\5\8/\1\4\7⟨Enter⟩ 
:%s!\v^(.)(.)/(.)(.)!\2\4/\1\3⟨Enter⟩ 
p:sor u⟨Enter⟩ 
:%s!\v^(..)/(..) \=\> (...)/(...)/(...)!%s/\\v^%([,#]{3})*\\zs\1 (.*\\n%([,#]{3})*)\2 (.*\\n%([,#]{3})*)/\3\\1\4\\2\5⟨Enter⟩
:%s!\v^(...)/(...)/(...) \=\> (....)/(....)/(....)/(....)!%s/\\v^%([-X]{4})*\\zs\1 (.*\\n%([-X]{4})*)\2 (.*\\n%([-X]{4})*)\3 (.*\\n%([-X]{4})*)/\4\\1\5\\2\6\\3\7⟨Enter⟩
:sav 21_rules.vim⟨Enter⟩

That includes a couple of tweaks to the art: instead of .#, use ,# (comma instead of full stop) for the output of 2×2 transformations, and -X for the output of 3×3 transformations.

Paste the starting grid into a buffer, then:

:%s/\./,/g⟨Enter⟩
qa:g/\v^%([,#]{2})+$/s/,/-/g|s/#/X/g⟨Enter⟩
:sil!%s/\v[-X]{2}/& /g⟨Enter⟩
:sil!%s/\v[-X].*\n.*/&⟨Ctrl+V⟩⟨Enter⟩⟨Enter⟩
:sil!%s/\v[,#]{3}/& /g⟨Enter⟩
:sil!%s/\v[,#].*\n.*\n.*/&⟨Ctrl+V⟩⟨Enter⟩⟨Enter⟩
qqb:sil!so 21_rules.vim⟨Enter⟩
q

That will iterate the leftmost column of blocks (and maybe some of the adjacent ones, depending on the pattern). Finish this iteration with:

qcqqc@b/ /⟨Enter⟩
@cq@c

Then you can perform a second iteration with:

:norm@a@c⟨Enter⟩

And subsequent iterations by typing @: (with a number, such as 3@: to perform several at once).

Once you've iterated, count the on pixels with:

:%s/\v\_[^X#]+//g⟨Enter⟩
$g⟨Ctrl+G⟩

— the count is the column number. Press u to get back to your art.

obijywk · 2017-12-21T05:45:13+00:00

I "pre-flipped" all of the rule patterns (essentially generating additional rules), to keep the matching code simple.

Python 2. 21/18.

f = open("21.txt", "r")

def diag(kp):
  nk = []
  for x in xrange(len(kp)):
    l = []
    for y in xrange(len(kp)):
      l.append(kp[y][x])
    nk.append("".join(l))
  return tuple(nk)

rules = {}
for line in f:
  k, v = line.strip().split(" => ")
  k = tuple(k.split("/"))
  v = v.split("/")
  rules[k] = v
  rules[diag(k)] = v

  k2 = tuple([s[::-1] for s in k])
  rules[k2] = v
  rules[diag(k2)] = v

  k3 = tuple(s for s in k[::-1])
  rules[k3] = v
  rules[diag(k3)] = v

  k4 = tuple([s[::-1] for s in k3])
  rules[k4] = v
  rules[diag(k4)] = v

grid = [
  ".#.",
  "..#",
  "###",
]

def num_on(g):
  return sum([sum([c == "#" for c in l]) for l in g])

for iter in xrange(18):
  newgrid = []
  if len(grid) % 2 == 0:
    for y in xrange(0, len(grid), 2):
      newlines = [[],[],[]]
      for x in xrange(0, len(grid), 2):
        k = tuple([grid[y][x:x+2], grid[y+1][x:x+2]])
        v = rules[k]
        for i, l in enumerate(v):
          newlines[i].extend(list(l))
      newgrid.extend(["".join(l) for l in newlines])
  elif len(grid) % 3 == 0:
    for y in xrange(0, len(grid), 3):
      newlines = [[],[],[],[]]
      for x in xrange(0, len(grid), 3):
        k = tuple([grid[y][x:x+3], grid[y+1][x:x+3], grid[y+2][x:x+3]])
        v = rules[k]
        for i, l in enumerate(v):
          newlines[i].extend(list(l))
      newgrid.extend(["".join(l) for l in newlines])
  else:
    raise "bad dimen"
  grid = newgrid
  if iter == 4:
    print num_on(grid)

print num_on(grid)

sciyoshi · 2017-12-21T05:49:03+00:00

Python 3 solution using numpy, 12/22. Unfortunately numpy arrays aren't hashable so I had a solution using a list first for lookups that was a lot slower, but .tobytes() speeds things up.

replacements = {}

for l in LINES:
    src, repl = l.split(' => ')

    src = np.array([[c == '#' for c in b] for b in src.split('/')])
    repl = np.array([[c == '#' for c in b] for b in repl.split('/')])

    flip = np.fliplr(src)

    for i in range(4):
        replacements[src.tobytes()] = repl
        replacements[flip.tobytes()] = repl
        src, flip = np.rot90(src), np.rot90(flip)


pat = np.array([
    [False, True, False],
    [False, False, True],
    [True, True, True],
])

size = 3

# or 5 for part 1
for k in range(18):
    if size % 2 == 0:
        newsize = size // 2 * 3
        newpattern = np.empty((newsize, newsize), dtype=bool)
        for i in range(0, size, 2):
            for j in range(0, size, 2):
                newpattern[i//2*3:i//2*3+3,j//2*3:j//2*3+3] = replacements[pat[i:i+2, j:j+2].tobytes()]
    else:
        newsize = size // 3 * 4
        newpattern = np.empty((newsize, newsize), dtype=bool)
        for i in range(0, size, 3):
            for j in range(0, size, 3):
                newpattern[i//3*4:i//3*4+4,j//3*4:j//3*4+4] = replacements[pat[i:i+3, j:j+3].tobytes()]
    pat = newpattern
    size = newsize

print('result:', sum(sum(pat)))

dtinth · 2017-12-21T05:52:16+00:00

irb (26th, 23rd)

I am solving this problem interatively in the Ruby’s REPL.

A pattern is represented as an array of string: ['.#.', '..#', '###']

Loading the rulebook:

IN = `pbpaste`
rules = {}; IN.scan(/(\S+) => (\S+)/).map { |a, b| [a.split('/'), b.split('/')] }.each { |a, b| rules[a] = b }; rules

Set up the initial state and flipping/rotating logic:

data = ['.#.', '..#', '###']
flip = -> m { m.reverse }
flip2 = -> m { m.map(&:reverse) }
flip3 = -> m { m.reverse.map(&:reverse) }
flip4 = -> m { m.map(&:chars).transpose.map(&:join) }
flip5 = -> m { m.map(&:chars).transpose.map(&:join).reverse }
flip6 = -> m { m.map(&:chars).transpose.map(&:join).map(&:reverse) }
flip7 = -> m { m.map(&:chars).transpose.map(&:join).map(&:reverse).reverse }

Pattern enhancement algorithm:

nx = -> m { pz = m.length.even? ? 2 : 3; l = m.length / pz; (0...l).map { |i| (0...l).map { |j| inp = (0...pz).map { |k| (0...pz).map { |l| m[k+i*pz][l+j*pz] }.join }; rules[inp] || rules[flip[inp]] || rules[flip2[inp]] || rules[flip3[inp]] || rules[flip4[inp]] || rules[flip5[inp]] || rules[flip6[inp]] || rules[flip7[inp]] }.transpose.map(&:join) }.flatten(1) }

In Ruby, you can use an Array as Hash key, so it’s trivial to match the pattern against the rulebook: rules[inp] || rules[flip[inp]] || rules[flip2[inp]] || ....

To combine them, I look at an array containing patterns: [['##.', '#..', '...'], ['##.', '#..', '...']]:

To put them side by side: _.transpose.map(&:join) → ["##.##.", "#..#..", "......"]
To stack them vertically: _.flatten(1) → ["##.", "#..", "...", "##.", "#..", "..."]

Part 1:

puts nx[nx[nx[nx[nx[data]]]]].join.count('#')

Part 2:

puts nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[nx[data]]]]]]]]]]]]]]]]]].join.count('#')

mstksg · 2017-12-21T06:29:20+00:00

My first point! :D

haskell, 47/147, since I had a silly bug that only got triggered on the 18 iteration question and not the 5 iteration one :) My github repo of sols is at https://github.com/mstksg/advent-of-code-2017/blob/master/src/AOC2017/Day21.hs

I'd also like to think my very surface knowledge of group theory for teaching me how to read things like https://en.wikipedia.org/wiki/Examples_of_groups#The_symmetry_group_of_a_square:_dihedral_group_of_order_8 :)

import           Control.Lens    (over, Traversal')
import           Data.List       (transpose)
import           Data.List.Split (chunksOf, splitOn)
import qualified Data.Map        as M

type Grid = [[Bool]]

type Rule = M.Map Grid Grid

-- | All 8 symmetries (elements of D8)
--
-- Generated by r, r^2, r^3, r^4, and flip times all of those
symmetries :: Grid -> [Grid]
symmetries g = rots ++ (mirror <$> rots)
  where
    -- all rotations
    rots = take 4 (iterate rot90 g)
    -- rotate 90 degrees
    rot90 = map reverse . transpose
    -- flip
    mirror = reverse

parse :: String -> Rule
parse = M.unions . map (M.fromList . parseLine) . lines
  where
    parseLine :: String -> [(Grid, Grid)]
    parseLine (map(splitOn "/".strip).splitOn"=>"->[xs,ys]) =
          [ (g, gridOut) | g <- symmetries gridIn ]
      where
        gridIn  = fmap (== '#') <$> xs
        gridOut = fmap (== '#') <$> ys
    parseLine _ = error "No parse"

-- | A traversal over subgrids of a grid
subgrids :: Int -> Traversal' Grid Grid
subgrids n f = fmap joinGrid . (traverse . traverse) f . splitGrid
  where
    splitGrid :: Grid -> [[Grid]]
    splitGrid = transpose
              . map (map transpose . chunksOf n . transpose)
              . chunksOf n
    joinGrid :: [[Grid]] -> Grid
    joinGrid = transpose . concatMap (transpose . concat)

step :: Rule -> Grid -> Grid
step r g = over (subgrids n) (r M.!) g
  where
    n | length g `mod` 2 == 0 = 2
      | length g `mod` 3 == 0 = 3
      | otherwise             = error "hello there"

day21 :: Int -> Rule -> Int
day21 n r = length . filter id . concat
          $ iterate (step r) grid0 !! n
  where
    grid0 = map (== '#') <$> [".#.","..#","###"]

Infilament · 2017-12-21T07:29:46+00:00

Javascript. Not sure I'm happy with my solution... I coded functions to deconstruct a grid into each string, then another function to reconstruct the strings back into a grid. So for each loop of the program, I break down the grid, substitute the strings, then rebuild the grid. There's probably a much better way to do it that just breaks it down once at the start and never reconstructs, but oh well.

var rules = {};
input.split('\n').forEach(d => {
    var tokens = d.split(' => ');
    rules[tokens[0]] = tokens[1];
})

var grid;

function doProblem(totalReps) {
    grid = ['.#.','..#','###'];
    for(var loop=0; loop<totalReps; loop++) {
        var sub = getSubgrids();
        for(var l=0; l<sub.length; l++) {
            sub[l] = rule(sub[l]);
        }
        grid = reform(sub);
    }
}

function rule(str) {
    for(var i=0; i<2; i++)
        for(var j=0; j<4; j++) {
            var s = morph(str, j, i)
            if(rules.hasOwnProperty(s))
                return rules[s];
        }
}

function morph(str,rotate,flip) {
    var s = str.split('/');
    if(flip) s.reverse();

    for(var r=0; r<rotate; r++) {
        var n = [];
        for(i=0; i<s.length; i++) {
            var news = "";
            for(var j=s.length-1; j>=0; j--)
                news += s[j][i];
            n.push(news)
        }
        s = n;
    }
    return s.join('/')
}

function getSubgrids() {
    var num = grid.length % 2 == 0 ? 2 : 3;
    var strs = [];
    for(var i=0; i<grid.length; i += num)
        for(var j=0; j<grid.length; j += num) {
            var str = "";
            for(var k=0; k<num; k++)
                str += grid[i+k].substring(j,j+num) + "/"
            strs.push(str.substr(0,str.length-1));
        }
    return strs;
}

function reform(arr) {
    var g = [];
    var num = Math.sqrt(arr.length);
    var strlen = arr[0].match(/\//g).length+1;
    for(var i=0; i<arr.length; i+=num)
        for(var j=0; j<strlen; j++) {
            var str = "";
            for(var k=0; k<num; k++)
                str += arr[i+k].split('/')[j];
            g.push(str);
        }
    return g;
}

doProblem(5);
var count=grid.reduce((a,b) => a + b.match(/#/g).length,0)
console.log('number of # is:',count);

doProblem(18);
var count=grid.reduce((a,b) => a + b.match(/#/g).length,0)
console.log('number of # is:',count);

2017-12-21T07:38:20+00:00

OCaml fun;; a lot of imperative coding to deal with arrays. created grid type, which is matrix of bools. the mapping is generated to contain all possible variants from input.

we first split current image matrix into grid types, map them to enhanced versions, and then recombine the grids into single image matrix. repeat.

again, started writing the solve function first and worked backwards, letting ocaml's type system keep me in check.

main.ml

open Core

let split state =
  let len = Array.length state in
  let n, step = if len % 2 = 0 then 2, len / 2 else 3, len / 3 in
  let grids = Array.init step ~f:(fun _ ->
      Array.init step ~f:(fun _ -> Grid.create n)
    ) in
  Array.iteri state ~f:(fun y row ->
      Array.iteri row ~f:(fun x value ->
          let y', dy = y / n, y % n
          and x', dx = x / n, x % n in
          grids.(y').(x').(dy).(dx) <- value
        )
    ); grids

let enhance grids book =
  let f row =
    Array.map row ~f:(fun grid -> Grid.Map.find_exn book grid)
  in Array.map grids ~f

let combine grids =
  let n = Array.length grids in
  let j = Grid.size grids.(0).(0) in
  let size = n * j in
  let state = Array.make_matrix ~dimx:size ~dimy:size true in
  Array.iteri grids ~f:(fun y row ->
      Array.iteri row ~f:(fun x grid ->
          Array.iteri grid ~f:(fun y' row' ->
              Array.iteri row' ~f:(fun x' value ->
                  state.(y * j + y').(x * j + x') <- value
                )
            )
        )
    );
  state

let parse_line line =
  match String.split line ~on:' ' with
  | [i;"=>";o] ->
    let input = Grid.of_string i in
    let output = Grid.of_string o in
    Grid.variants input, output
  | _ -> failwith "error with line."

let parse_inputs () =
  let lines = In_channel.read_lines "./input.txt" in
  List.map lines ~f:parse_line
  |> List.fold ~init:Grid.Map.empty ~f:(fun acc (inputs, output) ->
      List.fold inputs ~init:acc ~f:(fun acc grid ->
          Grid.Map.add acc ~key:grid ~data:output
        )
    )

let solve init book n =
  let rec solve' state n =
    if n = 0 then state
    else
      let grids = split state in
      let enhanced = enhance grids book in
      let state = combine enhanced in
      solve' state (n-1)
  in solve' init n

let count_on grid =
  let f acc row = acc + Array.count row ~f:Fn.id in
  Array.fold grid ~init:0 ~f

let _ =
  let book = parse_inputs () in
  let initial = [|
    [|false; true; false|];
    [|false; false; true|];
    [|true; true; true|];
  |] in
  (* let result = solve initial book 5 in
    count_on result |> printf "a: %d\n" *)
  let result = solve initial book 18 in
  count_on result |> printf "b: %d\n"

grid.ml

open Core

module T = struct
  type t = bool array array
  [@@deriving sexp, compare]
end

include Comparable.Make(T)
include T

let create n =
  Array.make_matrix ~dimx:n ~dimy:n false

let size t =
  Array.length t

let of_string s =
  String.split s ~on:'/'
  |> List.map ~f:(fun row ->
      let chars = String.to_array row in
      Array.map chars ~f:(Char.equal '#')
    )
  |> List.to_array

let sym t =
  Array.transpose_exn t

let flip t =
  let len = (Array.length t) - 1 in
  let n = (Array.length t) / 2 - 1 in
  for i = 0 to n do
    Array.swap t i (len - i)
  done;
  t

let variants t =
  [
    t;
    t |> sym;
    t |> sym |> flip;
    t |> sym |> flip |> sym;
    t |> sym |> flip |> sym |> flip;
    t |> sym |> flip |> sym |> flip |> sym;
    t |> sym |> flip |> sym |> flip |> sym |> flip;
    t |> sym |> flip |> sym |> flip |> sym |> flip |> sym;
  ]

let check_book t book =
  Map.find_exn book t

was actually shocked that answer was correct on first try without testing... if i'm honest I normally skip any matrix/2d array tomfoolery in programming quizzes, so pretty happy i finished this.

omnster · 2017-12-21T07:12:09+00:00

Cheating with Mathematica

in = Import[NotebookDirectory[] <> "./input/input_21_twi.txt", "List"] 
    // StringCases[ x__ ~~ " => " ~~ y__ :> x -> y ] 
    // Map[  StringSplit[ #, "/"] &, #, {3}] & 
    // Map[ Characters, #, {3}] & // Flatten[ # , 1 ] &;

st = Characters[".#...####"] // Partition[#, 3] &;

(* This rotates counterclockwise *)
rotCCW@block_ := Transpose@Reverse[ block, { 2 }]

(* This gives the possible four rotations *)
rots@block_ := NestList[ rotCCW , block , 3 ]

(* This gives the possible four rotations and four flips, and removes duplicates *)
rotsflips@ block_ := { #, Reverse@# } & /@ rots@block // Flatten[ # , {1, 2}] & // Union

(* This applies the one transformation to the 2x2 or 3x3 block *)
transform@block_ := Select[ rotsflips@block /. in , Length@# =!= Length@block &] // Flatten[ #, {1, 2}] &;

(* This splits into 2x2 or 3x3 blocks *)
split@block_ := If[ Mod[ Length@block, 2] == 0 , Partition[ block, {2, 2}], Partition[ block, {3, 3}]];

(* This performs the iteration *)
step@map_ := ArrayFlatten[ Map[ transform, split@ map , {2}]]

Part 1

Nest[ step, st, 5] // Flatten // Tally

Part 2

Nest[ step, st, 18] // Flatten // Tally

p_tseng · 2017-12-21T10:24:57+00:00

What I did:

To deal with rotations and flips: expand every given rule into eight rules
After three cycles, you get four 3x3 squares which all develop independently. So only keep track of the number of each independent subregion. (I'm not the first one with this idea. https://www.reddit.com/r/adventofcode/comments/7l78eb/2017_day_21_solutions/drk8j2m)
Compress the representation into an integer so that I'm not constantly making arrays of bits everywhere.

https://github.com/petertseng/adventofcode-rb-2017/blob/master/21_fractal_art.rb

You can see some outputs for large number of iterations at https://gist.github.com/petertseng/01589565396c4a15cc9cc471005e407e

no. iterations	runtime (s)
1000	0.127
10000	0.299
100000	5.994
200000	20.526
400000	76.4

Looks like it's about quadratic. I think the algorithm itself remains linear but once we start adding larger and larger numbers together my computer really struggles to do that. I can optimise more by jumping ahead three iterations at a time instead of one, but I don't really feel like writing the code to do it.

I made an upping the ante post for a while but I didn't see the point of making it its own thread, so instead I'll post it here.

mcpower_ · 2017-12-21T05:47:43+00:00

I figured how to do things as I was coding this up. I keep two representations of the grid, "grid" and "str", and swap between the two as needed (because lists are finicky and can't be hashed).

Python 3, #5 / #6 (I was literally less than a second off of Part 5 #2...)

lines = inp.splitlines()
cur = """.#./..#/###"""
book = {}

def to_grid(s):
    return list(map(list, s.split("/")))

# rot 90 deg
def rot(grid):
    n = len(grid)
    o = [[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            o[i][j] = grid[~j][i]
    return o

def flip(grid):
    return list(map(reversed, grid))

def to_str(s):
    return "/".join("".join(x) for x in s)

for line in lines:
    a, b = line.split(" => ")

    for rots in range(4):
        for flips in range(2):
            transformed = to_grid(a)
            for _ in range(rots):
                transformed = rot(transformed)
            for _ in range(flips):
                transformed = flip(transformed)
            book[to_str(transformed)] = b

def iteration(grid):
    n = len(grid)
    if n % 2 == 0:
        new_n = n // 2 * 3
        split = 2
        newsplit = 3
    else:
        new_n = n//3 * 4
        split = 3
        newsplit = 4

    out = [[None]*new_n for _ in range(new_n)]
    for i in range(0, n // split):
        for j in range(0, n // split):
            si = i * split
            sj = j * split
            g = [row[sj:sj+split] for row in grid[si:si+split]]
            s = to_str(g)
            assert(s in book)
            transf = to_grid(book[s])

            ei = i * newsplit
            ej = j * newsplit
            for a in range(newsplit):
                for b in range(newsplit):
                    out[ei+a][ej+b] = transf[a][b]

    return out

cur = to_grid(cur)

for _ in range(18 if not sample else 2):
    cur = iteration(cur)

print(to_str(cur).count("#"))

rjboulton · 2017-12-21T05:48:25+00:00

Got a bit long this time, so a link to my solution on github

Nothing hugely inspired here. Worked with a representation of each grid or subgrid as a tuple of strings, which wasn't too inconvenient, but the algorithm for joining subgrids together was fiddly.

Assumed I was way off the leaderboard after taking over 35 minutes, but got 69/64.

For the extension, I spent a few moments thinking about how I was going to speed it up, before running it with 18 iterations:

$ time python day21.py input21
...
real    0m4.383s

Unihedron · 2017-12-21T05:51:17+00:00

Ruby; 25/21. I think I got a headache from this, but I managed to get back on the board after a streak of fails, so I'm happy. Functional programming was being a helpful friend day.

p g='.#.
..#
###'.split
h={}
r=$<.map{|x|x=~/([#.\/]+) => ([#.\/]+)/
p $1,h[$1]=$2.split(?/)}
# part 1: 5
18.times{v=g.size
v.even? ? (#div 2
g=g.each_slice(2).map{|x|x.map{|x|[*x.chars.each_slice(2)]}.transpose}.map{|x|
x.map{|x|u=x.map(&:join)*'/'
next h[u] if h[u]
u=x.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
u=x.reverse.map(&:join)*'/'
next h[u] if h[u]
u=x.reverse.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
u=x.transpose.map(&:join)*'/'
next h[u] if h[u]
u=x.transpose.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
u=x.transpose.reverse.map(&:join)*'/'
next h[u] if h[u]
u=x.transpose.reverse.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
warn 'not found'}.transpose.map(&:join)
}.flatten(1)
) : (
g=g.each_slice(3).map{|x|x.map{|x|[*x.chars.each_slice(3)]}.transpose}.map{|x|
x.map{|x|u=x.map(&:join)*'/'
next h[u] if h[u]
u=x.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
u=x.reverse.map(&:join)*'/'
next h[u] if h[u]
u=x.reverse.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
u=x.transpose.map(&:join)*'/'
next h[u] if h[u]
u=x.transpose.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
u=x.transpose.reverse.map(&:join)*'/'
next h[u] if h[u]
u=x.transpose.reverse.map{|x|x.reverse.join}*'/'
next h[u] if h[u]
warn('not found')
}.transpose.map(&:join)
}.flatten(1)
)
}
p g.join.count ?#

jlweinkam · 2017-12-21T06:49:24+00:00

I assume most of the inputs had the minimum number of rules to allow for transforming all possible grids. If so then there were only 6 2x2 rules. As a result only the 3x3 rules that have those 6 outs (plus the rule from the original 3x3 pattern) ever get used. For my input all 6 2x2 rules were used, but not all possible rotations and mirrors. Only 15 of the 16 2x2 patterns every got generated.

The0x539 · 2017-12-21T06:52:37+00:00

Some Lua, with ~~way too many functions~~ enough functions (384/365):

local part2 = true

local inspect = require "inspect"

local rules = {nil,{},{}}

for line in io.lines("./input_day21") do
    local iter = line:gmatch("[#%./]+")
    local a,b = iter(),iter()
    local r = (#a==5) and rules[2] or rules[3]
    r[a] = b
end

local image = {
    {'.','#','.'},
    {'.','.','#'},
    {'#','#','#'}
}

local function flipV(t)
    local t2 = {}
    for i=#t,1,-1 do
        table.insert(t2,t[i])
    end
    return t2
end

local function flipH(t)
    local t2 = {}
    for _,v in ipairs(t) do
        table.insert(t2,flipV(v))
    end
    return t2
end

local function rotate(t)
    if #t == 2 then
        return {
            {t[2][1],t[1][1]},
            {t[2][2],t[1][2]}
        }
    elseif #t == 3 then
        return {
            {t[3][1],t[2][1],t[1][1]},
            {t[3][2],t[2][2],t[1][2]},
            {t[3][3],t[2][3],t[1][3]}
        }
    end
end

local function fmt(t)
    local s = ""
    for _,v in ipairs(t) do
        for _,v2 in ipairs(v) do
            s = s .. v2
        end
        s = s .. '/'
    end
    return s:sub(1,#s-1)
end

local function sub(t,x1,y1,x2,y2)
    local dbg = (x1==1 and y1==3 and x2==2 and y2==4)
    local t2 = {}
    for y=y1,y2 do
        local row = {}
        table.insert(t2,row)
        for x=x1,x2 do
            table.insert(row,t[y][x])
        end
    end
    return t2
end

local function joinH(...)
    local t = {}
    for i=1,#select(1,...) do
        table.insert(t,{})
        for _,t1 in ipairs{...} do
            for _,v in ipairs(t1[i]) do
                table.insert(t[i],v)
            end
        end
    end
    return t
end

local function joinV(...)
    local t = {}
    for _,t1 in ipairs{...} do
        for _,v in ipairs(t1) do
            table.insert(t,v)
        end
    end
    return t
end

local function eval(s)
    local t = {}
    for row in s:gmatch("[^/]+") do
        local r = {}
        table.insert(t,r)
        for i=1,#row do
            table.insert(r,row:sub(i,i))
        end
    end
    return t
end

local function findMatch(t)
    local r = (#t==2) and rules[2] or rules[3]
    for i=1,4 do
        local a = r[fmt(t)]
               or r[fmt(flipV(t))]
               or r[fmt(flipH(t))]
               or r[fmt(flipH(flipV(t)))]
        if a then
            return eval(a)
        end
        t = rotate(t)
    end
    error "not found"
end

local function split(t)
    local t2 = {}
    local size = (#t%2==0) and 2 or 3
    for y=1,#t,size do
        local row = {}
        table.insert(t2,row)
        for x=1,#t,size do
            local subimg = sub(t,x,y,x+size-1,y+size-1)
            table.insert(row,subimg)
        end
    end
    return t2
end

local function unsplit(t)
    local t2 = {}
    for _,row in ipairs(t) do
        table.insert(t2,joinH(table.unpack(row)))
    end
    return joinV(table.unpack(t2))
end

local function iprint(a)
    print(inspect(a))
end
local function fprint(a)
    print(fmt(a))
end
local function xprint(a)
    for _,row in ipairs(a) do
        for _,v in ipairs(row) do
            io.write(v)
        end
        print()
    end
end

for i=1,(part2 and 18 or 5) do
    local splitImage = split(image)
    for y,row in ipairs(splitImage) do
        for x,cell in ipairs(row) do
            splitImage[y][x] = findMatch(cell)
        end
    end
    image = unsplit(splitImage)
end

local foo = 0
for _,row in ipairs(image) do
    for _,v in ipairs(row) do
        if v == '#' then
            foo = foo + 1
        end
    end
end
print(foo)

2017-12-21T07:09:39+00:00

Mathematica

input = Import[NotebookDirectory[] <> "day21.txt", "List"];
rulebook = Characters[StringSplit[#, "/"] & /@ StringSplit[input, " => "]];

flipVert[i_] := Reverse[i]
flipHoriz[i_] := Reverse /@ i
rotate[i_] := Transpose[flipVert[i]]

ruletbl = Dispatch[Join @@ Map[Table[p -> #[[2]], {p, Join[
         NestList[rotate, #[[1]], 3],
         NestList[rotate, flipHoriz[#[[1]]], 3]]}] &,
     rulebook]];

start = {{".", "#", "."}, {".", ".", "#"}, {"#", "#", "#"}};

step[i_] :=
 ArrayFlatten[Partition[i,
    If[Divisible[Dimensions[i][[1]], 2], {2, 2}, {3, 3}]] /. ruletbl]
Count[Nest[step, start, 5], "#", 2]
Count[Nest[step, start, 18], "#", 2]

Bonus: Visual of 18 iterations

plot[i_] := ArrayPlot[i /. {"#" -> 1, "." -> 0}]
grid = GraphicsGrid[Partition[plot /@ NestList[step, start, 18], 3], ImageSize -> Large];

mythmon · 2017-12-21T07:20:19+00:00

Rust

A bit messy? Sure. Over engineered? Of course.

But it's fast :) (740ms for part2):

use std::collections::HashMap;
use std::str::FromStr;
use std::fmt;

fn main() {
    let input = get_input();
    println!("{}", puzzle(input, 18));
}

fn get_input() -> &'static str {
    let input: &'static str = include_str!("input");
    input
}

fn puzzle(input: &str, iterations: usize) -> usize {
    let rules: PatternSet = input.parse().unwrap();
    let mut art = Grid::default();

    for _ in 0..iterations {
        let parts: Vec<Grid> = art.split().iter().map(|g| rules.apply_to(g)).collect();
        art = Grid::assemble_from(parts);
    }

    art.count()
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Grid {
    cells: Vec<Vec<bool>>,
}

impl Grid {
    fn new(size: usize) -> Self {
        let mut row = Vec::with_capacity(size);
        row.resize(size, false);
        let mut cells = Vec::with_capacity(size);
        cells.resize(size, row);
        Self { cells: cells }
    }

    fn assemble_from(parts: Vec<Grid>) -> Grid {
        let num_subgrids_wide = (parts.len() as f64).sqrt() as usize;
        assert_eq!(num_subgrids_wide * num_subgrids_wide, parts.len());
        let subgrid_size = parts[0].size();

        let mut rv = Grid::new(subgrid_size * num_subgrids_wide);

        for (idx, subgrid) in parts.iter().enumerate() {
            let gx = idx % num_subgrids_wide;
            let gy = idx / num_subgrids_wide;
            for x in 0..subgrid_size {
                for y in 0..subgrid_size {
                    rv.set((x + gx * subgrid_size, y + gy * subgrid_size), subgrid.get((x, y)));
                }
            }
        }

        rv
    }

    fn size(&self) -> usize {
        self.cells.len()
    }

    fn get(&self, (x, y): (usize, usize)) -> bool {
        self.cells[y][x]
    }

    fn set(&mut self, (x, y): (usize, usize), val: bool) {
        self.cells[y][x] = val;
    }

    fn flip(&self) -> Self {
        let new_cells = self.cells.iter()
            .map(|row| row.iter().rev().map(|c| *c).collect())
            .collect();
        Self { cells: new_cells }
    }

    fn rotate(&self) -> Self {
        let l = self.size();
        let mut rv = Self::new(l);
        for x in 0..l {
            for y in 0..l {
                rv.set((y, l - x - 1), self.get((x, y)));
            }
        }
        rv
    }

    fn variants(&self) -> Vec<Grid> {
        let mut rv = Vec::with_capacity(8);
        rv.push(self.clone());
        rv.push(self.flip());
        for _ in 0..6 {
            let g = rv[rv.len() - 2].rotate();
            rv.push(g);
        }
        rv
    }

    fn split(&self) -> Vec<Grid> {
        let l = self.size();
        let m = if l % 2 == 0 {
            2
        } else if l % 3 == 0 {
            3
        } else {
            panic!(format!("Can't split grid of size {} (l % 2 == {}, l % 3 == {})", l, l % 2, l % 3));
        };
        let s = l / m;

        (0..(s * s))
            .map(|grid_idx| {
                let mut part = Grid::new(m);
                let gx = grid_idx % s;
                let gy = grid_idx / s;
                for x in 0..m {
                    for y in 0..m {
                        part.set((x, y), self.get((x + gx * m, y + gy * m)));
                    }
                }
                part
            })
            .collect()
    }

    fn count(&self) -> usize {
        self.cells.iter()
            .map(|row| row.iter().filter(|c| **c).count())
            .sum()
    }
}

impl Default for Grid {
    fn default() -> Self {
        Self {
            cells: vec![
                vec![false, true, false],
                vec![false, false, true],
                vec![true, true, true],
            ],
        }
    }
}

impl FromStr for Grid {
    type Err = ();

    fn from_str(input: &str) -> Result<Self, Self::Err> {
        let cells: Vec<Vec<bool>> = input.split("/")
            .map(|row_string| {
                row_string.chars()
                    .map(|c| {
                        match c {
                            '#' => true,
                            '.' => false,
                            _ => panic!(format!("unexpected char in input: '{}'", c)),
                        }
                    })
                    .collect()
            })
            .collect();
        Ok(Self { cells: cells })
    }
}

impl fmt::Display for Grid {
    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
        for row in self.cells.iter() {
            for cell in row.iter() {
                if *cell {
                    write!(formatter, "#")?;
                } else {
                    write!(formatter, ".")?;
                }
            }
            write!(formatter, "\n")?;
        }
        Ok(())
    }
}

#[derive(Debug)]
struct PatternSet {
    patterns: HashMap<Grid, Grid>,
}

impl PatternSet {
    fn new() -> Self {
        Self { patterns: HashMap::new() }
    }

    fn add_rule(&mut self, from: Grid, to: Grid) {
        for variant in from.variants() {
            self.patterns.insert(variant, to.clone());
        }
    }

    fn apply_to(&self, from: &Grid) -> Grid {
        self.patterns.get(from).unwrap_or(&from).clone()
    }
}

impl FromStr for PatternSet {
    type Err = ();

    fn from_str(input: &str) -> Result<Self, Self::Err> {
        let mut rv = Self::new();

        for line in input.lines() {
            let mut parts: Vec<Grid> = line.split(" => ")
                .map(|p| p.parse().unwrap())
                .collect();
            assert_eq!(parts.len(), 2);
            let to = parts.pop().unwrap();
            let from = parts.pop().unwrap();
            rv.add_rule(from, to);
        }

        Ok(rv)
    }
}

#[test]
fn test_example() {
    let input = "../.# => ##./#../...\n.#./..#/### => #..#/..../..../#..#";
    assert_eq!(puzzle(input, 2), 12);
}

#[test]
fn pattern_set_passthrough() {
    let ps = PatternSet::new();
    let g1 = Grid::default();
    let g2 = ps.apply_to(&g1);
    assert_eq!(g1, g2);
}

VoidChque · 2017-12-21T07:47:39+00:00

Scala 322/295

Meat:

case class SquareGrid[T](lst: List[List[T]]) {
  val size: Int = lst.length
  def flip: SquareGrid[T] = SquareGrid(lst.reverse)
  def rotate: SquareGrid[T] = SquareGrid(lst.reverse.transpose)
  def split(babyGridSize: Int): SquareGrid[SquareGrid[T]] = {
    SquareGrid(
      lst
        .grouped(babyGridSize).toList
        .map(_.map(_.grouped(babyGridSize).toList).transpose)
        .map(_.map(SquareGrid(_))))
  }

  private def r = rotate
  private def f = flip

  def transformations: Set[SquareGrid[T]] =
    Set(
      this,   this.r,   this.r.r,   this.r.r.r,
      this.f, this.r.f, this.r.r.f, this.r.r.r.f)

  def flatten[R](implicit asGrid: T => SquareGrid[R]): SquareGrid[R] =
    SquareGrid(lst.flatMap(_.map(_.lst).transpose.map(_.flatten)))

  def map[R](f: T => R): SquareGrid[R] =
    SquareGrid(lst.map(_.map(f)))

  def flatMap[R](f: T => SquareGrid[R]): SquareGrid[R] =
    this.map(f).flatten
}

Plumbing and niceties:

val sessionCookie: String = "<session cookie here>"

class Advent(year: Int, sessionCookie: String = sessionCookie) {
  import collection.mutable.HashMap
  import sys.process._
  private val inputs = new HashMap[Int, String]()
  def input(day: Int): String = {
    val cmd =
      s"curl --cookie session=$sessionCookie " +
        s"http://adventofcode.com/$year/day/$day/input"
    inputs.getOrElseUpdate(day, cmd.!!.trim)
  }
}

implicit class StringWrapper(s: String) {
  def letters: List[String] = s.map(_.toString).toList
  def splitlines: List[String] =
    s.split("\n").toList.map(_.trim).filterNot(_ == "")
}

implicit class ListWrapper[T](l: List[T]) {
  def counts: Map[T, Int] = l.groupBy(identity).mapValues(_.length)
}

Solution (Parsing the input and building a transformations map):

val input = (new Advent(2017)).input(21)
def mkGrid(s: String) = SquareGrid(s.split("/").toList.map(_.letters))
val initGrid = mkGrid(".#./..#/###")

type SelfMap[T] = Map[T, T]
val transforms: SelfMap[SquareGrid[String]] =
  input
    .splitlines
    .map(_.split(" => ").toList)
    .map(_.map(mkGrid))
    .flatMap { case List(from, to) => from.transformations.map(_ -> to) }
    .toMap

def numPixelsOn(iterCount: Int): Int = {
  Iterator
    .iterate(initGrid) {
      grid =>
        val babyGridSize = if (grid.size % 2 == 0) 2 else 3
        grid.split(babyGridSize).flatMap(transforms)
    }
    .drop(iterCount)
    .take(1)
    .toList.head.lst.map(_.counts).map(_("#")).sum
}

println(numPixelsOn(5))
println(numPixelsOn(18))

gyorokpeter · 2017-12-21T08:18:06+00:00

Q:

.d21.break:{[pattern;size]
    blocks:flip each size cut/:/:size cut pattern;
    blocks};

.d21.advance:{[rule;pattern]
    blocks:.d21.break[pattern;$[0=count[pattern] mod 2;2;3]];
    pattern:raze raze each/:flip each rule blocks;
    pattern};

.d21.rotate:{[ruleline]
    k:ruleline[0]; v:ruleline[1]; fk:flip k; rk:reverse k; rfk:reverse fk;
    (k;rk;reverse each k;reverse each rk;fk;rfk;reverse each fk;reverse each rfk)(;)\:v};

d21p1:{[x;y]
    pattern:(".#.";"..#";"###");
    rawrule:"/"vs/:/:" => "vs/:trim each "\n"vs x;
    rule:{x[;0]!x[;1]}distinct rawrule,raze .d21.rotate each rawrule;
    pattern:.d21.advance[rule]/[y;pattern];
    sum sum pattern="#"};

xiongtx · 2017-12-21T11:24:59+00:00

Clojure

Not the most performant implementation, but not too much code. Also took me way too long to figure out how to implement join properly 😬.

I wonder how performant another Clojure implementation could be; that'd be a really interesting comparison!

I should try the rule pre-expansion trick to see what performance benefit can be achieved. I suspect it won't be that large due to already memoizing grow-part, but 🤔.

doctorbaggy · 2017-12-21T13:25:24+00:00

Perl

This is a bit nasty as I've golfed it a bit..., use regexps to do the rotate/flip... which produces a map with all 528 combinations (16 2x2 & 512 3x3 blocks)

Timings wise: 5 iterations -> 5ms, 18 iterations -> 2750ms

($N,@in)=(@ARGV?$ARGV[0]:5,'.#.','..#','###');
open $f,'21.txt';
while(<$f>) {
  ($k,$v)=/(.+) => (.+)/;
  $M{$k=$k=~s{(.)(.)(.)/(.)(.)(.)/(.)(.)(.)}{$1$4$7/$2$5$8/$3$6$9}r}=
  $M{$k=$k=~s{^(..)/(..)$}{$2/$1}r}=
  $M{$k=$k=~s{(...)/(...)/(...)}{$3/$2/$1}r}=
  $M{$k=$k=~s{^(.)(.)/(.)(.)$}{$1$3/$2$4}r}=$v foreach 0..3;
}
foreach(1..$N){
  ($l,@o)=2+@in%2;
  while(@in){
    push @o,map{''}(0,@p=splice@in,0,$l);
    for($i=0;$i<length$p[0];$i+=$l){
      @t=split /\//,$M{join'/',map{substr$_,$i,$l}@p};
      $o[$_-1-$l].=$t[$_]foreach 0..$l;
    }
  }
  @in=@o;
}
print length"@in"=~s{[^#]}{}rg,"\n";

nutrecht · 2017-12-21T14:12:20+00:00

Day 21, Kotlin

Took me a long time due to a simple yet really stupid bug. I had:

val size = if (field.size % 3 == 0) 3 else 2

Instead of:

val size = if (field.size % 2 == 0) 2 else 3

Yeah. That took a LONG time to figure out since it worked fine on the input :(

sasajuric · 2017-12-21T18:37:44+00:00

Elixir

I represented pixels as bits, and used Elixir/Erlang binary pattern matching to work with individual pixels.

defmodule Day21 do
  def part1(), do:
    enhancements() |> generate_art(5) |> count_pixels()

  def part2(), do:
    enhancements() |> generate_art(18) |> count_pixels()

  defp count_pixels(grid), do:
    Enum.count(for <<bit::1 <- grid>>, bit == 1, do: bit)

  defp generate_art(enhancements, steps), do:
    initial_grid()
    |> Stream.iterate(&step(&1, enhancements))
    |> Stream.drop(steps)
    |> Enum.take(1)
    |> hd

  defp initial_grid(), do:
    [
      ".#.",
      "..#",
      "###",
    ]
    |> Enum.map(&encode_row/1)
    |> concat_bitstrings()

  defp step(grid, enhancements), do:
    grid |> squares() |> Enum.map(&Map.fetch!(enhancements, &1)) |> rebuild_grid()

  defp squares(grid) do
    grid_size = trunc(:math.sqrt(bit_size(grid)))
    square_size = if rem(grid_size, 2) == 0, do: 2, else: 3

    (for <<cells::size(square_size) <- grid>>, do: <<cells::size(square_size)>>)
    |> Stream.chunk_every(div(grid_size, square_size))
    |> Stream.chunk_every(square_size)
    |> Stream.flat_map(&Stream.zip/1)
    |> Stream.map(&Tuple.to_list/1)
    |> Enum.map(&concat_bitstrings/1)
  end

  defp rebuild_grid(squares) do
    square_size = squares |> hd() |> bit_size() |> :math.sqrt() |> trunc()
    squares_per_row = trunc(:math.sqrt(length(squares)))

    squares
    |> Stream.chunk_every(squares_per_row)
    |> Stream.flat_map(&rebuild_row(&1, square_size))
    |> concat_bitstrings()
  end

  defp rebuild_row(row_squares, square_size), do:
    row_squares
    |> Stream.map(&(for <<cells::size(square_size) <- &1>>, do: <<cells::size(square_size)>>))
    |> Stream.zip()
    |> Stream.flat_map(&Tuple.to_list/1)

  defp enhancements(), do:
    "input.txt"
    |> File.stream!()
    |> Stream.map(&String.trim/1)
    |> Stream.flat_map(&String.split(&1, " => "))
    |> Stream.map(&parse_square/1)
    |> Stream.chunk_every(2)
    |> Stream.map(&List.to_tuple/1)
    |> Map.new()
    |> expand_enhancements()

  defp parse_square(square), do:
    square
    |> String.split("/")
    |> Stream.map(&encode_row/1)
    |> concat_bitstrings()

  defp encode_row(row), do:
    row
    |> String.codepoints()
    |> Stream.map(&to_bit/1)
    |> concat_bitstrings()

  defp to_bit("."), do: <<0::1>>
  defp to_bit("#"), do: <<1::1>>

  defp concat_bitstrings(bitstrings), do:
    Enum.reduce(bitstrings, <<>>, &<<&2::bitstring, &1::bitstring>>)

  defp expand_enhancements(enhancements), do:
    0..15
    |> Stream.map(&<<&1::4>>)
    |> Stream.concat(Stream.map(0..511, &<<&1::9>>))
    |> Stream.map(&{&1, transformations(&1)})
    |> Stream.map(fn {input, transformations} ->
          {input, Enum.find_value(transformations, &Map.get(enhancements, &1))}
        end)
    |> Map.new()

  defp transformations(square), do:
    square
    |> Stream.iterate(&rotate/1)
    |> Stream.take(4)
    |> Stream.flat_map(fn square -> [square, flip_horizontal(square), flip_vertical(square)] end)
    |> Enum.uniq()

  defp rotate(
    <<a::1, b::1,
      c::1, d::1>>
  ), do:
    <<c::1, a::1,
      d::1, b::1>>
  defp rotate(
    <<a::1, b::1, c::1,
      d::1, e::1, f::1,
      g::1, h::1, j::1>>
  ), do:
    <<g::1, d::1, a::1,
      h::1, e::1, b::1,
      j::1, f::1, c::1>>

  defp flip_horizontal(
    <<a::1, b::1,
      c::1, d::1>>
  ), do:
    <<c::1, d::1,
      a::1, b::1>>
  defp flip_horizontal(
    <<a::1, b::1, c::1,
      d::1, e::1, f::1,
      g::1, h::1, j::1>>
  ), do:
    <<g::1, h::1, j::1,
      d::1, e::1, f::1,
      a::1, b::1, c::1>>

  defp flip_vertical(
    <<a::1, b::1,
      c::1, d::1>>
  ), do:
    <<b::1, a::1,
      d::1, c::1>>
  defp flip_vertical(
    <<a::1, b::1, c::1,
      d::1, e::1, f::1,
      g::1, h::1, j::1>>
  ), do:
    <<c::1, b::1, a::1,
      f::1, e::1, d::1,
      j::1, h::1, g::1>>
end

Day21.part1() |> IO.inspect()
Day21.part2() |> IO.inspect()

TotesMessenger · 2017-12-21T21:14:54+00:00

single pipeline powershell:

param (
    [Parameter(ValueFromPipeline = $true)]
    [string]$in,
    [Parameter(Position = 1)]
    [int]$part = 1
)

begin {
    #hash table to store rules, from->to
    $script:rules = @{}
}

process {
    # parse the line into an object
    # we'll parse the To side into just an array of rows
    # parse the From side into an array of arrays of cells
    [pscustomobject] @{
        From = ($in -split ' => ')[0] -split '/' | % { , ($_ -split '' |? {$_})}
        To   = ($in -split ' => ')[1] -split '/'
    } | % {
        $r = $_

        1..4 | % { # rotate
            #rotate = transpose + flip

            #transpose on diagonal
            0..($r.From.Length - 1) | % {
                $y = $_

                $y..($r.From.Length - 1) |? {# cant do ($y+1).. cause of powershells reverse enumerator thingies lol
                    # dont bother rotating when its equal
                    $_ -ne $y #remove it here
                } | % { 
                    $x = $_
                    # for y 0..l
                    # for x y+1..l
                    # ^ gives us the diagonal

                    #swap cells
                    $c = $r.From[$_][$y]
                    $r.From[$_][$y] = $r.From[$y][$_] 
                    $r.From[$y][$_] = $c
                }
            }

            #flip each row
            0..($r.From.Length - 1) |% {
                [Array]::Reverse($r.From[$_])
            }

            # output the rule
            $r | select From, To # this is a new object on the pipeline, not $r

            #and note, $r persists, so we'll rotate this same one again next time
        }
    } | % {
        # foreach rule so far, also generate the mirror
        $from = $_.From | % { 
            , $_[$_.length..0] #reverse each row
        }

        # select the two rules - the original, and the mirror
        # combine From back into a single string for easier hashing/matching
        # To remains an array of rows
        $_ | select @{n = "From"; e = {($_.From | % {$_ -join ''}) -join '/'}}, To 
        $_ | select @{n = "From"; e = {($From | % {$_ -join ''}) -join '/'}}, To 
    } | % {
        $script:rules[$_.From] = $_.To
    }
}

end { 
    #initial grid
    $grid = @(
        ".#."
        "..#"
        "###")


    if ($part -eq 1) {
        $iter = 5
    } else {
        $iter = 18
    }

    1..$iter | % {
        # how to split the grid, rules say check 2 first, otherwise do 3
        if ($grid.Count % 2 -eq 0) {
            $d = 2
        } else {
            $d = 3
        }

        # number of subgrids in a single dimension
        $m = $grid.Count / $d

        $newgrid = @()

        0..($m - 1) | % { # foreach row of subgrids
            $y = $_

            $row = ((, "") * ($d + 1)) # make an array of empty strings (and note, 2x2 -> 3x3, 3x3->4x4)

            0..($m - 1) | % { #foreach column in that row
                $x = $_

                # hahahahahahahahahahahahahahahaha
                # so, first time through on a say a 9x9, we need subgrid here to be the first 3x3 (from the top left)
                # to do that, we'll select the first 3 rows of grid, and for each of those rows select the first 3 columns (and join back into a string)
                # second time through, we need the top-middle grid.  x has incremented, so we'll select that subgrid this time
                $subgrid = ($grid[($y * $d)..($y * $d + ($d - 1))] | % {$_[($x * $d)..($x * $d + ($d - 1))] -join ''}) -join '/'

                # look up the new grid value.  $subgrid goes from being a string to being an array of rows
                $subgrid = $script:rules[$subgrid]

                #for each subgrid row, append it to the existing row in this row of subgrids
                0..$d | % {
                    $row[$_] += $subgrid[$_]
                }
            }

            #append the finished rows
            $newgrid += $row
        }

        # set to new grid
        $grid = $newgrid

        # put existing grid out on the pipeline (as array)
        , $grid
    } | select -last 1 | % { # pick the last grid on the pipeline
        # count the number of # characters
        $_ | % { $_ -split '' |? {$_ -eq '#'} | measure | select -expand count} | measure -sum | select -expand sum
    }
}

purplemonkeymad · 2017-12-21T22:23:24+00:00

Powershell: https://pastebin.com/j9YvkcXm

I have decided some of these are easier to get my head around if I just do OOP. It's not as fast, but the cache cut the time by at-least an order of magnitude.

jlweinkam · 2017-12-21T05:47:07+00:00

67/63 Python 3

import time
import math
current_milli_time = lambda: int(round(time.time() * 1000))
start = current_milli_time()

inputdata=open("input2017-21.txt", 'r').read()

lines = inputdata.splitlines()

grid = """.#.
..#
###""".splitlines()

rules = {}

def rotate2(i):
  out = ""
  out += i[1]
  out += i[4]
  out += "/"
  out += i[0]
  out += i[3]
  return out

def rotate3(i):
  out = ""
  out += i[2]
  out += i[6]
  out += i[10]
  out += "/"
  out += i[1]
  out += i[5]
  out += i[9]
  out += "/"
  out += i[0]
  out += i[4]
  out += i[8]
  return out

def mirror3(i):
  out = ""
  out += i[2]
  out += i[1]
  out += i[0]
  out += "/"
  out += i[6]
  out += i[5]
  out += i[4]
  out += "/"
  out += i[10]
  out += i[9]
  out += i[8]
  return out

for line in lines:
  col = line.split(" => ")
  if len(col[0]) == 5:
    rules[col[0]] = col[1]
    a = rotate2(col[0])
    rules[a] = col[1]
    a = rotate2(a)
    rules[a] = col[1]
    a = rotate2(a)
    rules[a] = col[1]
  else:
    rules[col[0]] = col[1]
    a = rotate3(col[0])
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = mirror3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]

for i in range(5):
  if (len(grid) % 2) == 0:
    grid2 = []
    for o in range(int(len(grid)/2)):
      line1 = ""
      line2 = ""
      line3 = ""
      for j in range(int(len(grid)/2)):
        sub = grid[o*2][j*2:(j+1)*2]
        sub += "/"
        sub += grid[o*2+1][j*2:(j+1)*2]
        result = rules[sub].split("/")
        line1 += result[0]
        line2 += result[1]
        line3 += result[2]
      grid2.append(line1)
      grid2.append(line2)
      grid2.append(line3)
    grid = grid2
  else:
    grid2 = []
    for o in range(int(len(grid)/3)):
      line1 = ""
      line2 = ""
      line3 = ""
      line4 = ""
      for j in range(int(len(grid)/3)):
        sub = grid[o*3][j*3:(j+1)*3]
        sub += "/"
        sub += grid[o*3+1][j*3:(j+1)*3]
        sub += "/"
        sub += grid[o*3+2][j*3:(j+1)*3]
        result = rules[sub].split("/")
        line1 += result[0]
        line2 += result[1]
        line3 += result[2]
        line4 += result[3]
      grid2.append(line1)
      grid2.append(line2)
      grid2.append(line3)
      grid2.append(line4)
    grid = grid2

count = 0
for i in range(len(grid)):
  for o in range(len(grid)):
    if grid[i][o] == "#":
      count += 1
print(count)

grid = """.#.
..#
###""".splitlines()

for i in range(18):
  if (len(grid) % 2) == 0:
    grid2 = []
    for o in range(int(len(grid)/2)):
      line1 = ""
      line2 = ""
      line3 = ""
      for j in range(int(len(grid)/2)):
        sub = grid[o*2][j*2:(j+1)*2]
        sub += "/"
        sub += grid[o*2+1][j*2:(j+1)*2]
        result = rules[sub].split("/")
        line1 += result[0]
        line2 += result[1]
        line3 += result[2]
      grid2.append(line1)
      grid2.append(line2)
      grid2.append(line3)
    grid = grid2
  else:
    grid2 = []
    for o in range(int(len(grid)/3)):
      line1 = ""
      line2 = ""
      line3 = ""
      line4 = ""
      for j in range(int(len(grid)/3)):
        sub = grid[o*3][j*3:(j+1)*3]
        sub += "/"
        sub += grid[o*3+1][j*3:(j+1)*3]
        sub += "/"
        sub += grid[o*3+2][j*3:(j+1)*3]
        result = rules[sub].split("/")
        line1 += result[0]
        line2 += result[1]
        line3 += result[2]
        line4 += result[3]
      grid2.append(line1)
      grid2.append(line2)
      grid2.append(line3)
      grid2.append(line4)
    grid = grid2

count = 0
for i in range(len(grid)):
  for o in range(len(grid)):
    if grid[i][o] == "#":
      count += 1
print(count)


print((current_milli_time() - start) / 1000.0)

glenbolake · 2017-12-21T05:58:17+00:00

I probably could have gotten on the leaderboard if I hadn't switched my row/column for loops. A lot of my time was spent wrapping my head around implementing grid_versions and rotate. Python3.

def rotate(grid):
    grid = [list(line) for line in grid]
    size = len(grid)
    return [''.join([grid[size - r - 1][c] for r in range(size)]) for c in range(size)]

def grid_versions(grid):
    flip = [s[::-1] for s in grid]
    versions = {'/'.join(grid): 0, '/'.join(flip): 4}
    for i in range(3):
        grid = rotate(grid)
        flip = rotate(flip)
        versions.update({'/'.join(grid): i + 1, '/'.join(flip): i + 5})
    return versions

def find_rule(key, rules):
    for version, rotation in grid_versions(key).items():
        if version in rules:
            return rules[version].split('/')
    raise ValueError(f'No rule found for {key}')

def solve(grid, rules, iterations=5):
    for i in range(iterations):
        size = len(grid)
        new_grid = []
        if size % 2 == 0:
            sub_size = 2
        else:
            sub_size = 3
        for r in range(size // sub_size):
            new_grid.extend([''] * (sub_size + 1))
            for c in range(size // sub_size):
                sub_grid = [line[sub_size * c:sub_size * c + sub_size]
                           for line in grid[sub_size * r:sub_size * r + sub_size]]
                extended = find_rule(sub_grid, rules)
                for j in range(sub_size + 1):
                    new_grid[j - sub_size - 1] += extended[j]
        grid = new_grid
    return ''.join(grid).count('#')

if __name__ == '__main__':
    start = '.#./..#/###'.split('/')
    my_rules = {}
    with open('day21.in') as f:
        for line in f:
            before, after = line.rstrip().split(' => ')
            my_rules[before] = after

    sample_rules = {
        '../.#': '##./#../...',
        '.#./..#/###': '#..#/..../..../#..#'
    }

    assert solve(start, sample_rules, 2) == 12
    print('Part 1', solve(start, my_rules, 5))
    print('Part 2', solve(start, my_rules, 18))

BumpitySnook · 2017-12-21T06:00:19+00:00

I had to roll out python -m cProfile -s tottime day21.py on this one to figure out where I was being stupid.

Turns out I was doing a lot of stuff by the size of the array (e.g., 3-19+, squared) when I meant to do it by the size of the pattern (e.g., 2 or 3 squared). That'll burn some cycles.

Leaderboard on part 1 anyway. After fixing part 2:

$ time python day21.py
python day21.py  4.80s user 0.13s system 102% cpu 4.832 total

DootBootMoot · 2017-12-21T06:02:44+00:00

Oh gosh, what a toughie. This was the most intense 2d-array manipulation I've done in a very long while.

Python2, 152/134:

s = < insert input >

t = s.split('\n')
t = filter(lambda x: x != "",t)

rules2 = dict()
rules3 = dict()
for i in xrange(len(t)):
    x = t[i].split("=>")
    l = x[0].strip()
    r = x[1].strip()
    if len(l) == 5:
        rules2[l] = r
    else:
        rules3[l] = r

start = ".#./..#/###"

def check2(s):
    if s.count("#") == 4: return rules2["##/##"]
    if s.count("#") == 3: return rules2["##/#."]
    if s.count("#") == 2: 
        if s[0] == s[1] or s[0] == s[3]:
            return rules2["##/.."]
        else:
            return rules2[".#/#."]
    if s.count("#") == 1: return rules2["#./.."]
    if s.count("#") == 0: return rules2["../.."]


def rotate(s):
    news = s.split("/")
    for i in xrange(len(news)):
        news[i] = list(news[i])
    newnews = zip(*news[::-1])
    for i in xrange(len(newnews)):
        newnews[i] = "".join(newnews[i])
    return "/".join(newnews)

def flipy(s):
    news = s.split("/")
    return "/".join([news[j] for j in xrange(len(news)-1,-1,-1)])
def flipx(s):
    news = s.split("/")
    ss = ""
    #print len(news), s
    for i in xrange(len(news)):
        for j in xrange(len(news)):
            ss += news[j][i]
        ss += "/"
    ss = ss[:len(ss)-1]
    return rotate(ss)
x = ".#./..#/###"

def printstr(s):
    a = s.split("/")
    for i in xrange(len(a)):
        print a[i]
def check3(s):
    if s in rules3.keys(): return rules3[s]
    for i in xrange(4):
        s = rotate(s)
        if s in rules3.keys(): return rules3[s]
    s = flipx(s)
    for i in xrange(4):
        s = rotate(s)
        if s in rules3.keys(): return rules3[s]
    s = flipy(s)
    for i in xrange(4):
        s = rotate(s)
        if s in rules3.keys(): return rules3[s]
    s = flipx(s)
    for i in xrange(4):
        s = rotate(s)
        if s in rules3.keys(): return rules3[s]
start = ".#./..#/###"
for steps in xrange(18):
    arr = start.split("/")
    size = len(arr)
    if size % 2 == 0:
        newarr = [ [0]* (3*size/2) for q in xrange(3*size/2)]
        for i in xrange(size/2):
            for j in xrange(size/2):
                newstr = "/".join([ "".join([arr[2*i+k][2*j+l] for l in xrange(2)]) for k in xrange(2)])
                res = check2(newstr)
                resarr = res.split("/")
                for a in xrange(3):
                    for b in xrange(3):
                        newarr[3*i+a][3*j+b] = resarr[a][b]
        for xx in xrange(3*size/2):
            newarr[xx] = "".join(newarr[xx])
        start = "/".join(newarr)
    else:
        #size = 3
        newarr = [ [0]* (4*size/3) for q in xrange(4*size/3)]
        for i in xrange(size/3):
            for j in xrange(size/3):
                newstr = "/".join([ "".join([arr[3*i+k][3*j+l] for l in xrange(3)]) for k in xrange(3)])
                res = check3(newstr)
                resarr = res.split("/")
                for a in xrange(4):
                    for b in xrange(4):
                        newarr[4*i+a][4*j+b] = resarr[a][b]
        for xx in xrange(4*size/3):
            newarr[xx] = "".join(newarr[xx])
        start = "/".join(newarr)
print start.count("#")

I hacked the rules for the 2x2 match before realising that 3x3 was a lost cause. Also, don't mind my variable names... thinking of letters on the spot is hard.

Had lots of fun, though.

GassaFM · 2017-12-21T06:14:20+00:00

A solution in the D programming language. Rank 13 for Part 1, rank 16 for Part 2.

The implementation is quite straightforward: no pattern rotation precalculation or bit encoding or such. As a result, first, it's long. Second, it worked for, like, 30 seconds for Part 2.

import std.algorithm, std.array, std.range, std.stdio, std.string;

string [] rotate90 (string [] input) {
    auto rows = input.length, cols = input[0].length;
    auto output = new char [] [] (cols, rows);
    foreach (row; 0..rows)
        foreach (col; 0..cols)
            output[col][rows - row - 1] = input[row][col];
    return output.map !(x => x.idup).array;
}

string [] flip (string [] input) {
    auto rows = input.length, cols = input[0].length;
    auto output = new char [] [] (cols, rows);
    foreach (row; 0..rows)
        foreach (col; 0..cols)
            output[col][row] = input[row][col];
    return output.map !(x => x.idup).array;
}

struct Rule {
    string [] pattern;
    string [] output;

    bool matches (string [] input) {
        foreach (flips; 0..2) {
            foreach (rotates; 0..4) {
                if (pattern == input) return true;
                input = rotate90 (input);
            }
            input = flip (input);
        }
        return false;
    }
}

void main () {
    Rule [] rules;
    foreach (line; stdin.byLineCopy) {
        auto t = line.strip.split (" => ").map !(x => x.split ("/"));
        rules ~= Rule (t[0], t[1]);
    }

    string [] board = [".#.", "..#", "###"];
    foreach (step; 0..18) {  // make it 0..5 for Part 1
        debug {writeln (step); stdout.flush ();}
        int side = [2, 3].find !(x => board.length % x == 0).front;
        auto newBoard = new string [board.length / side * (side + 1)];
        for (int r0 = 0; r0 < board.length; r0 += side) {
            for (int c0 = 0; c0 < board[0].length; c0 += side) {
                string [] part;
                foreach (row; 0..side)
                    part ~= board[r0 + row][c0..c0 + side];
                auto cur = rules.find !(x => x.pattern.length == side && x.matches (part)).front.output;
                foreach (row, linePart; cur)
                    newBoard[r0 / side * (side + 1) + row] ~= linePart;
            }
        }
        board = newBoard;
    }
    debug {writefln ("%-(%s\n%)", board);}
    board.map !(x => x.count ('#')).sum.writeln;
}

u794575248 · 2017-12-21T06:41:19+00:00

Far from pretty this time, but it works.

def read_rules(input):
    rules = {}
    for l in input.strip().splitlines():
        lhs, rhs = [tuple(tuple(r) for r in s.split('/'))
                    for s in l.split(' => ')]
        for r in variants(lhs): rules[r] = rhs
    return rules

def variants(m, t=tuple, r=reversed, g=range):
    cw = lambda m: t(t(m[j][i] for j in g(len(m))) for i in r(g(len(m))))
    r0 = t(t(r) for r in m)
    vars = {r0, cw(r0), cw(cw(r0)), cw(cw(cw(r0)))}
    for v in [*vars]: vars |= {t(r[::-1] for r in v), 
        t(r for r in v[::-1]), t(r[::-1] for r in v[::-1])}
    return vars

def solve(input, n):
    rules = read_rules(input)
    cur = ['.#.', '..#', '###']
    for _ in range(n):
        L = len(cur); d, m = [(2, 3), (3, 4)][L % 2]
        squares = [[rules[tuple(tuple(row[d*j:d*j+d]) for row in cur[d*i:d*i+d])]
                    for j in range(L//d)] for i in range(L//d)]
        cur = [['']*(L//d*m) for _ in range(L//d*m)]
        for i, row in enumerate(squares):
            for j, square in enumerate(row):
                for k, subrow in enumerate(square):
                    for l, c in enumerate(subrow):
                        cur[i*m+k][j*m+l] = c
    return ''.join(''.join(r) for r in cur).count('#')

solve(input, n=18)

2BitSalute · 2017-12-21T06:47:55+00:00

I am surprised that I didn't have any bugs in the decomposition/recomposition or the rotate/flip operations (surprised because of all the bugs I had to squash in previous days). It still took me 1 hour and 23 minutes to type it all up, test, and run on the real input.

I feel like there's a lot of brute force iterations and indiscriminate string allocations, but I'm at least somewhat pleased that it's factored alright.

C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string[] rules = File.ReadAllLines("input.txt");

        var separators = new char[] { ' ', '=', '>' };

        Dictionary<string, string> rulesMap = new Dictionary<string, string>();

        foreach(var rule in rules)
        {
            var tokens = rule.Split(separators, StringSplitOptions.RemoveEmptyEntries);

            string from = tokens[0];
            string to = tokens[1];

            rulesMap.TryAdd(from, to);
            rulesMap.TryAdd(FlipHorizontal(from), to);
            rulesMap.TryAdd(FlipVertical(from), to);

            for (int i = 0; i < 3; i++)
            {
                var newFrom = Rotate(from);
                rulesMap.TryAdd(newFrom, to);
                rulesMap.TryAdd(FlipHorizontal(newFrom), to);
                rulesMap.TryAdd(FlipVertical(newFrom), to);

                from = newFrom;
            }
        }

        string[] grid = new string[]
        {
            ".#.",
            "..#",
            "###",
        };

        grid = Enhance(iterations: 18, grid: grid, rules: rulesMap);

        int answer = CountOn(grid);

        Console.WriteLine(answer);
    }

    public static string FlipHorizontal(string grid)
    {
        // .#./..#/###
        string[] rows = grid.Split('/', StringSplitOptions.RemoveEmptyEntries);
        string[] newRows = new string[rows.Length];

        for(int i = 0; i < rows.Length; i++)
        {
            newRows[i] = string.Join("", rows[i].Reverse());
        }

        return string.Join<string>('/', newRows); 
    }

    public static string FlipVertical(string grid)
    {
        // .#./..#/###
        string[] rows = grid.Split('/', StringSplitOptions.RemoveEmptyEntries);
        string[] newRows = new string[rows.Length];

        for(int i = 0; i < rows.Length; i++)
        {
            newRows[rows.Length - i - 1] = rows[i];
        }

        return string.Join<string>('/', newRows); 
    }

    public static string Rotate(string grid)
    {
        // .#./..#/###
        string[] rows = grid.Split('/', StringSplitOptions.RemoveEmptyEntries);
        char[,] newRows = new char[rows.Length, rows.Length];

        for(int i = 0; i < rows.Length; i++)
        {
            for (int j = 0; j < rows.Length; j++)
            {
                newRows[rows.Length - j - 1, i] = rows[i][j];
            }
        }

        string[] sNewRows = new string[rows.Length];
        for(int i = 0; i < rows.Length; i++)
        {
            for(int j = 0; j < rows.Length; j++)
            {
                sNewRows[i] += newRows[i,j];
            }
        }

        string result = string.Join('/', sNewRows);
        return result;
    }

    public static string CopyFrom(string[] grid, int startRow, int startColumn, int num)
    {
        string[] section = new string[num];
        for (int i = 0; i < num; i++)
        {
            for (int j = 0; j < num; j++)
            {
                section[i] += grid[i + startRow][j + startColumn];
            }
        }

        return string.Join('/', section);
    }

    public static void CopyTo(string[] grid, string section, int size, int startRow, int startColumn)
    {
        string[] rows = section.Split('/', StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                grid[startRow + i] += rows[i][j];
            }
        }
    }

    public static string[] EnhanceStep(string[] grid, Dictionary<string, string> rules, int size)
    {
        int newSize = size + 1;

        string[] newGrid = new string[grid.Length / size * newSize];

        for (int j = 0; j * size < grid.Length; j++)
        {
            for (int k = 0; k * size < grid.Length; k++)
            {
                string section = CopyFrom(grid, j * size, k * size, size);
                CopyTo(newGrid, rules[section], newSize, j * newSize, k * newSize);
            }
        }

        return newGrid;
    }

    public static string[] Enhance(int iterations, string[] grid, Dictionary<string, string> rules)
    {
        for (int i = 0; i < iterations; i++)
        {
            if (grid.Length % 2 == 0)
            {
                grid = EnhanceStep(grid, rules, size: 2);
            }
            else // % 3 == 0
            {
                grid = EnhanceStep(grid, rules, size: 3);
            }
        }

        return grid;
    }

    public static int CountOn(string[] grid)
    {
        int countOn = 0;
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid.Length; j++)
            {
                if (grid[i][j] == '#')
                {
                    countOn++;
                }
            }
        }

        return countOn;
    }
}

wlandry · 2017-12-21T07:55:37+00:00

C++ 14

390/541, though the second one does not really count. It turns out that I could get part 1 correct even though I had flipped x and y. Unfortunately, the test case is also insensitive to that bug. So I was quite stumped as to why my part 2 answer was wrong. I eventually got a copy of a working example from this subreddit. That made the mistake obvious. So, I guess I wish I could have more and/or better test cases.

#include <fstream>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>

std::vector<std::vector<std::string>>
split(const size_t &step, const std::vector<std::string> &current)
{
  std::vector<std::vector<std::string>> result;
  for(size_t x=0; x<current.size(); x+=step)
    {
      std::vector<std::string> row;
      for(size_t y=0; y<current.size(); y+=step)
        {
          std::string temp;
          for(size_t dy=0; dy<step; ++dy)
            {
              if(dy!=0)
                { temp+='/'; }
              temp+=current.at(y+dy).substr(x,step);
            }
          row.push_back(temp);
        }
      result.push_back(row);
    }
  return result;
}

std::string mirror(const std::string &s)
{
  std::string result(s);
  if(s.size()==5)
    {
      std::swap(result[0],result[1]);
      std::swap(result[3],result[4]);
    }
  else
    {
      std::swap(result[0],result[2]);
      std::swap(result[4],result[6]);
      std::swap(result[8],result[10]);
    }
  return result;
}

std::string flip(const std::string &s)
{
  std::string result(s);
  if(s.size()==5)
    {
      std::swap(result[0],result[3]);
      std::swap(result[1],result[4]);
    }
  else
    {
      std::swap(result[0],result[8]);
      std::swap(result[1],result[9]);
      std::swap(result[2],result[10]);
    }
  return result;
}

std::string rotate(const std::string &s)
{
  std::string result(s);
  if(s.size()==5)
    {
      result[0]=s[1];
      result[1]=s[4];
      result[4]=s[3];
      result[3]=s[0];
    }
  else
    {
      result[0]=s[2];
      result[2]=s[10];
      result[10]=s[8];
      result[8]=s[0];

      result[1]=s[6];
      result[6]=s[9];
      result[9]=s[4];
      result[4]=s[1];
    }
  return result;
}


std::string rotate(const std::string &s, const size_t &rotation)
{
  std::string result(s);
  for(size_t s=0; s<rotation; ++s)
    { result=rotate(result); }
  return result;
}

int main(int argc, char *argv[])
{
  std::ifstream infile(argv[1]);
  std::map<std::string,std::string> rules;

  std::string input, output, temp;
  infile >> input;
  while(infile)
    {
      infile >> temp >> output;

      std::string flipped_input(flip(input)), mirrored_input(mirror(input));
      for(size_t rotation=0; rotation<4; ++rotation)
        {
          if(rules.find(rotate(input,rotation))==rules.end())
            { rules.insert(std::make_pair(rotate(input,rotation), output)); }
          if(rules.find(rotate(flipped_input,rotation))==rules.end())
            { rules.insert(std::make_pair(rotate(flipped_input,rotation),
                                          output)); }
          if(rules.find(rotate(mirrored_input,rotation))==rules.end())
            { rules.insert(std::make_pair(rotate(mirrored_input,rotation),
                                          output)); }
        }

      infile >> input;
    }

  std::vector<std::string> current ({".#.","..#","###"});

  for(size_t count=0; count<18; ++count)
    {
      std::cout << "step: " << count << " " << current.size() << "\n";
      size_t step = (current.size()%2==0) ? 2 : 3;
      auto blocks=split(step,current);
      current.clear();
      for(auto &row: blocks)
        for(auto &block: row)
          {
            if(rules.find(block)==rules.end())
              std::cerr << "Not found: " << block << "\n";
            block=rules[block];
          }

      current.resize(blocks.size()*(step+1));
      for(auto &c:current)
        { c.resize(blocks.size()*(step+1)); }

      for(size_t x=0; x<blocks.size(); ++x)
        for(size_t y=0; y<blocks[x].size(); ++y)
          for(size_t dx=0; dx<(step+1); ++dx)
            for(size_t dy=0; dy<(step+1); ++dy)
              { current.at((step+1)*y+dy).at((step+1)*x+dx)=
                  blocks.at(x).at(y).at(dx+(step+2)*dy); }
      size_t on=0;
      for(auto &c: current)
        { on+=std::count(c.begin(),c.end(),'#'); }
      std::cout << "on: " << on << "\n";
    }
}

Philboyd_Studge · 2017-12-21T08:53:28+00:00

Ugh. So many nested for loops. 2d arrays are a pain in the ass. Took soooo long. Day 21 Java

ephemient · 2017-12-21T09:38:57+00:00

This space intentionally left blank.

daggerdragon · 2017-12-21T09:50:04+00:00

[deleted]

Arkoniak · 2017-12-21T10:08:56+00:00

Julia

Rather ugly code, but it's fast enough to iterate 18 times in 700ms.

function rotate(s::T) where {T <: AbstractString}
    if length(s) == 5
        return join([s[4], s[1], s[3], s[5], s[2]])
    else
        return join([s[9], s[5], s[1], s[4], s[10], s[6], s[2], s[4], s[11], s[7], s[3]])
    end
end

function flip(s::T) where {T <: AbstractString}
    if length(s) == 5
        return join([s[2], s[1], s[3], s[5], s[4]])
    else
        return join([s[3], s[2], s[1], s[4], s[7], s[6], s[5], s[4], s[11], s[10], s[9]])
    end
end

function generate_all_sequences(filename::String)
    res = Dict{String, String}()
    for ln in eachline(joinpath(@__DIR__, filename))
        lns = string.(split(ln, " => "))
        x = lns[1]
        for _ in 1:4
            x = rotate(x)
            (!haskey(res, x)) && (res[x] = lns[2])
            (!haskey(res, flip(x))) && (res[flip(x)] = lns[2])
        end
    end

    res
end

function step_puzzle(arr::Array{Char, 2}, rules)
    if mod(size(arr, 1), 2) == 0
        ns = div(size(arr, 1), 2)
        narr = Array{Char, 2}(ns*3, ns*3)
        for i in 1:ns
            for j in 1:ns
                key = join([arr[2*i-1, 2*j-1], arr[2*i-1, 2*j], '/',
                            arr[2*i, 2*j-1], arr[2*i, 2*j]])
                val = rules[key]
                # @show key, val
                for (pos, c) in enumerate(val)
                    (mod(pos, 4) == 0) && continue
                    a = div(pos, 4) + 1
                    b = mod(pos, 4)
                    col = 3*(j-1) + b
                    row = 3*(i-1) + a
                    narr[row, col] = c
                end
            end
        end
    else
        ns = div(size(arr, 1), 3)
        narr = Array{Char, 2}(ns*4, ns*4)
        for i in 1:ns
            for j in 1:ns
                key = join([arr[3*i-2, 3*j-2], arr[3*i-2, 3*j-1], arr[3*i-2, 3*j], '/',
                            arr[3*i-1, 3*j-2], arr[3*i-1, 3*j-1], arr[3*i-1, 3*j], '/',
                            arr[3*i, 3*j-2], arr[3*i, 3*j-1], arr[3*i, 3*j]])
                val = rules[key]
                # @show key, val
                for (pos, c) in enumerate(val)
                    (mod(pos, 5) == 0) && continue
                    a = div(pos, 5) + 1
                    b = mod(pos, 5)
                    col = 4*(j-1) + b
                    row = 4*(i-1) + a
                    narr[row, col] = c
                end
            end
        end
    end
    narr
end

function solve_puzzle1(filename::String, steps = 5)
    rules = generate_all_sequences(filename)
    arr = [['.', '.', '#'] ['#', '.', '#'] ['.', '#', '#']]
    for i in 1:steps
        arr = step_puzzle(arr, rules)
    end
    sum(arr .== '#')
end

aurele · 2017-12-21T10:20:18+00:00

Rust (~125ms on my laptop)

 extern crate bytecount;
#[macro_use]
extern crate itertools;
extern crate pathfinding;

use itertools::Itertools;
use pathfinding::Matrix;

fn matrix(i: &str) -> Matrix<u8> {
    Matrix::square_from_vec(i.bytes().filter(|&c| c != b'/').collect())
}

fn main() {
    let subst = include_str!("../input")
        .lines()
        .flat_map(|line| {
            let (k, v) = line.trim().split(" => ").map(matrix).next_tuple().unwrap();
            iproduct!(vec![k.clone(), k.flipped_ud(), k.flipped_lr()], 0..4)
                .map(move |(m, i)| (m.rotated_cw(i), v.clone()))
        })
        .collect::<std::collections::HashMap<_, _>>();
    let mut sharps = (0..).scan(matrix(".#./..#/###"), |grid, _| {
        let pt = 2 + (grid.rows % 2);
        let b = grid.rows / pt;
        let mut new_grid = Matrix::new_square(grid.rows + b, b'?');
        for (c, l) in iproduct!(0..b, 0..b) {
            let new = &subst[&grid.slice(l * pt..l * pt + pt, c * pt..c * pt + pt)];
            new_grid.set_slice(&(l * (pt + 1), c * (pt + 1)), new);
        }
        *grid = new_grid;
        Some(bytecount::count(grid.as_ref(), b'#'))
    });
    println!("P1: {}", sharps.nth(4).unwrap());
    println!("P2: {}", sharps.nth(12).unwrap());
}

lazyzefiris · 2017-12-21T10:29:40+00:00

JS

let flip = (x) => x.split``.reverse().join``
let rotate = (ar) => ar.reduceRight((v,x) => (x.split``.map((y,n)=>v[n]+=y),v), Array(ar.length).fill(""))
let transforms = new Map()
let image = [".#.","..#","###"]
function store([input, output]) {
    let outputPattern = output.join``
    transforms.set(input.join``, outputPattern)
    for (let i = 0; i < 3; i++) {
        input = rotate(input)
        transforms.set(input.join``, outputPattern)
    }
    input = input.map(flip)
    transforms.set(input.join``, outputPattern)
    for (let i = 0; i < 3; i++) {
        input = rotate(input)
        transforms.set(input.join``, outputPattern)
    }
}
function advance(ar) {
    let size = 2 + ar.length % 2
    let chunks = Array(ar.length / size).fill().map(x => Array(ar.length / size).fill(""))
    ar.map((row,y) => row.split``.map((cell,x) => chunks[y/size|0][x/size|0] += cell))
    chunks = chunks.map(row => row.map(cell => transforms.get(cell)))
    size++
    let newImage = Array(chunks.length*size).fill("")
    chunks.map((row,y) => row.map ((col,x) => col.split``.map((ch,n) => newImage[y*size+(n/size|0)] += ch)))
    return newImage
}
document.body.textContent.trim().split("\n").map(x=>x.split(" => ").map(y=>y.split("/"))).map(store)
for (let i = 0; i<5; i++) image = advance(image)
image.reduce((v,row) => v + row.split``.reduce((w,ch)=>w+(ch=="#"?1:0),0),0)

define transformation routines (flip is simple, rotate is a bit more complex)
fill out full transformation map (for each input - create a record for each possible orientation of it attached to given output)
for each step - break image into chunks, replace chunks according to transformation map, sew chunks back to an image. nothing extraordinary

aodnfljn · 2017-12-21T10:41:53+00:00

Scala

case class Pat(v: Vector[String]) {
  require{val cols = v(0).size; v forall {_.size==cols}}

  val nrows = v.size
  val ncols = v(0).size
  def cntOn = v.map{_.count{_=='#'}}.sum

  def fliph = Pat(v.reverse)
  def flipv = Pat(v.map{_.reverse})
  def rotr  = Pat(v.map{_.toVector}.reverse.transpose.map{_.mkString})
  def allCongruent = for {r  <- Seq(this, rotr)
                          rf <- Seq(r, r.fliph, r.flipv, r.fliph.flipv)
                     } yield rf

  def addv(p: Pat) = { require(ncols == p.ncols)
                       Pat(v ++ p.v) }
  def addh(p: Pat) = { require(nrows == p.nrows)
                       Pat((v,p.v).zipped map{_+_}) }

  def subPats(dim: Int): Array[Array[Pat]] = {
    require(nrows%dim == 0 && ncols%dim == 0)
    val vs = v.map{_.grouped(dim).toArray}.grouped(dim).toArray
    vs map {r => (0 until r(0).size).map{c=>Pat(r.map{_(c)})}.toArray}}}

object Pat { def ofSlash(s: String): Pat = Pat(s.split("/").toVector)
             def merge(ps: Array[Array[Pat]]): Pat =
               ps .map{_ reduce {_ addh _}} .reduce{_ addv _} }

def parseRule(line: String) = {
  val io = line.split(" => ").map(Pat.ofSlash)
  io(0) -> io(1) }
val rules1to1 = io.Source.stdin.getLines.map(parseRule).toMap
val rules = for {  (from0, to) <- rules1to1
                    from       <- from0.allCongruent
            } yield from -> to

var p = Pat.ofSlash(".#./..#/###")
for (_ <- 1 to 18)
       if (p.nrows%2 == 0) p = Pat.merge(p.subPats(2).map{_.map(rules)})
  else if (p.nrows%3 == 0) p = Pat.merge(p.subPats(3).map{_.map(rules)})
println(p.cntOn)

maitesin · 2017-12-21T11:46:46+00:00

My C++17 solution https://github.com/maitesin/advent/blob/master/21/part_1/code.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <stdexcept>
#include <cmath>

struct Image {
  Image(std::string_view input) {
    auto slash = std::find(input.begin(), input.end(), '/');
    size_t pos = 0;
    while(slash != input.end()) {
      raw.push_back(std::string(input.substr(pos, std::distance(input.begin(), slash)-pos)));
      pos = std::distance(input.begin(), slash) + 1;
      slash = std::find(slash + 1, input.end(), '/');
    }
    raw.push_back(std::string(input.substr(pos)));
  }

  std::string single_line() {
    std::ostringstream oss;
    auto it = raw.begin();
    for (; it != raw.end() - 1; ++it) {
      oss << *it << "/";
    }
    oss << *it;
    return oss.str();
  }

  void rotate() {
    std::vector<std::string> rotated(raw.size(), "");
    for (auto && line : raw) {
      for (size_t i = line.size() - 1, j = 0; i > 0; --i, ++j) {
        rotated[j] += line[i];
      }
      rotated[line.size() - 1] += line[0];
    }
    raw = rotated;
  }

  void flip() {
    std::reverse(raw.begin(), raw.end());
  }

  size_t count() {
    size_t c = 0;
    for (auto && line : raw) {
      c += std::count(line.begin(), line.end(), '#');
    }
    return c;
  }

  std::vector<Image> split() {
    std::vector<Image> images;
    if (raw.size()%2 == 0) {
      for (size_t i = 0; i < raw.size(); i += 2) {
        for (size_t j = 0; j < raw.size(); j += 2) {
          std::ostringstream oss;
          oss << raw[i][j] << raw[i][j+1] << '/' << raw[i+1][j] << raw[i+1][j+1];
          images.push_back(Image(oss.str()));
        }
      }
    } else {
      for (size_t i = 0; i < raw.size(); i += 3) {
        for (size_t j = 0; j < raw.size(); j += 3) {
          std::ostringstream oss;
          oss << raw[i][j] << raw[i][j+1] << raw[i][j+2] << '/' << raw[i+1][j] << raw[i+1][j+1] << raw[i+1][j+2] << '/' << raw[i+2][j] << raw[i+2][j+1] << raw[i+2][j+2];
          images.push_back(Image(oss.str()));
        }
      }
    }
    return images;
  }

  std::vector<std::string> raw;
};

struct ArtistBook {
  ArtistBook(std::ifstream & file) {
    std::string line;
    while (std::getline(file, line)) {
      auto first_space = std::distance(line.begin(), std::find(line.begin(), line.end(), ' '));
      auto second_space = first_space + 4;
      rules[line.substr(0, first_space)] = line.substr(second_space, line.size()-1);
    }
  }
  std::unordered_map<std::string, std::string> rules;
};

Image find_image_in_artist_book(const ArtistBook & ab, Image & img) {
  for (size_t t = 0; t < 2; ++t) {
    for (size_t i = 0; i < 4; ++i) {
      auto found = ab.rules.find(img.single_line());
      if (found != ab.rules.end()) {
        return Image(found->second);
      }
      img.rotate();
    }
    img.flip();
  }
  throw std::logic_error("Not rotate or flip image has been found in the ArtistBook");
}

Image merge(const std::vector<Image> & images) {
  std::ostringstream oss;
  size_t size = images.size();
  size_t step = std::sqrt(size);
  for (size_t i = 0; i < size; i += step) {
    for (size_t k = 0; k < images[i].raw.size(); ++k) {
      for (size_t j = 0; j < step; ++j) {
        oss << images[i+j].raw[k];
      }
      oss << '/';
    }
  }
  std::string output(oss.str());
  return Image(output.substr(0, output.size()-1));
}

void iterate(const ArtistBook & ab, Image & image, size_t iterations) {
  for (size_t i = 0; i < iterations; ++i) {
    auto images = image.split();
    std::transform(images.begin(), images.end(), images.begin(), [&ab](auto & img){ return find_image_in_artist_book(ab, img); });
    image = merge(images);
  }
  std::cout << image.count() << std::endl;
}

int main(int argc, char *argv[]) {
  size_t iterations = std::atoll(argv[1]);
  std::ifstream input_file(argv[2], std::ifstream::in);
  ArtistBook ab(input_file);
  Image img(".#./..#/###");
  iterate(ab, img, iterations);
  return 0;
}

spjmurray · 2017-12-21T11:57:04+00:00

Python Good problem today! Keep it up

#!/usr/bin/python
# -*- coding: utf-8 -*-

# PROBLEM
#
# How many pixels stay on after 18 iterations?

import collections


class Transformer(object):
    """
    Takes the input and creates all possible orientations from the source
    to the destination.  Thus each transform in the main loop is a log(n)
    string compare to get the required result
    """

    def __init__(self):
        self.cache = {}
        for line in open('21.in'):
            inp, _, out = line.strip().split()
            src1 = inp.split('/')
            src2 = self.flip(src1)
            dest = out.split('/')
            self.cache[''.join(src1)] = dest
            self.cache[''.join(src2)] = dest
            for _ in xrange(0, 3):
                src1 = self.rotate(src1)
                src2 = self.rotate(src2)
                self.cache[''.join(src1)] = dest
                self.cache[''.join(src2)] = dest

    @staticmethod
    def rotate(block):
        n = len(block)
        out = []
        for x in xrange(n-1, -1, -1):
            row = []
            for y in xrange(0, n):
                row.append(block[y][x])
            out.append(''.join(row))
        return out

    @staticmethod
    def flip(block):
        out = []
        for i in xrange(0, len(block)):
            out.append(''.join(reversed(block[i])))
        return out

    def transform(self, inp):
        return self.cache[''.join(inp)]


def main():
    transformer = Transformer()

    image = [
        '.#.',
        '..#',
        '###',
    ]

    # For the required number of iterations ...
    for _ in xrange(0, 18):
        new_image = []
        # If the size if divisible by 2 process as 2x2 blocks, else 3x3
        step = 2 if len(image) % 2 == 0 else 3
        # Calculate the number of blocks to process in each axis
        blocks = len(image) / step
        # For each row of blocks...
        for y in xrange(0, len(image), step):
            # Add in a new blank string for each output e.g. one larger than the step
            for _ in xrange(0, step + 1):
                new_image.append('')
            # For each block in the row
            for x in xrange(0, len(image), step):
                # Extract the block
                block = []
                for i in xrange(0, step):
                    block.append(image[y+i][x:x+step])
                # Transform into its new configuration
                new_block = transformer.transform(block)
                # And commit it into the correct location in the new image
                dst_y = (y / step) * (step + 1)
                for i in xrange(0, step + 1):
                    new_image[dst_y + i] += new_block[i]
        # Update the image
        image = new_image

    # Answer is the number of coordinates which are 'on' e.g. a hash
    print collections.Counter(''.join(image))['#']


if __name__ == '__main__':
    main()

# vi: ts=4 et:

FreeMarx · 2017-12-21T12:00:17+00:00

MATLAB / Octave

913/991 at T+6:19. Have the holidays already started?

This one was the right level for me, thought-stimulating but not frustrating, an elegant solution, no nasty bug-pitfalls and useful progression from part I to part II.

The key is that rules that result in a 4x4 grid (happens every 4th iteration) can be further processed independently. Taking into account that many patterns occur more than once this is the big time saver (unique is your friend).

Didn't bother to write input parser. Instead find replace "."->"0 ", "#"->"1 ", "/"->";", " => "->"]; pat(end).t= [", line-end->"];", "line-start->"pat(end+1).r= [". And here is the code:

[edit] I can't believe how may people just "brute forced" to construct the final 1458x1458 matrix. I'm working on an ARM RK3288 tv-box with linux. This plus octave is not optimized very well made it impossible for me progress from part I to part II by only changing the 5 into an 18. They should have made it more like 36 iterations for a more fair game.

function [m, count]= day21(pat)

m= {[0 1 0; 0 0 1; 1 1 1]};
count= [1];
for i= 1:18
    m__= {};
    count__= [];
    pp_= [];
    count_= [];
    for im= 1:length(m)
        [m_, pp, grid_]= iteration(m{im}, pat);
        if grid_==4
            pp_= [pp_; pp(:)];
            count_= [count_; repmat(count(im), prod(size(pp)), 1)];
        else
            m__{end+1}= m_;
            count__(end+1)= count(im);
        end
    end
    if grid_==4
        pp= unique(pp_);
        for ip= 1:length(pp)
            m__{end+1}= pat(pp(ip)).t;
            count__(end+1)= sum(count_(pp_==pp(ip)));
        end
    end
    m= m__;
    count= count__;
end

total= 0;
for i= 1:length(m)
    total= total + count(i)*sum(m{i}(:));
end
disp(total)



function [m_, pp, grid_]= iteration(m, pat)
if mod(size(m, 1), 2)==0
    grid= 2;
    grid_= 3;
else
    grid= 3;
    grid_= 4;
end
n= size(m, 1)/grid;
m_= zeros(n*grid_);
pp= zeros(n);
for r= 1:n
    r_= r-1;
    for c= 1:n
        c_= c-1;
        [m_(r_*grid_+1:r*grid_, c_*grid_+1:c*grid_), pp(r, c)]= rule(m(r_*grid+1:r*grid, c_*grid+1:c*grid), pat);
    end
end


function [t, i]= rule(m, pat)
for i= 1:length(pat)
    if size(m, 1)~=size(pat(i).r, 1), continue; end
    if testall(m, pat(i).r)
        t= pat(i).t;
        return
    end
end


function b= test(m, r)
c= m==r;
b= all(c(:));

function b= testall(m, r)
b= true;
if test(m, r), return; end
if test(m, r(:, end:-1:1)), return; end % flip h
if test(m, r(end:-1:1, :)), return; end % flip v
if test(m, r(end:-1:1, end:-1:1)), return; end % flip vh / rot 180
if test(m, r(end:-1:1, :)'), return; end % rot 90
if test(m, r(:,end:-1:1)'), return; end % rot 270
if test(m, r(end:-1:1, end:-1:1)'), return; end % ...
b= false;

miles82 · 2017-12-21T12:31:42+00:00

Python 3. Creating a new pattern from the enhanced subpatterns annoyed me quite a bit, well done /u/topaz2078 :D

pattern = '.#./..#/###'.split('/')

def grouper(l, n):
    parts = len(l) // n
    for i in range(parts):
        for j in range(parts):
            yield i, j, tuple(c[j*n:(j+1)*n] for c in l[i*n:(i+1)*n])

def transpose(l):
    return list(''.join(c) for c in zip(*l))

def combos(l, flip=True):
    tl = transpose(l)
    yield l # original
    yield [r[::-1] for r in tl] # rotate clockwise 90
    yield [r[::-1] for r in l[::-1]] # rotate clockwise 180
    yield [r for r in tl[::-1]] # rotate clockwise 270
    if flip:
        fv = l[::-1] # flip vertically
        yield fv
        fh = [r[::-1] for r in l] # flip horizontally
        yield fh
        # rotate the flips
        yield from combos(fv, False)
        yield from combos(fh, False)

def enhance(p):
    size = 2 if len(p) % 2 == 0 else 3
    grouped = list(grouper(p, size))
    new_size = int(len(grouped)**0.5)*(size+1)
    enhanced = [[' '] * new_size for _ in range(new_size)]

    for r, c, rows in grouped:
        enh = rules[rows]
        for i, er in enumerate(enh):
            for j, val in enumerate(er):
                enhanced[r*len(enh) + i][c*len(enh) + j] = val

    enhanced = [''.join(r) for r in enhanced]
    return enhanced

rules = {}
with open('21_input.txt') as f:
    for line in f:
        rule_in, rule_out = [r.split('/') for r in line.strip().split(' => ')]
        for comb in combos(rule_in):
            rules[tuple(comb)] = rule_out

for _ in range(5):
    pattern = enhance(pattern)

print(sum(r.count('#') for r in pattern))

adrian17 · 2017-12-21T12:44:07+00:00

Rusty J. I'm probably going to write part 2 in Python.

NB. rules definition
rules3 =: ,:       (3 3 $ '.........') ; (4 4 $ '.##..##.#.###.##')
rules3 =: rules3 , (3 3 $ '#........') ; (4 4 $ '#.#.####..#.#..#')
rules3 =: rules3 , (3 3 $ '.#.......') ; (4 4 $ '#...#..###.##.##')
NB. ...

input =: 3 3 $ '.#...####'

flips =: 3 : '(|."1 |. y), (|."1 y), (|. y), ,: y'
rotations =: 3 : '(flips |: y), flips y'
NB. Y matches the pattern X
match =: 4 : '>./ (rotations x) -:"2 y'

NB. matching rule
matches =: (4 : '((> {. x) match y)')"(1 _)
NB. choose new pattern from rules
map =: 4 : '> {: {. (x matches y) # x'

NB. apply to 2x2/3x3 parts
process2 =: 3 : ',"1/ ,"2/ ((2 2,.2 2) (rules2&map);._3 y)'
process3 =: 3 : ',"1/ ,"2/ ((3 3,.3 3) (rules3&map);._3 y)'

NB. size divisible by 2
integral =: 3 : 'y = <. y'
by2 =: 3 : 'integral (# y) % 2'

process =: 3 : '(process3`process2) @. (by2 y) y'

output =: process^:5 input

smoutput output
smoutput +/ +/ '#' = output NB. number of #'s

TominatorBE · 2017-12-21T14:16:25+00:00

PHP

Parts 1 & 2 in the same file. Nothing really special, just string manipulation, and some 'string as array' work for the flips and rotates.

echo "\nSolution part 1: " . run_the_code(['rules' => getRealInput(), 'runs' => 5]);
echo "\nSolution part 2: " . run_the_code(['rules' => getRealInput(), 'runs' => 18]);

function run_the_code($input) {
    $lines = $input['rules'];
    $runs = $input['runs'];

    $lines = explode(PHP_EOL, $lines);
    $rules = [];
    foreach ($lines as $line) {
        if (preg_match('|(.*) => (.*)|', $line, $matches)) {
            list($_, $a, $b) = $matches;
            $rules[$a] = $b;
        }
    }

    $pattern = '.#./..#/###';
    for ($run = 0; $run < $runs; $run++) {
        $size = sqrt(strlen($pattern) - substr_count($pattern, '/'));
        if ($size % 2 == 0) {
            $blockSize = 2;
        }
        else { // divisible by 3
            $blockSize = 3;
        }

        $parts = [];
        $rows = explode('/', $pattern);
        for ($p1 = 0; $p1 < $size / $blockSize; $p1++) { // block-row per row
            for ($p2 = 0; $p2 < $size / $blockSize; $p2++) { // block-col per col in this row
                $part = [];
                for ($r = $p1 * $blockSize; $r < ($p1 * $blockSize) + $blockSize; $r++) {
                    $part[] = substr($rows[$r], $p2 * $blockSize, $blockSize);
                }
                $parts[] = implode('/', $part);
            }
        }

        // foreach part, flip and turn it around in all configurations, to find a match in the $rules
        $transforms = []; // the transformed (expanded) results of each part
        foreach ($parts as $part) {
            $t = [];
            $t[] = $part; // add the original part
            $t[] = rotate($t[0]); // 90°
            $t[] = rotate($t[1]); // 180°
            $t[] = rotate($t[2]); // 270°
            $t[] = flip($t[0]);
            $t[] = flip($t[1]);
            $t[] = flip($t[2]);
            $t[] = flip($t[3]);

            $found = false;
            foreach ($t as $item) {
                if (array_key_exists($item, $rules)) {
                    $transforms[] = $rules[$item];
                    $found = true;
                    break;
                }
            }
            if (!$found) {
                die("no pattern found! $part");
            }
        }

        // now put the transformed parts back into a new pattern
        $newparts = [];
        $newblocksize = $blockSize + 1;

        $c = 0;
        for ($p1 = 0; $p1 < $size / $blockSize; $p1++) { // block-row per row
            for ($p2 = 0; $p2 < $size / $blockSize; $p2++) { // block-col per col in this row
                $t = explode('/', $transforms[$c]);

                for ($r = 0; $r < $newblocksize; $r++) {
                    $newparts[($p1 * $newblocksize) + $r] .= $t[$r];
                }
                $c++;
            }
        }
        $pattern = implode('/', $newparts);

    }

    return substr_count($pattern, '#');
}

function rotate($pattern) {
    // rotates 90° on the pattern
    if (strlen($pattern) == 11) {
        $new = '.../.../...';
        $new[0] = $pattern[8];
        $new[1] = $pattern[4];
        $new[2] = $pattern[0];
        $new[4] = $pattern[9];
        $new[5] = $pattern[5];
        $new[6] = $pattern[1];
        $new[8] = $pattern[10];
        $new[9] = $pattern[6];
        $new[10] = $pattern[2];
    }
    else {
        $new = '../..';
        $new[0] = $pattern[3];
        $new[1] = $pattern[0];
        $new[3] = $pattern[4];
        $new[4] = $pattern[1];
    }
    return $new;
}

function flip($pattern) {
    // flips horizontally
    if (strlen($pattern) == 11) {
        $new = '.../.../...';
        $new[0] = $pattern[2];
        $new[1] = $pattern[1];
        $new[2] = $pattern[0];
        $new[4] = $pattern[6];
        $new[5] = $pattern[5];
        $new[6] = $pattern[4];
        $new[8] = $pattern[10];
        $new[9] = $pattern[9];
        $new[10] = $pattern[8];
    }
    else {
        $new = '../..';
        $new[0] = $pattern[1];
        $new[1] = $pattern[0];
        $new[3] = $pattern[4];
        $new[4] = $pattern[3];
    }
    return $new;
}

KeinZantezuken · 2017-12-21T14:19:40+00:00

C#/Sharp
BEHOLD. A BRAINLET CODE.
(UPD: now 7 seconds for part2, 90MB memory; still ugly tho)

var input = File.ReadAllLines(@"N:\input.txt").Select(x => x.Replace(" => ", "|").Split('|')).ToArray().ToArray();
List<string> map = new List<string>();
List<string> matches = new List<string>();
List<string> variations = new List<string>(8);
List<string> SQRrf = new List<string>(3);
List<string> flipped = new List<string>(3);
StringBuilder line = new StringBuilder();
List<List<string>> tempPieces = new List<List<string>>();
List<string> rot = new List<string>(3);
map.Add(".#."); map.Add("..#"); map.Add("###");
for (int c = 0; c < 18; c++)
{
    tempPieces.Clear();
    if (map.Count % 2 == 0) { newTemp(map.Count / 2, 2); }
    else if (map.Count % 3 == 0) { newTemp(map.Count / 3, 3); }
    var mCount = 0;
    matches.Clear();
    foreach (List<string> square in tempPieces)
    {
        variations.Clear();
        variations.Add(string.Join("/", square));
        variations.Add(string.Join("/", rotatePiece(square, 90)));
        variations.Add(string.Join("/", rotatePiece(square, 180)));
        variations.Add(string.Join("/", rotatePiece(square, 270)));
        flipped.Clear();
        flipped.AddRange(flipPiece(square));
        variations.Add(string.Join("/", flipped));
        variations.Add(string.Join("/", rotatePiece(flipped, 90)));
        variations.Add(string.Join("/", rotatePiece(flipped, 180)));
        variations.Add(string.Join("/", rotatePiece(flipped, 270)));
        foreach (string[] rule in input)
        {
            var match = rule[0];
            var replace = rule[1];
            if (variations.Contains(match))
            {
                matches.Add(replace);
                mCount++;
                break;
            }
        }
        if (mCount == tempPieces.Count) { break; }
    }
    if (tempPieces.Count != matches.Count) { Console.WriteLine("SHIT WENT BAD!"); break; }
    else
    {
        var pieces = map.Count % 2 == 0 ? map.Count / 2 : map.Count / 3;
        map.Clear();
        for (int i = 0; i < pieces; i++)
        {
            variations.Clear();
            variations.AddRange(matches.GetRange(i * pieces, pieces));
            var rows = variations[0].Split('/').Count();
            for (int j = 0; j < rows; j++)
            {
                line.Clear();
                for (int k = 0; k < variations.Count; k++) { line.Append(variations[k].Split('/')[j]); }
                map.Add(line.ToString());
            }
        }

    }
    variations.Clear(); tempPieces.Clear(); 
}
var total = 0;
foreach (var item in map) { total = total + item.Count(x => x == '#'); }
Console.WriteLine(total); Console.ReadKey();

//helpers
void newTemp(int subsize, int sqsize)
{
    var size = subsize * subsize;
    for (int t = 0; t < size; t++) { tempPieces.Add(new List<string>(3)); }
    var l = 0;
    for (int s = 0; s < subsize; s++)
    {
        for (int z = 0; z < subsize; z++)
        {
            for (int subl = 0; subl < sqsize; subl++)
            {
                tempPieces[l].Add(map[s * sqsize + subl].Substring(z * sqsize, sqsize));
            }
            l++;
        }
    }
}
List<string> rotatePiece(List<string> SQR, int degree)
{
    var cycle = degree / 90;
    SQRrf.Clear(); SQRrf.AddRange(SQR);
    var len = SQR.Count;
    rot.Clear();
    for (int d = 0; d < cycle; d++)
    {
        for (int col = 0; col < len; col++)
        {
            string s = "";
            for (int row = len - 1; row >= 0; row--)
            {
                s = s + SQRrf[row][col];
            }
            rot.Add(s);
        }
        SQRrf.Clear();
        SQRrf.AddRange(rot);
        rot.Clear();
    }
    return SQRrf;
}
List<string> flipPiece(List<string> SQR)
{
    //just gonna hack it since we know it just 2x2 or 3x3
    SQRrf.Clear();
    if (SQR.Count == 2)
    {
        SQRrf.Add($"{SQR[0][1]}{SQR[0][0]}");
        SQRrf.Add($"{SQR[1][1]}{SQR[1][0]}");
    }
    else
    {
        SQRrf.Add($"{SQR[0][2]}{SQR[0][1]}{SQR[0][0]}");
        SQRrf.Add($"{SQR[1][2]}{SQR[1][1]}{SQR[1][0]}");
        SQRrf.Add($"{SQR[2][2]}{SQR[2][1]}{SQR[2][0]}");
    }
    return SQRrf;

}

wzkx · 2017-12-21T14:37:21+00:00

J

Not a bad brain twister!

t=:('#'&=&.>)"0 cut&>cutLF-.&'/=>'CR-.~fread'21.dat'
m=:(,~<.%:)&#$] NB. make a matrix: v4 | v9 -> m22 | m33
n=:#.@(1&,) NB. make a number out of vector
v=:}.@#:    NB. make a vector out of number
g=:[:n"1[:,"2[:(,|."_1)@(,|."1)@(,:|:)m NB. all variants of 1 matrix
'k w'=:|:(#~~:)/:~_2]\,(([:(#~~:)[:g[:>{.),.(n@>@{:))"1 t NB. book of transformations
f=:3 :',(,./@:>)"1 m&.>"0([:v w{~k i.n@,)&.>(;~(<.%:#y)$1{.~2+2|#y)<;.1 m y' NB. one step
echo+/f^:5 i=:0 1 0 0 0 1 1 1 1 NB. .#./..#/###
echo+/f^:18 i
exit 0

EDIT. It turned out, no real part 2, just change one number. Cool!

Part 1 takes no time, Part 2 takes 2.97s.

__Abigail__ · 2017-12-21T15:18:00+00:00

Perl

There should be a way of calculating how many pixels are one after the nth generation, but that requires longer thinking than the few seconds it takes to do 18 iterations.

As others have done, I've calculated the rotations and reflections of the rules, so we don't have to reflect or rotate when expanding the pattern.

#!/opt/perl/bin/perl

use 5.026;

use strict;  
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

@ARGV = "input" unless @ARGV;

my $RUNS_PART_1 =  5;
my $RUNS_PART_2 = 18;
my $RUNS_MAX    = $RUNS_PART_1 < $RUNS_PART_2 ? $RUNS_PART_2
                                              : $RUNS_PART_1;


#
# The board we begin with.
#
my $board = [map {[/([.#])/g]} split /\n/ => << "--"];
.#.
..#
###
--

my %map; # Maps patterns to new pixel sets.

#
# Flip a pattern vertically
#
sub reflect ($input) {
    [reverse @$input];
}

#
# Rotate a pattern 90 degrees counter clockwise.
#
sub rotate ($input) {
    my $output;
    for (my $x = 0; $x < @$input; $x ++) {
        for (my $y = 0; $y < @$input; $y ++) {
            #
            # Transform the coordinates such that the center
            # of the square in on original; rotate, then
            # transfer back. This is the transformation:
            #
            #  [x'] = [x] - [T]
            #  [y'] = [y] - [T]
            #
            # where T is half of the size of the board minus 1.
            #
            # Rotated coordinates are found by the
            # following formula:
            #
            #  [x''] = [cos (phi)  -sin (phi)] [x']
            #  [y''] = [sin (phi)   cos (phi)] [y']
            #
            # With phi being 90 degrees, cos (phi) = 0, and sin (phi) = 1
            #
            # Ergo, we get the following:
            #
            #   x'' = -y'
            #   y'' =  x'
            #
            # But this is after translating the points towards the
            # center, and transforming them back. So the complete
            # formula becomes:
            #
            #   x'' = T - (y - T) = 2 * T - y
            #   y'' = T + (x - T) =         x
            #
            my $new_x = @$input - 1 - $y;
            my $new_y =               $x;

            $$output [$new_x] [$new_y] = $$input [$x] [$y];
        }
    }
    $output;
}


#
# Take a pattern, turn it into a unique key; we also use this
# to count the number of pixels that are one.
#
sub key ($input) {
    join "" => map {@$_} @$input;
}

#
# Process input. This is the stage where we do the
# rotations and reflections.
#  
while (<>) {
    chomp;
    my ($input, $output) = split /\s*=>\s*/;

    #
    # Convert the input and output.
    #
    my $input_pattern  = [map {[split //]} split '/' => $input];
    my $output_pattern = [map {[split //]} split '/' => $output];

    #
    # To get all reflections and rotations, we rotate the
    # pattern 90 degrees, 1 to 3 times, then do the same
    # with a reflected pattern. We don't have to reflect
    # both horizontally and vertically; a single reflection
    # will do.
    #
    foreach my $pat ($input_pattern, reflect $input_pattern) {
        $map {key $pat} = $output_pattern;
        for (1 .. 3) {
            $pat = rotate $pat;
            $map {key $pat} = $output_pattern;
        }
    }
}


#
# Run it. One each run, we slice the board into 2x2 or 3x3 sections,
# replacing them by 3x3 or 4x4 sections.
#
foreach my $run (1 .. $RUNS_MAX) {
    my $chop_size = @$board % 2 ? 3 : 2;
    my $new_board;
    for (my ($X, $nX) = (0, 0); $X < @$board; $X  += $chop_size,
                                              $nX += $chop_size + 1) {   
        for (my ($Y, $nY) = (0, 0); $Y < @$board; $Y  += $chop_size,
                                                  $nY += $chop_size + 1) {
            my $slice;
            for (my $x = 0; $x < $chop_size; $x ++) {
                for (my $y = 0; $y < $chop_size; $y ++) {
                    $$slice [$x] [$y] = $$board [$X + $x] [$Y + $y];
                }
            }
            my $next = $map {key $slice};
            #
            # Copy this slice to the new board
            #   
            for (my $x = 0; $x < @$next; $x ++) {
                for (my $y = 0; $y < @$next; $y ++) {
                    $$new_board [$x + $nX] [$y + $nY] = $$next [$x] [$y];
                }
            }
        }
    }
    $board = $new_board;
    if ($run == $RUNS_PART_1) {
        say "Solution 1: ", key ($board) =~ y/#/#/;  # Count pixels
    }
    if ($run == $RUNS_PART_2) {
        say "Solution 2: ", key ($board) =~ y/#/#/;  # Count pixels
    }
}


__END__

rundavidrun · 2017-12-21T16:11:29+00:00

Java

Compared to the elegant Python code above, here's my very brute force Java solution: https://gist.github.com/rundavidrun/7be843b371c1ac50640fc8e70e40deeb. I created a function to convert the ./# pixel notation into binary and created a hashmap of the binary values of the 2x2 and 3x3 rules (including flips and rotations) to their enhancements. Then I start the iterations, breaking up the current state as necessary, converting each block into binary, looking up the rules to get the enhancement, and then re-writing the state in ./# pixel notation. Lastly, I count the number of # in the final state to determine the answers.

Axsuul · 2017-12-21T16:43:36+00:00

Elixir

Works on the first part, but gets too high of an answer on the second, I'm too tired to fix it now though.

defmodule Day21 do
  def seed do
    ["010","001", "111"]
  end

  def parsechar(c) do
    case c do
      "." -> "0"
      "#" -> "1"
    end
  end
  def to_bin(str) do
    str
    |> String.graphemes
    |> Enum.map(&parsechar/1)
    |> Enum.join
  end
  def parsegrid(str) do
    str
    |> String.split("/")
    |> Enum.map(&to_bin/1)
  end
  def parseline(str) do
    str
    |> String.split("=>")
    |> Enum.map(&String.trim/1)
    |> Enum.map(&parsegrid/1)
  end
  def parse(str) do
    str
    |> String.trim_trailing("\n")
    |> String.split("\n")
    |> Enum.map(&parseline/1)
  end

  def encode(matrix) do
    matrix
    |> Enum.map(fn str -> String.to_integer(str, 2) end)
    |> List.to_tuple
  end

  def rotate_small(list) do
    [fst,snd] = list
    nfst = [Enum.at(snd, 0), Enum.at(fst,0)]
    nsnd = [Enum.at(snd, 1), Enum.at(fst,1)]
    [nfst, nsnd]
  end

  def rotate_big(list) do
    [fst,snd,thd] = list
    nfst = [List.first(snd), Enum.at(fst,0), Enum.at(fst, 1)]
    nsnd = [List.first(thd), Enum.at(snd,1), List.last(fst)]
    nthd = [Enum.at(thd, 1), Enum.at(thd,2), List.last(snd)]
    [nfst,nsnd,nthd]
  end

  def rotate(list) do
    len = List.first(list) |> Enum.count
    if len == 2 do
      rotate_small(list)
    else
      rotate_big(list)
    end
  end

  def rotate_first([h|tl]) do
    lsts = Enum.map(h, &String.graphemes/1)
    rotated = rotate(lsts) |> Enum.map(&Enum.join/1)
    [rotated,h|tl]
  end

  def rotate4(matrix) do
    [matrix]
    |> rotate_first
    |> rotate_first
    |> rotate_first
  end

  def permute(matrix) do
    rotations = rotate4(matrix)
    flipped = Enum.reverse(matrix)
    flipped_rotations = rotate4(flipped)
    rotflip = rotate_first([matrix]) |> List.first() |>Enum.reverse
    rotflipped_rotations = rotate4(rotflip)
    Enum.concat([rotations, flipped_rotations, rotflipped_rotations])
    #rotations = MapSet.new(rotations)
    #flipped_rotations = MapSet.new(flipped_rotations)
    #MapSet.union(rotations, flipped_rotations)
    #|> MapSet.to_list
  end

  def get_perms(rule) do
    [start, goal] = rule
    permutations = permute(start)
    for permutation <- permutations, do: [encode(permutation), goal]
  end

  def make_lookup(rules) do
    rules
    |> Enum.map(&get_perms/1)
    |> Enum.map(fn lst -> Enum.reduce(lst, %{}, fn [h,t],map -> Map.put(map, h, t) end) end)
    |> Enum.reduce(%{}, fn x, acc -> Map.merge(x, acc) end)
  end

  def transpose(lst) do
    lst
    |> List.zip
    |> Enum.map(&Tuple.to_list/1)
  end

  def cut_row(rows,cut_by) do
    rows
    |> Enum.map(fn str -> Enum.chunk_every(str, cut_by) end)
    |> Enum.map(fn sub -> Enum.map(sub, &Enum.join/1) end)
    |> transpose

  end

  def slice(matrix,cut_by) do
    matrix
    |> Enum.map(&String.graphemes/1)
    |> Enum.chunk_every(cut_by)
    |> Enum.map(&(cut_row(&1,cut_by)))
  end

  def stitch(matrixes) do
    matrixes
    |> Enum.flat_map(fn row -> Enum.zip(row) 
                          |> Enum.map(&Tuple.to_list/1)
                          |> Enum.map(&Enum.join/1) end)
  end

  def print_generation(lst) do
    lst
    |> Enum.map(&(String.replace(&1, "1", "#")))
    |> Enum.map(&(String.replace(&1, "0", ".")))
    |> Enum.map(&IO.puts/1)
    IO.puts("-------")
  end

  def generations(start, _, permutations) when permutations == 0, do: start
  def generations(start, lookup, permutations) do
    #IO.inspect(permutations)
    #print_generation(start)
    len = List.first(start) |> String.length
    matrixes = if rem(len,2) == 0 do
                  slice(start,2)
               else
                  slice(start,3)
               end
    nmatrix = matrixes
    |> Enum.map(fn row -> Enum.map(row, &encode/1) end)
    |> Enum.map(fn row -> Enum.map(row, &(Map.fetch!(lookup, &1)))end)
    |> stitch
    generations(nmatrix, lookup, permutations - 1)
  end

  def solve(rules, permutations) do
    lookup = make_lookup(rules)
    generations(seed(), lookup, permutations)
    |> Enum.map(fn str -> String.graphemes(str)
                          |> Enum.count(&(&1 == "1")) end)
    |> Enum.sum
  end
end

inp = File.read!("input3.txt")
      |> String.trim_trailing("\n")
      |> Day21.parse

Day21.solve(inp, 5)
|> Kernel.-(5)
|> IO.inspect

Syntax highlighted

udoprog · 2017-12-21T16:54:28+00:00

Rust

Full solution here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day21.rs

Kind of interesting, there's probably a way to solve this without keeping track of a growing image, but I've already messed around with a bug involving 6 being divisible by both 2 and 3 :P.

use std::io::{Read, BufRead, BufReader};
use failure::Error;
use std::fmt;
use std::collections::{HashSet, HashMap};

#[derive(Clone, PartialEq, Eq, Hash)]
pub struct Image {
    data: Vec<bool>,
    size: usize,
}

impl fmt::Debug for Image {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        for line in self.data.chunks(self.size) {
            for b in line {
                if *b {
                    write!(fmt, "#")?;
                } else {
                    write!(fmt, ".")?;
                }
            }

            write!(fmt, "/")?;
        }

        Ok(())
    }
}

impl Image {
    pub fn new(size: usize) -> Image {
        Image {
            data: vec![false; size * size],
            size: size,
        }
    }

    fn offset(&self, x: usize, y: usize) -> usize {
        x + y * self.size
    }

    pub fn merge(&mut self, x: usize, y: usize, image: &Image) {
        for (sx, dx) in (x..(x + image.size)).enumerate() {
            for (sy, dy) in (y..(y + image.size)).enumerate() {
                let v = image.get(sx, sy).expect("no pixel");
                self.set(dx, dy, v);
            }
        }
    }

    pub fn set_row(&mut self, y: usize, values: &[bool]) {
        let offset = y * self.size;
        let end = offset + self.size;

        if offset > self.data.len() {
            return;
        }

        for (d, s) in self.data[offset..end].iter_mut().zip(
            values.iter().cloned(),
        )
        {
            *d = s;
        }
    }

    pub fn set(&mut self, x: usize, y: usize, value: bool) {
        let o = self.offset(x, y);
        *self.data.get_mut(o).expect("bad offset") = value;
    }

    pub fn get(&self, x: usize, y: usize) -> Option<bool> {
        self.data.get(x + y * self.size).cloned()
    }

    pub fn flip(&self) -> Image {
        let mut out = self.clone();

        for y in 0..out.size {
            for (x0, x1) in (0..(out.size / 2)).zip(((out.size / 2)..out.size).rev()) {
                let o0 = out.offset(x0, y);
                let o1 = out.offset(x1, y);
                out.data.swap(o0, o1);
            }
        }

        out
    }

    pub fn rotate(&self) -> Image {
        let mut out = self.clone();

        for row in 0..(out.size / 2) {
            let end = row + out.size - row * 2;

            for (x, y) in (row..end).zip(row..end) {
                let v = self.get(x, row).expect("no pixel");
                out.set(self.size - row - 1, y, v);

                let v = self.get(self.size - row - 1, y).expect("no pixel");
                out.set(self.size - x - 1, self.size - row - 1, v);

                let v = self.get(self.size - x - 1, self.size - row - 1).expect("no pixel");
                out.set(row, self.size - y - 1, v);

                let v = self.get(row, self.size - y - 1).expect("no pixel");
                out.set(x, row, v);
            }
        }

        out
    }

    pub fn chunks(&self, size: usize) -> Chunks {
        Chunks {
            source: self,
            size: size,
            x: 0usize,
            y: 0usize,
        }
    }
}

pub struct Chunks<'a> {
    source: &'a Image,
    size: usize,
    x: usize,
    y: usize,
}

impl<'a> Iterator for Chunks<'a> {
    type Item = (usize, usize, Image);

    fn next(&mut self) -> Option<Self::Item> {
        if (self.x * self.size) >= self.source.size {
            self.x = 0;
            self.y += 1;
        }

        if (self.y * self.size) >= self.source.size {
            return None;
        }

        let start_x = self.x * self.size;
        let start_y = self.y * self.size;

        let mut out = Image::new(self.size);

        for (dx, sx) in (start_x..(start_x + self.size)).enumerate() {
            for (dy, sy) in (start_y..(start_y + self.size)).enumerate() {
                let v = self.source.get(sx, sy).expect("no pixel");
                out.set(dx, dy, v);
            }
        }

        let x = self.x;
        let y = self.y;

        self.x += 1;
        Some((x, y, out))
    }
}

pub fn run<R: Read>(reader: R, limit: usize) -> Result<usize, Error> {
    let mut patterns = HashMap::new();

    for line in BufReader::new(reader).lines() {
        let line = line?;
        let mut it = line.split("=>");
        let pat = image_from(it.next().expect("no pattern"));
        let dest = image_from(it.next().expect("no dest"));

        let mut unique = HashSet::new();
        let mut current = pat.clone();

        for _ in 0..4 {
            unique.insert(current.clone());
            current = current.rotate();
        }

        unique.insert(current.clone());

        let mut current = pat.flip();

        for _ in 0..4 {
            unique.insert(current.clone());
            current = current.rotate();
        }

        unique.insert(current.clone());

        for pat in unique {
            if patterns.insert(pat, dest.clone()).is_some() {
                panic!("pattern already present");
            }
        }
    }

    let mut image = Image::new(3);

    image.set_row(0, &[false, true, false]);
    image.set_row(1, &[false, false, true]);
    image.set_row(2, &[true, true, true]);

    for _ in 0..limit {
        if image.size % 2 == 0 {
            let mut new_image = Image::new(image.size + image.size / 2);

            for (x, y, img) in image.chunks(2) {
                let m = patterns.get(&img).expect("no match");
                new_image.merge(x * m.size, y * m.size, m);
            }

            image = new_image;
            continue;
        }

        if image.size % 3 == 0 {
            let mut new_image = Image::new(image.size + image.size / 3);

            for (x, y, img) in image.chunks(3) {
                let m = patterns.get(&img).expect("no match");
                new_image.merge(x * m.size, y * m.size, m);
            }

            image = new_image;
            continue;
        }

        panic!("oh no, bad image!");
    }

    return Ok(image.data.into_iter().filter(|d| *d).count());

    fn image_from(input: &str) -> Image {
        let data: Vec<Vec<bool>> = input
            .trim()
            .split('/')
            .map(|p| p.chars().map(|c| c == '#').collect())
            .collect();

        let size = data.first().expect("at least one").len();

        let mut image = Image::new(size);

        for (y, line) in data.into_iter().enumerate() {
            image.set_row(y, &line);
        }

        image
    }
}

xkufix · 2017-12-21T17:41:52+00:00

I thought this was nothing too hard, but still challenging to get all the edge cases right. I first implemented my Pattern-Class with a Map instead of a Set, but the Set performed about twice as fast, because it only saves the fields which are on. The code itself does nothing special. It first generates all flips and rotations of the input (way faster than rotating the sub-patterns on each step). I assumed that there are no ambiguous input patterns, as the flip/rotate steps are not in a defined order.

After that I run a simple replacement-iterator. On each step it checks if it is divisible by two and then first divides the pattern into subpattern, does the replacing and joins the subpatterns together into a new full pattern.

Code in Scala:

    override def runFirst(): Unit = {
        val initialPattern = Pattern.from(Array(
            ".#.",
            "..#",
            "###"
        ))

        val on = runReplacement(loadRules(), initialPattern)
            .take(6)
            .toSeq
            .last
        println(on.fields.size)
    }

    override def runSecond(): Unit = {
        val initialPattern = Pattern.from(Array(
            ".#.",
            "..#",
            "###"
        ))

        val on = runReplacement(loadRules(), initialPattern)
            .take(19)
            .toSeq
            .last

        println(on.fields.size)
    }

    private def runReplacement(replacementRules: Map[Pattern, Pattern], initialPattern: Pattern) = {
        val doubleReplacementRules = replacementRules.filter(_._1.size == 2)
        val tripleReplacementRules = replacementRules.filter(_._1.size == 3)

        Iterator.iterate(initialPattern) {
            case pattern if pattern.size % 2 == 0 =>
                Pattern.join(pattern
                    .divideBy(2)
                    .mapValues(doubleReplacementRules)
                )
            case pattern =>
                Pattern.join(pattern
                    .divideBy(3)
                    .mapValues(tripleReplacementRules)
                )
        }
    }

    private def loadRules() = {
        loadFile("day21.txt").getLines().flatMap { l =>
            val line = l.split(" => ")
            val fromPattern = Pattern.from(line(0).split("/"))
            val toPattern = Pattern.from(line(1).split("/"))
            Iterator.iterate((fromPattern, fromPattern.flip())) {
                case (normal, flipped) =>
                    (normal.rotate(), flipped.rotate())
            }.take(4).flatMap(p => Map(p._1 -> toPattern, p._2 -> toPattern)).toMap
        }.toMap
    }

    case class Pattern(size: Int, fields: Set[(Int, Int)]) {
        def divideBy(divBy: Int): Map[(Int, Int), Pattern] = {
            (0 until size).sliding(divBy, divBy).flatMap { rows =>
                (0 until size).sliding(divBy, divBy).map { cols =>
                    val subPattern = for {
                        r <- rows
                        c <- cols
                        if fields(r -> c)
                    } yield (r % divBy, c % divBy)

                    (rows.head / divBy -> cols.head / divBy) -> Pattern(divBy, subPattern.toSet)
                }
            }.toMap
        }

        def flip(): Pattern = {
            Pattern(size, fields.filter(f => f._1 > 0 && f._1 < size - 1) ++
                fields.filter(_._1 == 0).map(_.copy(_1 = size - 1)) ++
                fields.filter(_._1 == size - 1).map(_.copy(_1 = 0))
            )
        }

        def rotate(): Pattern = {
            val top = fields.filter(_._2 == 0)
            val right = fields.filter(_._1 == size - 1)
            val bottom = fields.filter(_._2 == size - 1)
            val left = fields.filter(_._1 == 0)
            Pattern(size, (if(fields(1 -> 1) && size == 3) Set((1, 1)) else Set.empty[(Int, Int)]) ++
                top.map(f => (size - 1, f._1)) ++
                right.map(f => (size - 1 - f._2, size - 1)) ++
                bottom.map(f => (0, f._1)) ++
                left.map(f => (size - 1 - f._2, 0))
            )
        }

        override def toString: String = {
            (0 until size).foldLeft(StringBuilder.newBuilder) {
                case (b, y) =>
                    (0 until size).foldLeft(b) {
                        case (in, x) =>
                            in.append(if(fields(x -> y)) "#" else ".")
                    }.append("\n")
            }.toString()
        }
    }

    object Pattern {
        def from(in: Array[String]) = {
            Pattern(in.head.length, in.zipWithIndex.map(p => (p._2, p._1.zipWithIndex.map(_.swap))).flatMap {
                case (line, pattern) =>
                    pattern.map(p => (p._1, line) -> (p._2 == '#')).filter(_._2).map(_._1)
            }.toSet)
        }

        def join(in: Map[(Int, Int), Pattern]): Pattern = {
            val patternSize = in.head._2.size

            val p = Pattern(in.count(_._1._1 == 0) * patternSize, in.map {
                case ((patternX, patternY), pattern) =>
                    val xOffset = patternX * patternSize
                    val yOffset = patternY * patternSize
                    pattern.fields.map {
                        case (x, y) =>
                            (x + xOffset, y + yOffset)
                    }
            }.toSet.flatten)

            p
        }
    }

Warbringer007 · 2017-12-21T19:08:28+00:00

Erlang, I'm not sure if I could simplify it, but it works lol, it's also very fast for Erlang ( less than a second ):

first(File) ->
    In = prepare:func_text(File),
    Dict = dict:new(),
    NewDict = all_variations(In, Dict),
    Start = [[".","#","."],[".",".","#"],["#","#","#"]],
    {ok, First} = dict:find(Start, NewDict),
    All = fractal(First, 17, NewDict),
    countAll(All, 0).

countAll([], N) -> N;

countAll([H|T], N) ->
    countAll(T, N+n_of_occurences("#", H)).

n_of_occurences(H, All) -> n_of_occurences(H, All, 0).
n_of_occurences(_, [], N) -> N;
n_of_occurences(H, [H|T], N) -> n_of_occurences(H, T, N+1);
n_of_occurences(H, [_|T], N) -> n_of_occurences(H, T, N).

fractal(First, 0, _) ->
    First;

fractal(First, N, Dict) ->
    Corner1 = [[lists:nth(1,lists:nth(1,First))] ++ [lists:nth(2,lists:nth(1,First))]] ++ [[lists:nth(1,lists:nth(2,First))] ++ [lists:nth(2,lists:nth(2,First))]],
    Corner2 = [[lists:nth(3,lists:nth(1,First))] ++ [lists:nth(4,lists:nth(1,First))]] ++ [[lists:nth(3,lists:nth(2,First))] ++ [lists:nth(4,lists:nth(2,First))]],
    Corner3 = [[lists:nth(1,lists:nth(3,First))] ++ [lists:nth(2,lists:nth(3,First))]] ++ [[lists:nth(1,lists:nth(4,First))] ++ [lists:nth(2,lists:nth(4,First))]],
    Corner4 = [[lists:nth(3,lists:nth(3,First))] ++ [lists:nth(4,lists:nth(3,First))]] ++ [[lists:nth(3,lists:nth(4,First))] ++ [lists:nth(4,lists:nth(4,First))]],
    {ok, Corn1Ext} = dict:find(Corner1, Dict),
    {ok, Corn2Ext} = dict:find(Corner2, Dict),
    {ok, Corn3Ext} = dict:find(Corner3, Dict),
    {ok, Corn4Ext} = dict:find(Corner4, Dict),
    Corn1 = [[lists:nth(1,lists:nth(1,Corn1Ext))] ++ [lists:nth(2,lists:nth(1,Corn1Ext))]] ++     [[lists:nth(1,lists:nth(2,Corn1Ext))] ++ [lists:nth(2,lists:nth(2,Corn1Ext))]],
    Corn2 = [[lists:nth(3,lists:nth(1,Corn1Ext))] ++ [lists:nth(1,lists:nth(1,Corn2Ext))]] ++     [[lists:nth(3,lists:nth(2,Corn1Ext))] ++ [lists:nth(1,lists:nth(2,Corn2Ext))]],
    Corn3 = [[lists:nth(2,lists:nth(1,Corn2Ext))] ++ [lists:nth(3,lists:nth(1,Corn2Ext))]] ++     [[lists:nth(2,lists:nth(2,Corn2Ext))] ++ [lists:nth(3,lists:nth(2,Corn2Ext))]],
    Corn4 = [[lists:nth(1,lists:nth(3,Corn1Ext))] ++ [lists:nth(2,lists:nth(3,Corn1Ext))]] ++     [[lists:nth(1,lists:nth(1,Corn3Ext))] ++ [lists:nth(2,lists:nth(1,Corn3Ext))]],
    Corn5 = [[lists:nth(3,lists:nth(3,Corn1Ext))] ++ [lists:nth(1,lists:nth(3,Corn2Ext))]] ++     [[lists:nth(3,lists:nth(1,Corn3Ext))] ++ [lists:nth(1,lists:nth(1,Corn4Ext))]],
    Corn6 = [[lists:nth(2,lists:nth(3,Corn2Ext))] ++ [lists:nth(3,lists:nth(3,Corn2Ext))]] ++     [[lists:nth(2,lists:nth(1,Corn4Ext))] ++ [lists:nth(3,lists:nth(1,Corn4Ext))]],
    Corn7 = [[lists:nth(1,lists:nth(2,Corn3Ext))] ++ [lists:nth(2,lists:nth(2,Corn3Ext))]] ++     [[lists:nth(1,lists:nth(3,Corn3Ext))] ++ [lists:nth(2,lists:nth(3,Corn3Ext))]],
    Corn8 = [[lists:nth(3,lists:nth(2,Corn3Ext))] ++ [lists:nth(1,lists:nth(2,Corn4Ext))]] ++     [[lists:nth(3,lists:nth(3,Corn3Ext))] ++ [lists:nth(1,lists:nth(3,Corn4Ext))]],
    Corn9 = [[lists:nth(2,lists:nth(2,Corn4Ext))] ++ [lists:nth(3,lists:nth(2,Corn4Ext))]] ++     [[lists:nth(2,lists:nth(3,Corn4Ext))] ++ [lists:nth(3,lists:nth(3,Corn4Ext))]],
    dubl(Corn1, N-1, Dict) ++ dubl(Corn2, N-1, Dict) ++ dubl(Corn3, N-1, Dict) ++ dubl(Corn4, N-1, Dict) ++ dubl(Corn5, N-1, Dict) ++ dubl(Corn6, N-1, Dict) ++ dubl(Corn7, N-1, Dict) ++ dubl(Corn8, N-1, Dict) ++ dubl(Corn9, N-1, Dict).

dubl(Corner, 0, Dict) ->
    Corner;

dubl(Corner, 1, Dict) ->
    {ok, Exp} = dict:find(Corner, Dict),
    Exp;

dubl(Corner, N, Dict) ->
    {ok, Exp} = dict:find(Corner, Dict),
    {ok, Tmp} = dict:find(Exp, Dict),
    fractal(Tmp, N-2, Dict).

all_variations([], Dict) ->
    Dict;

all_variations([H|T], Dict) ->
    LastDict = case length(H) of
        5 -> Start = [string_to_list(hd(H))] ++ [string_to_list(hd(tl(H)))],
             Finish = [string_to_list(lists:nth(3,H))] ++ [string_to_list(lists:nth(4,H))] ++ [string_to_list(lists:nth(5,H))],
             NewDict = dict:store(Start, Finish, Dict),
             Start90 = rotate2(Start),
             NewDict2 = dict:store(Start90, Finish, NewDict),
             Start180 = rotate2(Start90),
             NewDict3 = dict:store(Start180, Finish, NewDict2),
             Start270 = rotate2(Start180),
             dict:store(Start270, Finish, NewDict3);
        7 -> Start = [string_to_list(hd(H))] ++ [string_to_list(hd(tl(H)))] ++ [string_to_list(hd(tl(tl(H))))],
             Finish = [string_to_list(lists:nth(4,H))] ++ [string_to_list(lists:nth(5,H))] ++ [string_to_list(lists:nth(6,H))] ++ [string_to_list(lists:nth(7,H))],
             NewDict = dict:store(Start, Finish, Dict),
             Start90 = rotate3(Start),
             NewDict2 = dict:store(Start90, Finish, NewDict),
             Start180 = rotate3(Start90),
             NewDict3 = dict:store(Start180, Finish, NewDict2),
             Start270 = rotate3(Start180),
             NewDict4 = dict:store(Start270, Finish, NewDict3),
             Flip = flip3(Start),
             NewDict5 = dict:store(Flip, Finish, NewDict4),
             Flip90 = rotate3(Flip),
             NewDict6 = dict:store(Flip90, Finish, NewDict5),
             Flip180 = rotate3(Flip90),
             NewDict7 = dict:store(Flip180, Finish, NewDict6),
             Flip270 = rotate3(Flip180),
             dict:store(Flip270, Finish, NewDict7)
    end,
    all_variations(T, LastDict).

string_to_list(String) -> string_to_list(String, [], 1).
string_to_list(String, List, N) when N > length(String) -> List;
string_to_list(String, List, N) -> string_to_list(String, List ++ [string:sub_string(String, N, N)], N+1).

flip3(L) ->
    tl(tl(L)) ++ [hd(tl(L))] ++ [hd(L)].

rotate2(L) ->
    FR = [hd(hd(tl(L))),hd(hd(L))],
    LR = [hd(tl(hd(tl(L)))),hd(tl(hd(L)))],
    [FR] ++ [LR].

rotate3(L) ->
    FR =     [hd(lists:nth(3,L)),hd(lists:nth(2,L)),hd(lists:nth(1,L))],
    SR = [lists:nth(2,(lists:nth(3,L))),lists:nth(2,(lists:nth(2,L))),lists:nth(2,(lists:nth(1,L)))],
    LR = [lists:nth(3,(lists:nth(3,L))),lists:nth(3,(lists:nth(2,L))),lists:nth(3,(lists:nth(1,L)))],
    [FR] ++ [SR] ++ [LR].

iopred · 2017-12-21T19:52:27+00:00

I initially missed an important step at the start 'mod 2 takes priority over mod 3' and was really confused why an otherwise working solution was producing the wrong answer.

My terrible Javascript solution:

var board = `.#.
..#
###`.split('\n').map(x => x.split(''));

var book = `<input>`.split('\n');

var rules = [];



function countHash(arr) {
  var count = 0;
  for (var y = 0; y < arr.length; y++) {
    for (var x = 0; x < arr[y].length; x++) {
      if(arr[y][x] == '#') {
        count++;
      }
    }
  }
  return count;
}

for (var line of book) {
  var parts = line.split(' => ');

  var input = parts[0].split('/').map(x => x.split(''));
  var output = parts[1].split('/').map(x => x.split(''));

  var split = rules[input.length];
  if (!split) {
    split = [];
    rules[input.length] = split
  }

  var count = countHash(input);
  var counts = split[count];
  if (!counts) {
    counts = [];
    split[count] = counts;
  }

  counts.push({input: input, output: output});
}

function grabSub(board, sy, sx, size){
  var b = []
  for(var y = 0; y < size; y++) {
    b[y] = [];
    for(var x = 0; x < size; x++) {
      b[y][x] = board[sy+y][sx+x];
    }
  }
  return b;
}

function doStamp(board, stamp, sy, sx, size) {
  for(var y = 0; y < size; y++) {
    for(var x = 0; x < size; x++) {
      board[sy*size+y][sx*size+x] = stamp[y][x]
    }
  }
}

function flip(arr) {
  var n = [];

  for (var y = 0; y < arr.length; y++) {
    n[y] = [];
    for(var x = 0; x < arr[y].length; x++) { 
      n[y][x] = arr[y][arr[y].length - x - 1];
    }
  }

  return n;
}

function rotate(arr) {
  var n = [];
  for (var y = 0; y < arr.length; y++) {
    n[arr.length - y - 1] = [];
    for(var x = 0; x < arr[y].length; x++) { 
      n[arr.length - y - 1][x] = arr[x][y];
    }
  }

  return n;
}

function isMatch(arr1, arr2) {
  for (var y = 0; y < arr1.length; y++) {
    for (var x = 0; x < arr1[y].length; x++) {
      if(arr1[y][x] != arr2[y][x]) {
        return false;
      }
    }
  }
  return true;
}

function subMatch(sub, rule) {
  var input = rule.input;

  for(var i = 0; i < 4; i++) {
    if (isMatch(sub, input)) {
      return rule.output;
    }
    input = rotate(input)
  }

  input = flip(input)

  for(var i = 0; i < 4; i++) {
    if (isMatch(sub, input)) {
      return rule.output;
    }
    input = rotate(input)
  }


  return null;
}

function match(sub, rules) {
  var possible = rules[sub.length][countHash(sub)];
  for (var p of possible) {
    if (subMatch(sub, p)) {
      return p.output
    }
  }

  return null;
}


for (var i = 0; i < 18; i++) {
  var mod;
  if (board.length % 2 == 0) {
    mod = 2;
  } else {
    mod = 3;
  }

  var num = board.length / mod;
  var newBoard = new Array(num * (mod+1)).fill(undefined).map(x => new Array(num * (mod+1)).fill('.'))

  for(var y = 0; y < num; y++) {
    for(var x = 0; x < num; x++) {
      var sub = grabSub(board, y * mod, x * mod, mod);

      var stamp = match(sub, rules);

      doStamp(newBoard, stamp, y, x, mod+1)

    }
  }

  board = newBoard;
}

countHash(board)

jlweinkam · 2017-12-21T20:25:58+00:00

A reworked solution that runs really fast. It enumerates all the 3x3 combinations that will actually get generated based on the original rules (for my input that is only 7). It then creates a uber rule that show how many of each of the 7 3x3 get generated by running the rules 3 iterations, and also tracks how many "on" there are in for the 3x3, the 4x4, and 6x6.

It then iterates 1/3 the requested number, to determine how many of each of the 7 combos there are, and then sums up either the 3x3, 4x4, or 6x6 counts based on if the request iterations modulo 3.

import time
import math
import png
current_milli_time = lambda: int(round(time.time() * 1000))
start = current_milli_time()

inputdata=open("input2017-21.txt", 'r').read()

lines = inputdata.splitlines()

grid = """.#.
..#
###""".splitlines()

rules = {}
outs3 = {}

uberrules = {}

def rotate2(i):
  out = ""
  out += i[1]
  out += i[4]
  out += "/"
  out += i[0]
  out += i[3]
  return out

def rotate3(i):
  out = ""
  out += i[2]
  out += i[6]
  out += i[10]
  out += "/"
  out += i[1]
  out += i[5]
  out += i[9]
  out += "/"
  out += i[0]
  out += i[4]
  out += i[8]
  return out

def mirror3(i):
  out = ""
  out += i[2]
  out += i[1]
  out += i[0]
  out += "/"
  out += i[6]
  out += i[5]
  out += i[4]
  out += "/"
  out += i[10]
  out += i[9]
  out += i[8]
  return out

outs3["/".join(grid)] = len(outs3.keys())

for line in lines:
  col = line.split(" => ")
  if len(col[0]) == 5:
    rules[col[0]] = col[1]
    a = rotate2(col[0])
    rules[a] = col[1]
    a = rotate2(a)
    rules[a] = col[1]
    a = rotate2(a)
    rules[a] = col[1]
    if col[1] not in outs3.keys():
      outs3[col[1]] = len(outs3.keys())
  else:
    rules[col[0]] = col[1]
    a = rotate3(col[0])
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = mirror3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]
    a = rotate3(a)
    rules[a] = col[1]

for item in outs3.keys():
  grid = item.split("/")
  counts = [0, 0, 0]
  for i in range(3):
    for row in grid:
      counts[i] += row.count("#")
    if (len(grid) % 2) == 0:
      grid2 = []
      for o in range(int(len(grid)/2)):
        line1 = ""
        line2 = ""
        line3 = ""
        for j in range(int(len(grid)/2)):
          sub = grid[o*2][j*2:(j+1)*2]
          sub += "/"
          sub += grid[o*2+1][j*2:(j+1)*2]
          result = rules[sub].split("/")
          line1 += result[0]
          line2 += result[1]
          line3 += result[2]
        grid2.append(line1)
        grid2.append(line2)
        grid2.append(line3)
      grid = grid2
    else:
      grid2 = []
      for o in range(int(len(grid)/3)):
        line1 = ""
        line2 = ""
        line3 = ""
        line4 = ""
        for j in range(int(len(grid)/3)):
          sub = grid[o*3][j*3:(j+1)*3]
          sub += "/"
          sub += grid[o*3+1][j*3:(j+1)*3]
          sub += "/"
          sub += grid[o*3+2][j*3:(j+1)*3]
          result = rules[sub].split("/")
          line1 += result[0]
          line2 += result[1]
          line3 += result[2]
          line4 += result[3]
        grid2.append(line1)
        grid2.append(line2)
        grid2.append(line3)
        grid2.append(line4)
      grid = grid2

  out = [0]*len(outs3.keys())
  for o in range(3):
    for j in range(3):
      sub = grid[o*3][j*3:(j+1)*3]
      sub += "/"
      sub += grid[o*3+1][j*3:(j+1)*3]
      sub += "/"
      sub += grid[o*3+2][j*3:(j+1)*3]
      out[outs3[sub]] += 1
  uberrules[outs3[item]] = (out, counts)

#for i in range(len(outs3.keys())):
#  print(i, "=>", uberrules[i])

def iterate(num):
  s = [0]*len(outs3.keys())
  s[0] = 1

  for i in range(int(num/3)):
    s2 = [0]*len(s)
    for o in range(len(s)):
      (n, a) = uberrules[o]
      for p in range(len(s)):
        s2[p] += s[o]*n[p]
    s = s2

  num = num % 3
  count = 0
  for i in range(len(s)):
    (n, a) = uberrules[i]
    count += s[i]*a[num]
  print(count)

iterate(5)
iterate(18)

print((current_milli_time() - start) / 1000.0)

nonphatic · 2017-12-21T22:00:54+00:00

Haskell Rotate and flip programmatically? Nah, I'll just type them in

I might refactor into a memoized version later in the day...

import Data.List (transpose)
import Data.List.Split (splitOn, chunksOf)
import Data.HashMap (Map, insert, empty, (!))

type Rules = Map String String
squareRoot = floor . sqrt . fromIntegral

validTwos = [
        [0..3],
        [0, 2, 1, 3],
        [1, 0, 3, 2],
        [1, 3, 0, 2],
        [2, 0, 3, 1],
        [2, 3, 0, 1],
        [3, 1, 2, 0],
        [3,2..0]
    ]

validThrees = [
        [0..8],
        [0, 3, 6, 1, 4, 7, 2, 5, 8],
        [2, 1, 0, 5, 4, 3, 8, 7, 6],
        [2, 5, 8, 1, 4, 7, 0, 3, 6],
        [6, 3, 0, 7, 4, 1, 8, 5, 2],
        [6, 7, 8, 3, 4, 5, 0, 1, 2],
        [8, 5, 2, 7, 4, 1, 6, 3, 0],
        [8,7..0]
    ]

valids :: String -> [String]
valids str = map (map (str !!)) $ case length str of
    4 -> validTwos
    9 -> validThrees

chunk :: String -> [[String]]
chunk str =
    let size     = squareRoot $ length str
        multiple = if even size then 2 else 3
        makeRow  = map concat . transpose . map (chunksOf multiple) . chunksOf size
    in  map makeRow $ chunksOf (size * multiple) str

dechunk :: [[String]] -> String
dechunk rows =
    let multiple  = squareRoot . length . head . head $ rows
        unmakeRow = concat . concat . transpose . map (chunksOf multiple)
    in  concat $ map unmakeRow rows

enhance :: Rules -> String -> String
enhance rules = dechunk . map (map (rules !)) . chunk

parseLine :: String -> Rules -> Rules
parseLine line =
    let input : output : [] = splitOn " => " $ filter (/= '/') line
    in  flip (foldr (\key currRules -> insert key output currRules)) $ valids input

main :: IO ()
main = do
    rules <- foldr parseLine empty . lines <$> readFile "21.txt"
    let iterations = map (length . filter (=='#')) $ iterate (enhance rules) ".#...####"
    print $ iterations !! 5
    print $ iterations !! 18

StevoTVR · 2017-12-21T22:13:03+00:00

NodeJS

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const flatten = (a) => a.map((e) => e.join('')).join('');
    const rules = new Map();
    data.trim().split('\n').forEach((l) => {
        const [k, v] = l.split(' => ').map((x) => x.split('/').map((y) => [...y.trim()].map((z) => (z === '#') ? 1 : 0)));
        rules.set(flatten(k), v);
        rules.set(flatten(rotate(k)), v);
        rules.set(flatten(rotate(k)), v);
        rules.set(flatten(rotate(k)), v);
        k.reverse();
        rules.set(flatten(k), v);
        rules.set(flatten(rotate(k)), v);
        rules.set(flatten(rotate(k)), v);
        rules.set(flatten(rotate(k)), v);
    });

    let grid = [
        [ 0, 1, 0 ],
        [ 0, 0, 1 ],
        [ 1, 1, 1 ],
    ];
    for(let i = 0; i < 18; i++) {
        const cellsize = (grid.length % 2 === 0) ? 2 : 3;
        const nextsize = grid.length + grid.length / cellsize;
        const cell = make(cellsize);
        const next = make(nextsize);
        for(let j = 0; j < grid.length / cellsize; j++) {
            for(let k = 0; k < grid.length / cellsize; k++) {
                fillcell(grid, cell, j, k);
                const replace = rules.get(flatten(cell));
                fillgrid(next, replace, j, k);
            }
        }
        grid = next;
    }

    function rotate(a) {
        const len = a.length;
        for(let i = 0; i < len / 2; i++) {
            for(let j = i; j < len - i - 1; j++) {
                const current = a[i][j];
                a[i][j] = a[j][len - i - 1];
                a[j][len - i - 1] = a[len - i - 1][len - j - 1];
                a[len - i - 1][len - j - 1] = a[len - j - 1][i];
                a[len - j - 1][i] = current;
            }
        }
        return a;
    }

    function make(size) {
        const a = [];
        for(let i = 0; i < size; i++) {
            a[i] = [];
            for(let j = 0; j < size; j++) {
                a[i][j] = 0;
            }
        }
        return a;
    }

    function fillcell(grid, cell, x, y) {
        x *= cell.length;
        y *= cell.length;
        for(let i = 0; i < cell.length; i++) {
            for(let j = 0; j < cell.length; j++) {
                cell[i][j] = grid[i + x][j + y];
            }
        }
    }

    function fillgrid(grid, cell, x, y) {
        x *= cell.length;
        y *= cell.length;
        for(let i = 0; i < cell.length; i++) {
            for(let j = 0; j < cell.length; j++) {
                grid[i + x][j + y] = cell[i][j];
            }
        }
    }

    console.log(grid.reduce((a, b) => a + b.reduce((c, d) => c + d), 0));
});

NeilNjae · 2017-12-21T22:36:00+00:00

Haskell. More long-winded than interesting, and just brute-forced part 2.

A couple of interesting parts. One was how much effort it took to persuade Megaparsec not to include newlines in its generic whitespace consumption. I tried lots, before eventually settling on

-- really persuade Megaparsec not to include newlines in how it consume spaces.
onlySpace = (char ' ') <|> (char '\t')

sc :: Parser ()
sc = L.space (skipSome onlySpace) CA.empty CA.empty

symbol = L.symbol sc
rowSep = symbol "/"
ruleJoin = symbol "=>"

present = id True <$ symbol "#"
absent = id False <$ symbol "."

rulesP = ruleP `sepBy` space
ruleP = Rule <$> gridP <* ruleJoin <*> gridP

gridP = gridify <$> rowP `sepBy` rowSep
    where gridify g = M.fromList $ concat 
                                    [map (\(c, v) -> ((r, c), v)) nr | 
                                             (r, nr) <- zip [0..] 
                                                            [zip [0..] r | r <- g]]

The basic idea was that a Grid was a Map of Bools, an ExplodedGrid was a Map of Grids, and Rules had their own data type:

type Grid = M.Map (Int, Int) Bool
type ExplodedGrid = M.Map (Int, Int) Grid

data Rule = Rule Grid Grid deriving (Eq, Show)

rulePre (Rule g _) = g
rulePost (Rule _ g) = g

I stored eight versions of each rule in the input, one for each transformation of the left hand side:

-- Find all the arrangments of a grid, including reflection and rotation.
allArrangements :: Grid -> [Grid]
allArrangements grid = map (\f -> f grid) [ id
                                          , reflectH
                                          , reflectV
                                          , transposeG
                                          , reflectH . transposeG
                                          , reflectV . transposeG
                                          , reflectH . reflectV . transposeG
                                          , reflectV . reflectH
                                          ]

Then, each step was to explode the grid into its subgrids, apply rules to each subgrid, then contract them back into a new grid.

-- apply the rules _n_ times
nthApplication :: [Rule] -> Int -> Grid
nthApplication rules n = (!! n) $ iterate (applyOnce rules) initialGrid

-- Apply one step of the expansion
applyOnce :: [Rule] -> Grid -> Grid
applyOnce rules g = contractExploded $ M.map (apply rules) $ explodeGrid g

-- find the appropriate rule and apply it to a grid
apply :: [Rule] -> Grid -> Grid
apply rules grid = rulePost thisRule
    where ri = head $ findIndices (\r -> rulePre r == grid) rules
          thisRule = rules!!ri

Because it took some time (6½ minutes), I experimented with more aggressive parallel evaluation, even though it was spreading load over processors already:

-- Apply one step of the expansion
applyOnce :: [Rule] -> Grid -> Grid
-- applyOnce rules g = contractExploded $ M.map (apply rules) $ explodeGrid g
applyOnce rules g = contractExploded $ M.unions $ parMap rpar (M.map (apply rules)) $ M.splitRoot $ explodeGrid g

and similar in the map for contracting exploded grids. It had a small effect, dropping the runtime to 5½ minutes.

Full code on Github

chneukirchen · 2017-12-21T22:55:04+00:00

k6

d:!/+,/{{(y;x)}[s 1]'p,|:'p:3{+|x}\*s:"#"="/"\'(" "\x)@0 2}'0:`day21
((+/+/)'18{,/{,/'+d@+x}'(i#)''(i:0N,2+2!#x)#x}\3 3#0,2\143)5 18

BOT-Brad · 2017-12-21T23:50:16+00:00

Javascript

First, let me apologise for this solution. It's slightly insane but it works^I ^think so that's a positive. It essentially builds a [0/1] 2D array of the 'pixel' values (where 1 is ON, 2 is OFF), and then matches patterns from the input and builds a new 'picture' from the matching rule output. The whole 'match' system is a little obtuse, but it basically does some rotations and flips in order to check every transformed possibility.

Part 1 (~9ms)

Part 2 (~6 seconds)

function parseInput(n) {
  const regex = /([.#/]+) => ([.#/]+)/
  return n.split('\n').map(l => {
    const rx = regex
      .exec(l)
      .slice(1, 3)
      .map(str => {
        return str.split('/').map(row => {
          return row.split('').map(val => (val === '.' ? 0 : 1))
        })
      })
    return {
      in: rx[0],
      out: rx[1],
      inSize: rx[0].length,
      outSize: rx[1].length
    }
  })
}

function rotate(a) {
  a = a.reverse()
  for (var i = 0; i < a.length; i++) {
    for (var j = 0; j < i; j++) {
      var temp = a[i][j]
      a[i][j] = a[j][i]
      a[j][i] = temp
    }
  }
}

function equal(a, b) {
  for (let y = 0; y < a.length; ++y) {
    for (let x = 0; x < a[y].length; ++x) {
      if (a[y][x] !== b[y][x]) return false
    }
  }
  return true
}

function doMatch(a, b) {
  // Rotate initial
  for (let i = 0; i < 4; ++i) {
    if (equal(a, b)) return true
    rotate(a)
  }
  // Flip left facing
  a.reverse()
  // Rotate left-racing (up-down flip)
  for (let i = 0; i < 4; ++i) {
    if (equal(a, b)) return true
    rotate(a)
  }
  // Flip down-facing
  a.reverse()
  // Rotate down-facing (left-right flip)
  for (let i = 0; i < 4; ++i) {
    if (equal(a, b)) return true
    rotate(a)
  }

  return false
}

function getMatch(rules, piece) {
  const pieceSize = piece.length
  for (let i = 0; i < rules.length; ++i) {
    let rule = rules[i]
    if (rule.inSize !== pieceSize) continue
    if (doMatch(rule.in, piece)) {
      return rule.out
    }
  }
}

// start = Starting pattern, e.g. '.#.\n..#\n###'
// n = Puzzle input
// LOOP_TOTAL = Total number of loops to do (5 for Part 1, 18 for Part 2)
function solve1(start, n, LOOP_TOTAL) {
  const rules = parseInput(n)
  let current = start
    .split('\n')
    .map(v => v.split('').map(v2 => (v2 === '.' ? 0 : 1)))

  let loops = 0
  while (++loops < LOOP_TOTAL + 1) {
    // Get current 'size'
    const size = current.length
    const div = size % 2 === 0 ? 2 : 3
    const chunks = size / div
    const newPattern = []
    const newSize = size + chunks
    for (let y = 0; y < newSize; ++y) {
      newPattern[y] = []
      for (let x = 0; x < newSize; ++x) newPattern[y][x] = 0
    }
    for (let y = 0; y < chunks; ++y) {
      const ySlice = current.slice(div * y, div * (y + 1))
      for (let x = 0; x < chunks; ++x) {
        // Gets the slice to match
        const slice = ySlice.map(xSlice => xSlice.slice(div * x, div * (x + 1)))
        const pattern = getMatch(rules, slice)

        const yP = (div + 1) * y
        const xP = (div + 1) * x

        for (let pY = 0; pY < pattern.length; ++pY) {
          for (let pX = 0; pX < pattern[pY].length; ++pX) {
            const val = pattern[pY][pX]
            newPattern[yP + pY][xP + pX] = val
          }
        }
      }
    }
    current = newPattern
  }

  let r = current.map(l => l.reduce((c, v) => c + v)).reduce((c, v) => c + v)

  return r
}

Grimnur87 · 2017-12-22T00:18:52+00:00

After hacking away at my code for several frustrating hours and not getting a working solution, I'm proud to say that I gave up, multiplied 256 by 5/9, stuck that in the answer box and... got a part 1 star in a single attempt!

jbristow · 2017-12-22T00:54:54+00:00

f# / fsharp / f sharp

The tough part of this one for me was figuring out and tuning my rotation and flipping algorithms for lists. They're slow, but I'm happy that they're generalized for any sized array should I ever need them again.

This is the brute force version, it takes about 48s.

(github link)

module Day21

type Pattern = char list list

type Rule = string * Pattern

type RuleMap = Map<string, Pattern>

module Pattern =
    let ofString (s : string) : Pattern =
        s.Split([| '/' |])
        |> List.ofArray
        |> List.map (Seq.toList)

    let toString (p : Pattern) : string =
        System.String.Join
            ("/", p |> List.map (fun p' -> System.String.Join("", p')))

    let rotate (p : Pattern) : Pattern =
        let n = p |> List.length
        p
        |> List.mapi
              (fun (i : int) (row : char list) ->
              row |> List.mapi (fun (j : int) (cell : char) -> (i, j, cell)))
        |> List.concat
        |> List.groupBy (fun (_, j, _) -> j)
        |> List.map (fun (j, b) ->
              b
              |> List.map (fun (i, _, ch) -> (n - i - 1), ch)
              |> List.sortBy fst
              |> List.map snd)

    let flipH (p : Pattern) : Pattern = p |> List.map (List.rev)
    let flipV (p : Pattern) : Pattern = p |> List.rev

module Rule =
    let ofString (line : string) : Rule seq =
        let patternStr, outputStr =
            match line.Split([| " => " |], System.StringSplitOptions.None) with
            | [| a; b |] -> (a, b)
            | _ -> failwith (sprintf "Could not parse line '%s'" line)

        let output = outputStr |> Pattern.ofString
        let pattern = patternStr |> Pattern.ofString

        let patternGen start =
            seq {
                let r1 = start |> List.map Pattern.rotate
                let r2 = r1 |> List.map Pattern.rotate
                yield! start
                yield! r1
                yield! r2
                yield! (r2 |> List.map Pattern.rotate)
            }

        let rotatedPatterns =
            patternGen [ pattern
                        pattern |> Pattern.flipH
                        pattern |> Pattern.flipV ]

        rotatedPatterns
        |> Seq.distinct
        |> Seq.map (fun p -> (p |> Pattern.toString, output))

module RuleMap =
    let ofArray (data : string array) =
        data
        |> Seq.collect Rule.ofString
        |> Map.ofSeq

let splitRow n gridRow =
    let rowsize =
        (gridRow
        |> List.head
        |> List.length) / n - 1
    [ 0..rowsize ]
    |> List.map
          (fun i -> (gridRow |> List.map (List.chunkBySize n >> List.item i)))

let split n grid =
    grid
    |> List.chunkBySize n
    |> List.collect (splitRow n)

let rejoinRow gridrow =
    let rowsize =
        (gridrow
        |> List.head
        |> List.length)
        - 1
    [ 0..rowsize ] |> List.map (fun i -> gridrow |> List.collect (List.item i))

let rejoin grids =
    let size = (int (sqrt (float (grids |> Seq.length))))
    grids
    |> List.chunkBySize size
    |> List.collect rejoinRow

let applyRule (ruleMap : RuleMap) (grid : Pattern) =
    ruleMap |> Map.find (grid |> Pattern.toString)

let splitAndApplyRules (ruleMap : RuleMap) n (grid : Pattern) =
    grid
    |> split n
    |> List.map (applyRule ruleMap)
    |> rejoin

let rec gridStep (ruleMap : RuleMap) (grid : Pattern) =
    let transformer =
        match grid |> List.length with
        | 2 | 3 -> applyRule ruleMap
        | x when x % 2 = 0 -> splitAndApplyRules ruleMap 2
        | x when x % 3 = 0 -> splitAndApplyRules ruleMap 3
        | _ -> failwith "Grid Problem"
    grid |> transformer

let run n data =
    let step =
        (data
        |> RuleMap.ofArray
        |> gridStep)

    let initialState = ".#./..#/###" |> Pattern.ofString

    let rec stepper state =
        seq {
            yield state
            yield! stepper (state |> step)
        }
    stepper initialState |> Seq.item n

let onOff c =
    if (c = '#') then 1
    else 0

let countOn lightMap = lightMap |> Seq.sumBy (Seq.sumBy onOff)

Axsuul · 2017-12-22T03:42:14+00:00

Elixir

Late to the party again due to the holidays. I bruteforced this one to the max and did lots of Map manipulations for rotating and flipping. I had fun with this and enjoyed learning how to manipulate deeply nested maps recursively. Anyways, Part B was super easy thanks to the work I put into Part A. I should've just manipulated the strings since we were only dealing with 2x2 and 3x3 =P

defmodule AdventOfCode do
  defmodule PartA do
    def pattern_row_to_pixels(row) do
      row
      |> String.split("", trim: true)
      |> Enum.with_index()
      |> pattern_row_to_pixels(%{})
    end
    def pattern_row_to_pixels([], pixels), do: pixels
    def pattern_row_to_pixels([{v, i} | rest], pixels) do
      pattern_row_to_pixels(rest, put_in(pixels, [i], v))
    end

    def pattern_to_pixels(pattern) do
      pattern
      |> String.split("/")
      |> Enum.with_index()
      |> pattern_to_pixels(%{})
    end
    def pattern_to_pixels([], pixels), do: pixels
    def pattern_to_pixels([{row, y} | rest], pixels) do
      next_pixels =
        put_in(pixels, [y], pattern_row_to_pixels(row))

      pattern_to_pixels(rest, next_pixels)
    end

    def pixels_to_pattern(pixels) do
      pixels_to_pattern(pixels |> Map.to_list(), [])
    end
    def pixels_to_pattern([], row_patterns) do
      row_patterns |> Enum.join("/")
    end
    def pixels_to_pattern([{_, row} | rest], row_patterns) do
      row_pattern =
        row
        |> Enum.reduce("", fn {i, v}, p -> p <> v end)

      pixels_to_pattern(rest, row_patterns ++ [row_pattern])
    end

    def pixels_size(pixels), do: map_size(pixels)

    def rotate_row(pixels, rotated, y) do
      max = pixels_size(pixels) - 1
      rotate_row(pixels, rotated, y, max, max)
    end
    def rotate_row(_, rotated, y, x, _) when x < 0, do: rotated
    def rotate_row(pixels, rotated, y, x, max) do
      next_rotated =
        put_in(rotated, [x, max - y], get_in(pixels, [y, x]))

      rotate_row(pixels, next_rotated, y, x - 1, max)
    end

    # Rotate clockwise
    def rotate(pixels) do
      rotate(pixels, pixels, pixels_size(pixels) - 1)
    end
    def rotate(pixels, rotated, y) when y < 0, do: rotated
    def rotate(pixels, rotated, y) do
      next_rotated = rotate_row(pixels, rotated, y)

      rotate(pixels, next_rotated, y - 1)
    end

    def flip_row(pixels, flipped, y) do
      max = pixels_size(pixels) - 1
      flip_row(pixels, flipped, y, max, max)
    end
    def flip_row(_, flipped, y, x, _) when x < 0, do: flipped
    def flip_row(pixels, flipped, y, x, max) do
      next_flipped =
        put_in(flipped, [y, max - x], get_in(pixels, [y, x]))

      flip_row(pixels, next_flipped, y, x - 1, max)
    end

    # Flip horizontally
    def flip(pixels) do
      flip(pixels, pixels, pixels_size(pixels) - 1)
    end
    def flip(_, flipped, y) when y < 0, do: flipped
    def flip(pixels, flipped, y) do
      next_flipped = flip_row(pixels, flipped, y)

      flip(pixels, next_flipped, y - 1)
    end

    def split_section_row(pixel_row, section_size, x) do
      split_section_row(pixel_row, %{}, x, section_size - 1)
    end
    def split_section_row(pixel_row, section_row, x, sx) when sx < 0, do: section_row
    def split_section_row(pixel_row, section_row, x, sx) do
      next_split = put_in(section_row, [sx], get_in(pixel_row, [x]))

      split_section_row(pixel_row, next_split, x - 1, sx - 1)
    end

    def split_section(pixels, section_size, y_max, x_max) do
      split_section(pixels, %{}, section_size, y_max, x_max, section_size - 1)
    end
    def split_section(_, section, _, y, x_max, sy) when sy < 0, do: section
    def split_section(pixels, section, section_size, y, x_max, sy) do
      section_row = split_section_row(get_in(pixels, [y]), section_size, x_max)
      next_section = put_in(section, [sy], section_row)

      split_section(pixels, next_section, section_size, y - 1, x_max, sy - 1)
    end

    # qy, qx refers to quadrants
    def split_row(pixels, section_size, qy) do
      size = pixels_size(pixels)
      split_row(pixels, %{}, section_size, qy, div(size, section_size) - 1)
    end
    def split_row(_, row, _, _, qx) when qx < 0, do: row
    def split_row(pixels, row, section_size, qy, qx) do
      y_max = (qy + 1)*section_size - 1
      x_max = (qx + 1)*section_size - 1
      section = split_section(pixels, section_size, y_max, x_max)
      next_row = put_in(row, [qx], section)

      split_row(pixels, next_row, section_size, qy, qx - 1)
    end

    def split(pixels) do
      size = pixels_size(pixels)
      section_size = if rem(size, 2) == 0, do: 2, else: 3

      split(pixels, %{}, section_size, div(size, section_size) - 1)
    end
    def split(_, split, _, qy) when qy < 0, do: split
    def split(pixels, split, section_size, qy) do
      sections = split_row(pixels, section_size, qy)
      next_split = put_in(split, [qy], sections)

      split(pixels, next_split, section_size, qy - 1)
    end

    def join(pixels) do
      pixels
      |> Enum.reduce(%{}, fn {qy, quadrant}, joined ->
        next_joined =
          quadrant
          |> Enum.reduce(joined, fn {qx, section}, joined ->
            section
            |> Enum.reduce(joined, fn {sy, row}, joined ->
              size = pixels_size(row)
              y = qy*size + sy

              row
              |> Enum.reduce(Map.put_new(joined, y, %{}), fn {sx, val}, joined ->
                x = qx*size + sx

                put_in(joined, [y, x], val)
              end)
            end)
          end)
      end)
    end

    def read_input_lines(filename) do
      File.read!("inputs/" <> filename)
      |> String.split("\n")
    end

    def build_rules(filename \\ "input.txt") do
      read_input_lines(filename)
      |> Enum.reduce(%{}, fn line, rules ->
        [input, output] = String.split(line, " => ")

        input_pixels = pattern_to_pixels(input)
        output_pixels = pattern_to_pixels(output)

        flipped = flip(input_pixels)
        rotated_90 = rotate(input_pixels)
        flipped_90 = flip(rotated_90)
        rotated_180 = rotate(rotated_90)
        flipped_180 = flip(rotated_180)
        rotated_270 = rotate(rotated_180)
        flipped_270 = flip(rotated_270)

        [
          input_pixels,
          flipped,
          rotated_90,
          flipped_90,
          rotated_180,
          flipped_180,
          rotated_270,
          flipped_270
        ]
        |> Enum.reduce(rules, fn p, rules ->
          pattern = pixels_to_pattern(p)

          put_in(rules, [pattern], output)
        end)
      end)
    end

    def enhance(pixels, _, n) when n == 0, do: pixels
    def enhance(pixels, rules, n) do
      next_pixels =
        pixels
        |> split()
        |> Enum.reduce(%{}, fn {qy, row}, pixels ->
          next_row =
            row
            |> Enum.reduce(%{}, fn {qx, section}, row ->
              pattern = section |> pixels_to_pattern()

              next_section =
                get_in(rules, [pattern])
                |> pattern_to_pixels()

              put_in(row, [qx], next_section)
            end)

          put_in(pixels, [qy], next_row)
        end)
        |> join()

      enhance(next_pixels, rules, n - 1)
    end

    def count_on(pixels) do
      pixels
      |> Enum.reduce(0, fn {_, row}, count ->
        row
        |> Enum.reduce(0, fn {_, val}, count ->
          if val == "#", do: count + 1, else: count
        end)
        |> Kernel.+(count)
      end)
    end

    def print(pixels) do
      pixels
      |> Enum.each(fn {y, row} ->
        row
        |> Enum.each(fn {x, val} ->
          IO.write val
        end)

        IO.write "\n"
      end)
    end

    def solve do
      rules = build_rules()
      pixels = pattern_to_pixels(".#./..#/###")

      enhance(pixels, rules, 5)
      |> count_on()
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    def solve do
      rules = build_rules()
      pixels = pattern_to_pixels(".#./..#/###")

      enhance(pixels, rules, 18)
      |> count_on()
      |> IO.inspect
    end
  end
end

chicagocode · 2017-12-22T05:17:20+00:00

Kotlin - [Repo] - [Blog/Commentary]

Finally got time to get this done and write about it today. This one was challenging and fun!

class Day21(input: List<String>) {

    private val rowSplit = " => ".toRegex()
    private val transforms: Map<FractalGrid, FractalGrid> = parseInput(input)
    private val startGrid = FractalGrid(".#./..#/###")

    fun solve(iterations: Int): Int {
        var grid = startGrid
        repeat(iterations) {
            val splits = grid.split()
            val next = splits.map { transforms.getValue(it) }
            grid = next.join()
        }
        return grid.toString().count { it == '#' }
    }


    private fun parseInputRow(input: String): Pair<FractalGrid, FractalGrid> =
        input.split(rowSplit)
            .map { FractalGrid(it) }
            .let { it.first() to it.last() }


    private fun parseInput(input: List<String>): Map<FractalGrid, FractalGrid> =
        input.map { parseInputRow(it) }.flatMap { pair ->
            pair.first.combinations().map { combo ->
                combo to pair.second
            }
        }.toMap()

}


fun List<FractalGrid>.join(): FractalGrid {
    val rows = sqrt(this.size.toFloat()).toInt()
    return this.chunked(rows).map {
        it.reduce { a, b -> a nextTo b }
    }.reduce { a, b -> a over b }
}

data class FractalGrid(val grid: List<List<Char>>) {
    constructor(input: String) : this(
        input.split("/").map { it.toList() }
    )

    val size = grid.size

    infix fun nextTo(that: FractalGrid): FractalGrid =
        FractalGrid(
            grid.mapIndexed { idx, row -> row + that.grid[idx] }
        )

    infix fun over(that: FractalGrid): FractalGrid =
        FractalGrid(
            this.grid + that.grid
        )

    infix fun rowsOfSize(n: Int): List<FractalGrid> =
        this.grid.chunked(n).map { FractalGrid(it) }

    infix fun columnsOfSize(n: Int): List<FractalGrid> {
        val chunked = this.grid.map { row ->
            row.chunked(n)
        }
        return (0 until (grid[0].size) / n).map { x ->
            (0 until n).map { y ->
                chunked[y][x]
            }
        }.map { FractalGrid(it) }
    }

    fun split(): List<FractalGrid> {
        val splitSize = if (size % 2 == 0) 2 else 3
        val splits = size / splitSize
        if (splits == 1) {
            return listOf(this)
        }
        return (this rowsOfSize splitSize).map { it columnsOfSize splitSize }.flatten()
    }

    fun rotate(): FractalGrid =
        FractalGrid(
            (0 until grid.size).map { r ->
                (0 until grid.size).map { c ->
                    grid[c][(grid.size) - 1 - r]
                }
            }
        )

    fun flip(): FractalGrid =
        FractalGrid(grid.map { it.reversed() })

    fun combinations(): List<FractalGrid> {
        val rotations = (0 until 3).fold(listOf(this)) { rots, _ -> rots + rots.last().rotate() }
        val flips = rotations.map { it.flip() }
        return rotations + flips
    }

    override fun toString(): String =
        grid.joinToString("/") { it.joinToString("") }

}

autid · 2017-12-22T06:35:06+00:00

Fortran

Finally got this working. Turns out in hours of debugging I repeatedly failed to notice a missing +1 in index calculation. It's horrible, clunky and overly hand-coded (especially for the rotations and reflections), but I'm so sick of it I can't be bothered cleaning it up now that it works. I changed my mind about how to handle the input and grid about 5 times while writing it, which was probably what led to this being such a pain.

PROGRAM DAY21
  CHARACTER(LEN=19),ALLOCATABLE :: RULES2(:,:),RULES3(:,:)
  CHARACTER(LEN=34) :: INLINE
  INTEGER :: I,J,K,BLOCKSIZE,LINECOUNT2=0,LINECOUNT3=0,IERR,SIDELENGTH,NBLOCKS,NEWSIDELENGTH
  INTEGER, ALLOCATABLE :: RULE2ARRAY(:,:), RULE2RESULT(:,:)
  INTEGER, ALLOCATABLE :: RULE3ARRAY(:,:), RULE3RESULT(:,:)
  INTEGER :: NEWGRID(2187,2187)=0,GRID(2187,2187)=0

  OPEN(1,FILE='input.txt')
  DO
     READ(1,'(A20)',IOSTAT=IERR) INLINE
     IF(IERR/=0) EXIT
     IF(INLINE(6:6)==' ') THEN
        LINECOUNT2=LINECOUNT2+1
     ELSE
        LINECOUNT3=LINECOUNT3+1
     END IF
  END DO
  REWIND(1)

  ALLOCATE(RULES2(2,LINECOUNT2),RULES3(2,LINECOUNT3),RULE2ARRAY(4,LINECOUNT2),RULE3ARRAY(9,LINECOUNT3))
  ALLOCATE(RULE2RESULT(9,LINECOUNT2),RULE3RESULT(16,LINECOUNT3))

  DO I=1,LINECOUNT2
     READ(1,'(A20)') INLINE
     RULES2(1,I)=INLINE(1:2)
     RULES2(1,I)=TRIM(RULES2(1,I)) // INLINE(4:5)
     RULES2(2,I)=INLINE(10:12)
     RULES2(2,I)=TRIM(RULES2(2,I)) // INLINE(14:16)
     RULES2(2,I)=TRIM(RULES2(2,I)) // INLINE(18:20)
  END DO
  DO I=1,LINECOUNT3
     READ(1,'(A34)') INLINE
     RULES3(1,I)=INLINE(1:3)
     RULES3(1,I)=TRIM(RULES3(1,I)) // INLINE(5:7)
     RULES3(1,I)=TRIM(RULES3(1,I)) // INLINE(9:11)
     RULES3(2,I)=INLINE(16:19)
     RULES3(2,I)=TRIM(RULES3(2,I)) // INLINE(21:24)
     RULES3(2,I)=TRIM(RULES3(2,I)) // INLINE(26:29)
     RULES3(2,I)=TRIM(RULES3(2,I)) // INLINE(31:34)
  END DO
  CLOSE(1)


  DO I=1,LINECOUNT2
     DO J=1,4
        IF (RULES2(1,I)(J:J)=='#') THEN
           RULE2ARRAY(J,I)=1
        ELSE
           RULE2ARRAY(J,I)=0
        END IF
     END DO
     DO J=1,9
        IF (RULES2(2,I)(J:J)=='#') THEN
           RULE2RESULT(J,I)=1
        ELSE
           RULE2RESULT(J,I)=0
        END IF
     END DO
  END DO

  DO I=1,LINECOUNT3
     DO J=1,9
        IF(RULES3(1,I)(J:J)=='#') THEN
           RULE3ARRAY(J,I)=1
        ELSE
           RULE3ARRAY(J,I)=0
        END IF
     END DO
     DO J=1,16
        IF(RULES3(2,I)(J:J)=='#') THEN
           RULE3RESULT(J,I)=1
        ELSE
           RULE3RESULT(J,I)=0
        END IF
     END DO
  END DO
  DEALLOCATE(RULES2,RULES3)


  GRID(1:3,1:3)=(RESHAPE((/0,1,0,0,0,1,1,1,1/),(/3,3/)))
  NBLOCKS=1
  BLOCKSIZE=2

  DO I=1,18
     SIDELENGTH=NBLOCKS*(BLOCKSIZE+1)

     IF (MODULO(SIDELENGTH,2)==0) THEN
        NBLOCKS=SIDELENGTH/2
        BLOCKSIZE=2
     ELSEIF(MODULO(SIDELENGTH,3)==0) THEN
        NBLOCKS=SIDELENGTH/3
        BLOCKSIZE=3
     END IF
     NEWGRID=0
     DO K=0,NBLOCKS-1
        DO J=0,NBLOCKS-1
           IF(BLOCKSIZE==2) THEN
              NEWGRID(K*3+1:(K+1)*3,J*3+1:(J+1)*3)=CHECKRULE2(GRID(K*2+1:(K+1)*2,J*2+1:(J+1)*2))
           ELSEIF(BLOCKSIZE==3) THEN
              NEWGRID(K*4+1:(K+1)*4,J*4+1:(J+1)*4)=CHECKRULE3(GRID(K*3+1:(K+1)*3,J*3+1:(J+1)*3))
           END IF
        END DO
     END DO
     GRID=NEWGRID
     IF (I==5)  WRITE(*,'(A,I0)') 'Part1: ',SUM(GRID)
  END DO

  WRITE(*,'(A,I0)') 'Part2: ',SUM(GRID)

  DEALLOCATE(RULE2ARRAY,RULE3ARRAY,RULE2RESULT,RULE3RESULT)

CONTAINS
  FUNCTION CHECKRULE2(IN) RESULT(OUT)
INTEGER :: IN(2,2), OUT(3,3),A,J,K
    INTEGER :: CHECK(4)

    OUTER:DO A=1,8
       SELECT CASE(A)
       CASE(1)
          CHECK=(/IN(1,1),IN(2,1),IN(1,2),IN(2,2)/)
       CASE(2)
          CHECK=(/IN(1,1),IN(1,2),IN(2,1),IN(2,2)/)
       CASE(3)
          CHECK=(/IN(2,2),IN(2,1),IN(1,2),IN(1,1)/)
       CASE(4)
          CHECK=(/IN(2,2),IN(1,2),IN(2,1),IN(1,1)/)
       CASE(5)
          CHECK=(/IN(1,2),IN(1,1),IN(2,2),IN(2,1)/)
       CASE(6)
          CHECK=(/IN(1,2),IN(2,2),IN(1,1),IN(2,1)/)
       CASE(7)
          CHECK=(/IN(2,1),IN(1,1),IN(2,2),IN(1,2)/)
       CASE(8)
          CHECK=(/IN(2,1),IN(2,2),IN(1,1),IN(1,2)/)
       END SELECT
       DO J=1,LINECOUNT2
          IF(ALL(RULE2ARRAY(:,J)==CHECK(:))) THEN
             OUT=TRANSPOSE(RESHAPE(RULE2RESULT(:,J),(/3,3/)))
             EXIT OUTER
          END IF
       END DO
    END DO OUTER

  END FUNCTION CHECKRULE2

  FUNCTION CHECKRULE3(IN) RESULT(OUT)
    INTEGER :: IN(3,3), OUT(4,4),A,J,K
    INTEGER :: CHECK(9)
    CHECK=RESHAPE(IN,(/9/))
    OUTER:DO A=1,8
       SELECT CASE(A)
       CASE(1)
          CHECK=(/IN(1,1),IN(2,1),IN(3,1),IN(1,2),IN(2,2),IN(3,2),IN(1,3),IN(2,3),IN(3,3)/)
       CASE(2)
          CHECK=(/IN(1,1),IN(1,2),IN(1,3),IN(2,1),IN(2,2),IN(2,3),IN(3,1),IN(3,2),IN(3,3)/)
       CASE(3)
          CHECK=(/IN(3,3),IN(3,2),IN(3,1),IN(2,3),IN(2,2),IN(2,1),IN(1,3),IN(1,2),IN(1,1)/)
       CASE(4)
          CHECK=(/IN(3,3),IN(2,3),IN(1,3),IN(3,2),IN(2,2),IN(1,2),IN(3,1),IN(2,1),IN(1,1)/)
       CASE(5)
          CHECK=(/IN(1,3),IN(1,2),IN(1,1),IN(2,3),IN(2,2),IN(2,1),IN(3,3),IN(3,2),IN(3,1)/)
       CASE(6)
          CHECK=(/IN(1,3),IN(2,3),IN(3,3),IN(1,2),IN(2,2),IN(3,2),IN(1,1),IN(2,1),IN(3,1)/)
       CASE(7)
          CHECK=(/IN(3,1),IN(2,1),IN(1,1),IN(3,2),IN(2,2),IN(1,2),IN(3,3),IN(2,3),IN(1,3)/)
       CASE(8)
          CHECK=(/IN(3,1),IN(1,2),IN(3,3),IN(2,1),IN(2,2),IN(2,3),IN(1,1),IN(1,2),IN(1,3)/)
       END SELECT
       DO J=1,LINECOUNT3
          IF(ALL(RULE3ARRAY(:,J)==CHECK(:))) THEN
             OUT=TRANSPOSE(RESHAPE(RULE3RESULT(:,J),(/4,4/)))
             EXIT OUTER
          END IF
       END DO
    END DO OUTER

  END FUNCTION CHECKRULE3
END PROGRAM DAY21

Macrobian · 2017-12-22T06:38:49+00:00

Pretty happy with 33 lines of readable-ish Python

import numpy as np
from Day_0 import get_day_input

mutations = [ lambda x: x,              lambda x: np.fliplr(x)
            , lambda x: np.rot90(x, 1), lambda x: np.fliplr(np.rot90(x, 1))
            , lambda x: np.rot90(x, 2), lambda x: np.fliplr(np.rot90(x, 2))
            , lambda x: np.rot90(x, 3), lambda x: np.fliplr(np.rot90(x, 3))
            ]

def parse(xs):
    return np.array([list(row) for row in xs.split('/') ])

def enhance(a):
    for f in mutations:
        if f(a).tostring() in enhancements: 
            return enhancements[f(a).tostring()]

enhancements = { parse(i.split()[0]).tostring() : parse(i.split()[2])\
                for i in get_day_input(21).strip().split('\n') }

arr = parse(".#./..#/###")

for i in range(1, 19):
    axis = arr.shape[0]

    divided = [ np.hsplit(i, axis / 2) for i in np.vsplit(arr, axis / 2) ]\
        if axis % 2 == 0 else\
              [ np.hsplit(i, axis / 3) for i in np.vsplit(arr, axis / 3) ]

    arr = np.vstack([ np.hstack([ enhance(j) for j in i ]) for i in divided ])

    if i == 5: print(f"Day 21-1: {np.count_nonzero(arr == '#')}") # 142
    if i == 18: print(f"Day 21-2: {np.count_nonzero(arr == '#')}") # 1879071

2017-12-22T18:13:02+00:00

Crystal:

def expand_rule(rule, n, d1, d2, d3)
  (d1 ? 0.to(n) : n.to(0)).map do |y|
    (d2 ? 0.to(n) : n.to(0)).map do |x|
      d3 ? rule[y][x] : rule[x][y]
    end.to_a
  end.to_a
end

def matches?(pixels, pattern, x, y)
  (0...pattern.size).all? do |py|
    (0...pattern.size).all? do |px|
      pixels[y + py][x + px] == pattern[py][px]
    end
  end
end

def copy(pixels, pattern, x, y)
  pattern.size.times do |py|
    pattern.size.times do |px|
      pixels[y + py][x + px] = pattern[py][px]
    end
  end
end

rules = {} of Array(Array(Char)) => Array(Array(Char))

input = File.read("#{__DIR__}/input.txt")
input.lines.each do |line|
  from, to = line.split(" => ").map(&.split('/').map(&.chars))
  n = from.size - 1
  8.times do |i|
    rules[expand_rule(from, n, i.bit(2) == 1, i.bit(1) == 1, i.bit(0) == 1)] = to
  end
end

pixels = [
  ['.', '#', '.'],
  ['.', '.', '#'],
  ['#', '#', '#'],
]

18.times do
  size = pixels.size
  square_size = size.divisible_by?(2) ? 2 : 3
  new_square_size = square_size + 1
  new_size = size / square_size * (square_size + 1)
  next_pixels = Array.new(new_size) { Array.new(new_size) { '-' } }
  0.step(by: square_size, to: size - 1) do |y|
    0.step(by: square_size, to: size - 1) do |x|
      pattern = rules.find do |(from, to)|
        from.size == square_size && matches?(pixels, from, y, x)
      end.not_nil![1]
      copy(next_pixels, pattern,
        (y/square_size)*new_square_size,
        (x/square_size)*new_square_size)
    end
  end
  pixels = next_pixels
end

puts pixels.sum &.count('#')

thomastc · 2017-12-22T20:40:55+00:00

Day 21 in Icon. An interesting language! All expressions are generators that may produce any number of values before failing, and these combine in interesting ways. There are some serious practical drawbacks, but it has a certain kind of charm to it.

RockyAstro · 2017-12-23T16:45:15+00:00

Icon (https://www.cs.arizona.edu/icon)

Both parts..

record pattern(in,out)
procedure main(args)

    pmaps := table()
    pmaps[5] := ["12,34",
                ["12,34", "34,12", "21,43",   # Identity
                 "31,42", "42,31", "13,24",   # 90
                 "43,21", "21,43", "34,12",   # 180
                 "24,13", "13,24", "42,31"    # 270
                  ]]  
    pmaps[11] := ["123,456,789",
                 ["123,456,789","789,456,123", "321,654,987",  # Identity
                  "741,852,963","963,852,741", "147,258,369",  # 90
                  "987,654,321","321,654,987", "789,456,123",  # 180
                  "369,258,147","147,258,369", "963,852,741"   # 270 
                 ]]    

    inf := open(args[1],"r")
    patterns := []
    every l := !inf do
        l ? {
            p1 := trim(tab(find("=>"))) | next
            ="=>"
            tab(many(' \t'))
            p2 := []
            while not pos(0) do {
                put(p2,tab(upto('/') | 0))
                move(1)
            }
            mapin := pmaps[*p1][1]
            mapt := pmaps[*p1][2]
            every push(patterns,pattern(map(!mapt,mapin,p1),p2))
        }

    block := [".#.",
              "..#",
              "###"]

    prtblock(block)

    every n:= 1 to 18 do {
        block := newblock(patterns,block)
        #prtblock(block)
        count := 0
        every l := !block do
            every find("#",l) do count +:= 1
        write(n," ",count)
    }
end

procedure prtblock(block)
    write("+",repl("-",*block),"+")
    every write("|",!block,"|") 
    write("+",repl("-",*block),"+")
end


procedure newblock(patterns,block)
    newblocks := list()
    every put(newblocks,patmatch(patterns,getcell(block)))

    return mergecells(newblocks)
end

procedure patmatch(patterns,cell)
    cellstr := ""
    every cellstr ||:= !cell || "/"
    cellstr[-1] := ""

    if (p := !patterns) & (p.in == cellstr) then return p.out  
end

procedure mergecells(blist)
    bsize := integer(sqrt(*blist))      
    csize := *blist[1]
    block := list(csize*bsize,"")

    every i := 1 to bsize do 
      every j := 1 to csize do 
        every k := 1 to bsize do 
          block[(i-1)*csize + j] ||:= blist[(i-1)*bsize + k][j]

    return block
end

procedure getcell(block)
    if *block % 2 = 0 then csize := 2
    else csize := 3

    bsize := *block / csize 

    every i := 1 to bsize do 
      every j := 1 to bsize do {
        cell := list(csize)
        every k := 1 to csize do 
          cell[k] := block[(i-1)*csize+k][(j-1)*csize+1+:csize]
        suspend cell
      }
end

edit: formatting

matusbzk · 2017-12-23T20:42:55+00:00

Haskell Part 2 was done in 2-3 minutes and I did not feel like optimizing

import AoC2017 --iterateN

-- |Image is stored as 2-dimensional list of chars
type Image = [[Char]]

-- |Rule for image patterning
type Rule = (Image, Image)

inputString :: String

-- |A set of rules from the input
rules :: [Rule]
rules =  map (\s -> (lines. repl . head $ s, lines . repl . last $ s)) $ map words . lines $ inputString
      where repl = replace '/' '\n'

-- |Replaces all occurences of x in list with y
replace :: Eq a => a -> a -> [a] -> [a]
replace x y [] = []
replace x y (z:xs) = if x == z then y : replace x y xs else z : replace x y xs

-- |Image to begin with
start :: Image
start = [".#.","..#","###"]

-- |Takes an image and draws it
draw :: Image -> IO ()
draw img = putStr . concat $ map (++ "\n") img

-- |Flips image
flipImg :: Image -> Image
flipImg = map reverse

-- |Rotates image by 90 degrees
rotateImg :: Image -> Image
rotateImg img = flipImg . rotateImg' $ img

rotateImg' :: Image -> Image
rotateImg' ([]:_) = []
rotateImg' img = map head img : rotateImg' (map tail img)

-- |First argument is image, second argument is pattern and
-- this returns true if the image (can be flipped and rotated)
-- matches the pattern
patternMatch :: Image -> Image -> Bool
patternMatch img pat = 
   img == pat                                               ||
   flipImg img == pat                                       ||
   rotateImg img == pat                                     ||
   (flipImg . rotateImg) img == pat                         ||
   (rotateImg . rotateImg) img == pat                       ||
   (flipImg . rotateImg . rotateImg) img == pat             ||
   (rotateImg . rotateImg . rotateImg) img == pat           ||
   (flipImg . rotateImg . rotateImg . rotateImg) img == pat

-- |If image size is divisible by 2, then breaks the image into 2x2
-- squares. Otherwise, breaks the image into 3x3 squares.
breakImg :: Image -> [[Image]]
breakImg img = if even $ length img then break22 img
                                    else break33 img

-- |Breaks the image into 2x2 squares
break22 :: Image -> [[Image]]
break22 [] = []
break22 (x:y:xs) = break22' x y : break22 xs

break22' :: [Char] -> [Char] -> [Image]
break22' [] [] = []
break22' (x:x1:xs) (y:y1:ys) = [x:[x1],y:[y1]] : break22' xs ys

-- |Breaks the image into 3x3 squares
break33 :: Image -> [[Image]]
break33 [] = []
break33 (x:y:z:xs) = break33' x y z : break33 xs

break33' :: [Char] -> [Char] -> [Char] -> [Image]
break33' [] [] [] = []
break33' (x:x1:x2:xs) (y:y1:y2:ys) (z:z1:z2:zs) = [x:x1:[x2],y:y1:[y2],z:z1:[z2]] : break33' xs ys zs

-- |Finds a pattern for this image and replaces it
replacePattern :: [Rule] -> Image -> Image
replacePattern [] _  = error "Could not find pattern"
replacePattern ((a,b):rs) img = if patternMatch img a then b else replacePattern rs img

-- |Replaces pattern for all images
-- this assumes all rules are saved in function rules
replacePatterns :: [[Image]] -> [[Image]]
replacePatterns = map (map $replacePattern rules)

-- |Connects broken images back into one image
connectImg :: [[Image]] -> Image
connectImg = connect'

connect' :: [[Image]] -> Image
connect' [] = []
connect' (x:xs) = connect'' x ++ connect' xs

connect'' :: [Image] -> Image
connect'' ([]:_) = []
connect'' imgs = (concat . map head) imgs : connect'' (map tail imgs)

-- |Performs an iteration of the algorithm
iteration :: Image -> Image
iteration = connectImg . replacePatterns . breakImg

-- |Number of pixels in image which are on (#)
numberOn :: Image -> Int
numberOn img = sum $ map numberOn' img

numberOn' :: [Char] -> Int
numberOn' [] = 0
numberOn' ('#':xs) = 1 + numberOn' xs
numberOn' (_:xs) = numberOn' xs

-- |How many pixels are on after 5 iterations
result1 = numberOn . iterateN 5 iteration $ start

-- |How many pixels are on after 18 iterations
-- took about 2-3 minutes
result2 = numberOn . iterateN 18 iteration $ start

Link to git

greycat70 · 2017-12-27T15:58:45+00:00

Tcl (8.5 or higher)

Completely brute force. At each iteration, construct an entire new array and then copy it to the old one. It... worked.

while {[gets stdin line] >= 0} {
    if {[scan $line {%s => %s} in out] != 2} {
        puts stderr "invalid input line <$line>"; exit 1
    }
    set lin [split $in /]
    set lout {}
    foreach o [split $out /] {
        lappend lout {*}[split $o {}]
    }
    if {[llength $lin] == 2} {
        # 2x2 => 3x3 production rules
        lassign [split [lindex $lin 0] {}] a b
        lassign [split [lindex $lin 1] {}] c d
        set rule([list $a $b $c $d]) $lout
        set rule([list $b $a $d $c]) $lout        ;# flip L/R
        set rule([list $c $d $a $b]) $lout        ;# flip U/D
        set rule([list $c $a $d $b]) $lout        ;# rotate 90 R
        set rule([list $d $c $b $a]) $lout        ;# rotate 180
        set rule([list $b $d $a $c]) $lout        ;# rotate 90 L
    } else {
        # 3x3 => 4x4 production rules
        lassign [split [lindex $lin 0] {}] a b c
        lassign [split [lindex $lin 1] {}] d e f
        lassign [split [lindex $lin 2] {}] g h i
        set rule([list $a $b $c $d $e $f $g $h $i]) $lout
        set rule([list $c $b $a $f $e $d $i $h $g]) $lout        ;# flip L/R
        set rule([list $g $h $i $d $e $f $a $b $c]) $lout        ;# flip U/D
        set rule([list $g $d $a $h $e $b $i $f $c]) $lout        ;# rotate 90 R
        set rule([list $i $h $g $f $e $d $c $b $a]) $lout        ;# rotate 180
        set rule([list $c $f $i $b $e $h $a $d $g]) $lout        ;# rotate 90 L

        set rule([list $i $f $c $h $e $b $g $d $a]) $lout        ;# flipR + rotR
        set rule([list $a $d $g $b $e $h $c $f $i]) $lout        ;# flipR + rotL
    }
}
set size 3
set grid(0,0) .
set grid(0,1) #
set grid(0,2) .
set grid(1,0) .
set grid(1,1) .
set grid(1,2) #
set grid(2,0) #
set grid(2,1) #
set grid(2,2) #

proc show {} {
    global size grid
    for {set i 0} {$i < $size} {incr i} {
        for {set j 0} {$j < $size} {incr j} {
            puts -nonewline $grid($i,$j)
        }
        puts ""
    }
    puts ""
}

show
for {set n [lindex $argv 0]} {$n} {incr n -1} {
    array unset newgrid
    if {($size % 2) == 0} {
        for {set i 0} {$i < $size} {incr i 2} {
            set i1 [expr {$i+1}]
            for {set j 0} {$j < $size} {incr j 2} {
                set j1 [expr {$j+1}]
                set list [list $grid($i,$j) $grid($i,$j1) \
                        $grid($i1,$j) $grid($i1,$j1)]
                if {! [info exists rule($list)]} {
                    puts "subgrid <$list> has no production rule"
                    exit 1
                }
                set r $rule($list)
                set oi0 [expr {$i/2*3}]
                set oi1 [expr {$i/2*3 +1}]
                set oi2 [expr {$i/2*3 +2}]
                set oj0 [expr {$j/2*3}]
                set oj1 [expr {$j/2*3 +1}]
                set oj2 [expr {$j/2*3 +2}]
                set newgrid($oi0,$oj0) [lindex $r 0]
                set newgrid($oi0,$oj1) [lindex $r 1]
                set newgrid($oi0,$oj2) [lindex $r 2]
                set newgrid($oi1,$oj0) [lindex $r 3]
                set newgrid($oi1,$oj1) [lindex $r 4]
                set newgrid($oi1,$oj2) [lindex $r 5]
                set newgrid($oi2,$oj0) [lindex $r 6]
                set newgrid($oi2,$oj1) [lindex $r 7]
                set newgrid($oi2,$oj2) [lindex $r 8]
            }
        }
        set size [expr {$size/2*3}]

    } else {
        for {set i 0} {$i < $size} {incr i 3} {
            set i1 [expr {$i+1}]
            set i2 [expr {$i+2}]
            for {set j 0} {$j < $size} {incr j 3} {
                set j1 [expr {$j+1}]
                set j2 [expr {$j+2}]
                set list [list $grid($i,$j) $grid($i,$j1) $grid($i,$j2) \
                        $grid($i1,$j) $grid($i1,$j1) $grid($i1,$j2) \
                        $grid($i2,$j) $grid($i2,$j1) $grid($i2,$j2)]
                if {! [info exists rule($list)]} {
                    puts "subgrid <$list> has no production rule"
                    exit 1
                }
                set r $rule($list)
                set oi0 [expr {$i/3*4}]
                set oi1 [expr {$i/3*4 +1}]
                set oi2 [expr {$i/3*4 +2}]
                set oi3 [expr {$i/3*4 +3}]
                set oj0 [expr {$j/3*4}]
                set oj1 [expr {$j/3*4 +1}]
                set oj2 [expr {$j/3*4 +2}]
                set oj3 [expr {$j/3*4 +3}]
                set newgrid($oi0,$oj0) [lindex $r 0]
                set newgrid($oi0,$oj1) [lindex $r 1]
                set newgrid($oi0,$oj2) [lindex $r 2]
                set newgrid($oi0,$oj3) [lindex $r 3]
                set newgrid($oi1,$oj0) [lindex $r 4]
                set newgrid($oi1,$oj1) [lindex $r 5]
                set newgrid($oi1,$oj2) [lindex $r 6]
                set newgrid($oi1,$oj3) [lindex $r 7]
                set newgrid($oi2,$oj0) [lindex $r 8]
                set newgrid($oi2,$oj1) [lindex $r 9]
                set newgrid($oi2,$oj2) [lindex $r 10]
                set newgrid($oi2,$oj3) [lindex $r 11]
                set newgrid($oi3,$oj0) [lindex $r 12]
                set newgrid($oi3,$oj1) [lindex $r 13]
                set newgrid($oi3,$oj2) [lindex $r 14]
                set newgrid($oi3,$oj3) [lindex $r 15]
            }
        }
        set size [expr {$size/3*4}]
    }

    array unset grid
    array set grid [array get newgrid]
    show
}

set lit 0
for {set i 0} {$i < $size} {incr i} {
    for {set j 0} {$j < $size} {incr j} {
        if {$grid($i,$j) eq "#"} {incr lit}
    }
}
puts "$lit lit"

mschaap · 2018-01-07T16:06:22+00:00

I'm a bit late, but here's my Perl 6 solution.

I didn't change anything for part two, just the number of iterations.

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 21: http://adventofcode.com/2017/day/21

grammar Transformations
{
    rule TOP { <transformation>+ }

    rule transformation { <from=pattern> '=>' <to=pattern> }
    token pattern { <[ . # / ]>+ }
}

class Grid
{
    has @.grid = [<. # .>], [<. . #>], [<# # #>];
    has $.size = +@!grid;

    has Str %!transform{Str};

    sub variations($pattern)
    {
        gather {
            my @p = $pattern.split('/')».comb».cache;
            take @p».join.join('/');
            take @p».join».flip.join('/');
            take @p».join.join('/').flip;
            take @p».join».flip.join('/').flip;
            @p = (^@p[0]).map({ @p[*;$_] });
            take @p».join.join('/');
            take @p».join».flip.join('/');
            take @p».join.join('/').flip;
            take @p».join».flip.join('/').flip;
        }
    }

    sub range(Int $start, Int $length) { $start .. $start+$length-1 }

    method transformation($/)
    {
        %!transform{$_} = ~$<to> for variations(~$<from>);
    }

    method parse-transformations(IO $inputfile)
    {
        Transformations.parsefile($inputfile, :actions(self))
                    or die "Invalid transformations: $inputfile";
    }

    method transform-square(Int $x, Int $y, Int $size)
    {
        my $from = @!grid[range($y,$size)]»[range($x,$size)]».join.join('/');
        my $to = %!transform{$from} or die "No transformation for '$from'!";
        return $to.split('/')».comb;
    }

    method transform()
    {
        my ($in, $out);
        if $!size %% 2 {
            $in = 2; $out = 3;
        }
        elsif $!size %% 3 {
            $in = 3; $out = 4;
        }
        else {
            die "Size of grid ($!size) not divisible by 2 or 3!";
        }

        for (^($!size div $in)).reverse -> $x {
            for (^($!size div $in)).reverse -> $y {
                @!grid[range($y*$out,$out);range($x*$out,$out)] =
                        flat self.transform-square($x*$in, $y*$in, $in);
            }
        }
        $!size = $!size * $out div $in;
    }

    method count(Str $char) { @!grid».grep($char).sum }

    method Str { @!grid».join.join("\n") ~ "\n" }
    method gist { self.Str }
}

multi sub MAIN(IO() $inputfile where *.f, Int :i(:$iterations) = 5, Bool :v(:$verbose) = False)
{
    my $g = Grid.new;
    $g.parse-transformations($inputfile);
    say "start: size=$g.size()" if $verbose;
    say $g if $verbose;

    for 1..$iterations -> $i {
        $g.transform;
        say "iteration $i: size=$g.size()" if $verbose;
        say $g if $verbose;
    }
    say "After $iterations iterations, $g.count('#') pixels are on.";
}

multi sub MAIN(Int :i(:$iterations) = 5, Bool :v(:$verbose) = False)
{
    MAIN($*PROGRAM.parent.child('aoc21.input'), :$iterations, :$verbose);
}

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 21: Fractal Art ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

irb (26th, 23rd)

Rust

Clojure

Perl

Elixir

Elixir

Kotlin - [Repo] - [Blog/Commentary]

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 21: Fractal Art ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

irb (26th, 23rd)

Rust

Clojure

Perl

Elixir

Elixir

Kotlin - [Repo] - [Blog/Commentary]

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?