~williewillus/advent_of_code

e2d43d789a233fdefe501b3bdde2d89a82890a9a — Vincent Lee 10 months ago 362c77c master
2022: d14p2
1 files changed, 73 insertions(+), 24 deletions(-)

M aoc_2022/day14/day14.go
M aoc_2022/day14/day14.go => aoc_2022/day14/day14.go +73 -24
@@ 32,11 32,26 @@ func iorder(a, b int) (int, int) {
	}
}

const spawnX int = 500
const spawnY int = 0
var spawnPos vec2 = vec2{500, 0}

func posOccupied(state map[int][]int, pos vec2) bool {
	col, ok := state[pos.X]
type state struct {
	// x -> occupied y positions (sorted)
	inner      map[int][]int
	p2         bool
	floorLevel int
}

func (s state) setPos(pos vec2) {
	col := append(s.inner[pos.X], pos.Y)
	sort.Ints(col)
	s.inner[pos.X] = col
}

func (s state) isOccupied(pos vec2) bool {
	if s.p2 && pos.Y == s.floorLevel {
		return true
	}
	col, ok := s.inner[pos.X]
	if !ok {
		return false
	}


@@ 46,17 61,23 @@ func posOccupied(state map[int][]int, pos vec2) bool {

// Get the next occupied y coordinate "below" (greater than) the given x, y coordinate.
// Returns -1 if one doesn't exist
func getNextOccupiedBelow(state map[int][]int, pos vec2) int {
	col, ok := state[pos.X]
func (s state) getNextOccupiedBelow(pos vec2) int {
	col, ok := s.inner[pos.X]
	if !ok {
		return -1
		if s.p2 {
			return s.floorLevel
		} else {
			return -1
		}
	}
	nextYIdx := sort.Search(len(col), func(idx int) bool {
		return col[idx] > pos.Y
	})
	

	if nextYIdx < len(col) {
		return col[nextYIdx]
	} else if s.p2 && pos.Y < s.floorLevel {
		return s.floorLevel
	} else {
		return -1
	}


@@ 65,11 86,11 @@ func getNextOccupiedBelow(state map[int][]int, pos vec2) int {
// Spawn a sand at spawnX, spawnY and simulate it until it comes to rest
// Second return value is false if the particle falls off the board, vec2 holds the last known step before falling off
// if it's true, then vec2 is the place it came to rest
func simulateNextSand(state map[int][]int) (vec2, bool) {
	pos := vec2{spawnX, spawnY}
func simulateNextSand(state *state) (vec2, bool) {
	pos := spawnPos
	for {
		// Try moving down
		nextOccupied := getNextOccupiedBelow(state, pos)
		nextOccupied := state.getNextOccupiedBelow(pos)
		if nextOccupied == -1 {
			return pos, false
		}


@@ 78,11 99,11 @@ func simulateNextSand(state map[int][]int) (vec2, bool) {

		if toMoveDownTo == pos {
			// Already as far down as we can go, try moving sideways
			downLeft := vec2{pos.X-1, pos.Y + 1}
			downRight := vec2{pos.X+1, pos.Y + 1}
			if !posOccupied(state, downLeft) {
			downLeft := vec2{pos.X - 1, pos.Y + 1}
			downRight := vec2{pos.X + 1, pos.Y + 1}
			if !state.isOccupied(downLeft) {
				pos = downLeft
			} else if !posOccupied(state, downRight) {
			} else if !state.isOccupied(downRight) {
				pos = downRight
			} else {
				// Nowhere to go, come to rest


@@ 96,8 117,8 @@ func simulateNextSand(state map[int][]int) (vec2, bool) {

func Run() (string, string) {
	scanner := bufio.NewScanner(os.Stdin)
	// x -> filled Y coords (sorted)
	state := make(map[int][]int)

	inner := make(map[int][]int)
	for scanner.Scan() {
		line := scanner.Text()
		points := []vec2{}


@@ 115,26 136,54 @@ func Run() (string, string) {

			for x := startX; x <= endX; x++ {
				for y := startY; y <= endY; y++ {
					state[x] = append(state[x], y)
					inner[x] = append(inner[x], y)
				}
			}
		}
	}

	for _, col := range state {
	lowestOccupied := -1
	for _, col := range inner {
		sort.Ints(col)

		lowestThisCol := col[len(col)-1]
		if lowestThisCol > lowestOccupied {
			lowestOccupied = lowestThisCol
		}
	}

	floorLevel := lowestOccupied + 2

	innerP1 := make(map[int][]int)
	for k, v := range inner {
		innerP1[k] = append([]int{}, v...)
	}

	stateP1 := state{
		innerP1, false, floorLevel,
	}
	p1 := 0
	for ; ; p1++ {
		restPos, didRest := simulateNextSand(state)
		restPos, didRest := simulateNextSand(&stateP1)
		if !didRest {
			break
		} else {
			state[restPos.X] = append(state[restPos.X], restPos.Y)
			sort.Ints(state[restPos.X])
			stateP1.setPos(restPos)
		}
	}	
	}

	stateP2 := state{
		inner, true, floorLevel,
	}
	p2 := 0
	for ; ; p2++ {
		if stateP2.isOccupied(spawnPos) {
			break
		}
		restPos, didRest := simulateNextSand(&stateP2)
		util.Assert(didRest)
		stateP2.setPos(restPos)
	}

	return strconv.Itoa(p1), "incomplete"
	return strconv.Itoa(p1), strconv.Itoa(p2)
}