use advent_of_code::prelude::*; static CONNECTIVITY1: &[&[&[usize]]] = &[ &[ &[], &[1], &[1, 2], &[1, 2, 3], &[1, 2, 3, 4], &[1, 2, 3, 4, 5], &[1, 2, 3, 4, 5, 6], &[1, 2, 3, 4, 5, 6, 7], &[1, 2, 3, 4, 5, 6, 7, 8], &[1, 2, 3, 4, 5, 6, 7, 8, 9], &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], &[1, 2, 11], &[1, 2, 3, 4, 12], &[1, 2, 3, 4, 5, 6, 13], &[1, 2, 3, 4, 5, 6, 7, 8, 14], &[1, 2, 11, 15], &[1, 2, 3, 4, 12, 16], &[1, 2, 3, 4, 5, 6, 13, 17], &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18], ], &[ &[0], &[], &[2], &[2, 3], &[2, 3, 4], &[2, 3, 4, 5], &[2, 3, 4, 5, 6], &[2, 3, 4, 5, 6, 7], &[2, 3, 4, 5, 6, 7, 8], &[2, 3, 4, 5, 6, 7, 8, 9], &[2, 3, 4, 5, 6, 7, 8, 9, 10], &[2, 11], &[2, 3, 4, 12], &[2, 3, 4, 5, 6, 13], &[2, 3, 4, 5, 6, 7, 8, 14], &[2, 11, 15], &[2, 3, 4, 12, 16], &[2, 3, 4, 5, 6, 13, 17], &[2, 3, 4, 5, 6, 7, 8, 14, 18], ], &[ &[1, 0], &[1], &[], &[3], &[3, 4], &[3, 4, 5], &[3, 4, 5, 6], &[3, 4, 5, 6, 7], &[3, 4, 5, 6, 7, 8], &[3, 4, 5, 6, 7, 8, 9], &[3, 4, 5, 6, 7, 8, 9, 10], &[11], &[3, 4, 12], &[3, 4, 5, 6, 13], &[3, 4, 5, 6, 7, 8, 14], &[11, 15], &[3, 4, 12, 16], &[3, 4, 5, 6, 13, 17], &[3, 4, 5, 6, 7, 8, 14, 18], ], &[ &[2, 1, 0], &[2, 1], &[2], &[], &[4], &[4, 5], &[4, 5, 6], &[4, 5, 6, 7], &[4, 5, 6, 7, 8], &[4, 5, 6, 7, 8, 9], &[4, 5, 6, 7, 8, 9, 10], &[2, 11], &[4, 12], &[4, 5, 6, 13], &[4, 5, 6, 7, 8, 14], &[2, 11, 15], &[4, 12, 16], &[4, 5, 6, 13, 17], &[4, 5, 6, 7, 8, 14, 18], ], &[ &[3, 2, 1, 0], &[3, 2, 1], &[3, 2], &[3], &[], &[5], &[5, 6], &[5, 6, 7], &[5, 6, 7, 8], &[5, 6, 7, 8, 9], &[5, 6, 7, 8, 9, 10], &[3, 2, 11], &[12], &[5, 6, 13], &[5, 6, 7, 8, 14], &[3, 2, 11, 15], &[12, 16], &[5, 6, 13, 17], &[5, 6, 7, 8, 14, 18], ], &[ &[4, 3, 2, 1, 0], &[4, 3, 2, 1], &[4, 3, 2], &[4, 3], &[4], &[], &[6], &[6, 7], &[6, 7, 8], &[6, 7, 8, 9], &[6, 7, 8, 9, 10], &[4, 3, 2, 11], &[4, 12], &[6, 13], &[6, 7, 8, 14], &[4, 3, 2, 11, 15], &[4, 12, 16], &[6, 13, 17], &[6, 7, 8, 14, 18], ], &[ &[5, 4, 3, 2, 1, 0], &[5, 4, 3, 2, 1], &[5, 4, 3, 2], &[5, 4, 3], &[5, 4], &[5], &[], &[7], &[7, 8], &[7, 8, 9], &[7, 8, 9, 10], &[5, 4, 3, 2, 11], &[5, 4, 12], &[13], &[7, 8, 14], &[5, 4, 3, 2, 11, 15], &[5, 4, 12, 16], &[13, 17], &[7, 8, 14, 18], ], &[ &[6, 5, 4, 3, 2, 1, 0], &[6, 5, 4, 3, 2, 1], &[6, 5, 4, 3, 2], &[6, 5, 4, 3], &[6, 5, 4], &[6, 5], &[6], &[], &[8], &[8, 9], &[8, 9, 10], &[6, 5, 4, 3, 2, 11], &[6, 5, 4, 12], &[6, 13], &[8, 14], &[6, 5, 4, 3, 2, 11, 15], &[6, 5, 4, 12, 16], &[6, 13, 17], &[8, 14, 18], ], &[ &[7, 6, 5, 4, 3, 2, 1, 0], &[7, 6, 5, 4, 3, 2, 1], &[7, 6, 5, 4, 3, 2], &[7, 6, 5, 4, 3], &[7, 6, 5, 4], &[7, 6, 5], &[7, 6], &[7], &[], &[9], &[9, 10], &[7, 6, 5, 4, 3, 2, 11], &[7, 6, 5, 4, 12], &[7, 6, 13], &[14], &[7, 6, 5, 4, 3, 2, 11, 15], &[7, 6, 5, 4, 12, 16], &[7, 6, 13, 17], &[14, 18], ], &[ &[8, 7, 6, 5, 4, 3, 2, 1, 0], &[8, 7, 6, 5, 4, 3, 2, 1], &[8, 7, 6, 5, 4, 3, 2], &[8, 7, 6, 5, 4, 3], &[8, 7, 6, 5, 4], &[8, 7, 6, 5], &[8, 7, 6], &[8, 7], &[8], &[], &[10], &[8, 7, 6, 5, 4, 3, 2, 11], &[8, 7, 6, 5, 4, 12], &[8, 7, 6, 13], &[8, 14], &[8, 7, 6, 5, 4, 3, 2, 11, 15], &[8, 7, 6, 5, 4, 12, 16], &[8, 7, 6, 13, 17], &[8, 14, 18], ], &[ &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0], &[9, 8, 7, 6, 5, 4, 3, 2, 1], &[9, 8, 7, 6, 5, 4, 3, 2], &[9, 8, 7, 6, 5, 4, 3], &[9, 8, 7, 6, 5, 4], &[9, 8, 7, 6, 5], &[9, 8, 7, 6], &[9, 8, 7], &[9, 8], &[9], &[], &[9, 8, 7, 6, 5, 4, 3, 2, 11], &[9, 8, 7, 6, 5, 4, 12], &[9, 8, 7, 6, 13], &[9, 8, 14], &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15], &[9, 8, 7, 6, 5, 4, 12, 16], &[9, 8, 7, 6, 13, 17], &[9, 8, 14, 18], ], &[ &[2, 1, 0], &[2, 1], &[2], &[2, 3], &[2, 3, 4], &[2, 3, 4, 5], &[2, 3, 4, 5, 6], &[2, 3, 4, 5, 6, 7], &[2, 3, 4, 5, 6, 7, 8], &[2, 3, 4, 5, 6, 7, 8, 9], &[2, 3, 4, 5, 6, 7, 8, 9, 10], &[], &[2, 3, 4, 12], &[2, 3, 4, 5, 6, 13], &[2, 3, 4, 5, 6, 7, 8, 14], &[15], &[2, 3, 4, 12, 16], &[2, 3, 4, 5, 6, 13, 17], &[2, 3, 4, 5, 6, 7, 8, 14, 18], ], &[ &[4, 3, 2, 1, 0], &[4, 3, 2, 1], &[4, 3, 2], &[4, 3], &[4], &[4, 5], &[4, 5, 6], &[4, 5, 6, 7], &[4, 5, 6, 7, 8], &[4, 5, 6, 7, 8, 9], &[4, 5, 6, 7, 8, 9, 10], &[4, 3, 2, 11], &[], &[4, 5, 6, 13], &[4, 5, 6, 7, 8, 14], &[4, 3, 2, 11, 15], &[16], &[4, 5, 6, 13, 17], &[4, 5, 6, 7, 8, 14, 18], ], &[ &[6, 5, 4, 3, 2, 1, 0], &[6, 5, 4, 3, 2, 1], &[6, 5, 4, 3, 2], &[6, 5, 4, 3], &[6, 5, 4], &[6, 5], &[6], &[6, 7], &[6, 7, 8], &[6, 7, 8, 9], &[6, 7, 8, 9, 10], &[6, 5, 4, 3, 2, 11], &[6, 5, 4, 12], &[], &[6, 7, 8, 14], &[6, 5, 4, 3, 2, 11, 15], &[6, 5, 4, 12, 16], &[17], &[6, 7, 8, 14, 18], ], &[ &[8, 7, 6, 5, 4, 3, 2, 1, 0], &[8, 7, 6, 5, 4, 3, 2, 1], &[8, 7, 6, 5, 4, 3, 2], &[8, 7, 6, 5, 4, 3], &[8, 7, 6, 5, 4], &[8, 7, 6, 5], &[8, 7, 6], &[8, 7], &[8], &[8, 9], &[8, 9, 10], &[8, 7, 6, 5, 4, 3, 2, 11], &[8, 7, 6, 5, 4, 12], &[8, 7, 6, 13], &[], &[8, 7, 6, 5, 4, 3, 2, 11, 15], &[8, 7, 6, 5, 4, 12, 16], &[8, 7, 6, 13, 17], &[18], ], &[ &[11, 2, 1, 0], &[11, 2, 1], &[11, 2], &[11, 2, 3], &[11, 2, 3, 4], &[11, 2, 3, 4, 5], &[11, 2, 3, 4, 5, 6], &[11, 2, 3, 4, 5, 6, 7], &[11, 2, 3, 4, 5, 6, 7, 8], &[11, 2, 3, 4, 5, 6, 7, 8, 9], &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10], &[11], &[11, 2, 3, 4, 12], &[11, 2, 3, 4, 5, 6, 13], &[11, 2, 3, 4, 5, 6, 7, 8, 14], &[], &[11, 2, 3, 4, 12, 16], &[11, 2, 3, 4, 5, 6, 13, 17], &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18], ], &[ &[12, 4, 3, 2, 1, 0], &[12, 4, 3, 2, 1], &[12, 4, 3, 2], &[12, 4, 3], &[12, 4], &[12, 4, 5], &[12, 4, 5, 6], &[12, 4, 5, 6, 7], &[12, 4, 5, 6, 7, 8], &[12, 4, 5, 6, 7, 8, 9], &[12, 4, 5, 6, 7, 8, 9, 10], &[12, 4, 3, 2, 11], &[12], &[12, 4, 5, 6, 13], &[12, 4, 5, 6, 7, 8, 14], &[12, 4, 3, 2, 11, 15], &[], &[12, 4, 5, 6, 13, 17], &[12, 4, 5, 6, 7, 8, 14, 18], ], &[ &[13, 6, 5, 4, 3, 2, 1, 0], &[13, 6, 5, 4, 3, 2, 1], &[13, 6, 5, 4, 3, 2], &[13, 6, 5, 4, 3], &[13, 6, 5, 4], &[13, 6, 5], &[13, 6], &[13, 6, 7], &[13, 6, 7, 8], &[13, 6, 7, 8, 9], &[13, 6, 7, 8, 9, 10], &[13, 6, 5, 4, 3, 2, 11], &[13, 6, 5, 4, 12], &[13], &[13, 6, 7, 8, 14], &[13, 6, 5, 4, 3, 2, 11, 15], &[13, 6, 5, 4, 12, 16], &[], &[13, 6, 7, 8, 14, 18], ], &[ &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0], &[14, 8, 7, 6, 5, 4, 3, 2, 1], &[14, 8, 7, 6, 5, 4, 3, 2], &[14, 8, 7, 6, 5, 4, 3], &[14, 8, 7, 6, 5, 4], &[14, 8, 7, 6, 5], &[14, 8, 7, 6], &[14, 8, 7], &[14, 8], &[14, 8, 9], &[14, 8, 9, 10], &[14, 8, 7, 6, 5, 4, 3, 2, 11], &[14, 8, 7, 6, 5, 4, 12], &[14, 8, 7, 6, 13], &[14], &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15], &[14, 8, 7, 6, 5, 4, 12, 16], &[14, 8, 7, 6, 13, 17], &[], ], ]; static CONNECTIVITY2: &[&[&[usize]]] = &[ &[ &[], &[1], &[1, 2], &[1, 2, 3], &[1, 2, 3, 4], &[1, 2, 3, 4, 5], &[1, 2, 3, 4, 5, 6], &[1, 2, 3, 4, 5, 6, 7], &[1, 2, 3, 4, 5, 6, 7, 8], &[1, 2, 3, 4, 5, 6, 7, 8, 9], &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], &[1, 2, 11], &[1, 2, 3, 4, 12], &[1, 2, 3, 4, 5, 6, 13], &[1, 2, 3, 4, 5, 6, 7, 8, 14], &[1, 2, 11, 15], &[1, 2, 3, 4, 12, 16], &[1, 2, 3, 4, 5, 6, 13, 17], &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18], &[1, 2, 11, 15, 19], &[1, 2, 3, 4, 12, 16, 20], &[1, 2, 3, 4, 5, 6, 13, 17, 21], &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], &[1, 2, 11, 15, 19, 23], &[1, 2, 3, 4, 12, 16, 20, 24], &[1, 2, 3, 4, 5, 6, 13, 17, 21, 25], &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[0], &[], &[2], &[2, 3], &[2, 3, 4], &[2, 3, 4, 5], &[2, 3, 4, 5, 6], &[2, 3, 4, 5, 6, 7], &[2, 3, 4, 5, 6, 7, 8], &[2, 3, 4, 5, 6, 7, 8, 9], &[2, 3, 4, 5, 6, 7, 8, 9, 10], &[2, 11], &[2, 3, 4, 12], &[2, 3, 4, 5, 6, 13], &[2, 3, 4, 5, 6, 7, 8, 14], &[2, 11, 15], &[2, 3, 4, 12, 16], &[2, 3, 4, 5, 6, 13, 17], &[2, 3, 4, 5, 6, 7, 8, 14, 18], &[2, 11, 15, 19], &[2, 3, 4, 12, 16, 20], &[2, 3, 4, 5, 6, 13, 17, 21], &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22], &[2, 11, 15, 19, 23], &[2, 3, 4, 12, 16, 20, 24], &[2, 3, 4, 5, 6, 13, 17, 21, 25], &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[1, 0], &[1], &[], &[3], &[3, 4], &[3, 4, 5], &[3, 4, 5, 6], &[3, 4, 5, 6, 7], &[3, 4, 5, 6, 7, 8], &[3, 4, 5, 6, 7, 8, 9], &[3, 4, 5, 6, 7, 8, 9, 10], &[11], &[3, 4, 12], &[3, 4, 5, 6, 13], &[3, 4, 5, 6, 7, 8, 14], &[11, 15], &[3, 4, 12, 16], &[3, 4, 5, 6, 13, 17], &[3, 4, 5, 6, 7, 8, 14, 18], &[11, 15, 19], &[3, 4, 12, 16, 20], &[3, 4, 5, 6, 13, 17, 21], &[3, 4, 5, 6, 7, 8, 14, 18, 22], &[11, 15, 19, 23], &[3, 4, 12, 16, 20, 24], &[3, 4, 5, 6, 13, 17, 21, 25], &[3, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[2, 1, 0], &[2, 1], &[2], &[], &[4], &[4, 5], &[4, 5, 6], &[4, 5, 6, 7], &[4, 5, 6, 7, 8], &[4, 5, 6, 7, 8, 9], &[4, 5, 6, 7, 8, 9, 10], &[2, 11], &[4, 12], &[4, 5, 6, 13], &[4, 5, 6, 7, 8, 14], &[2, 11, 15], &[4, 12, 16], &[4, 5, 6, 13, 17], &[4, 5, 6, 7, 8, 14, 18], &[2, 11, 15, 19], &[4, 12, 16, 20], &[4, 5, 6, 13, 17, 21], &[4, 5, 6, 7, 8, 14, 18, 22], &[2, 11, 15, 19, 23], &[4, 12, 16, 20, 24], &[4, 5, 6, 13, 17, 21, 25], &[4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[3, 2, 1, 0], &[3, 2, 1], &[3, 2], &[3], &[], &[5], &[5, 6], &[5, 6, 7], &[5, 6, 7, 8], &[5, 6, 7, 8, 9], &[5, 6, 7, 8, 9, 10], &[3, 2, 11], &[12], &[5, 6, 13], &[5, 6, 7, 8, 14], &[3, 2, 11, 15], &[12, 16], &[5, 6, 13, 17], &[5, 6, 7, 8, 14, 18], &[3, 2, 11, 15, 19], &[12, 16, 20], &[5, 6, 13, 17, 21], &[5, 6, 7, 8, 14, 18, 22], &[3, 2, 11, 15, 19, 23], &[12, 16, 20, 24], &[5, 6, 13, 17, 21, 25], &[5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[4, 3, 2, 1, 0], &[4, 3, 2, 1], &[4, 3, 2], &[4, 3], &[4], &[], &[6], &[6, 7], &[6, 7, 8], &[6, 7, 8, 9], &[6, 7, 8, 9, 10], &[4, 3, 2, 11], &[4, 12], &[6, 13], &[6, 7, 8, 14], &[4, 3, 2, 11, 15], &[4, 12, 16], &[6, 13, 17], &[6, 7, 8, 14, 18], &[4, 3, 2, 11, 15, 19], &[4, 12, 16, 20], &[6, 13, 17, 21], &[6, 7, 8, 14, 18, 22], &[4, 3, 2, 11, 15, 19, 23], &[4, 12, 16, 20, 24], &[6, 13, 17, 21, 25], &[6, 7, 8, 14, 18, 22, 26], ], &[ &[5, 4, 3, 2, 1, 0], &[5, 4, 3, 2, 1], &[5, 4, 3, 2], &[5, 4, 3], &[5, 4], &[5], &[], &[7], &[7, 8], &[7, 8, 9], &[7, 8, 9, 10], &[5, 4, 3, 2, 11], &[5, 4, 12], &[13], &[7, 8, 14], &[5, 4, 3, 2, 11, 15], &[5, 4, 12, 16], &[13, 17], &[7, 8, 14, 18], &[5, 4, 3, 2, 11, 15, 19], &[5, 4, 12, 16, 20], &[13, 17, 21], &[7, 8, 14, 18, 22], &[5, 4, 3, 2, 11, 15, 19, 23], &[5, 4, 12, 16, 20, 24], &[13, 17, 21, 25], &[7, 8, 14, 18, 22, 26], ], &[ &[6, 5, 4, 3, 2, 1, 0], &[6, 5, 4, 3, 2, 1], &[6, 5, 4, 3, 2], &[6, 5, 4, 3], &[6, 5, 4], &[6, 5], &[6], &[], &[8], &[8, 9], &[8, 9, 10], &[6, 5, 4, 3, 2, 11], &[6, 5, 4, 12], &[6, 13], &[8, 14], &[6, 5, 4, 3, 2, 11, 15], &[6, 5, 4, 12, 16], &[6, 13, 17], &[8, 14, 18], &[6, 5, 4, 3, 2, 11, 15, 19], &[6, 5, 4, 12, 16, 20], &[6, 13, 17, 21], &[8, 14, 18, 22], &[6, 5, 4, 3, 2, 11, 15, 19, 23], &[6, 5, 4, 12, 16, 20, 24], &[6, 13, 17, 21, 25], &[8, 14, 18, 22, 26], ], &[ &[7, 6, 5, 4, 3, 2, 1, 0], &[7, 6, 5, 4, 3, 2, 1], &[7, 6, 5, 4, 3, 2], &[7, 6, 5, 4, 3], &[7, 6, 5, 4], &[7, 6, 5], &[7, 6], &[7], &[], &[9], &[9, 10], &[7, 6, 5, 4, 3, 2, 11], &[7, 6, 5, 4, 12], &[7, 6, 13], &[14], &[7, 6, 5, 4, 3, 2, 11, 15], &[7, 6, 5, 4, 12, 16], &[7, 6, 13, 17], &[14, 18], &[7, 6, 5, 4, 3, 2, 11, 15, 19], &[7, 6, 5, 4, 12, 16, 20], &[7, 6, 13, 17, 21], &[14, 18, 22], &[7, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[7, 6, 5, 4, 12, 16, 20, 24], &[7, 6, 13, 17, 21, 25], &[14, 18, 22, 26], ], &[ &[8, 7, 6, 5, 4, 3, 2, 1, 0], &[8, 7, 6, 5, 4, 3, 2, 1], &[8, 7, 6, 5, 4, 3, 2], &[8, 7, 6, 5, 4, 3], &[8, 7, 6, 5, 4], &[8, 7, 6, 5], &[8, 7, 6], &[8, 7], &[8], &[], &[10], &[8, 7, 6, 5, 4, 3, 2, 11], &[8, 7, 6, 5, 4, 12], &[8, 7, 6, 13], &[8, 14], &[8, 7, 6, 5, 4, 3, 2, 11, 15], &[8, 7, 6, 5, 4, 12, 16], &[8, 7, 6, 13, 17], &[8, 14, 18], &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19], &[8, 7, 6, 5, 4, 12, 16, 20], &[8, 7, 6, 13, 17, 21], &[8, 14, 18, 22], &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[8, 7, 6, 5, 4, 12, 16, 20, 24], &[8, 7, 6, 13, 17, 21, 25], &[8, 14, 18, 22, 26], ], &[ &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0], &[9, 8, 7, 6, 5, 4, 3, 2, 1], &[9, 8, 7, 6, 5, 4, 3, 2], &[9, 8, 7, 6, 5, 4, 3], &[9, 8, 7, 6, 5, 4], &[9, 8, 7, 6, 5], &[9, 8, 7, 6], &[9, 8, 7], &[9, 8], &[9], &[], &[9, 8, 7, 6, 5, 4, 3, 2, 11], &[9, 8, 7, 6, 5, 4, 12], &[9, 8, 7, 6, 13], &[9, 8, 14], &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15], &[9, 8, 7, 6, 5, 4, 12, 16], &[9, 8, 7, 6, 13, 17], &[9, 8, 14, 18], &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], &[9, 8, 7, 6, 5, 4, 12, 16, 20], &[9, 8, 7, 6, 13, 17, 21], &[9, 8, 14, 18, 22], &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[9, 8, 7, 6, 5, 4, 12, 16, 20, 24], &[9, 8, 7, 6, 13, 17, 21, 25], &[9, 8, 14, 18, 22, 26], ], &[ &[2, 1, 0], &[2, 1], &[2], &[2, 3], &[2, 3, 4], &[2, 3, 4, 5], &[2, 3, 4, 5, 6], &[2, 3, 4, 5, 6, 7], &[2, 3, 4, 5, 6, 7, 8], &[2, 3, 4, 5, 6, 7, 8, 9], &[2, 3, 4, 5, 6, 7, 8, 9, 10], &[], &[2, 3, 4, 12], &[2, 3, 4, 5, 6, 13], &[2, 3, 4, 5, 6, 7, 8, 14], &[15], &[2, 3, 4, 12, 16], &[2, 3, 4, 5, 6, 13, 17], &[2, 3, 4, 5, 6, 7, 8, 14, 18], &[15, 19], &[2, 3, 4, 12, 16, 20], &[2, 3, 4, 5, 6, 13, 17, 21], &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22], &[15, 19, 23], &[2, 3, 4, 12, 16, 20, 24], &[2, 3, 4, 5, 6, 13, 17, 21, 25], &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[4, 3, 2, 1, 0], &[4, 3, 2, 1], &[4, 3, 2], &[4, 3], &[4], &[4, 5], &[4, 5, 6], &[4, 5, 6, 7], &[4, 5, 6, 7, 8], &[4, 5, 6, 7, 8, 9], &[4, 5, 6, 7, 8, 9, 10], &[4, 3, 2, 11], &[], &[4, 5, 6, 13], &[4, 5, 6, 7, 8, 14], &[4, 3, 2, 11, 15], &[16], &[4, 5, 6, 13, 17], &[4, 5, 6, 7, 8, 14, 18], &[4, 3, 2, 11, 15, 19], &[16, 20], &[4, 5, 6, 13, 17, 21], &[4, 5, 6, 7, 8, 14, 18, 22], &[4, 3, 2, 11, 15, 19, 23], &[16, 20, 24], &[4, 5, 6, 13, 17, 21, 25], &[4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[6, 5, 4, 3, 2, 1, 0], &[6, 5, 4, 3, 2, 1], &[6, 5, 4, 3, 2], &[6, 5, 4, 3], &[6, 5, 4], &[6, 5], &[6], &[6, 7], &[6, 7, 8], &[6, 7, 8, 9], &[6, 7, 8, 9, 10], &[6, 5, 4, 3, 2, 11], &[6, 5, 4, 12], &[], &[6, 7, 8, 14], &[6, 5, 4, 3, 2, 11, 15], &[6, 5, 4, 12, 16], &[17], &[6, 7, 8, 14, 18], &[6, 5, 4, 3, 2, 11, 15, 19], &[6, 5, 4, 12, 16, 20], &[17, 21], &[6, 7, 8, 14, 18, 22], &[6, 5, 4, 3, 2, 11, 15, 19, 23], &[6, 5, 4, 12, 16, 20, 24], &[17, 21, 25], &[6, 7, 8, 14, 18, 22, 26], ], &[ &[8, 7, 6, 5, 4, 3, 2, 1, 0], &[8, 7, 6, 5, 4, 3, 2, 1], &[8, 7, 6, 5, 4, 3, 2], &[8, 7, 6, 5, 4, 3], &[8, 7, 6, 5, 4], &[8, 7, 6, 5], &[8, 7, 6], &[8, 7], &[8], &[8, 9], &[8, 9, 10], &[8, 7, 6, 5, 4, 3, 2, 11], &[8, 7, 6, 5, 4, 12], &[8, 7, 6, 13], &[], &[8, 7, 6, 5, 4, 3, 2, 11, 15], &[8, 7, 6, 5, 4, 12, 16], &[8, 7, 6, 13, 17], &[18], &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19], &[8, 7, 6, 5, 4, 12, 16, 20], &[8, 7, 6, 13, 17, 21], &[18, 22], &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[8, 7, 6, 5, 4, 12, 16, 20, 24], &[8, 7, 6, 13, 17, 21, 25], &[18, 22, 26], ], &[ &[11, 2, 1, 0], &[11, 2, 1], &[11, 2], &[11, 2, 3], &[11, 2, 3, 4], &[11, 2, 3, 4, 5], &[11, 2, 3, 4, 5, 6], &[11, 2, 3, 4, 5, 6, 7], &[11, 2, 3, 4, 5, 6, 7, 8], &[11, 2, 3, 4, 5, 6, 7, 8, 9], &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10], &[11], &[11, 2, 3, 4, 12], &[11, 2, 3, 4, 5, 6, 13], &[11, 2, 3, 4, 5, 6, 7, 8, 14], &[], &[11, 2, 3, 4, 12, 16], &[11, 2, 3, 4, 5, 6, 13, 17], &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18], &[19], &[11, 2, 3, 4, 12, 16, 20], &[11, 2, 3, 4, 5, 6, 13, 17, 21], &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], &[19, 23], &[11, 2, 3, 4, 12, 16, 20, 24], &[11, 2, 3, 4, 5, 6, 13, 17, 21, 25], &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[12, 4, 3, 2, 1, 0], &[12, 4, 3, 2, 1], &[12, 4, 3, 2], &[12, 4, 3], &[12, 4], &[12, 4, 5], &[12, 4, 5, 6], &[12, 4, 5, 6, 7], &[12, 4, 5, 6, 7, 8], &[12, 4, 5, 6, 7, 8, 9], &[12, 4, 5, 6, 7, 8, 9, 10], &[12, 4, 3, 2, 11], &[12], &[12, 4, 5, 6, 13], &[12, 4, 5, 6, 7, 8, 14], &[12, 4, 3, 2, 11, 15], &[], &[12, 4, 5, 6, 13, 17], &[12, 4, 5, 6, 7, 8, 14, 18], &[12, 4, 3, 2, 11, 15, 19], &[20], &[12, 4, 5, 6, 13, 17, 21], &[12, 4, 5, 6, 7, 8, 14, 18, 22], &[12, 4, 3, 2, 11, 15, 19, 23], &[20, 24], &[12, 4, 5, 6, 13, 17, 21, 25], &[12, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[13, 6, 5, 4, 3, 2, 1, 0], &[13, 6, 5, 4, 3, 2, 1], &[13, 6, 5, 4, 3, 2], &[13, 6, 5, 4, 3], &[13, 6, 5, 4], &[13, 6, 5], &[13, 6], &[13, 6, 7], &[13, 6, 7, 8], &[13, 6, 7, 8, 9], &[13, 6, 7, 8, 9, 10], &[13, 6, 5, 4, 3, 2, 11], &[13, 6, 5, 4, 12], &[13], &[13, 6, 7, 8, 14], &[13, 6, 5, 4, 3, 2, 11, 15], &[13, 6, 5, 4, 12, 16], &[], &[13, 6, 7, 8, 14, 18], &[13, 6, 5, 4, 3, 2, 11, 15, 19], &[13, 6, 5, 4, 12, 16, 20], &[21], &[13, 6, 7, 8, 14, 18, 22], &[13, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[13, 6, 5, 4, 12, 16, 20, 24], &[21, 25], &[13, 6, 7, 8, 14, 18, 22, 26], ], &[ &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0], &[14, 8, 7, 6, 5, 4, 3, 2, 1], &[14, 8, 7, 6, 5, 4, 3, 2], &[14, 8, 7, 6, 5, 4, 3], &[14, 8, 7, 6, 5, 4], &[14, 8, 7, 6, 5], &[14, 8, 7, 6], &[14, 8, 7], &[14, 8], &[14, 8, 9], &[14, 8, 9, 10], &[14, 8, 7, 6, 5, 4, 3, 2, 11], &[14, 8, 7, 6, 5, 4, 12], &[14, 8, 7, 6, 13], &[14], &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15], &[14, 8, 7, 6, 5, 4, 12, 16], &[14, 8, 7, 6, 13, 17], &[], &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], &[14, 8, 7, 6, 5, 4, 12, 16, 20], &[14, 8, 7, 6, 13, 17, 21], &[22], &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[14, 8, 7, 6, 5, 4, 12, 16, 20, 24], &[14, 8, 7, 6, 13, 17, 21, 25], &[22, 26], ], &[ &[15, 11, 2, 1, 0], &[15, 11, 2, 1], &[15, 11, 2], &[15, 11, 2, 3], &[15, 11, 2, 3, 4], &[15, 11, 2, 3, 4, 5], &[15, 11, 2, 3, 4, 5, 6], &[15, 11, 2, 3, 4, 5, 6, 7], &[15, 11, 2, 3, 4, 5, 6, 7, 8], &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9], &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10], &[15, 11], &[15, 11, 2, 3, 4, 12], &[15, 11, 2, 3, 4, 5, 6, 13], &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14], &[15], &[15, 11, 2, 3, 4, 12, 16], &[15, 11, 2, 3, 4, 5, 6, 13, 17], &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18], &[], &[15, 11, 2, 3, 4, 12, 16, 20], &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21], &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], &[23], &[15, 11, 2, 3, 4, 12, 16, 20, 24], &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25], &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[16, 12, 4, 3, 2, 1, 0], &[16, 12, 4, 3, 2, 1], &[16, 12, 4, 3, 2], &[16, 12, 4, 3], &[16, 12, 4], &[16, 12, 4, 5], &[16, 12, 4, 5, 6], &[16, 12, 4, 5, 6, 7], &[16, 12, 4, 5, 6, 7, 8], &[16, 12, 4, 5, 6, 7, 8, 9], &[16, 12, 4, 5, 6, 7, 8, 9, 10], &[16, 12, 4, 3, 2, 11], &[16, 12], &[16, 12, 4, 5, 6, 13], &[16, 12, 4, 5, 6, 7, 8, 14], &[16, 12, 4, 3, 2, 11, 15], &[16], &[16, 12, 4, 5, 6, 13, 17], &[16, 12, 4, 5, 6, 7, 8, 14, 18], &[16, 12, 4, 3, 2, 11, 15, 19], &[], &[16, 12, 4, 5, 6, 13, 17, 21], &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22], &[16, 12, 4, 3, 2, 11, 15, 19, 23], &[24], &[16, 12, 4, 5, 6, 13, 17, 21, 25], &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[17, 13, 6, 5, 4, 3, 2, 1, 0], &[17, 13, 6, 5, 4, 3, 2, 1], &[17, 13, 6, 5, 4, 3, 2], &[17, 13, 6, 5, 4, 3], &[17, 13, 6, 5, 4], &[17, 13, 6, 5], &[17, 13, 6], &[17, 13, 6, 7], &[17, 13, 6, 7, 8], &[17, 13, 6, 7, 8, 9], &[17, 13, 6, 7, 8, 9, 10], &[17, 13, 6, 5, 4, 3, 2, 11], &[17, 13, 6, 5, 4, 12], &[17, 13], &[17, 13, 6, 7, 8, 14], &[17, 13, 6, 5, 4, 3, 2, 11, 15], &[17, 13, 6, 5, 4, 12, 16], &[17], &[17, 13, 6, 7, 8, 14, 18], &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19], &[17, 13, 6, 5, 4, 12, 16, 20], &[], &[17, 13, 6, 7, 8, 14, 18, 22], &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[17, 13, 6, 5, 4, 12, 16, 20, 24], &[25], &[17, 13, 6, 7, 8, 14, 18, 22, 26], ], &[ &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0], &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1], &[18, 14, 8, 7, 6, 5, 4, 3, 2], &[18, 14, 8, 7, 6, 5, 4, 3], &[18, 14, 8, 7, 6, 5, 4], &[18, 14, 8, 7, 6, 5], &[18, 14, 8, 7, 6], &[18, 14, 8, 7], &[18, 14, 8], &[18, 14, 8, 9], &[18, 14, 8, 9, 10], &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11], &[18, 14, 8, 7, 6, 5, 4, 12], &[18, 14, 8, 7, 6, 13], &[18, 14], &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15], &[18, 14, 8, 7, 6, 5, 4, 12, 16], &[18, 14, 8, 7, 6, 13, 17], &[18], &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20], &[18, 14, 8, 7, 6, 13, 17, 21], &[], &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24], &[18, 14, 8, 7, 6, 13, 17, 21, 25], &[26], ], &[ &[19, 15, 11, 2, 1, 0], &[19, 15, 11, 2, 1], &[19, 15, 11, 2], &[19, 15, 11, 2, 3], &[19, 15, 11, 2, 3, 4], &[19, 15, 11, 2, 3, 4, 5], &[19, 15, 11, 2, 3, 4, 5, 6], &[19, 15, 11, 2, 3, 4, 5, 6, 7], &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8], &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9], &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10], &[19, 15, 11], &[19, 15, 11, 2, 3, 4, 12], &[19, 15, 11, 2, 3, 4, 5, 6, 13], &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14], &[19, 15], &[19, 15, 11, 2, 3, 4, 12, 16], &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17], &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18], &[19], &[19, 15, 11, 2, 3, 4, 12, 16, 20], &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21], &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], &[], &[19, 15, 11, 2, 3, 4, 12, 16, 20, 24], &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25], &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[20, 16, 12, 4, 3, 2, 1, 0], &[20, 16, 12, 4, 3, 2, 1], &[20, 16, 12, 4, 3, 2], &[20, 16, 12, 4, 3], &[20, 16, 12, 4], &[20, 16, 12, 4, 5], &[20, 16, 12, 4, 5, 6], &[20, 16, 12, 4, 5, 6, 7], &[20, 16, 12, 4, 5, 6, 7, 8], &[20, 16, 12, 4, 5, 6, 7, 8, 9], &[20, 16, 12, 4, 5, 6, 7, 8, 9, 10], &[20, 16, 12, 4, 3, 2, 11], &[20, 16, 12], &[20, 16, 12, 4, 5, 6, 13], &[20, 16, 12, 4, 5, 6, 7, 8, 14], &[20, 16, 12, 4, 3, 2, 11, 15], &[20, 16], &[20, 16, 12, 4, 5, 6, 13, 17], &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18], &[20, 16, 12, 4, 3, 2, 11, 15, 19], &[20], &[20, 16, 12, 4, 5, 6, 13, 17, 21], &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22], &[20, 16, 12, 4, 3, 2, 11, 15, 19, 23], &[], &[20, 16, 12, 4, 5, 6, 13, 17, 21, 25], &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26], ], &[ &[21, 17, 13, 6, 5, 4, 3, 2, 1, 0], &[21, 17, 13, 6, 5, 4, 3, 2, 1], &[21, 17, 13, 6, 5, 4, 3, 2], &[21, 17, 13, 6, 5, 4, 3], &[21, 17, 13, 6, 5, 4], &[21, 17, 13, 6, 5], &[21, 17, 13, 6], &[21, 17, 13, 6, 7], &[21, 17, 13, 6, 7, 8], &[21, 17, 13, 6, 7, 8, 9], &[21, 17, 13, 6, 7, 8, 9, 10], &[21, 17, 13, 6, 5, 4, 3, 2, 11], &[21, 17, 13, 6, 5, 4, 12], &[21, 17, 13], &[21, 17, 13, 6, 7, 8, 14], &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15], &[21, 17, 13, 6, 5, 4, 12, 16], &[21, 17], &[21, 17, 13, 6, 7, 8, 14, 18], &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19], &[21, 17, 13, 6, 5, 4, 12, 16, 20], &[21], &[21, 17, 13, 6, 7, 8, 14, 18, 22], &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[21, 17, 13, 6, 5, 4, 12, 16, 20, 24], &[], &[21, 17, 13, 6, 7, 8, 14, 18, 22, 26], ], &[ &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0], &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1], &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2], &[22, 18, 14, 8, 7, 6, 5, 4, 3], &[22, 18, 14, 8, 7, 6, 5, 4], &[22, 18, 14, 8, 7, 6, 5], &[22, 18, 14, 8, 7, 6], &[22, 18, 14, 8, 7], &[22, 18, 14, 8], &[22, 18, 14, 8, 9], &[22, 18, 14, 8, 9, 10], &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11], &[22, 18, 14, 8, 7, 6, 5, 4, 12], &[22, 18, 14, 8, 7, 6, 13], &[22, 18, 14], &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15], &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16], &[22, 18, 14, 8, 7, 6, 13, 17], &[22, 18], &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20], &[22, 18, 14, 8, 7, 6, 13, 17, 21], &[22], &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24], &[22, 18, 14, 8, 7, 6, 13, 17, 21, 25], &[], ], ]; #[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)] enum Amphipod { A, B, C, D, } use Amphipod::*; impl Amphipod { fn step_cost(&self) -> u64 { match self { A => 1, B => 10, C => 100, D => 1000, } } } impl std::str::FromStr for Amphipod { type Err = anyhow::Error; fn from_str(s: &str) -> std::result::Result { match s { "A" => Ok(A), "B" => Ok(B), "C" => Ok(C), "D" => Ok(D), _ => Err(anyhow::anyhow!(s.to_string())), } } } impl std::fmt::Display for Amphipod { fn fmt( &self, f: &mut std::fmt::Formatter<'_>, ) -> std::result::Result<(), std::fmt::Error> { match self { A => write!(f, "A"), B => write!(f, "B"), C => write!(f, "C"), D => write!(f, "D"), } } } // ############# // #abcdefghijk# // ###l#m#n#o### // #p#q#r#s# // ######### #[derive(Debug, Clone, Copy, Default, Hash, PartialEq, Eq)] pub struct Burrow { spaces: [Option; 27], big: bool, } impl Burrow { fn to_big(self) -> Self { let mut big = self; big.spaces[23] = self.spaces[15]; big.spaces[24] = self.spaces[16]; big.spaces[25] = self.spaces[17]; big.spaces[26] = self.spaces[18]; big.spaces[15] = Some(D); big.spaces[16] = Some(C); big.spaces[17] = Some(B); big.spaces[18] = Some(A); big.spaces[19] = Some(D); big.spaces[20] = Some(B); big.spaces[21] = Some(A); big.spaces[22] = Some(C); big.big = true; big } fn path(&self, from: usize, to: usize) -> &[usize] { if self.big { CONNECTIVITY2[from][to] } else { CONNECTIVITY1[from][to] } } fn done(big: bool) -> Self { let mut done = Self::default(); done.spaces[11] = Some(A); done.spaces[15] = Some(A); done.spaces[12] = Some(B); done.spaces[16] = Some(B); done.spaces[13] = Some(C); done.spaces[17] = Some(C); done.spaces[14] = Some(D); done.spaces[18] = Some(D); if big { done.spaces[19] = Some(A); done.spaces[23] = Some(A); done.spaces[20] = Some(B); done.spaces[24] = Some(B); done.spaces[21] = Some(C); done.spaces[25] = Some(C); done.spaces[22] = Some(D); done.spaces[26] = Some(D); done.big = true; } done } fn move_cost(&self, mv: Move) -> u64 { self.spaces[mv.from].unwrap().step_cost() * u64::try_from(self.path(mv.from, mv.to).len()).unwrap() } fn make_move(&self, mv: Move) -> Self { let mut new = *self; let a = new.spaces[mv.from].take().unwrap(); assert!(new.spaces[mv.to].is_none()); new.spaces[mv.to] = Some(a); new } fn legal_moves(&self) -> Vec { let mut ret = vec![]; let size = if self.big { 27 } else { 19 }; for (from, space) in self.spaces.iter().enumerate().take(size) { if let Some(a) = space { for to in 0..size { if self.can_move(*a, from, to) { ret.push(Move::new(from, to)); } } } } ret } fn can_move(&self, a: Amphipod, from: usize, to: usize) -> bool { if !self.big && (from >= 19 || to >= 19) { return false; } // Amphipods will never stop on the space immediately outside any // room. if to == 2 || to == 4 || to == 6 || to == 8 { return false; } // Amphipods will never move from the hallway into a room unless that // room is their destination room and that room contains no amphipods // which do not also have that room as their own destination. match a { A => { if to == 12 || to == 13 || to == 14 || to == 16 || to == 17 || to == 18 || to == 20 || to == 21 || to == 22 || to == 24 || to == 25 || to == 26 { return false; } if self.big { if to == 11 && (self.spaces[15] != Some(A) || self.spaces[19] != Some(A) || self.spaces[23] != Some(A)) { return false; } if to == 15 && (self.spaces[19] != Some(A) || self.spaces[23] != Some(A)) { return false; } if to == 19 && self.spaces[23] != Some(A) { return false; } if from == 23 || (from == 19 && self.spaces[23] == Some(A)) || (from == 15 && self.spaces[23] == Some(A) && self.spaces[19] == Some(A)) || (from == 11 && self.spaces[23] == Some(A) && self.spaces[19] == Some(A) && self.spaces[15] == Some(A)) { return false; } } else { if to == 11 && self.spaces[15] != Some(A) { return false; } if from == 15 || (from == 11 && self.spaces[15] == Some(A)) { return false; } } } B => { if to == 11 || to == 13 || to == 14 || to == 15 || to == 17 || to == 18 || to == 19 || to == 21 || to == 22 || to == 23 || to == 25 || to == 26 { return false; } if self.big { if to == 12 && (self.spaces[16] != Some(B) || self.spaces[20] != Some(B) || self.spaces[24] != Some(B)) { return false; } if to == 16 && (self.spaces[20] != Some(B) || self.spaces[24] != Some(B)) { return false; } if to == 20 && self.spaces[24] != Some(B) { return false; } if from == 24 || (from == 20 && self.spaces[24] == Some(B)) || (from == 16 && self.spaces[24] == Some(B) && self.spaces[20] == Some(B)) || (from == 12 && self.spaces[24] == Some(B) && self.spaces[20] == Some(B) && self.spaces[16] == Some(B)) { return false; } } else { if to == 12 && self.spaces[16] != Some(B) { return false; } if from == 16 || (from == 12 && self.spaces[16] == Some(B)) { return false; } } } C => { if to == 11 || to == 12 || to == 14 || to == 15 || to == 16 || to == 18 || to == 19 || to == 20 || to == 22 || to == 23 || to == 24 || to == 26 { return false; } if self.big { if to == 13 && (self.spaces[17] != Some(C) || self.spaces[21] != Some(C) || self.spaces[25] != Some(C)) { return false; } if to == 17 && (self.spaces[21] != Some(C) || self.spaces[25] != Some(C)) { return false; } if to == 21 && self.spaces[25] != Some(C) { return false; } if from == 25 || (from == 21 && self.spaces[25] == Some(C)) || (from == 17 && self.spaces[25] == Some(C) && self.spaces[21] == Some(C)) || (from == 13 && self.spaces[25] == Some(C) && self.spaces[21] == Some(C) && self.spaces[17] == Some(C)) { return false; } } else { if to == 13 && self.spaces[17] != Some(C) { return false; } if from == 17 || (from == 13 && self.spaces[17] == Some(C)) { return false; } } } D => { if to == 11 || to == 12 || to == 13 || to == 15 || to == 16 || to == 17 || to == 19 || to == 20 || to == 21 || to == 23 || to == 24 || to == 25 { return false; } if self.big { if to == 14 && (self.spaces[18] != Some(D) || self.spaces[22] != Some(D) || self.spaces[26] != Some(D)) { return false; } if to == 18 && (self.spaces[22] != Some(D) || self.spaces[26] != Some(D)) { return false; } if to == 22 && self.spaces[26] != Some(D) { return false; } if from == 26 || (from == 22 && self.spaces[26] == Some(D)) || (from == 18 && self.spaces[26] == Some(D) && self.spaces[22] == Some(D)) || (from == 14 && self.spaces[26] == Some(D) && self.spaces[22] == Some(D) && self.spaces[18] == Some(D)) { return false; } } else { if to == 14 && self.spaces[18] != Some(D) { return false; } if from == 18 || (from == 14 && self.spaces[18] == Some(D)) { return false; } } } } // Once an amphipod stops moving in the hallway, it will stay in that // spot until it can move into a room. if from < 11 && to < 11 { return false; } // not actually a move if from == to { return false; } // we don't have an unblocked path for space in self.path(from, to) { if self.spaces[*space].is_some() { return false; } } true } } impl std::fmt::Display for Burrow { fn fmt( &self, f: &mut std::fmt::Formatter<'_>, ) -> std::result::Result<(), std::fmt::Error> { writeln!(f, "#############")?; write!(f, "#")?; for i in 0..11 { if let Some(a) = &self.spaces[i] { write!(f, "{}", a)?; } else { write!(f, ".")?; } } writeln!(f, "#")?; write!(f, "###")?; for i in 11..15 { if let Some(a) = &self.spaces[i] { write!(f, "{}#", a)?; } else { write!(f, ".#")?; } } writeln!(f, "##")?; write!(f, " #")?; for i in 15..19 { if let Some(a) = &self.spaces[i] { write!(f, "{}#", a)?; } else { write!(f, ".#")?; } } writeln!(f)?; if self.big { write!(f, " #")?; for i in 19..23 { if let Some(a) = &self.spaces[i] { write!(f, "{}#", a)?; } else { write!(f, ".#")?; } } writeln!(f)?; write!(f, " #")?; for i in 23..27 { if let Some(a) = &self.spaces[i] { write!(f, "{}#", a)?; } else { write!(f, ".#")?; } } writeln!(f)?; } write!(f, " #########")?; Ok(()) } } #[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)] struct Move { from: usize, to: usize, } impl Move { fn new(from: usize, to: usize) -> Self { Self { from, to } } } struct Pathfinder; impl advent_of_code::graph::Graph for Pathfinder { type Edges = Vec; fn edges(&self, v: Burrow) -> Self::Edges { v.legal_moves() } fn edge(&self, v: Burrow, e: Move) -> (Burrow, u64) { (v.make_move(e), v.move_cost(e)) } } pub fn parse(fh: File) -> Result { let mut burrow = Burrow::default(); let lines: Vec<_> = parse::raw_lines(fh).collect(); let captures = regex_captures!(r"###(.)#(.)#(.)#(.)###", &lines[2]).unwrap(); burrow.spaces[11] = Some(captures[1].parse()?); burrow.spaces[12] = Some(captures[2].parse()?); burrow.spaces[13] = Some(captures[3].parse()?); burrow.spaces[14] = Some(captures[4].parse()?); let captures = regex_captures!(r" #(.)#(.)#(.)#(.)#", &lines[3]).unwrap(); burrow.spaces[15] = Some(captures[1].parse()?); burrow.spaces[16] = Some(captures[2].parse()?); burrow.spaces[17] = Some(captures[3].parse()?); burrow.spaces[18] = Some(captures[4].parse()?); Ok(burrow) } pub fn part1(burrow: Burrow) -> Result { let (cost, _path) = Pathfinder.dijkstra(burrow, |v| v == Burrow::done(false)); // for burrow in path { // eprintln!("{}", burrow); // } Ok(cost) } pub fn part2(burrow: Burrow) -> Result { let (cost, _path) = Pathfinder.dijkstra(burrow.to_big(), |v| v == Burrow::done(true)); // for burrow in path { // eprintln!("{}", burrow); // } Ok(cost) } #[test] fn test() { assert_eq!( part1(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(), 10607 ); assert_eq!( part2(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(), 59071 ); }