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: line-col
	// line 0 is the hallway, 1,2,3... are the depth of side rooms
	// col 2-4-6-8 are the side room columns
	pos [2]int
}
type state [8]amphipod
type energy map[state]int
const (
	depth    = 2  // depth of the side-rooms
	width    = 4  // number of side-rooms
	offset   = 3  // first item in the first side-room
	hwLength = 10 // length of the hallway line
)
// forbiddenHallway stores the forbidden coordinates of the hallway
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 {
	// s[2].pos = [2]int{0, 3} // 40
	// s[1].pos = [2]int{1, 6} // 400
	// s[5].pos = [2]int{0, 5} // 3000
	// s[2].pos = [2]int{2, 4} // 30
	// s[0].pos = [2]int{1, 4} // 40
	// s[3].pos = [2]int{0, 7} // 2000
	// s[7].pos = [2]int{0, 9} // 3
	// log.Println("starting state:", s)
	breadcrumbs := map[state]state{}
	visited := energy{}
	queue := energy{}
	queue[s] = 0
	// queue[s] += 40
	// queue[s] += 400
	// queue[s] += 3000
	// queue[s] += 30
	// queue[s] += 40
	// queue[s] += 2000
	for len(queue) > 0 {
		// for steps := 0; steps < 1; steps++ {
		curr, currCost := queue.getLowest()
		delete(queue, curr)
		if _, ok := visited[curr]; ok {
			continue
		}
		visited[curr] = currCost
		if curr.isInPlace() {
			printBread(breadcrumbs, curr)
			return visited[curr]
		}
		for st, cost := range curr.getValidStates() {
			if _, ok := visited[st]; ok {
				continue
			}
			breadcrumbs[st] = curr
			if prevCost, ok := queue[st]; ok {
				if prevCost < currCost+cost {
					continue
				}
			}
			queue[st] = currCost + cost
		}
		// log.Println(queue)
	}
	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
}
// getValidStates returns all possible valid states based on the current state.
func (s state) getValidStates() energy {
	// 1. Check if an amphipod can go to its side-room
	if ret := s.checkSideRoom(); ret != nil {
		// log.Println("side-room:", ret)
		return ret
	}
	// log.Println("no way to side-room")
	// 2. Check if an amphipod can go to the hallway
	// 2.1 only consider amps _not_ on the hallway
	// 2.2 do not forget to consider all possible hallway spots where path is free!
	// 2.3 do not move when side-room is done
	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})
					// log.Println(steps, ok, hw)
					if !ok {
						continue
					}
					// add item to possibilities
					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 {
	// 1.1 there is place in the side-room
	// 1.2 there are only proper type amps in the room
	for i, amp := range s {
		sideRoom := int((offset - 1) * (amp.tp - 'A' + 1))
		if amp.pos[1] == sideRoom {
			// amphipod already on right place
			continue
		}
		counter := 0
		for j, other := range s {
			if i == j {
				continue
			}
			if other.pos[1] == sideRoom { // line must not be 0, do not have to check
				// this is the proper side-room
				if other.tp != amp.tp {
					// type mismatch!
					counter = 999
					break
				}
				counter++
			}
		}
		if counter == 999 || counter >= depth {
			// type mismatch or the side-room is full
			continue
		}
		// 1.3 check if path is free to side-room, count steps
		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) {
	// log.Println("checkPath", from, to)
	steps := 0
	for row, col := from[0], from[1]; ; steps++ {
		// check if occupied or not
		if steps != 0 {
			for _, amp := range s {
				if amp.pos == [2]int{row, col} {
					return 0, false
				}
			}
		}
		// reached destination, finish
		if row == to[0] && col == to[1] {
			break
		}
		// come out of the current side-room
		if row != 0 && col != to[1] {
			row--
			continue
		}
		// move along the hallway
		if row == 0 && col != to[1] {
			if col > to[1] {
				col--
			} else {
				col++
			}
			continue
		}
		// go into the poroper depth of the proper sideroom
		row++
	}
	return steps, true
}
func (amp amphipod) isOnHallway() bool {
	if amp.pos[0] == 0 {
		return true
	}
	return false
}
// isInPlace returns true when all amphipods are in right place.
func (amps state) isInPlace() bool {
	for _, amp := range amps {
		if amp.isOnHallway() { // amphipod is on the hallway
			return false
		}
		// check if amphipod is in right side-room
		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 {
			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
}

#############
#...........#
###D#D#B#A###
  #B#C#A#C#
  #########

#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########

module main
go 1.17