YAINRP36MHHQVYYHZBLLTOS42ZLVU5AZNQDSORDS7AAEGECXEO7AC
4JNBKPAS54EZSRZR7HXDZZGDZFPXRQ5SGZFG6XZNYA2RUTR7ME2AC
FTYBC7WGD6LTHF3HWWQZO5KUVOJD7DALKOJGGXQGFFCCDQVLOCBAC
MUEUHLZANBSXCPLXBLRIENE3J73IH2PAYWUNUSYATJIAF2I6XE4QC
4N7QA5YNEVRA6UYWNSDUJ4BMRCCQZCNNVDMNMGBDBMIDCOITNMCAC
SPON6U5RKD4XUHNHLXYUQ2IVY7VGQZT4U4MHDHH7BJBMLW42CZGAC
ISKIMCRTCM4ZY34QENDO4AN7ZAKRRBPFLA5MYHXH2K6Q2WKJDZNQC
NBWIQLPZIFZRXGCDMIFXQAAWWVQEOJDP6KIALLI2NJE4YSNCCNOAC
XWEEARPXLVNAC4HDK6T7PP3CSXBFFBV3ZRH4F5CY6YWLFFIJ7ZBAC
ZY26UMBLD4WVCQYQ63H72K5P3MQ7Q43WBZHBY7M2FZFNSDEYF6QAC
4C6H6ZYD4SVDHKIXD76SSFYE32V3GTY75WO6OVXZTL5JA3I3XL5AC
VNIWLW3267ZI5BQ334AEXCFY67UC4U6CDXJBGWUPQ3VFOKS4YKYAC
PPSVYG6ZWHZG2VE43TTNXQGNYV2TGGJLNCTSTZZUO2RYY6VP65QAC
## Day 23
I use Dijksra to solve this one. The various state representation is the
following:
```zig
const Amphipod = enum { A, B, C, D, };
const hallway_length = 7;
const siderooms = 4;
const sideroom_depth = 2; // 4 int the second part
const State = struct {
hallway: [hallway_length]?Amphipod,
rooms: [siderooms][sideroom_depth]?Amphipod,
};
```
I do not think that I am doing any particularly smart with the moves. But I move
the Amphipod to it's room whenever that is possible to lower state count.
I store state and it's energy in a `std.PriorityQueue`. I do not update queue
energy values as adding new ones is faster and I do not drain the queue, just
return when reached final state.
TODO:
- According to profiling hashing the states for the `std.AutoHashMap` which
strores the already visited states is the slow part.
- Maybe try using [BTreeMap](https://github.com/pmkap/zig-btreemap)
- Use A* heuristics for choosing better states to check, do not wast time on
useless states.