advent-of-code

Perserverance, or the lack thereof

git clone git://git.shimmy1996.com/advent-of-code.git

main.go (7066B)

    1 package main
    2 
    3 import (
    4 	"bufio"
    5 	"fmt"
    6 	"os"
    7 	"regexp"
    8 	"strconv"
    9 )
   10 
   11 const (
   12 	LIT    = 1
   13 	DARK   = 0
   14 	TOP    = 0
   15 	LEFT   = 1
   16 	BOTTOM = 2
   17 	RIGHT  = 3
   18 )
   19 
   20 type Tile struct {
   21 	id   int
   22 	size int
   23 	v    []int
   24 }
   25 
   26 func (this Tile) get(x, y int) int {
   27 	return this.v[x*this.size+y]
   28 }
   29 
   30 func (this Tile) set(x, y, val int) {
   31 	this.v[x*this.size+y] = val
   32 }
   33 
   34 func (this Tile) computeBorder() [4]int {
   35 	top, left, bottom, right := 0, 0, 0, 0
   36 	for i := 0; i < this.size; i++ {
   37 		top <<= 1
   38 		top += this.get(0, i)
   39 		left <<= 1
   40 		left += this.get(i, 0)
   41 		bottom <<= 1
   42 		bottom += this.get(this.size-1, i)
   43 		right <<= 1
   44 		right += this.get(i, this.size-1)
   45 	}
   46 	res := [4]int{top, left, bottom, right}
   47 	for i, _ := range res {
   48 		// Disambiguate by picking the larger between flipped versions.
   49 		res[i] = max(res[i], reverseBit(res[i], this.size))
   50 	}
   51 	return res
   52 }
   53 
   54 func (this Tile) rotate(rot int) (new Tile) {
   55 	// Rotate clockwise rot*90 degrees.
   56 	new = Tile{this.id, this.size, make([]int, this.size*this.size)}
   57 	for x := 0; x < this.size; x++ {
   58 		for y := 0; y < this.size; y++ {
   59 			xNew, yNew := x, y
   60 			for i := 0; i < rot%4; i++ {
   61 				xNew, yNew = yNew, this.size-1-xNew
   62 			}
   63 			new.set(xNew, yNew, this.get(x, y))
   64 		}
   65 	}
   66 	return new
   67 }
   68 
   69 func (this Tile) flip(flp int) (new Tile) {
   70 	// Flip left to right flp times.
   71 	new = Tile{this.id, this.size, make([]int, this.size*this.size)}
   72 	for x := 0; x < this.size; x++ {
   73 		for y := 0; y < this.size; y++ {
   74 			xNew, yNew := x, y
   75 			for i := 0; i < flp%2; i++ {
   76 				xNew, yNew = xNew, this.size-1-yNew
   77 			}
   78 			new.set(xNew, yNew, this.get(x, y))
   79 		}
   80 	}
   81 	return new
   82 }
   83 
   84 func (this Tile) toString() (res []string) {
   85 	for x := 0; x < this.size; x++ {
   86 		row := ""
   87 		for y := 0; y < this.size; y++ {
   88 			switch this.get(x, y) {
   89 			case LIT:
   90 				row += "#"
   91 			case DARK:
   92 				row += "."
   93 			}
   94 		}
   95 		res = append(res, row)
   96 	}
   97 	return
   98 }
   99 
  100 func reverseBit(x int, size int) (res int) {
  101 	for i := 0; i < size; i++ {
  102 		res <<= 1
  103 		res += x & 1
  104 		x >>= 1
  105 	}
  106 	return
  107 }
  108 
  109 func max(x int, y int) int {
  110 	if x > y {
  111 		return x
  112 	} else {
  113 		return y
  114 	}
  115 }
  116 
  117 func readInput(filename string) (res []Tile) {
  118 	file, _ := os.Open(filename)
  119 	defer file.Close()
  120 
  121 	matcher := regexp.MustCompile(`Tile ([0-9]{4}):`)
  122 	scanner := bufio.NewScanner(file)
  123 	for scanner.Scan() {
  124 		line := scanner.Text()
  125 		if line == "" {
  126 			continue
  127 		}
  128 		matched := matcher.FindStringSubmatch(line)
  129 		id, _ := strconv.Atoi(matched[1])
  130 		v := []int{}
  131 		size := len(line)
  132 		for i := 0; i < size; i++ {
  133 			scanner.Scan()
  134 			line := scanner.Text()
  135 			for _, ch := range line {
  136 				switch ch {
  137 				case '#':
  138 					v = append(v, LIT)
  139 				case '.':
  140 					v = append(v, DARK)
  141 				}
  142 			}
  143 		}
  144 		res = append(res, Tile{id, size, v})
  145 	}
  146 	return
  147 }
  148 
  149 func main() {
  150 	input := readInput("./input.txt")
  151 	// 7901522557967
  152 	fmt.Println(part1(input))
  153 	// 2476
  154 	fmt.Println(part2(input))
  155 }
  156 
  157 func countBorders(tiles []Tile) (res map[int]int) {
  158 	res = map[int]int{}
  159 	for _, t := range tiles {
  160 		for _, v := range t.computeBorder() {
  161 			res[v] += 1
  162 		}
  163 	}
  164 	return
  165 }
  166 
  167 func part1(input []Tile) (res int64) {
  168 	// Shared borders are unique, i.e. no more than 1 pair.
  169 	borderCount := countBorders(input)
  170 	// Angle tiles only have 2 shared borders.
  171 	angleTiles := []int{}
  172 	for _, t := range input {
  173 		sharedCount := 0
  174 		for _, v := range t.computeBorder() {
  175 			sharedCount += borderCount[v] / 2
  176 		}
  177 		if sharedCount == 2 {
  178 			angleTiles = append(angleTiles, t.id)
  179 		}
  180 	}
  181 	res = 1
  182 	for i := 0; i < 4; i++ {
  183 		res *= int64(angleTiles[i])
  184 	}
  185 	return
  186 }
  187 
  188 func assembleImage(tiles []Tile) (res Tile) {
  189 	borderCount := countBorders(tiles)
  190 	idMap := map[int]Tile{}
  191 	for _, v := range tiles {
  192 		idMap[v.id] = v
  193 	}
  194 	// Find correct arrangment of tile ids.
  195 	used := map[int]bool{}
  196 	image := [][]int{}
  197 	row := []int{}
  198 	leftReq, topReq := 0, 0
  199 	for {
  200 		// Find next tile according to left and top borders.
  201 		found := false
  202 		for id, t := range idMap {
  203 			if used[id] {
  204 				continue
  205 			}
  206 			leftSide, topSide := -1, -1
  207 			for side, v := range t.computeBorder() {
  208 				// 0 means unique borders not shared with others.
  209 				if borderCount[v] == 1 {
  210 					v = 0
  211 				}
  212 				if leftSide == -1 && v == leftReq {
  213 					leftSide = side
  214 				} else if topSide == -1 && v == topReq {
  215 					topSide = side
  216 				}
  217 			}
  218 			if leftSide != -1 && topSide != -1 {
  219 				// Add to image after correctly orienting it.
  220 				found = true
  221 				// Use top to compute rotation.
  222 				t = t.rotate(topSide)
  223 				// Use left to compute flip.
  224 				if left := t.computeBorder()[LEFT]; (leftReq != 0 && left != leftReq) ||
  225 					(leftReq == 0 && borderCount[left] != 1) {
  226 					t = t.flip(1)
  227 				}
  228 				idMap[id] = t
  229 				row = append(row, id)
  230 				used[id] = true
  231 				break
  232 			}
  233 		}
  234 		if !found {
  235 			panic("No matching tile found!")
  236 		}
  237 		// Update requirements.
  238 		lastBorder := idMap[row[len(row)-1]].computeBorder()
  239 		if borderCount[lastBorder[BOTTOM]] == 1 &&
  240 			borderCount[lastBorder[RIGHT]] == 1 {
  241 			// Image finished.
  242 			image = append(image, row)
  243 			break
  244 		} else if borderCount[lastBorder[RIGHT]] == 1 {
  245 			// Start new row.
  246 			image = append(image, row)
  247 			row = []int{}
  248 			leftReq = 0
  249 			topReq = idMap[image[len(image)-1][0]].computeBorder()[BOTTOM]
  250 		} else {
  251 			// Start next in row.
  252 			leftReq = lastBorder[RIGHT]
  253 			if len(image) == 0 {
  254 				topReq = 0
  255 			} else {
  256 				topReq = idMap[image[len(image)-1][len(row)]].computeBorder()[BOTTOM]
  257 			}
  258 		}
  259 	}
  260 	// Piece together full image. Resulting image is always square.
  261 	tileSize := idMap[image[0][0]].size
  262 	pixels := []int{}
  263 	for i := 0; i < len(image); i++ {
  264 		for x := 1; x < tileSize-1; x++ {
  265 			for j := 0; j < len(image[0]); j++ {
  266 				for y := 1; y < tileSize-1; y++ {
  267 					pixels = append(pixels, idMap[image[i][j]].get(x, y))
  268 				}
  269 			}
  270 		}
  271 	}
  272 	return Tile{0, (tileSize - 2) * len(image), pixels}
  273 }
  274 
  275 func findMonster(image []string, monsterRegex []*regexp.Regexp, monsterLen int) (res int) {
  276 	for x := 0; x <= len(image)-len(monsterRegex); x++ {
  277 		for yMax := monsterLen; yMax < len(image[0]); {
  278 			// Match per sliding window of same size so we have at most 1 match.
  279 			matchCount := 0
  280 			for i := 0; i < len(monsterRegex); i++ {
  281 				matchCount += len(monsterRegex[i].FindAllStringIndex(image[x+i][(yMax-monsterLen):yMax], -1))
  282 			}
  283 			if matchCount == len(monsterRegex) {
  284 				res += 1
  285 				// Sea monters don't overlap, so we can do this; makes counting easier too.
  286 				yMax += monsterLen
  287 			}
  288 			yMax += 1
  289 		}
  290 	}
  291 	return
  292 }
  293 
  294 func part2(input []Tile) (res int) {
  295 	monsterRegex := []*regexp.Regexp{
  296 		regexp.MustCompile(`..................#.`),
  297 		regexp.MustCompile(`#....##....##....###`),
  298 		regexp.MustCompile(`.#..#..#..#..#..#...`),
  299 	}
  300 	monsterLen := 20
  301 	monsterLitCount := 15 // Each sea monster has 15 '#'s.
  302 	image := assembleImage(input)
  303 	litSum := 0
  304 	for _, p := range image.v {
  305 		litSum += p
  306 	}
  307 	// Try all orientations of the image.
  308 	for rot := 0; rot <= 3; rot++ {
  309 		for flp := 0; flp <= 1; flp++ {
  310 			image := image.rotate(rot).flip(flp).toString()
  311 			monsterCount := findMonster(image, monsterRegex, monsterLen)
  312 			if monsterCount > 0 {
  313 				return litSum - monsterCount*monsterLitCount
  314 			}
  315 		}
  316 	}
  317 	return
  318 }