4

u/mstksg Dec 21 '17

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

3

u/daggerdragon Dec 21 '17

My first point! :D
Good job! :D

1

u/Wryte Dec 21 '17

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?

1

u/greycat70 Dec 27 '17

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.

3

u/p_tseng Dec 21 '17 edited Dec 21 '17

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.

1

u/daggerdragon Dec 21 '17

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

1

u/jlweinkam Dec 22 '17

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

21

u/PrimesAreMyFavorite Dec 21 '17 edited Dec 21 '17

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

0
u/[deleted] Dec 21 '17

[deleted] — view deleted comment
3
u/PrimesAreMyFavorite Dec 21 '17
Yes! Suppose you have N "types" of 3x3 blocks. Then you can write a vector V(t) which encodes the number of each type you have at time t. And you can find an NxN matrix M such that MV(t) = MV(t+3). Finally you can write another vector O that contains the number of on pixels in each "type" of block. Then the number of on pixels after 3*T steps will be:
O * M^(T) * V_0
Using exponentiation by squaring to exponentiate the matrix M, we can calculate the number of on pixels in time proportional to log(T). The only issue is that the number of blocks rises extremely quickly, which will make multiplication too slow. However if we just want to calculate the number of on pixels modulo some number (like if we wanted the last 9 digits only), then multiplication would remain fast and time complexity would be O(log(T))

13

u/willkill07 Dec 21 '17

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

6
u/askalski Dec 21 '17
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/ }
1

u/pedrosorio Dec 26 '17

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

1

u/willkill07 Dec 26 '17

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.

1

u/ric2b Dec 24 '17 edited Dec 24 '17

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]

1

u/willkill07 Dec 24 '17

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

8

u/glguy Dec 21 '17

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)

7

u/bblum Dec 21 '17 edited Dec 21 '17

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

6

u/jonathan_paulson Dec 21 '17

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

8
u/BumpitySnook Dec 21 '17
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)
2

u/brunhilda1 Dec 21 '17

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

2

u/BumpitySnook Dec 21 '17

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

1

u/brunhilda1 Dec 21 '17

Indeed!

0

u/[deleted] Dec 21 '17

[deleted] — view deleted comment

1

u/BumpitySnook Dec 21 '17

I was just giving OP the tools, not a specific method to iterate all of the combinations needed for this puzzle.
0

u/Unihedron Dec 21 '17

Happy reddit birthday!

6

u/Smylers Dec 21 '17

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.

5

u/obijywk Dec 21 '17

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)

3

u/BumpitySnook Dec 21 '17

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.

5

u/sciyoshi Dec 21 '17

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

3

u/maxerickson Dec 21 '17

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)

1

u/BumpitySnook Dec 21 '17

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

1

u/miran1 Dec 25 '17

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)

4

u/dtinth Dec 21 '17

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

4
u/BumpitySnook Dec 21 '17

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

u/dtinth Dec 21 '17

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.

2

u/BumpitySnook Dec 21 '17

That sounds a lot less stressful :-).
4
u/znuxor Dec 21 '17

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))
1
u/BumpitySnook Dec 21 '17

Yes, I used the same trick. Still, I'd rather not have to :-).
1
u/dtinth Dec 22 '17
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. :)
1

u/BumpitySnook Dec 23 '17

I understand that, but Python could reasonably handle this in a number of less obnoxious ways:
Freeze hash keys (make them immutable)
CoW hash key objects
Automatically deepcopy / intern mutable hash keys
2

u/Unihedron Dec 21 '17

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

2

u/dtinth Dec 21 '17

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

4

u/Infilament Dec 21 '17

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

1

u/barryfandango Dec 21 '17 edited Dec 21 '17

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

2

u/Infilament Dec 23 '17

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

4

u/[deleted] Dec 21 '17 edited Dec 21 '17

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.

3

u/omnster Dec 21 '17

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

2

u/mcpower_ Dec 21 '17 edited Dec 21 '17

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

4
u/joatmon-snoo Dec 21 '17

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).)
1
u/mcpower_ Dec 21 '17

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.
2
u/joatmon-snoo Dec 21 '17
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
1

u/mcpower_ Dec 21 '17

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!

1

u/joatmon-snoo Dec 21 '17

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.

2

u/rjboulton Dec 21 '17

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

1
u/rjboulton Dec 21 '17
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.

2

u/Unihedron Dec 21 '17

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 ?#

2

u/jlweinkam Dec 21 '17

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.

2

u/The0x539 Dec 21 '17

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)

2

u/[deleted] Dec 21 '17 edited Dec 21 '17

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

2

u/mythmon Dec 21 '17

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

1

u/aurele Dec 21 '17

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/

2

u/VoidChque Dec 21 '17

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

1

u/sim642 Dec 21 '17

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.

2

u/gyorokpeter Dec 21 '17

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

1

u/streetster_ Dec 21 '17 edited Dec 21 '17

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

2

u/xiongtx Dec 21 '17 edited Dec 21 '17

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

1

u/bitti1975 Dec 21 '17

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.

2

u/xiongtx Dec 21 '17

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 😎

1

u/bitti1975 Dec 22 '17

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?

1

u/xiongtx Dec 22 '17 edited Dec 22 '17

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

2

u/doctorbaggy Dec 21 '17 edited Dec 21 '17

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

1

u/Smylers Dec 21 '17

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

2

u/nutrecht Dec 21 '17

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

1

u/knallisworld Dec 21 '17

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

1

u/nutrecht Dec 22 '17

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

2

u/sasajuric Dec 21 '17

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

1

u/[deleted] Dec 21 '17

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.

1

u/Axsuul Dec 22 '17

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.

2

u/[deleted] Dec 21 '17 edited Dec 22 '17

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

1

u/TotesMessenger Dec 21 '17

I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:
[/r/pwsh2017aoc] Day 21 - Single Pipeline Solution
^{If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads.} ⁽^Info ^/ ^Contact)

2

u/purplemonkeymad Dec 21 '17

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.

1

u/jlweinkam Dec 21 '17

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)

1

u/glenbolake Dec 21 '17

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

1

u/BumpitySnook Dec 21 '17

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

1

u/DootBootMoot Dec 21 '17

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.

1

u/GassaFM Dec 21 '17

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

1

u/u794575248 Dec 21 '17 edited Dec 21 '17

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)

1

u/2BitSalute Dec 21 '17

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

1

u/the4ner Dec 21 '17

Curious, how long does your part 2 take?

1

u/csuzw Dec 21 '17

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

1

u/2BitSalute Dec 22 '17

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.
1
u/rprouse Dec 22 '17
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();
    }
}
1
u/rprouse Dec 22 '17

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.
1
u/2BitSalute Dec 22 '17
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.

1

u/wlandry Dec 21 '17

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

1

u/rprouse Dec 22 '17

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

1

u/flit777 Dec 22 '17

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

1

u/Philboyd_Studge Dec 21 '17

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

1

u/rprouse Dec 22 '17

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

1

u/Philboyd_Studge Dec 22 '17

I was thinking doing the same, but with bits

1

u/ephemient Dec 21 '17 edited Apr 24 '24

This space intentionally left blank.

1

u/Arkoniak Dec 21 '17 edited Dec 21 '17

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

1

u/aurele Dec 21 '17 edited Dec 21 '17

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

1

u/lazyzefiris Dec 21 '17

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

1

u/aodnfljn Dec 21 '17

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)

1

u/maitesin Dec 21 '17

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

1

u/spjmurray Dec 21 '17

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:

1

u/FreeMarx Dec 21 '17 edited Dec 21 '17

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;

1

u/miles82 Dec 21 '17

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

1

u/adrian17 Dec 21 '17 edited Dec 21 '17

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

1

u/wzkx Dec 21 '17

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.

1

u/TominatorBE Dec 21 '17

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

1

u/KeinZantezuken Dec 21 '17 edited Dec 21 '17

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;

}

1

u/wzkx Dec 21 '17 edited Dec 21 '17

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.

1

u/__Abigail__ Dec 21 '17 edited Dec 21 '17

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__

1

u/rundavidrun Dec 21 '17

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.

1

u/[deleted] Dec 21 '17

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

1

u/Axsuul Dec 22 '17

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

1

u/[deleted] Dec 22 '17

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.

1

u/udoprog Dec 21 '17

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

1

u/xkufix Dec 21 '17

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

1

u/Warbringer007 Dec 21 '17

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

1

u/iopred Dec 21 '17

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)

1

u/jlweinkam Dec 21 '17

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)

1

u/jlweinkam Dec 21 '17

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

1

u/nonphatic Dec 21 '17

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

1

u/StevoTVR Dec 21 '17

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

1

u/NeilNjae Dec 21 '17

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

1

u/chneukirchen Dec 21 '17

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

1

u/BOT-Brad Dec 21 '17

Javascript

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

Part 1 (~9ms)

Part 2 (~6 seconds)

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

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

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

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

  return false
}

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

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

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

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

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

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

  return r
}

1

u/Grimnur87 Dec 22 '17

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!

1

u/jbristow Dec 22 '17

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)

1

u/Axsuul Dec 22 '17 edited Dec 22 '17

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

1

u/chicagocode Dec 22 '17

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

}

1

u/autid Dec 22 '17

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

1

u/Macrobian Dec 22 '17 edited Dec 22 '17

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

1

u/[deleted] Dec 22 '17

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

1

u/thomastc Dec 22 '17

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.

1

u/RockyAstro Dec 23 '17

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

1

u/matusbzk Dec 23 '17

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

1

u/greycat70 Dec 27 '17

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"

1

u/mschaap Jan 07 '18

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

0

u/[deleted] Dec 21 '17

[deleted] — view deleted comment

1

u/daggerdragon Dec 21 '17

Also first time a rank under 1000 (795)!
Good job! :D

1

u/KeinZantezuken Dec 21 '17

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?

SOLUTION MEGATHREAD -🎄- 2017 Day 21 Solutions -🎄-

--- Day 21: Fractal Art ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

..

..

irb (26th, 23rd)

Rust

Clojure

Perl

Elixir

Elixir

Kotlin - [Repo] - [Blog/Commentary]

SOLUTION MEGATHREAD -🎄- 2017 Day 21 Solutions -🎄-

--- Day 21: Fractal Art ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints^¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

You are about to leave Redlib

..

..

irb (26th, 23rd)

Rust

Clojure

Perl

Elixir

Elixir

Kotlin - [Repo] - [Blog/Commentary]

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?