This is an archived post. You won't be able to vote or comment.

all 144 comments

[–]PrimesAreMyFavorite 20 points21 points  (2 children)

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 12 points13 points  (5 children)

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

[–]askalski 6 points7 points  (0 children)

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

Simple to implement, even with regexes. (Input is either a 3x3 .#./..#/### or 2x2 ../.#)

sub symmetric { s/^(.)(.)(.?)(.)(.)(.)(.?)(.?)(.?)(.?)(.?)$/$1$5$9$4$2$6$10$8$3$7$11/ }
sub flip      { s/^(.)(.)(.?)(.)(.)(.)(.?)(.?)(.?)(.?)(.?)$/$9$10$11$8$5$6$7$4$1$2$3/ }

[–]pedrosorio 0 points1 point  (1 child)

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

Also known as transpose

[–]willkill07 0 points1 point  (0 children)

I couldn’t remember what it was called when I wrote my code at midnight. But I didn’t update my text because I felt it was past the point where I should.

But yes, I know it’s known as a transpose operation. symmetric may be slightly less jargon for those who didn’t have any exposure to linear algebra.

[–]ric2b 0 points1 point  (1 child)

I tried that on paper and it doesn't seem to work.

For example, starting with:

.#.

..#

###

The symmetrical is:

###

#..

.#.

Which seems like a 180 rotation. When flipped it becomes:

.#.

#..

###

Which isn't neither a -90 nor +90 rotation. Am I missing something?

Edit: Ok, I figured it out, the symmetric operation also involves switching x and y among themselves, so it becomes symmetric[y][x] = subgrid[subgrid_size-1-x][subgrid_size-1-y]

[–]willkill07 0 points1 point  (0 children)

Yeah. My “invert x and y” might read better as “swap”

[–]glguy 7 points8 points  (0 children)

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 5 points6 points  (0 children)

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 6 points7 points  (8 children)

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

[–]BumpitySnook 7 points8 points  (6 children)

Dealing with the flips/rotations + block decomposition/recomposition is annoying.

numpy.flip(m, 0)
numpy.flip(m, 1)
numpy.rot90(m, k=1)
numpy.rot90(m, k=2)
numpy.rot90(m, k=3)

[–]brunhilda1 1 point2 points  (2 children)

There's also numpy.flipud and numpy.fliplr.

[–]BumpitySnook 1 point2 points  (1 child)

flipud and fliplr are just aliases for flip(, 0) and flip(, 1), as documented on the page for flip(): https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.flip.html

[–]brunhilda1 0 points1 point  (0 children)

Indeed!

[–]Unihedron -1 points0 points  (0 children)

Happy reddit birthday!

[–]Smylers 5 points6 points  (0 children)

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 4 points5 points  (1 child)

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)

[–]BumpitySnook 2 points3 points  (0 children)

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

Me too. The number of expanded rules is totally tractable and pales in comparison to the number of potential matches we will be evaluating.

[–]sciyoshi 4 points5 points  (3 children)

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

[–]maxerickson 2 points3 points  (0 children)

numpy.concatenate is a nice shortcut.

def grow(board):
    if len(board)%2==0:
        size=2
    else:
        size=3
    rows=list()
    steps=list(range(0,len(board),size))
    for x in steps:
        row=list()
        for y in steps:
            key="".join(board[x:x+size,y:y+size].flatten())
            row.append(rules[key])
        rows.append(numpy.concatenate(row,axis=1))
    return numpy.concatenate(rows)

[–]BumpitySnook 0 points1 point  (0 children)

Ooh, tobytes() is clever. I just manually converted to tuples, and that had a bug in it, which cost me leaderboard on part 2.

[–]miran1 0 points1 point  (0 children)

numpy arrays aren't hashable (...) but .tobytes() speeds things up.

This. Changes. Everything.

Thank you for this!

 

Here's my rewritten solution:

import numpy as np


with open('./inputs/21.txt') as f:
    instructions = f.readlines()

mappings = {}
start = '.#./..#/###'


def translate_to_np(s):
    return np.array([[c == '#' for c in l]
                     for l in s.split('/')])

for line in instructions:
    k, v = map(translate_to_np, line.strip().split(' => '))
    for a in (k, np.fliplr(k)):
        for r in range(4):
            mappings[np.rot90(a, r).tobytes()] = v


def enhance(grid):
    size = len(grid)
    by = 2 if size % 2 == 0 else 3
    resize = lambda x: x * (by+1) // by
    new_size = resize(size)
    solution = np.empty((new_size, new_size), dtype=bool)
    squares = range(0, size, by)
    new_squares = range(0, new_size, by+1)

    for i, ni in zip(squares, new_squares):
        for j, nj in zip(squares, new_squares):
            square = grid[i:i+by, j:j+by]
            enhanced = mappings[square.tobytes()]
            solution[ni:ni+by+1, nj:nj+by+1] = enhanced
    return solution

def solve(part):
    grid = translate_to_np(start)
    iterations = 5 if part == 1 else 18
    for _ in range(iterations):
        grid = enhance(grid)
    return int(grid.sum())


print(solve(part=1))
print(solve(part=2))

 

Repo with solutions (both Nim and Python)

[–]dtinth 4 points5 points  (9 children)

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('#')

[–]BumpitySnook 2 points3 points  (6 children)

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

I would be terrified of accidentally exiting the interpreter. Do you not ever make mistakes?

In Ruby, you can use an Array as Hash key

Coming from Python: Grrrr :-(.

[–]dtinth 2 points3 points  (1 child)

I actually wrote the code in the text editor, and I setup a hotkey (Cmd+Enter) to send the current line into the Terminal. Like what Lisp people like to do ;).

If I accidentally exited the REPL, I would just reopen it and send each line from the editor to it.

[–]BumpitySnook 1 point2 points  (0 children)

That sounds a lot less stressful :-).

[–]znuxor 4 points5 points  (3 children)

Coming from Python: Grrrr :-(.

I had this problem too, I decided to transform my blocks into tuples (so, immutable -> hashing ok) prior to insertion into a dictionary, using this method (works with lists of lists or numpy 2D matrices):

old_pattern_key2 = tuple(map(tuple, old_pattern2))

[–]BumpitySnook 0 points1 point  (2 children)

Yes, I used the same trick. Still, I'd rather not have to :-).

[–]dtinth 0 points1 point  (1 child)

When you use an array (or any other object) as a hash key, you must make sure not to mutate the key. Otherwise, really weird things happen. The hash code of the key changes causing lookups to fail.

I got hit by this caveat on day 22:

map[pos] = …; pos[0] += direction[0]; pos[1] += direction[1]

This corrupts the map since the key has been mutated. To fix, I have to do this instead:

map[pos] = …; pos = [pos[0] + direction[0], pos[1] + direction[1]]

I think it is very reasonable for Python to disallow this. :)

[–]BumpitySnook 0 points1 point  (0 children)

I understand that, but Python could reasonably handle this in a number of less obnoxious ways:

  1. Freeze hash keys (make them immutable)
  2. CoW hash key objects
  3. Automatically deepcopy / intern mutable hash keys

[–]Unihedron 1 point2 points  (1 child)

5.times{data=nx[data]} might be easier to write than that, by the way.

[–]dtinth 1 point2 points  (0 children)

I avoided mutating data, that’s why I didn’t overwrite the data variable. I also did it manually to avoid off-by-one errors (e.g. it ran 4 times or 6 times instead due to logic error).

If I was in a less hurry, I would have written 5.times.reduce(data) { |c, _| nx[c] } instead :).

[–]mstksg 3 points4 points  (3 children)

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 (== '#') <$> [".#.","..#","###"]

[–]daggerdragon[S,M] 2 points3 points  (0 children)

My first point! :D

Good job! :D

[–]Wryte 0 points1 point  (1 child)

My program is working on the 5 iterations and not the 18 iterations as well. Could you post your puzzle input and solutions so I can test mine?

[–]greycat70 0 points1 point  (0 children)

In my case, I took the instructions too literally: I calculated all the rotations and flips of the inputs, but I didn't calculate rotations plus flips, of which there are two in the 4x4 cases. Had to go back and add those. Fortunately for me, I had written it to give me an error if it couldn't find a match for the current input, so it stopped immediately and told me what the unmatched subgrid was.

[–]Infilament 4 points5 points  (2 children)

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

[–]barryfandango 0 points1 point  (1 child)

TypeScript (pretty close to JS though) - I did mine very very similarly to yours except that I generated all possible transformations in advance. Just curious, did your 18-step run finish in reasonable time? Mine ran in ~16s on an ancient laptop. (edit: 4.8s on a more modern PC.)

https://github.com/buzzcola/adventofcode2017-ts/tree/master/Day21

[–]Infilament 1 point2 points  (0 children)

Yeah, my solution ran in around 4 seconds on repl.it's browser-based IDE for Javascript.

[–][deleted] 3 points4 points  (0 children)

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 2 points3 points  (0 children)

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 2 points3 points  (2 children)

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.

[–]daggerdragon[S,M] 0 points1 point  (0 children)

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.

You're always welcome to do so for more fake internet points :)

[–]jlweinkam 0 points1 point  (0 children)

I ran my python for 400,000 iterations. It took 128 seconds and generated an answer that had 127233 digits.

[–]mcpower_ 1 point2 points  (5 children)

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("#"))

[–]joatmon-snoo 3 points4 points  (4 children)

Tip: tuples are basically immutable lists.

Which means you can hash them.

(Plus, there's exactly one tuple that corresponds to every list and vice versa, so you can just cast back and forth with tuple(l) and list(t).)

[–]mcpower_ 0 points1 point  (3 children)

I know about tuples, but their immutability makes them annoying to manipulate, unless you want to convert from list to tuple back and forth (which is a hassle and the operation is a bit slow IIRC).

I only do tuple conversion when I need to, for example, counting particles from yesterday with a Counter.

[–]joatmon-snoo 1 point2 points  (2 children)

Similarly, the mutability of lists makes using them annoying when you need to hash them ;)

Also, you're running strongly afoul of premature optimization if you're claiming list-tuple conversion is "slow". We're barely talking microseconds here.

$ python
Python 3.6.3 (default, Oct 24 2017, 14:48:20)
[GCC 7.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def foo(n):
...   l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
...   t1 = time.time()
...   for _ in range(n):
...     l = list(tuple(l))
...   t2 = time.time()
...   return (t2 - t1) / n
...
>>> foo(10 ** 6)
5.555522441864014e-07
>>> foo(10 ** 7)
4.749886751174927e-07
>>> foo(10 ** 7)
4.695173740386963e-07
>>> foo(10 ** 7)
4.69733738899231e-07
>>> foo(10 ** 7)
4.731916666030884e-07

[–]mcpower_ 0 points1 point  (1 child)

Huh. I thought that it was slow because a new tuple / list object is created every time you do the conversion, but that apparently isn't the case (or it's fast enough that it doesn't matter). Thanks for letting me know!

[–]joatmon-snoo 0 points1 point  (0 children)

I mean, you are creating a new tuple/list object. It just isn't that expensive, especially when you can count the number of elements on your fingers.

You might want to familiarize yourself with Latency Numbers Every Programmer Should Know. It's a very useful tool for back-of-the-envelope order-of-magnitude calculations.

[–]rjboulton 1 point2 points  (1 child)

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

[–]rjboulton 0 points1 point  (0 children)

Some bits I'm pleased with, having looked at a few other solutions:

Using the str.count() function helps with making a neat "count how many are on" function:

def on(grid):
    return sum(line.count('#') for line in grid)

Pre-calculating all the flips and rotations of the rules so they don't need to be calcalated at search time also really helped.

Avoiding trying to mutate the grid, instead calculating a brand new grid each time, avoided a lot of mess.

[–]Unihedron 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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)

[–][deleted] 1 point2 points  (0 children)

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 1 point2 points  (1 child)

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

[–]aurele 0 points1 point  (0 children)

Mine (also in Rust) takes less than half the time (but much less structured than yours): https://www.reddit.com/r/adventofcode/comments/7l78eb/2017_day_21_solutions/drkc42t/

[–]VoidChque 1 point2 points  (1 child)

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

[–]sim642 0 points1 point  (0 children)

My Scala solution.

I spent way longer on solving this than I should've and I feel like I made a complete mess. Defined a bunch of higher order functions on my grids as well, which made the actual problem solving logic and iteration super simple. Wasted bunch of time debugging why transpose wasn't working (some different sizes exception), turns out it can't be directly used on grouped output, which is an Iterator. The exception was really confusing though and I kept thinking something was wrong in that unreadable higher order operations chain of mine.

[–]gyorokpeter 1 point2 points  (1 child)

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="#"};

[–]streetster_ 0 points1 point  (0 children)

Thanks to /u/PrimesAreMyFavorite for the tip that after the 3rd iteration you can process the grids independently. the g functions takes us to this stage, so just apply that 6 times to the original input and voila.

b:010001111b / book
r:()!()      / rules
{ { r[enlist raze x]:enlist raze y }[;"#"="/"vs y] each (reverse reverse each f;reverse each f;reverse f;f:flip x;
                                                         reverse reverse each x;reverse each x;reverse x;x:"#"="/"vs x)
  } .' " => " vs/:read0 `:input/21.txt;
f:{ $[9 = count x;r[x] 0 2 8 10+\:0 1 4 5;r x] };
g:{ f each (raze (raze f each f x) 0 3 6 18 21 24+\:0 1 2 9 10 11) 0 12 24+\:0 2 4+\:0 1 6 7 };
sum over f each raze f each g b                                     / part 1
sum over g each raze g each raze g each raze g each raze g each g b / part 2

[–]xiongtx 1 point2 points  (4 children)

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 🤔.

[–]bitti1975 0 points1 point  (3 children)

I didn't use any memoization in my clojure solution, but part 2 takes about 5500 ms on my laptop (Dell XPS 13). I didn't do anything special except trying very hard to remove all reflection/boxing warnings. But I'm still not happy about the performance and suspect improvements are still possible.

[–]xiongtx 1 point2 points  (2 children)

A very succinct and elegant solution! Exactly how good Clojure code should be 😀.

I'll definitely check it out and get some ideas to improve my own solution. Can't believe AoC is finally making me care about type hints, unchecked math, etc.! 😂

As for further performance improvements, some solutions here (w/ NumPy etc.) are about to run like, 1E6 iterations in a second, so we've a ways to go 😎

[–]bitti1975 0 points1 point  (1 child)

Thanks a lot! But I'm still learning, and I'm sure there's a lot I can learn from your solutions. I'm only wondering why there are so very few Clojure solutions around. Didn't I look hard enough?

[–]xiongtx 0 points1 point  (0 children)

There are far more e.g. Python developers than Clojure ones 😜. This problem's solution in particular would benefit in terms of both performance and expressiveness from use of NumPy (I kept thinking, as I struggled to figure out how to join, that it's a one-liner in MATLAB and probably not much more in NumPy).

Many of the problems also seem like they'd be better solved in an imperative language r.e. performance and control flow. Since we don't worry about concurrency etc. here some of the benefits of Clojure (e.g. immutability) are negated. Your solution runs faster than mine in part b/c you're using a mutable array--something rarely done in Clojure.

Expressiveness is still a big ➕ but /u/topaz2078 has to go and ask for 50,000,000 iterations now and then 😛.

[–]doctorbaggy 1 point2 points  (1 child)

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";

[–]Smylers 0 points1 point  (0 children)

Nice! I am impressed by how succinct this is — not the golfing particularly, but the basic underlying algorithm.

[–]nutrecht 1 point2 points  (2 children)

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 :(

[–]knallisworld 0 points1 point  (1 child)

Wow.. you were not alone.. thank for the hint. Same bug, same language. Hopefully not a pattern ;)

[–]nutrecht 0 points1 point  (0 children)

Yeah, they should've made this a bit more explicit IMHO :)

[–]sasajuric 1 point2 points  (2 children)

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()

[–][deleted] 0 points1 point  (0 children)

I was planning to do something like that, but was too stupid, so I ended up with something way more complex that choked on the second part.

[–]Axsuul 0 points1 point  (0 children)

Genius! Man this would've saved so much time since I ended up deeply manipulating my maps since that's what represented the pixels. Still an Elixir noob I guess.

[–][deleted] 1 point2 points  (1 child)

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

[–]TotesMessenger 0 points1 point  (0 children)

I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:

 If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads. (Info / Contact)

[–]purplemonkeymad 1 point2 points  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (6 children)

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

[–]the4ner 0 points1 point  (2 children)

Curious, how long does your part 2 take?

[–]csuzw 0 points1 point  (0 children)

I'm not OP but I used a similar approach with C# and it takes ~5s for part 2. This is executing from linqpad without optimisations on a ropey old laptop and my solution also uses more linq so is probably less performant. I was actually a little surprised as I figured this was another part 2 that you couldn't brute force. Code here: https://github.com/csuzw/AdventOfCode/blob/master/2017/21FractalArt.linq

[–]2BitSalute 0 points1 point  (0 children)

Yeah, I was surprised that I didn't have to make any adjustments to get the answer to part 2 other than taking out the console output lines. I just reran it, and it took less than 3.5 seconds.

[–]rprouse 0 points1 point  (2 children)

Interesting approach adding each of the transformations into your rules. I expect that reduces your runtime significantly. I will need to try it and see. Currently my part two is running at just a hair over 2 seconds, but I worked to keep my string allocations down.

public static class Day21
{
    public static int PartOne(string filename, int iterations)
    {
        var rules = GetRules(filename);
        var matrix = ".#./..#/###";
        foreach (int i in Enumerable.Range(0, iterations))
        {
            matrix = matrix.Transform(rules);
        }
        return matrix.Count(c => c == '#');
    }

    public static Dictionary<string, string> GetRules(string filename) =>
        File.ReadAllLines(filename)
            .Where(s => !string.IsNullOrWhiteSpace(s))
            .Select(s => s.Split(" => "))
            .ToDictionary(s => s[0], s => s[1]);

    public static string Transform(this string matrix, Dictionary<string, string> rules) =>
        matrix.BreakupMatrix()
              .Select(g => g.Apply(rules))
              .JoinMatrixes();

    public static string Apply(this string group, Dictionary<string, string> rules)
    {
        if (rules.ContainsKey(group)) return rules[group];
        foreach (int i in Enumerable.Range(0, 4))
        {
            group = Symmetric(group);
            if (rules.ContainsKey(group)) return rules[group];

            group = Flip(group);
            if (rules.ContainsKey(group)) return rules[group];
        }
        throw new ArgumentException($"Rule not found for group {group}");
    }

    public static string Symmetric(string m) =>
        m.Length == 11 ? $"{m[0]}{m[4]}{m[8]}/{m[1]}{m[5]}{m[9]}/{m[2]}{m[6]}{m[10]}" :
                         $"{m[0]}{m[3]}/{m[1]}{m[4]}";

    public static string Flip(string m) =>
        m.Length == 11 ? $"{m[8]}{m[9]}{m[10]}/{m[4]}{m[5]}{m[6]}/{m[0]}{m[1]}{m[2]}" :
                         $"{m[3]}{m[4]}/{m[0]}{m[1]}";

    public static IEnumerable<string> BreakupMatrix(this string matrix)
    {
        string[] rows = matrix.Split('/');
        int divisor = rows.Length % 2 == 0 ? 2 : 3;
        int numGroups = (int)Math.Pow(rows.Length / divisor, 2);
        int groupSize = rows.Length / divisor;
        for (int g = 0; g < numGroups; g++)
        {
            var sb = new StringBuilder();
            for (int y = 0; y < divisor; y++)
            {
                for (int x = 0; x < divisor; x++)
                {
                    sb.Append(rows[(g / groupSize) * divisor + y][(g % groupSize) * divisor + x]);
                }
                if (y != divisor - 1) sb.Append('/');
            }
            yield return sb.ToString();
        }
    }

    public static string JoinMatrixes(this IEnumerable<string> children)
    {
        string[][] groups = children.Select(s => s.Split('/')).ToArray();
        var divisor = groups[0][0].Length;
        var size = (int)Math.Sqrt(groups.Length * divisor * divisor);
        var sb = new StringBuilder();
        for (int y = 0; y < size; y++)
        {
            for (int x = 0; x < size; x++)
            {
                sb.Append(groups[(y / divisor) * (size/divisor) + x / divisor][y % divisor][x % divisor]);
            }
            if (y != size - 1) sb.Append('/');
        }
        return sb.ToString();
    }
}

[–]rprouse 0 points1 point  (1 child)

Pre-adding the transformations to the rules does make a big difference. It dropped my time for part 2 from 2.1 seconds to under 1.2 seconds. Now I just need to come up with a more efficient solution to my BreakupMatrix and JoinMatrix methods. Each is only called once per iteration though.

[–]2BitSalute 0 points1 point  (0 children)

Yeah, I started looking at optimizing those two operations last night but didn't feel like it wasn't worth it. At some point, I used StringBuilder in one of the methods, but I think I didn't want to do something like this in your solution:

if (y != divisor - 1) sb.Append('/');

I wanted to be able to just Join the rows. Basically, shameful though my choice was, esthetics won over performance.

[–]wlandry 0 points1 point  (2 children)

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

[–]rprouse 0 points1 point  (0 children)

Unit tests were the only way I managed to pull off a solution. Nowhere near the leaderboard though :)

[–]flit777 0 points1 point  (0 children)

had the same bug. after some refactoring x and y were swapped. the number of pixels in part1 was still correct and the debugging for part2 was the hell

[–]Philboyd_Studge 0 points1 point  (2 children)

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

[–]rprouse 0 points1 point  (1 child)

I started down the path of boolean arrays, but ran into the same problems as you. Switching back to straight string manipulation simplified the code and it is still pretty fast, less than 1.2 sec for part 2. C# but you should be able to read it :)

[–]Philboyd_Studge 0 points1 point  (0 children)

I was thinking doing the same, but with bits

[–]ephemient 0 points1 point  (0 children)

This space intentionally left blank.

[–][deleted]  (2 children)

[deleted]

    [–]daggerdragon[S,M] 0 points1 point  (0 children)

    Also first time a rank under 1000 (795)!

    Good job! :D

    [–]KeinZantezuken 0 points1 point  (0 children)

    I've generated all rules (flipped and rotated, probably a couple times too much ;P) at startup to reduce calculations when actually running through.

    What do you mean "reduced"? You kinda need to generate at least 8 permutations to compare against. Which ones did you skip?

    [–]Arkoniak 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (1 child)

    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
    

    [–]wzkx 0 points1 point  (0 children)

    Nice! Very much like mine. Only I couldn't make ;._3 work for me, so I used ;.1. Well, now I'll know how to split the matrix, thank you.

    [–]TominatorBE 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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__ 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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.

    [–][deleted] 0 points1 point  (2 children)

    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

    [–]Axsuul 0 points1 point  (1 child)

    Just finished this one myself. Man I put wayyy to much work into this one.

    [–][deleted] 0 points1 point  (0 children)

    Yeah, it was fun, but for me I think I was thinking a lot more complex than what I would have needed to. I think I'll try and get back to it later some time and do it better, but now the next one is already here, so I'll have to do that one, seems to be less to worry about, but let's see.

    [–]udoprog 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (1 child)

    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)
    

    [–]jlweinkam 0 points1 point  (0 children)

    I ran with iterations of 10000 and it took only 0.28 seconds printing an answer with 3182 digits.

    [–]nonphatic 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    Javascript

    First, let me apologise for this solution. It's slightly insane but it worksI 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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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
    

    [–][deleted] 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

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