day20.nim

import tables
import streams
import strutils
import parseutils

const N: int = 12

type Tile = array[0..9, array[0..9, bool]]
type Offset = tuple[x, y: int]
type TileSide = enum TTop, TLeft, TRight, TBottom
type GridSide = enum GTop, GLeft, GRight, GBottom
type Orientation = enum
        R0, R90, R180, R270,
        RH, RV, RTL, RTR
type Edge = array[0..9, bool]

proc `$`(t: Tile): string =
    var s = ""
    for i in 0..9:
        for j in 0..9:
            s &= (if t[i][j]: '#' else: '.')
        s &= "\n"
    return s

proc `$`(e: Edge): string =
    var s = ""
    for i in 0..9:
        s &= (if e[i]: "#" else: ".")
    return s

proc readTile(s: Stream, t: var Tile, id: var uint16): bool =
    var line: string
    if not s.readLine(line):
        return false
    assert line.startsWith("Tile ")
    var id1: uint
    if parseUInt(line, id1, start=len("Tile ")) == 0:
        return false
    id = (uint16)id1
    for i in 0..9:
        if not s.readLine(line):
            return false
        for j in 0..9:
            t[i][j] = line[j] == '#'
    return true

proc readTiles(filename: string): Table[uint16, Tile] =
    var file = newFileStream("input.txt", fmRead)

    var tiles: Table[uint16, Tile]
    var t: Tile
    var id: uint16
    var line: string

    while readTile(file, t, id):
        tiles[id] = t
        discard file.readLine(line)

    return tiles

var tiles = readTiles("test.txt")

proc getEdge(tile: Tile, side: TileSide): Edge =
    var r: Edge
    if side == TTop:
        for i in 0..9:
            r[i] = tile[0][i]
    elif side == TBottom:
        for i in 0..9:
            r[i] = tile[9][i]
    elif side == TLeft:
        for i in 0..9:
            r[i] = tile[i][0]
    elif side == TRight:
        for i in 0..9:
            r[i] = tile[i][9]
    return r

var tileToGridMapping: Table[tuple[orn: Orientation, side: TileSide], tuple[side: GridSide, reverse: bool]]
tileToGridMapping = {
    (R0, TTop): (GTop, false),
    (R0, TRight): (GRight, false),
    (R0, TBottom): (GBottom, false),
    (R0, TLeft): (GLeft, false),
    (R90, TTop): (GRight, false),
    (R90, TRight): (GBottom, true),
    (R90, TBottom): (GLeft, false),
    (R90, TLeft): (GTop, true),
    (R180, TTop): (GBottom, true),
    (R180, TRight): (GLeft, true),
    (R180, TBottom): (GTop, true),
    (R180, TLeft): (GRight, true),
    (R270, TTop): (GLeft, true),
    (R270, TRight): (GTop, false),
    (R270, TBottom): (GRight, true),
    (R270, TLeft): (GBottom, false),
    (RH, TTop): (GBottom, false),
    (RH, TRight): (GRight, true),
    (RH, TBottom): (GTop, false),
    (RH, TLeft): (GLeft, true),
    (RV, TTop): (GTop, true),
    (RV, TRight): (GLeft, false),
    (RV, TBottom): (GBottom, true),
    (RV, TLeft): (GRight, false),
    (RTL, TTop): (GLeft, false),
    (RTL, TRight): (GBottom, false),
    (RTL, TBottom): (GRight, false),
    (RTL, TLeft): (GTop, false),
    (RTR, TTop): (GRight, true),
    (RTR, TRight): (GTop, true),
    (RTR, TBottom): (GLeft, true),
    (RTR, TLeft): (GBottom, true)
}.toTable

var inv: Table[Orientation, Orientation] = {
    R0: R0,
    R90: R270,
    R180: R180,
    R270: R90,
    RH: RH,
    RV: RV,
    RTL: RTL,
    RTR: RTR,
}.toTable

var gridToTileMapping: Table[tuple[orn: Orientation, side: GridSide], tuple[side: TileSide, reverse: bool]]
for k, v in tileToGridMapping.pairs():
    var (orn, tside) = k
    var (gside, reverse) = v
    gridToTileMapping[(inv[orn], gside)] = (tside, reverse)

var toOrientation: Table[tuple[fromSide: TileSide, toSide: GridSide, reversed: bool], Orientation]
for k, v in gridToTileMapping.pairs():
    var (orn, target) = k
    var (src, reversed) = v
    toOrientation[(fromSide: src, toSide: target, reversed: reversed)] = orn

proc transform(t: Tile, orn: Orientation): Tile =
    var t1: Tile
    for i in 0..9:
        for j in 0..9:
            case orn
            of R0: t1[i][j] = t[i][j]
            of R90: t1[j][9-i] = t[i][j]
            of R180: t1[9-i][9-j] = t[i][j]
            of R270: t1[9-j][i] = t[i][j]
            of RH: t1[9-i][j] = t[i][j]
            of RV: t1[i][9-j] = t[i][j]
            of RTL: t1[j][i] = t[i][j]
            of RTR: t1[9-j][9-i] = t[i][j]
    return t1


proc reverse(e: Edge): Edge =
    var e1: Edge
    for i in 0..9:
        e1[i] = e[9-i]
    return e1

proc getEdge(tile: Tile, orn: Orientation, gridSide: GridSide): Edge =
    var (tileSide, reverse) = gridToTileMapping[(orn, gridSide)]
    var edge = getEdge(tile, tileSide)
    if reverse:
        return reverse(edge)
    else:
        return edge

var edges: Table[Edge, seq[tuple[id: uint16, side: TileSide, reversed: bool]]]
for id, tile in tiles.pairs():
    for side in @[TTop, TRight, TBottom, TLeft]:
        var edge = getEdge(tile, side)
        if not edges.contains(edge):
            edges[edge] = newSeq[tuple[id: uint16, side: TileSide, reversed: bool]](0)
        edges[edge].add((id, side, false))

        var revEdge = reverse(edge)
        if not edges.contains(revEdge):
            edges[revEdge] = newSeq[tuple[id: uint16, side: TileSide, reversed: bool]](0)
        edges[revEdge].add((id, side, true))

var links: Table[tuple[id: uint16, side: TileSide], tuple[id: uint16, side: TileSide, reversed: bool]]
for vals in edges.values():
    if len(vals) == 1:
        continue
    assert len(vals) == 2
    var (id1, side1, rev1) = vals[0]
    var (id2, side2, rev2) = vals[1]
    links[(id1, side1)] = (id2, side2, rev1 != rev2)
    links[(id2, side2)] = (id1, side1, rev1 != rev2)

var match: Table[GridSide, GridSide]
match = {
    GTop: GBottom,
    GBottom: GTop,
    GLeft: GRight,
    GRight: GLeft,
}.toTable

var corner: uint16
var tl: set[TileSide]
tl.incl(TTop)
tl.incl(TLeft)
for id, tile in tiles.pairs():
    var sides: set[TileSide]
    for s in @[TTop, TRight, TBottom, TLeft]:
        var edge = getEdge(tile, s)
        if len(edges[edge]) == 1:
            sides.incl(s)
    if len(sides) == 2:
        echo "Corner: ", id
    if sides == tl:
        corner = id

var placement: array[0..N-1, array[0..N-1, tuple[id: uint16, orn: Orientation]]]
placement[0][0] = (corner, R0)

for i in 1..N-1:
    # Fill in the first row
    var (leftId, leftOrn) = placement[0][i-1]
    var (leftSide, leftReversed) = gridToTileMapping[(leftOrn, GRight)]
    var (rightId, rightSide, rightReversed) = links[(leftId, leftSide)]
    var rev = leftReversed != rightReversed
    var rightOrn = toOrientation[(rightSide, GLeft, rev)]
    if getEdge(tiles[leftId], leftOrn, GRight) != getEdge(tiles[rightId], rightOrn, GLeft):
        echo "Using ", leftSide, " of left tile with orientation ", leftOrn, "."
        echo "Using ", rightSide, " of right tile, using ", rightOrn
        var leftTile = tiles[leftId]
        var rightTile = tiles[rightId]
        var trLeftTile = transform(leftTile, leftOrn)
        var trRightTile = transform(rightTile, rightOrn)
        echo leftOrn
        for i in 0..9:
            for j in 0..9:
                write(stdout, if leftTile[i][j]: "#" else: ".")
            write(stdout, "    ")
            for j in 0..9:
                write(stdout, if trLeftTile[i][j]: "#" else: ".")
            write(stdout, "\n")

        echo ""
        echo rightOrn
        for i in 0..9:
            for j in 0..9:
                write(stdout, if rightTile[i][j]: "#" else: ".")
            write(stdout, "    ")
            for j in 0..9:
                write(stdout, if trRightTile[i][j]: "#" else: ".")
            write(stdout, "\n")

        echo "Links: ", links[(leftId, leftSide)]

        echo "Left Id: ", leftId, ", orientation=", leftOrn
        echo "Right Id: ", rightId, ", orientation=", rightOrn
        for i in 0..9:
            for j in 0..9:
                write(stdout, if trLeftTile[i][j]: "#" else: ".")
            write(stdout, "|")
            for j in 0..9:
                write(stdout, if trRightTile[i][j]: "#" else: ".")
            write(stdout, "\n")
        echo ""
        echo getEdge(tiles[leftId], leftOrn, GRight)
        echo getEdge(tiles[rightId], rightOrn, GLeft)
        quit(1)
    placement[0][i] = (rightId, rightOrn)

# Fill in the columns
for j in 0..N-1:
    for i in 1..N-1:
        var (topId, topOrn) = placement[i-1][j]
        var (topSide, topReversed) = gridToTileMapping[(topOrn, GBottom)]
        var (bottomId, bottomSide, bottomReversed) = links[(topId, topSide)]
        var rev = topReversed != bottomReversed
        var bottomOrn = toOrientation[(bottomSide, GTop, rev)]
        placement[i][j] = (bottomId, bottomOrn)
        if getEdge(tiles[topId], topOrn, GBottom) != getEdge(tiles[bottomId], bottomOrn, GTop):
            echo "Using ", topSide, " of top tile with orientation ", topOrn, "."
            echo "Using ", bottomSide, " of bottom tile, using ", bottomOrn
            var topTile = tiles[topId]
            var bottomTile = tiles[bottomId]
            var trTopTile = transform(topTile, topOrn)
            var trBottomTile = transform(bottomTile, bottomOrn)
            echo topOrn
            for i in 0..9:
                for j in 0..9:
                    write(stdout, if topTile[i][j]: "#" else: ".")
                write(stdout, "    ")
                for j in 0..9:
                    write(stdout, if trTopTile[i][j]: "#" else: ".")
                write(stdout, "\n")

            echo ""
            echo bottomOrn
            for i in 0..9:
                for j in 0..9:
                    write(stdout, if bottomTile[i][j]: "#" else: ".")
                write(stdout, "    ")
                for j in 0..9:
                    write(stdout, if trBottomTile[i][j]: "#" else: ".")
                write(stdout, "\n")

            echo "Links: ", links[(topId, topSide)]

            echo "Top Id: ", topId, ", orientation=", topOrn
            echo "Bottom Id: ", bottomId, ", orientation=", bottomOrn
            for i in 0..9:
                for j in 0..9:
                    write(stdout, if trTopTile[i][j]: "#" else: ".")
                write(stdout, "|")
                for j in 0..9:
                    write(stdout, if trBottomTile[i][j]: "#" else: ".")
                write(stdout, "\n")
            echo ""
            echo getEdge(tiles[topId], topOrn, GRight)
            echo getEdge(tiles[bottomId], bottomOrn, GLeft)
            quit(1)


var img: array[0..10*N-1, array[0..10*N-1, bool]]

for i in 0..N-1:
    for j in 0..N-1:
        var (id, orn) = placement[i][j]
        if id == 0:
            continue
        var t1 = transform(tiles[id], inv[orn])
        for a in 0..9:
            for b in 0..9:
                img[i*10+a][j*10+b] = t1[a][b]

for i in low(img)..high(img):
    write(stdout, "|")
    for j in low(img[0])..high(img[0]):
        write(stdout, if img[i][j]: "#" else: ".")
        if j mod 10 == 9:
            write(stdout, "|")
    write(stdout, "\n")
    if i mod 10 == 9:
        for j in low(img[0])..high(img[0]):
            write(stdout, "-")
        for j in 0..12:
            write(stdout, "-")
        write(stdout, "\n")

echo "Part 1 check: "
echo placement[0][0].id
echo placement[0][11].id
echo placement[11][0].id
echo placement[11][11].id
var p = 1
p *= (int)placement[0][0].id
p *= (int)placement[0][11].id
p *= (int)placement[11][0].id
p *= (int)placement[11][11].id
echo p

### Part 2
echo "Part 2"

const N1 = 95

proc transform1(t: array[0..N1, array[0..N1, bool]], orn: Orientation): array[0..N1, array[0..N1, bool]] =
    var t1: array[0..N1, array[0..N1, bool]]
    for i in low(t1)..high(t1):
        for j in low(t1[0])..high(t1[0]):
            case orn
            of R0: t1[i][j] = t[i][j]
            of R90: t1[j][N1-i] = t[i][j]
            of R180: t1[N1-i][N1-j] = t[i][j]
            of R270: t1[N1-j][i] = t[i][j]
            of RH: t1[N1-i][j] = t[i][j]
            of RV: t1[i][N1-j] = t[i][j]
            of RTL: t1[j][i] = t[i][j]
            of RTR: t1[N1-j][N1-i] = t[i][j]
    return t1

var img1: array[0..N1, array[0..N1, bool]]
for i in 0..N-1:
    for j in 0..N-1:
        var (id, orn) = placement[i][j]
        if id == 0:
            continue
        var t1 = transform(tiles[id], inv[orn])
        for a in 0..7:
            for b in 0..7:
                img1[i*8+a][j*8+b] = t1[a+1][b+1]

var seaMonsterTemplate: seq[Offset] = @[(0,1), (1,2), (4,2), (5,1), (6,1), (7,2), (10,2), (11,1), (12,1), (13,2), (16,2),
                                        (17,1), (18,0), (18,1), (19,1)]

proc seaMonsterAt(img: array[0..N1, array[0..N1, bool]], i, j: int): bool =
    for (x,y) in seaMonsterTemplate:
        if i+y > N1 or j+x > N1:
            return false
        if not img[i+y][j+x]:
            return false
    return true

proc maskSeaMonsterAt(img: var array[0..N1, array[0..N1, bool]], i: int, j: int) =
    for (x,y) in seaMonsterTemplate:
        img[i+y][j+x] = false

var monsterOrn: Orientation
var seaMonsters: seq[Offset]
for orn in @[R0, R90, R180, R270, RH, RV, RTL, RTR]:
    var img2 = transform1(img1, orn)
    echo "Using ", orn
    for i in low(img2)..high(img2):
        for j in low(img2[0])..high(img2[0]):
            if seaMonsterAt(img2, i, j):
                echo "  Sea monster at (", i, ", ", j, ")"
                seaMonsters.add((j, i))
                monsterOrn = orn

var fimg = transform1(img1, monsterOrn)
for monster in seaMonsters:
    var (x,y) = monster
    maskSeaMonsterAt(fimg, y, x)
var nWaves = 0
for i in 0..N1:
    for j in 0..N1:
        if fimg[i][j]:
            nWaves += 1
echo nWaves