adventofcode/2020/day23/main.go

package main

import (
	"fmt"

	h "git.bullercodeworks.com/brian/adventofcode/helpers"
)

var highest int
var lowest int
var AllCups map[int]*Cup

func init() {
	highest = h.MIN_INT
	lowest = h.MAX_INT
	AllCups = make(map[int]*Cup)
}

func main() {
	fmt.Println("# Day 23")
	inp := h.StdinToString()

	solve(inp, h.Atoi(h.OptArgNumber(1, "2")))
}

var move int
var first *Cup

func solve(inp string, part int) {
	moves := 100
	if part == 1 {
		BuildCircle(inp, -1)
	} else {
		BuildCircle(inp, 1000000)
		moves = 10000000
	}
	current := first
	for i := 0; i < moves; i++ {
		current = DoMove(current)
	}
	ans := FindLabel(1, first).next
	fmt.Println("## Part", part, ":\nAnswer:")
	if part == 1 {
		for ans.label != 1 {
			fmt.Print(ans.label)
			ans = ans.next
		}
	} else {
		fmt.Print(ans.label * ans.next.label)
	}
	fmt.Println()
}

func BuildCircle(inp string, cups int) *Cup {
	var wrk *Cup
	for k := range inp {
		next := &Cup{label: int(inp[k] - '0')}
		next.next = next
		next.prev = next
		if first == nil {
			first = next
			first.next = next
			first.prev = next
		} else {
			wrk.SetNext(next)
		}
		if next.label > highest {
			highest = next.label
		}
		if next.label < lowest {
			lowest = next.label
		}
		AllCups[next.label] = next
		wrk = next
	}
	total := Count(first)
	last := GetLast(first)
	nextLabel := highest + 1
	for cups > 0 && total < cups {
		next := &Cup{label: nextLabel}
		nextLabel++
		next.next = next
		next.prev = next
		last.SetNext(next)
		last = next
		if next.label > highest {
			highest = next.label
		}
		if next.label < lowest {
			lowest = next.label
		}
		AllCups[next.label] = next
		total++
	}
	return first
}

func DoMove(curr *Cup) *Cup {
	move++
	hold := curr.RemoveNext(3)
	target := curr.label - 1
	if target < lowest {
		target = highest
	}
	// Check the removed cups
	for FindLabel(target, hold) != nil {
		target = target - 1
		if target < lowest {
			target = highest
		}
	}
	//dest := FindLabel(target, curr)
	dest := AllCups[target]
	dest.SetNext(hold)
	return curr.next
}

func FindLabel(num int, first *Cup) *Cup {
	if first.label == num {
		return first
	}
	c := first.next
	for c != first {
		if c.label == num {
			return c
		}
		c = c.next
	}
	return nil
}

func StringifyCircle(first *Cup, current *Cup) string {
	c := first
	stringify := func(c *Cup) string {
		if c == nil {
			return "ERR"
		}
		if c == current {
			return fmt.Sprintf("(%d)", c.label)
		} else {
			return fmt.Sprintf(" %d ", c.label)
		}
	}
	ret := stringify(c)
	c = c.next
	for c != first {
		ret = ret + stringify(c)
		if c == nil {
			ret = ret + " ERR "
			break
		}
		if c.next == c {
			break
		}
		c = c.next
	}
	return ret
}

func GetLast(cups *Cup) *Cup {
	if cups.next == cups || cups.next == nil {
		return cups
	}
	c := cups.next
	for c.next != cups {
		if c.next == nil {
			break
		}
		c = c.next
	}
	return c
}

func Count(cups *Cup) int {
	start := cups
	wrk := start.next
	ret := 1
	for wrk != start {
		wrk = wrk.next
		ret++
	}
	return ret
}

var current *Cup

type Cup struct {
	label int
	next  *Cup
	prev  *Cup
}

func (c *Cup) SetNext(next *Cup) {
	if c.next == c {
		c.prev = next
		c.next = next
		next.next = c
		next.prev = c
		return
	}
	hold := c.next
	// c.p c c.n
	// c.p c next... c.n
	c.next = next
	if hold != nil {
		hold.prev = GetLast(next)
		GetLast(next).next = hold
	}
	next.prev = c
}

// RemoveNext removes the next cnt cups, returning a circle of the removed cups
func (c *Cup) RemoveNext(cnt int) *Cup {
	if cnt == 0 {
		return nil
	}
	hold := c.next
	dest := hold
	for cnt > 0 {
		dest = dest.next
		cnt--
	}
	c.next = dest
	dest.prev.next = hold
	hold.prev = dest.prev
	dest.prev = c
	return hold
}