day9.go

package main

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

func main() {
	fmt.Println("pt1:", part1(input1))
	fmt.Println("pt1:", part1(input2))
	fmt.Println()
	fmt.Println("pt2:", part2(input1))
	fmt.Println("pt2:", part2(input2))
}

type point struct {
	x, y int
}

func (p point) isConnected(h point) bool {
	return abs(p.x-h.x) < 2 && abs(p.y-h.y) < 2
}

// follow moves the tail in the direction of the head.
// Tail always moves 1 square horizontally or vertically if it is 2 squares
// away from the head.
// Tail will move diagonally if both x and y of the tail is not the same as
// the head.
func (p point) follow(h point) point {
	if p.isConnected(h) {
		return p
	}

	x := h.x - p.x
	y := h.y - p.y

	return point{
		x: p.x + int(math.Copysign(float64(min(abs(x), 1)), float64(x))),
		y: p.y + int(math.Copysign(float64(min(abs(y), 1)), float64(y))),
	}
}

func part1(input string) int {
	var head, tail point

	cache := make(map[point]bool)
	cache[tail] = true

	rows := parse(input)
	for _, row := range rows {
		parts := strings.Fields(row)
		dir, n := parts[0], toInt(parts[1])
		for i := 0; i < n; i++ {
			switch dir {
			case "U":
				head.y--
			case "D":
				head.y++
			case "L":
				head.x--
			case "R":
				head.x++
			}
			tail = tail.follow(head)
			cache[tail] = true
		}
	}
	return len(cache)
}

func part2(input string) int {
	cache := make(map[point]bool)
	ropes := make([]point, 10)
	cache[ropes[0]] = true

	rows := parse(input)
	for _, row := range rows {
		parts := strings.Fields(row)
		dir, n := parts[0], toInt(parts[1])
		for i := 0; i < n; i++ {
			switch dir {
			case "U":
				ropes[0].y--
			case "D":
				ropes[0].y++
			case "L":
				ropes[0].x--
			case "R":
				ropes[0].x++
			}
			for r := 1; r < len(ropes); r++ {
				head := ropes[r-1]
				tail := ropes[r]
				tail = tail.follow(head)
				ropes[r] = tail
			}
			//draw(ropes)
			cache[ropes[len(ropes)-1]] = true
		}
	}
	return len(cache)
}

func parse(input string) []string {
	return strings.Split(input, "\n")
}

func toInt(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		panic(err)
	}
	return n
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func draw(points []point) {
	minX, minY := math.MaxInt, math.MaxInt
	maxX, maxY := 0, 0
	for _, p := range points {
		if p.x > maxX {
			maxX = p.x
		}
		if p.x < minX {
			minX = p.x
		}
		if p.y > maxY {
			maxY = p.y
		}
		if p.y < minY {
			minY = p.y
		}
	}

	res := make([][]string, maxY-minY+1)
	for i := range res {
		res[i] = make([]string, maxX-minX+1)
		for j := range res[i] {
			res[i][j] = "."
		}
	}

	for i, p := range points {
		x := p.x - minX
		y := p.y - minY
		if res[y][x] == "." {
			if i == 0 {
				res[y][x] = "H"
			} else {
				res[y][x] = fmt.Sprint(i)
			}

		}
	}
	fmt.Println()
	for _, row := range res {
		fmt.Println(strings.Join(row, ""))
	}
}

var input1 = `R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2`
var input2 = `D 1
U 2
R 2
U 1
R 1
U 2
L 2
D 1
L 2
R 1
L 1
R 1
U 2
D 2
L 2
R 2
L 2
R 1
L 1
D 1
U 1
R 1
U 2
D 1
U 1
D 1
R 2
D 1
U 1
R 1
L 2
R 2
U 2
R 2
L 2
R 2
U 2
D 2
R 1
U 2
D 2
U 2
D 1
L 1
D 1
L 1
R 2
D 2
R 2
D 1
R 2
L 1
R 1
L 2
D 2
U 1
D 1
R 2
L 2
D 2
L 2
D 2
L 1
R 2
L 1
D 1
L 2
D 1
U 1
R 1
U 1
R 2
D 2
R 1
U 2
D 1
L 2
D 2
L 1
D 1
L 1
D 1
R 1
L 1
U 1
D 2
U 1
D 2
R 1
D 2
L 2
U 1
L 1
R 1
D 1
U 1
D 1
R 1
U 2
L 1
D 1
U 2
R 2
D 2
R 1
D 1
R 1
L 1
R 2
U 1
D 1
L 1
U 3
L 2
U 2
L 2
D 2
L 1
R 3
D 1
U 1
L 3
D 3
U 1
L 2
U 1
R 2
U 3
D 2
L 3
U 2
R 2
D 2
U 1
R 1
L 3
D 2
L 3
D 1
U 3
R 3
U 3
D 3
U 3
L 3
U 1
D 1
U 1
D 3
R 3
D 3
U 3
R 3
L 3
R 2
U 3
D 3
L 1
R 2
D 2
U 1
R 1
L 2
D 3
R 3
D 1
U 1
D 1
U 2
D 1
R 1
D 2
R 2
L 1
D 2
L 1
R 2
L 3
R 3
L 1
U 3
R 3
U 3
D 1
L 3
R 1
L 1
R 2
L 1
U 2
R 1
D 2
R 3
L 3
R 2
U 3
R 3
L 1
R 1
L 1
U 1
L 2
R 2
L 3
D 2
L 2
R 3
D 3
U 1
L 2
D 3
U 3
D 3
R 1
U 1
L 2
U 1
L 1
R 1
U 3
L 2
R 1
D 4
R 3
D 3
L 3
D 4
R 4
L 3
R 2
D 2
R 4
U 2
D 3
L 1
R 2
U 4
R 3
D 2
U 1
D 4
R 1
D 3
U 3
L 2
R 2
L 3
R 3
L 4
D 3
L 2
U 3
L 1
R 2
D 4
R 3
U 3
L 2
U 3
D 2
L 4
D 4
L 4
U 4
R 1
D 1
R 3
U 3
R 3
D 3
L 1
U 1
R 3
L 2
R 2
D 2
R 4
U 4
L 4
D 3
L 2
R 4
L 2
D 1
L 2
R 4
U 2
L 2
U 3
L 4
R 2
L 4
D 2
L 1
D 4
L 3
U 2
D 1
R 4
U 2
D 1
R 4
D 4
U 3
R 3
U 4
L 1
D 3
U 1
D 3
R 2
U 1
R 3
L 4
R 1
L 4
D 3
R 4
U 2
L 1
D 4
L 2
R 4
L 2
R 3
L 3
U 2
R 3
L 2
R 1
D 4
L 3
D 3
L 5
D 1
R 3
D 4
L 4
R 2
D 5
R 2
L 2
D 5
U 2
D 1
U 2
D 3
L 2
D 1
L 3
U 1
D 3
R 2
U 4
R 5
D 5
U 3
R 1
D 5
U 1
D 4
R 1
U 4
D 4
R 4
U 5
D 4
R 1
L 1
D 5
L 1
D 4
U 1
D 2
U 1
D 1
R 1
D 2
R 2
D 1
L 5
R 3
L 4
D 3
R 5
D 4
U 2
R 2
U 2
D 2
U 5
L 4
D 5
L 5
R 3
D 2
U 4
D 2
L 3
R 2
L 1
U 2
R 4
L 5
R 4
D 1
U 5
D 4
L 5
R 2
U 4
D 3
L 3
D 3
L 1
U 5
L 4
R 1
U 5
D 4
R 2
L 1
D 2
R 3
L 2
R 5
D 5
R 2
L 1
U 3
D 2
L 1
U 1
R 4
U 1
D 1
U 1
R 2
U 3
R 4
L 4
R 1
U 3
R 3
D 1
L 3
R 4
L 1
U 5
D 6
U 2
L 4
D 2
U 1
D 4
R 5
L 2
R 6
L 6
U 1
D 4
L 3
D 5
U 4
L 4
R 2
D 2
L 3
D 1
U 6
L 6
R 2
D 2
U 3
L 6
R 1
U 5
R 5
U 5
D 1
L 2
U 1
R 1
D 5
L 6
R 1
D 4
R 3
L 3
D 2
U 5
D 6
U 3
D 6
U 4
L 2
R 1
U 5
D 2
L 1
D 4
U 1
R 2
L 2
R 4
D 1
L 6
D 5
L 6
R 6
L 3
U 5
R 4
D 4
L 3
D 2
L 1
R 4
U 3
R 2
U 2
R 5
D 1
U 5
D 4
R 4
L 5
D 5
U 3
R 1
U 4
L 5
U 1
D 2
U 4
D 4
L 1
U 2
L 3
U 5
R 1
L 5
U 1
R 4
D 2
L 6
U 6
R 6
U 5
R 6
U 6
L 5
U 1
L 5
D 3
R 1
D 4
L 3
D 7
U 1
D 4
R 2
U 4
D 4
U 7
D 3
L 3
D 3
R 4
D 7
R 4
D 5
U 3
L 5
R 5
D 5
L 2
R 3
L 2
R 4
U 2
L 4
U 7
L 2
U 6
D 3
U 6
R 2
D 2
U 6
L 2
R 4
U 5
D 2
R 4
L 2
D 2
R 1
D 3
R 1
D 3
U 4
D 2
L 4
D 1
L 5
U 1
R 2
D 3
U 4
D 4
L 5
R 2
D 2
U 1
D 7
L 7
R 2
L 6
D 4
R 7
L 3
U 2
D 2
U 4
L 5
D 4
U 4
R 5
L 5
D 2
R 5
L 7
U 1
D 7
L 3
R 4
L 5
D 5
L 2
R 5
L 3
R 2
L 4
R 1
D 3
L 5
R 2
D 4
U 3
R 3
L 5
D 3
R 1
D 5
R 5
L 1
D 6
R 5
D 4
U 2
L 4
U 1
D 3
L 2
D 7
R 4
L 1
U 6
R 8
L 2
U 2
R 1
U 7
D 6
L 7
R 3
U 5
R 4
L 8
D 2
R 4
U 8
L 6
R 1
L 7
D 5
L 3
R 6
U 1
D 7
L 2
U 7
R 1
U 6
L 3
R 8
D 5
L 4
R 4
L 6
D 6
R 3
L 2
U 5
R 3
D 1
R 7
L 1
U 8
D 2
U 3
D 1
L 2
U 6
L 1
U 4
R 6
U 7
R 1
D 1
U 8
R 1
D 7
L 1
U 4
D 1
U 2
R 8
U 1
D 6
R 1
U 1
R 5
L 7
R 3
D 3
U 8
L 6
D 7
U 8
L 4
R 1
L 7
U 4
D 3
L 3
R 6
D 3
U 8
L 5
D 8
L 1
U 7
R 6
L 5
U 8
R 2
L 8
R 7
L 8
U 7
D 7
U 3
D 4
U 8
D 5
U 3
L 4
D 4
U 8
R 7
U 7
L 7
R 4
L 1
D 8
R 9
D 4
R 8
L 5
R 9
U 5
D 1
L 5
D 7
U 3
R 5
U 1
R 3
U 2
D 9
U 5
R 3
U 4
R 3
D 4
U 7
D 9
L 7
D 3
U 1
R 3
U 4
L 3
R 8
L 3
U 8
R 6
L 6
D 7
L 7
D 4
L 3
U 5
L 2
R 5
D 3
U 6
L 9
R 9
D 9
U 9
R 4
D 8
R 8
D 5
L 7
U 2
R 4
L 8
R 4
L 2
R 3
L 7
R 1
U 1
L 5
D 5
R 9
D 8
U 7
L 3
R 5
D 1
U 1
R 5
D 6
U 9
D 8
R 4
D 7
L 1
U 5
D 8
L 4
D 4
L 7
D 8
R 5
U 9
D 2
L 1
R 2
U 8
D 4
L 6
D 1
L 5
D 6
R 9
U 1
L 9
U 4
D 6
R 8
L 5
R 1
L 2
R 7
D 8
L 4
R 3
U 2
L 7
U 2
D 1
R 8
U 8
L 1
R 1
D 2
U 3
L 5
D 6
L 3
U 6
R 2
L 5
U 6
L 5
D 3
L 6
D 2
L 4
U 10
R 4
D 7
U 4
D 4
L 5
U 3
L 9
R 7
D 1
L 4
U 4
D 5
R 5
D 4
U 1
D 3
R 1
L 6
U 1
D 1
L 4
U 5
D 10
R 4
U 5
R 1
U 2
R 4
D 6
L 7
U 1
R 2
D 1
L 7
D 4
U 9
L 6
D 8
R 3
U 7
R 8
U 2
D 5
R 3
U 10
D 3
R 3
U 1
R 8
D 10
R 3
D 1
U 10
L 5
U 8
D 6
L 9
D 5
U 1
R 9
U 3
D 3
R 8
L 9
D 8
U 3
R 2
D 3
L 7
D 3
R 10
L 9
U 2
R 8
U 8
R 5
U 3
L 9
U 1
D 7
L 7
R 5
L 8
U 8
L 9
R 10
U 1
R 5
L 5
D 7
L 8
D 5
U 4
L 4
U 6
D 4
L 8
U 8
L 10
D 1
L 2
D 3
U 8
L 7
R 7
U 6
D 4
U 8
L 2
R 6
L 7
D 11
R 4
D 9
L 10
U 3
L 9
U 10
L 11
U 11
D 2
U 4
D 5
L 11
D 4
L 6
U 2
D 8
R 4
U 4
D 5
U 8
L 3
U 2
R 7
U 10
R 5
L 3
R 11
U 2
D 8
U 3
R 10
U 10
L 3
R 7
L 8
D 5
U 9
D 9
R 3
U 4
L 6
D 9
R 10
L 2
R 8
U 11
L 2
R 1
U 11
R 2
D 3
U 9
R 3
L 2
R 1
L 6
R 10
L 2
U 6
R 4
L 9
U 11
L 1
R 11
U 8
L 4
R 11
L 6
D 5
L 11
U 3
D 5
R 5
U 2
L 3
R 4
L 9
R 7
U 11
R 7
U 7
D 10
R 11
D 10
L 3
D 5
U 2
L 1
U 2
R 2
U 8
R 1
L 10
R 10
U 5
D 4
U 4
R 4
L 8
R 6
U 9
R 5
L 3
U 9
L 3
D 4
R 10
D 11
L 12
R 1
U 11
L 10
R 11
D 10
R 10
L 4
U 11
D 2
R 8
L 6
U 7
D 7
L 12
U 1
L 3
D 8
R 6
L 7
R 11
L 2
R 6
U 2
R 2
L 2
U 5
R 12
U 12
D 12
U 1
D 6
L 5
U 3
D 3
L 4
R 10
L 5
U 2
D 8
R 4
D 5
L 7
U 2
R 10
D 12
R 9
U 11
D 10
R 4
U 2
D 1
U 10
D 8
R 2
L 9
D 12
U 12
D 2
U 8
R 5
L 8
D 5
U 9
D 8
U 7
R 3
L 10
U 11
L 5
U 12
L 2
U 9
D 7
R 12
U 9
R 2
L 3
U 10
D 9
L 7
U 5
R 3
D 3
L 11
D 1
R 5
L 1
U 5
L 6
D 8
L 2
D 5
U 8
D 9
R 8
L 7
D 6
L 6
D 1
U 5
L 4
R 6
U 9
L 3
U 3
D 7
L 1
D 4
L 9
R 9
U 6
D 8
U 12
L 5
D 4
R 7
L 2
D 4
U 7
R 7
U 2
R 13
D 5
L 1
R 5
D 6
U 2
L 1
U 5
D 2
R 9
L 8
U 9
D 9
U 12
R 10
U 9
L 13
R 5
D 10
L 9
U 4
D 12
U 12
R 13
D 12
U 7
R 12
D 8
L 8
U 2
D 10
L 2
D 5
U 3
R 11
D 4
R 4
L 1
R 1
D 9
U 6
R 10
U 12
L 10
R 13
D 7
R 12
L 5
R 10
D 4
R 11
L 7
R 7
U 7
D 7
U 11
L 3
R 9
L 12
D 11
R 5
D 5
R 7
D 7
U 3
L 11
D 11
L 10
U 7
L 13
R 6
L 10
U 10
D 10
L 4
R 5
U 5
D 2
L 6
D 8
U 1
R 12
D 11
U 3
L 9
R 10
U 8
R 10
D 2
R 3
U 9
D 7
L 6
R 9
D 2
U 11
R 3
D 1
R 4
L 11
U 13
R 12
U 12
R 8
L 13
U 7
D 10
R 11
L 2
U 9
L 3
R 5
L 4
R 11
D 5
R 1
L 11
U 10
R 4
L 1
U 2
D 8
L 7
U 1
L 4
D 1
R 1
L 11
U 8
R 11
U 4
R 10
L 6
D 7
U 9
L 14
U 1
R 10
U 12
R 1
L 6
D 9
U 10
L 10
D 5
R 14
U 3
R 13
U 3
L 13
U 8
L 10
U 7
R 12
U 11
R 6
U 6
D 6
R 2
L 7
R 8
U 8
D 3
R 8
L 12
U 11
D 9
U 6
R 8
D 8
U 9
R 12
L 11
U 10
L 14
R 9
D 8
U 14
L 9
D 11
U 2
R 2
U 4
R 7
U 11
L 8
D 12
L 11
U 13
L 1
D 8
U 8
L 10
U 12
R 11
U 3
D 12
L 1
D 8
L 4
D 3
L 2
U 8
D 9
L 1
U 9
D 15
U 5
L 9
D 2
U 4
L 2
U 15
L 8
R 2
U 1
L 3
D 10
L 15
U 2
R 14
D 1
U 13
D 4
R 8
D 6
R 5
D 13
L 5
R 6
U 14
L 15
D 15
U 12
L 1
D 3
L 6
D 2
R 4
D 10
U 12
R 13
L 3
R 15
D 13
U 15
D 14
U 8
D 10
U 5
D 11
R 15
D 7
R 1
D 2
L 5
U 11
L 14
U 9
D 13
R 12
U 10
R 11
D 9
R 6
D 7
L 7
U 14
D 12
L 6
D 15
U 11
R 1
U 3
L 11
R 3
L 9
R 9
L 11
R 12
U 6
R 13
D 13
L 9
U 3
D 6
L 4
D 3
U 15
D 13
U 9
D 1
U 13
D 12
L 4
U 6
R 11
D 2
R 7
U 9
R 11
U 3
L 7
U 4
R 2
D 14
U 3
D 14
R 13
L 4
R 1
U 12
D 10
L 8
D 2
L 15
U 1
D 4
U 16
R 15
D 1
R 8
U 14
L 12
U 2
R 1
D 16
L 10
R 11
D 10
L 15
R 7
U 10
L 3
U 11
D 1
L 5
D 3
U 8
R 3
U 5
R 2
D 11
L 2
D 7
L 2
U 3
L 12
D 13
L 12
U 7
R 11
L 4
R 11
L 8
U 16
L 1
R 11
L 4
U 15
L 16
R 15
U 6
R 4
U 3
D 16
R 9
U 8
R 5
U 6
L 2
R 2
D 10
R 7
D 13
U 13
R 14
D 3
L 15
R 3
D 11
L 4
U 12
D 1
U 8
R 8
L 4
D 6
L 15
U 7
D 15
L 11
U 14
D 8
U 15
L 12
R 6
U 13
R 5
U 2
L 1
R 13
D 10
R 7
L 9
U 14
R 1
D 13
L 11
U 9
L 13
R 5
D 14
R 16
U 5
D 9
R 2
D 5
R 8
L 8
U 16
D 12
R 3
U 3
D 5
U 12
D 14
L 9
U 12
R 6
L 9
U 3
D 16
U 15
R 6
D 11
R 10
D 3
U 16
L 11
R 2
L 2
R 9
D 12
L 8
D 8
R 13
L 5
D 17
L 7
D 10
U 13
L 11
U 17
L 13
R 2
D 6
R 14
D 14
L 15
R 8
D 4
U 7
L 6
R 6
U 7
D 12
R 9
L 8
D 15
L 14
R 1
U 8
L 13
D 16
R 2
U 2
L 2
D 13
U 8
D 6
U 10
L 9
R 2
L 7
U 5
R 6
U 12
D 3
R 1
U 4
R 17
U 11
L 3
U 13
L 12
U 6
R 5
D 12
R 4
U 4
R 3
D 11
U 7
L 10
D 12
U 12
D 9
R 4
L 2
R 9
L 13
D 16
L 14
D 5
L 8
D 6
L 13
U 1
R 7
U 5
R 2
U 11
L 10
D 14
R 11
L 5
D 16
U 9
D 3
U 11
D 1
U 5
D 3
U 8
L 1
D 1
U 5
L 17
D 9
L 14
R 8
D 15
R 10
U 4
R 1
U 3
R 5
L 13
D 6
L 15
U 10
L 5
R 14
L 1
R 6
D 10
L 13
D 3
L 1
U 10
D 6
R 16
D 6
R 4
D 9
U 9
D 4
R 1
D 10
R 7
D 14
R 10
D 14
U 14
D 15
R 11
L 16
D 18
R 6
U 8
D 18
R 18
D 14
U 9
R 18
U 14
L 18
U 1
R 14
D 1
U 6
R 3
L 13
D 4
L 9
D 2
U 5
D 6
U 9
L 13
U 12
R 11
D 17
U 17
L 8
U 15
R 16
L 9
D 2
R 16
D 2
L 9
D 9
R 15
D 10
L 12
R 14
L 4
R 17
D 15
U 16
R 7
D 4
U 4
L 7
D 16
R 11
D 2
U 2
L 7
U 15
L 5
U 14
L 7
U 15
D 9
L 14
D 13
U 11
R 10
U 15
L 5
U 16
D 13
U 15
L 18
R 1
D 17
U 18
R 19
L 4
R 15
U 12
D 19
R 5
D 18
L 14
U 5
L 4
R 6
U 15
L 7
R 11
L 15
U 12
D 3
R 14
U 1
L 4
R 3
U 15
L 15
R 6
L 3
U 2
D 6
L 6
D 16
L 19
U 9
L 2
R 13
U 8
R 17
D 17
L 4
R 2
L 7
R 11
D 5
L 14
D 7
R 13
D 2
L 18
U 11
R 2
D 18
U 2
D 6
L 4
U 2
L 15
R 4
D 8
R 1
U 16
L 4
R 5
U 16
D 14
U 2
D 19
L 6
D 14
U 17
L 3
R 11
L 2
R 11
U 11
D 4
U 13
L 6
U 14
D 17
U 15
D 7
R 8
U 3
R 15
D 17
U 16
R 3
D 17
L 9
U 15
R 15
L 11
R 18
D 16
R 17
D 3
L 17
D 4
L 10
U 2
R 2
D 9
L 17
R 19`