package main
import (
"bufio"
"bytes"
"log"
"math"
"os"
)
func (s state) String() string {
blank := `
#############
#...........#
###.#.#.#.###
#.#.#.#.#
#.#.#.#.#
#.#.#.#.#
#########
`
out := bytes.Split([]byte(blank), []byte("\n"))
for _, amp := range s {
out[amp.pos[0]+2][amp.pos[1]+1] = amp.tp
}
return string(bytes.Join(out, []byte("\n")))
}
type amphipod struct {
tp byte
pos [2]int
}
type state [16]amphipod
type energy map[state]int
const (
depth = 4 width = 4 offset = 3 hwLength = 10 )
var forbiddenHallway = [width]int{2, 4, 6, 8}
func main() {
if err := myMain(); err != nil {
log.Println(err)
}
}
func myMain() error {
amps, err := parseInput("input.txt")
if err != nil {
return err
}
log.Println(solveFirst(amps))
return nil
}
func solveFirst(s state) int {
visited := energy{}
queue := energy{}
queue[s] = 0
for len(queue) > 0 {
curr, currCost := queue.getLowest()
delete(queue, curr)
if _, ok := visited[curr]; ok {
continue
}
visited[curr] = currCost
if curr.isInPlace() {
return visited[curr]
}
for st, cost := range curr.getValidStates() {
if _, ok := visited[st]; ok {
continue
}
if prevCost, ok := queue[st]; ok {
if prevCost < currCost+cost {
continue
}
}
queue[st] = currCost + cost
}
}
return len(queue)
}
func printBread(br map[state]state, end state) {
curr := end
for {
next, ok := br[curr]
if !ok {
return
}
log.Println(next)
curr = next
}
}
func (e energy) getLowest() (state, int) {
var ret state
min := int(math.Inf(1))
for st, cost := range e {
if cost < min {
ret = st
min = cost
}
}
return ret, min
}
func (s state) getValidStates() energy {
if ret := s.checkSideRoom(); ret != nil {
return ret
}
ret := energy{}
for col := offset - 1; col <= width*2; col += 2 {
if s.sideRoomDone(col) {
continue
}
for row := 1; row <= depth; row++ {
first := [2]int{0, 0}
idx := 999
for i, amp := range s {
if amp.pos == [2]int{row, col} {
first = [2]int{row, col}
idx = i
break
}
}
if first != [2]int{0, 0} {
for hw := 0; hw <= hwLength; hw++ {
if isForbidden(hw) {
continue
}
steps, ok := s.checkPath(first, [2]int{0, hw})
if !ok {
continue
}
next := s
next[idx].pos = [2]int{0, hw}
ret[next] = next[idx].calEnergy(steps)
}
}
}
}
return ret
}
func (s state) sideRoomDone(col int) bool {
var goodType byte
switch col {
case 2:
goodType = 'A'
case 4:
goodType = 'B'
case 6:
goodType = 'C'
case 8:
goodType = 'D'
default:
log.Panicln("unknown col")
}
for _, amp := range s {
if amp.pos[1] == col && amp.tp != goodType {
return false
}
}
return true
}
func isForbidden(hw int) bool {
for _, fb := range forbiddenHallway {
if hw == fb {
return true
}
}
return false
}
func (s state) checkSideRoom() energy {
for i, amp := range s {
sideRoom := int((offset - 1) * (amp.tp - 'A' + 1))
if amp.pos[1] == sideRoom {
continue
}
counter := 0
for j, other := range s {
if i == j {
continue
}
if other.pos[1] == sideRoom { if other.tp != amp.tp {
counter = 999
break
}
counter++
}
}
if counter == 999 || counter >= depth {
continue
}
steps, ok := s.checkPath(amp.pos, [2]int{depth - counter, sideRoom})
if !ok {
continue
}
ret := energy{}
next := s
next[i].pos = [2]int{depth - counter, sideRoom}
ret[next] = next[i].calEnergy(steps)
return ret
}
return nil
}
func (amp amphipod) calEnergy(steps int) int {
power := 0
switch amp.tp {
case 'A':
power = 0
case 'B':
power = 1
case 'C':
power = 2
case 'D':
power = 3
default:
log.Panicln("no such amphipod type")
}
return steps * int(math.Pow10(power))
}
func (s state) checkPath(from, to [2]int) (int, bool) {
steps := 0
for row, col := from[0], from[1]; ; steps++ {
if steps != 0 {
for _, amp := range s {
if amp.pos == [2]int{row, col} {
return 0, false
}
}
}
if row == to[0] && col == to[1] {
break
}
if row != 0 && col != to[1] {
row--
continue
}
if row == 0 && col != to[1] {
if col > to[1] {
col--
} else {
col++
}
continue
}
row++
}
return steps, true
}
func (amp amphipod) isOnHallway() bool {
if amp.pos[0] == 0 {
return true
}
return false
}
func (amps state) isInPlace() bool {
for _, amp := range amps {
if amp.isOnHallway() { return false
}
switch amp.tp {
case 'A':
if amp.pos[1] != (offset-1)*1 {
return false
}
case 'B':
if amp.pos[1] != (offset-1)*2 {
return false
}
case 'C':
if amp.pos[1] != (offset-1)*3 {
return false
}
case 'D':
if amp.pos[1] != (offset-1)*4 {
return false
}
}
}
return true
}
func parseInput(fileName string) (state, error) {
ret := state{}
fd, err := os.Open(fileName)
if err != nil {
return ret, err
}
defer fd.Close()
buf := bufio.NewScanner(fd)
for line := 0; buf.Scan(); line++ {
if line == 2 || line == 3 || line == 4 || line == 5 {
for i, counter := offset, (line-2)*4; i < width*2+offset; i, counter = i+2, counter+1 {
amp := amphipod{}
amp.tp = buf.Text()[i]
amp.pos = [2]int{line - 1, i - 1}
ret[counter] = amp
}
}
}
return ret, nil
}