245 lines
6.7 KiB
Go
245 lines
6.7 KiB
Go
|
package main
|
||
|
|
|
||
|
|
import (
|
||
|
|
"bufio"
|
||
|
|
"fmt"
|
||
|
|
"math"
|
||
|
|
"os"
|
||
|
|
"strconv"
|
||
|
|
"strings"
|
||
|
|
"time"
|
||
|
|
)
|
||
|
|
|
||
|
|
func main() {
|
||
|
|
start := time.Now()
|
||
|
|
partOne()
|
||
|
|
duration := time.Since(start)
|
||
|
|
partTwo()
|
||
|
|
duration2 := time.Since(start)
|
||
|
|
fmt.Printf("p1: %s, p2: %s\n", duration, duration2-duration)
|
||
|
|
}
|
||
|
|
|
||
|
|
type tile struct {
|
||
|
|
id int
|
||
|
|
neighbors map[int]int // key matches the edge key, so we can skip existing matches if we want
|
||
|
|
edges map[int]string
|
||
|
|
image map[int]string
|
||
|
|
}
|
||
|
|
|
||
|
|
// edges are always defined clockwise starting from 0:north
|
||
|
|
// as long as there's only ever one match for an edge, I don't _think_ I need to keep track of piece orientation...?
|
||
|
|
func parseTile(header string, body []string) tile {
|
||
|
|
id, _ := strconv.Atoi(strings.Trim(header, "Tile :"))
|
||
|
|
t := tile{
|
||
|
|
id: id,
|
||
|
|
neighbors: make(map[int]int, 4),
|
||
|
|
edges: make(map[int]string, 4),
|
||
|
|
image: make(map[int]string, 8),
|
||
|
|
}
|
||
|
|
// make edges and extract picture data...
|
||
|
|
left := []byte{}
|
||
|
|
right := []byte{}
|
||
|
|
for i := range body {
|
||
|
|
left = append(left, body[i][0])
|
||
|
|
right = append(right, body[i][9])
|
||
|
|
// image has edges removed; still want 0-indexed for sanity later!
|
||
|
|
if i != 0 && i != 9 {
|
||
|
|
t.image[i-1] = body[i-1][1:9]
|
||
|
|
}
|
||
|
|
}
|
||
|
|
t.edges[0] = body[0]
|
||
|
|
t.edges[1] = string(right)
|
||
|
|
t.edges[2] = body[9]
|
||
|
|
t.edges[3] = string(left)
|
||
|
|
return t
|
||
|
|
}
|
||
|
|
|
||
|
|
// return is match, inverted
|
||
|
|
func testEdge(one, two string) (bool, bool) {
|
||
|
|
if one == two {
|
||
|
|
return true, false
|
||
|
|
}
|
||
|
|
// go doesn't have a built-in "string reversal" method, so we just check it the hard way
|
||
|
|
// 9 is our magic number for a 10-character string, which we know they all are.
|
||
|
|
// This might not be 100% sound for unicode (byte != rune), but our string is ASCII so it's... fine.
|
||
|
|
for i := range one {
|
||
|
|
if one[i] != two[9-i] {
|
||
|
|
return false, false
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return true, true
|
||
|
|
}
|
||
|
|
|
||
|
|
// this is wasteful in that it happily checks edges that we've already determined neighbors for,
|
||
|
|
// but it's performant enough that I don't really care to fix it
|
||
|
|
func findPartners(id int, tiles map[int]tile) map[int]tile {
|
||
|
|
currentTile := tiles[id]
|
||
|
|
for tile := range tiles {
|
||
|
|
if tile != id {
|
||
|
|
for edgeID := range tiles[tile].edges {
|
||
|
|
for i := range currentTile.edges {
|
||
|
|
if ok, _ := testEdge(tiles[tile].edges[edgeID], currentTile.edges[i]); ok {
|
||
|
|
tiles[tile].neighbors[edgeID] = tiles[id].id
|
||
|
|
tiles[id].neighbors[i] = tiles[tile].id
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return tiles
|
||
|
|
}
|
||
|
|
|
||
|
|
// Starting from a corner, we can "walk" through the image by:
|
||
|
|
// stepping to the next tile in a known direction
|
||
|
|
// checking where _that_ tile thinks we came from
|
||
|
|
// then re-orienting ourselves and stepping again.
|
||
|
|
// For example, if we take a corner and go to its 0 neighbor,
|
||
|
|
// and that neighbor thinks our previous tile was 3,
|
||
|
|
// a "straight line" along the edge would be 1. Repeat as necessary until you hit an edge.
|
||
|
|
// Once we hit an edge, return to the start of the row,
|
||
|
|
// step to its 90° neighbor, then walk parallel to the initial edge.
|
||
|
|
// Repeat until we reach the far corner.
|
||
|
|
// Additionally, we need to "line up" the edges, so there's some alignment checking that has to happen.
|
||
|
|
func mergeTiles(corner int, tiles map[int]tile) []string {
|
||
|
|
// just to make the counting a little easier
|
||
|
|
sideLength := int(math.Sqrt(float64(len(tiles))))
|
||
|
|
result := make([]string, sideLength*8)
|
||
|
|
headOfRow := tiles[corner]
|
||
|
|
currentRowDirection := 0
|
||
|
|
nextRowDirection := 0
|
||
|
|
// what an absurd way to "pick" between two keys in a two-key map
|
||
|
|
for i := range headOfRow.neighbors {
|
||
|
|
if currentRowDirection == 0 {
|
||
|
|
currentRowDirection = i
|
||
|
|
} else if nextRowDirection == 0 {
|
||
|
|
nextRowDirection = i
|
||
|
|
}
|
||
|
|
}
|
||
|
|
currentTile := tiles[corner]
|
||
|
|
image := imageFromEdge(currentTile, 0)
|
||
|
|
for row, s := range image {
|
||
|
|
result[row] = result[row] + s
|
||
|
|
}
|
||
|
|
for i := 0; i < sideLength; i = i + 1 {
|
||
|
|
nextID := currentTile.neighbors[currentRowDirection]
|
||
|
|
for e, id := range tiles[nextID].neighbors {
|
||
|
|
if id == currentTile.id {
|
||
|
|
_, invert := testEdge(currentTile.edges[currentRowDirection], tiles[nextID].edges[e])
|
||
|
|
image := imageFromEdge(tiles[nextID], (e+1)%4)
|
||
|
|
if !invert {
|
||
|
|
for row, s := range image {
|
||
|
|
result[row] = result[row] + s
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
for row, s := range image {
|
||
|
|
result[7-row] = result[7-row] + s
|
||
|
|
}
|
||
|
|
}
|
||
|
|
currentRowDirection = (e + 2) % 4 // flip 180 around the compass
|
||
|
|
}
|
||
|
|
}
|
||
|
|
currentTile = tiles[nextID]
|
||
|
|
}
|
||
|
|
return result
|
||
|
|
}
|
||
|
|
|
||
|
|
// returns the image "rotated" so that the provided edge is on "top" (the 0 position)
|
||
|
|
func imageFromEdge(t tile, edge int) map[int]string {
|
||
|
|
if edge == 1 {
|
||
|
|
newImage := make(map[int]string, 8)
|
||
|
|
for i := 0; i < 8; i = i + 1 {
|
||
|
|
b := []byte{t.image[0][7-i], t.image[1][7-i], t.image[2][7-i], t.image[3][7-i], t.image[4][7-i], t.image[5][7-i], t.image[6][7-i], t.image[7][7-i]}
|
||
|
|
newImage[i] = string(b)
|
||
|
|
}
|
||
|
|
return newImage
|
||
|
|
}
|
||
|
|
if edge == 2 {
|
||
|
|
newImage := make(map[int]string, 8)
|
||
|
|
for i := 0; i < 8; i = i + 1 {
|
||
|
|
b := []byte{t.image[7-i][7], t.image[7-i][6], t.image[7-i][5], t.image[7-i][4], t.image[7-i][3], t.image[7-i][2], t.image[7-i][1], t.image[7-i][0]}
|
||
|
|
newImage[i] = string(b)
|
||
|
|
}
|
||
|
|
return newImage
|
||
|
|
}
|
||
|
|
if edge == 3 {
|
||
|
|
newImage := make(map[int]string, 8)
|
||
|
|
for i := 0; i < 8; i = i + 1 {
|
||
|
|
b := []byte{t.image[7][i], t.image[6][i], t.image[5][i], t.image[4][i], t.image[3][i], t.image[2][i], t.image[1][i], t.image[0][i]}
|
||
|
|
newImage[i] = string(b)
|
||
|
|
}
|
||
|
|
return newImage
|
||
|
|
}
|
||
|
|
// edge == 0 does nothing
|
||
|
|
return t.image
|
||
|
|
}
|
||
|
|
|
||
|
|
func partOne() {
|
||
|
|
f, _ := os.Open("input")
|
||
|
|
reader := bufio.NewReader(f)
|
||
|
|
scanner := bufio.NewScanner(reader)
|
||
|
|
|
||
|
|
buffer := []string{}
|
||
|
|
tiles := make(map[int]tile)
|
||
|
|
|
||
|
|
for scanner.Scan() {
|
||
|
|
line := scanner.Text()
|
||
|
|
if line == "" {
|
||
|
|
tile := parseTile(buffer[0], buffer[1:])
|
||
|
|
tiles[tile.id] = tile
|
||
|
|
buffer = []string{}
|
||
|
|
} else {
|
||
|
|
buffer = append(buffer, line)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
// catch that last tile
|
||
|
|
// weirdly, I'd think the trailing newline in the input would have done this for us
|
||
|
|
tile := parseTile(buffer[0], buffer[1:])
|
||
|
|
tiles[tile.id] = tile
|
||
|
|
|
||
|
|
corners := 1
|
||
|
|
for id := range tiles {
|
||
|
|
tiles = findPartners(id, tiles)
|
||
|
|
if len(tiles[id].neighbors) == 2 {
|
||
|
|
corners = corners * id
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
fmt.Println(corners)
|
||
|
|
}
|
||
|
|
|
||
|
|
func partTwo() {
|
||
|
|
f, _ := os.Open("testinput")
|
||
|
|
reader := bufio.NewReader(f)
|
||
|
|
scanner := bufio.NewScanner(reader)
|
||
|
|
|
||
|
|
buffer := []string{}
|
||
|
|
tiles := make(map[int]tile)
|
||
|
|
|
||
|
|
for scanner.Scan() {
|
||
|
|
line := scanner.Text()
|
||
|
|
if line == "" {
|
||
|
|
tile := parseTile(buffer[0], buffer[1:])
|
||
|
|
tiles[tile.id] = tile
|
||
|
|
buffer = []string{}
|
||
|
|
} else {
|
||
|
|
buffer = append(buffer, line)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
// catch that last tile
|
||
|
|
tile := parseTile(buffer[0], buffer[1:])
|
||
|
|
tiles[tile.id] = tile
|
||
|
|
|
||
|
|
corner := 0
|
||
|
|
for id := range tiles {
|
||
|
|
tiles = findPartners(id, tiles)
|
||
|
|
// grab a corner to start the merge from
|
||
|
|
if len(tiles[id].neighbors) == 2 && corner == 0 {
|
||
|
|
corner = id
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
for _, line := range mergeTiles(corner, tiles) {
|
||
|
|
fmt.Println(line)
|
||
|
|
}
|
||
|
|
}
|