1use std::collections::HashMap;23use itertools::Itertools;45#[derive(Debug, Copy, Clone, PartialEq, Eq, serde_derive::Deserialize)]6struct Domino([u8; 2]);78impl std::fmt::Display for Domino {9 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {10 write!(f, "{}|{}", self.0[0], self.0[1])11 }12}1314// Top left is 0,0.15// First is row (y)16// Second is column (x)17#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq, serde_derive::Deserialize)]18struct Index([u8; 2]);1920impl std::fmt::Display for Index {21 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {22 write!(f, "({}, {})", self.0[0], self.0[1])23 }24}2526#[derive(Debug, Clone, serde_derive::Deserialize)]27enum Type {28 #[serde(rename = "empty")]29 Empty,30 #[serde(rename = "equals")]31 Equals,32 #[serde(rename = "unequal")]33 Unequal,34 #[serde(rename = "greater")]35 Greater,36 #[serde(rename = "less")]37 Less,38 #[serde(rename = "sum")]39 Sum,40}4142#[derive(Debug, Clone, serde_derive::Deserialize)]43struct Region {44 indices: Vec<Index>,45 #[serde(rename = "type")]46 type_: Type,47 target: Option<u8>,48}4950#[derive(Debug, serde_derive::Deserialize)]51struct SinglePuzzleInput {52 dominoes: Vec<Domino>,53 regions: Vec<Region>,54}5556#[derive(Debug, serde_derive::Deserialize)]57struct PuzzleInput {58 easy: SinglePuzzleInput,59 medium: SinglePuzzleInput,60 hard: SinglePuzzleInput,61}6263fn parse(filename: &str) -> PuzzleInput {64 let file = std::fs::File::open(filename).unwrap();65 serde_json::from_reader(file).unwrap()66}6768#[derive(Debug, Clone)]69struct PuzzleSolveInfo {70 board: HashMap<Index, Option<u8>>,71 regions: Vec<Region>,72 dominoes: Vec<Domino>,73 solution: Vec<(Domino, (Index, Index))>,74}7576#[derive(Debug)]77enum CheckResult {78 Solved,79 Invalid,80 Plausible,81}8283struct FlattenErrIterator<I, IItem> {84 underlying: I,85 slice: Option<([Option<IItem>; 4], usize)>,86}8788impl<I, IItem> Iterator for FlattenErrIterator<I, IItem>89where90 I: Iterator<Item = [Option<IItem>; 4]>,91{92 type Item = Result<IItem, ()>;9394 fn next(&mut self) -> Option<Self::Item> {95 let Self { underlying, slice } = self;9697 loop {98 match slice.take() {99 Some((mut inner_slice, mut index)) => {100 if index >= 4 {101 *slice = None;102 } else {103 if let Some(res) = inner_slice[index].take() {104 index += 1;105 *slice = Some((inner_slice, index));106 return Some(Ok(res));107 } else {108 *slice = None;109 if index == 0 {110 return Some(Err(()));111 }112 }113 }114 }115 None => match underlying.next() {116 Some(new_slice) => {117 *slice = Some((new_slice, 0));118 }119 None => return None,120 },121 }122 }123 }124}125126impl PuzzleSolveInfo {127 fn is_empty(&self, index: Index) -> bool {128 matches!(self.board.get(&index), Some(None))129 }130131 fn all_positions(&self) -> impl Iterator<Item = Result<(Index, Index), ()>> {132 let iter = self133 .board134 .iter()135 .filter_map(|(index, value)| match value {136 Some(_) => None,137 None => Some(*index),138 })139 .map(|index| {140 let mut positions = [None; 4];141 let mut positions_idx = 0;142143 let y = index.0[0];144 let x = index.0[1];145146 if y > 0 {147 let up = Index([y - 1, x]);148 if self.is_empty(up) {149 positions[positions_idx] = Some((index, up));150 positions_idx += 1;151 }152 }153154 let down = Index([y + 1, x]);155 if self.is_empty(down) {156 positions[positions_idx] = Some((index, down));157 positions_idx += 1;158 }159160 if x > 0 {161 let left = Index([y, x - 1]);162 if self.is_empty(left) {163 positions[positions_idx] = Some((index, left));164 positions_idx += 1;165 }166 }167168 let right = Index([y, x + 1]);169 if self.is_empty(right) {170 positions[positions_idx] = Some((index, right));171 }172173 positions174 });175176 FlattenErrIterator {177 underlying: iter,178 slice: None,179 }180 }181182 /// For the provided domino, returns all possible places it could go.183 fn domino_positions(&self, domino: Domino) -> impl Iterator<Item = Result<(Index, Index), ()>> {184 self.all_positions().filter_map(move |place| {185 let place = match place {186 Ok(place) => place,187 Err(e) => return Some(Err(e)),188 };189190 let mut new = self.clone();191 match new.place_no_crank(domino, place) {192 CheckResult::Solved => {193 // TODO: Deal with this194 Some(Ok(place))195 }196 CheckResult::Invalid => None,197 CheckResult::Plausible => Some(Ok(place)),198 }199 })200 }201202 fn place_no_crank(&mut self, domino: Domino, position: (Index, Index)) -> CheckResult {203 self.solution.push((domino, position));204205 assert!(206 self.board207 .insert(position.0, Some(domino.0[0]))208 .unwrap()209 .is_none()210 );211 assert!(212 self.board213 .insert(position.1, Some(domino.0[1]))214 .unwrap()215 .is_none()216 );217218 let index = self.dominoes.iter().position(|e| *e == domino).unwrap();219 self.dominoes.swap_remove(index);220221 match self.check() {222 CheckResult::Solved => CheckResult::Solved,223 CheckResult::Invalid => CheckResult::Invalid,224 CheckResult::Plausible => {225 assert!(!self.dominoes.is_empty());226 CheckResult::Plausible227 }228 }229 }230231 /// Takes a board and resolves all trivial moves (i.e. placing dominoes if232 /// they can only go in one way).233 ///234 /// Returns false if the board was found to be invalid.235 fn crank(&mut self) -> CheckResult {236 loop {237 let mut place = None;238 for &domino in &self.dominoes {239 let mut options_iter = self.domino_positions(domino);240 let maybe_place = match options_iter.next() {241 Some(Ok(place)) => place,242 // This means a space was boxed in.243 Some(Err(())) => return CheckResult::Invalid,244 // If we can't place this domino anywhere, it must be invalid.245 None => return CheckResult::Invalid,246 };247248 match options_iter.next() {249 // There's more than one option, so this isn't a forced move.250 //251 // TODO: It could be forced if there are two options that252 // are mirrors and the domino is a mirror (or some other253 // similar cases.)254 Some(Ok(_)) => continue,255 Some(Err(())) => return CheckResult::Invalid,256 None => {257 place = Some((maybe_place, domino));258 }259 }260 }261262 if let Some((place, domino)) = place {263 match self.place_no_crank(domino, place) {264 CheckResult::Solved => return CheckResult::Solved,265 CheckResult::Invalid => return CheckResult::Invalid,266 CheckResult::Plausible => continue,267 }268 } else {269 break;270 }271 }272273 self.check()274 }275276 /// Checks all the constraints and returns the current state of the board.277 fn check(&self) -> CheckResult {278 for region in &self.regions {279 let mut nums = Vec::new();280 let mut num_needed_pips = 0;281 for index in ®ion.indices {282 let num = *self.board.get(index).unwrap();283 if let Some(num) = num {284 nums.push(num);285 } else {286 num_needed_pips += 1;287 }288 }289290 let mut remaining_pips: Vec<u8> = self.dominoes.iter().flat_map(|d| d.0).collect();291 remaining_pips.sort_unstable();292293 assert!(remaining_pips.len().is_multiple_of(2));294 assert!(295 remaining_pips.len() >= num_needed_pips,296 "{} was < {num_needed_pips}",297 remaining_pips.len()298 );299300 match region.type_ {301 // All good :-)302 Type::Empty => continue,303304 Type::Equals => {305 for (a, b) in nums.iter().tuple_windows() {306 if a != b {307 return CheckResult::Invalid;308 }309 }310311 // Check whether we even have enough possible312 // dominoes for this to work.313 let mut of_each = [0; 7];314 for &pip in &remaining_pips {315 of_each[pip as usize] += 1;316 }317318 // Number is already locked in.319 if let Some(&num) = nums.first() {320 if of_each[num as usize] < num_needed_pips {321 return CheckResult::Invalid;322 }323 } else if of_each.iter().all(|&n| n < num_needed_pips) {324 return CheckResult::Invalid;325 }326 }327 Type::Unequal => {328 for (a, b) in nums.iter().tuple_windows() {329 if a == b {330 return CheckResult::Invalid;331 }332 }333334 let mut available = [false; 7];335 for &pip in &remaining_pips {336 available[pip as usize] = true;337 }338 for &num in &nums {339 available[num as usize] = false;340 }341342 if num_needed_pips > available.iter().filter(|&&e| e).count() {343 return CheckResult::Invalid;344 }345 }346 Type::Greater => {347 let target = region.target.unwrap();348 let sum: u8 = nums.iter().sum();349350 if let Some(remainder) = target.checked_sub(sum) {351 // Can we possibly pass the target with the largest remaining pips.352 if remaining_pips353 .iter()354 .rev()355 .take(num_needed_pips)356 .sum::<u8>()357 <= remainder358 {359 return CheckResult::Invalid;360 }361 } else {362 // Already greater. We're good.363 }364 }365 Type::Less => {366 let target = region.target.unwrap();367 let sum: u8 = nums.iter().sum();368369 if sum >= target {370 return CheckResult::Invalid;371 }372 let remainder = target - sum; // must be >= 1.373374 // If we meet or exceed the target with the smallest375 // remaining pips, we're toast.376 if remaining_pips.iter().take(num_needed_pips).sum::<u8>() >= remainder {377 return CheckResult::Invalid;378 }379 }380 Type::Sum => {381 // TODO: Maybe can try permutations when the number382 // num_needed_pips is small enough.383 let target = region.target.unwrap();384 let sum: u8 = nums.iter().sum();385 if sum > target {386 } else if sum < target && num_needed_pips == 0387 || remaining_pips388 .iter()389 .rev()390 .take(num_needed_pips)391 .sum::<u8>()392 < target - sum393 {394 return CheckResult::Invalid;395 }396 }397 }398 }399400 if self.dominoes.is_empty() {401 CheckResult::Solved402 } else {403 CheckResult::Plausible404 }405 }406407 fn print_solution(&self) {408 for (domino, (a, b)) in &self.solution {409 println!("{domino}: {a} {b}");410 }411 }412413 fn solve(mut self) -> CheckResult {414 match self.crank() {415 CheckResult::Solved => {416 self.print_solution();417 return CheckResult::Solved;418 }419 CheckResult::Invalid => {420 return CheckResult::Invalid;421 }422 CheckResult::Plausible => {}423 }424425 let mut best_domino = None;426 let mut best_options: Option<Vec<(Index, Index)>> = None;427428 'domino_loop: for domino in &self.dominoes {429 let mut options = Vec::new();430 for position in self.domino_positions(*domino) {431 match position {432 Ok(position) => options.push(position),433 Err(()) => return CheckResult::Invalid,434 }435436 if options.len() >= best_options.as_ref().map(|v| v.len()).unwrap_or(usize::MAX) {437 continue 'domino_loop;438 }439 }440441 if options.is_empty() {442 return CheckResult::Invalid;443 }444445 let len = options.len();446 best_options = Some(options);447 best_domino = Some(*domino);448449 // We can't do better than 2 since we already played all forced450 // moves in crank.451 if len == 2 {452 break 'domino_loop;453 }454 }455456 for option in best_options.unwrap() {457 let mut new_board = self.clone();458 match new_board.place_no_crank(best_domino.unwrap(), option) {459 CheckResult::Solved => {460 new_board.print_solution();461 return CheckResult::Solved;462 }463 CheckResult::Invalid => continue,464 CheckResult::Plausible => match new_board.solve() {465 CheckResult::Solved => return CheckResult::Solved,466 CheckResult::Invalid => continue,467 CheckResult::Plausible => unreachable!(),468 },469 }470 }471472 CheckResult::Invalid473 }474}475476impl From<SinglePuzzleInput> for PuzzleSolveInfo {477 fn from(value: SinglePuzzleInput) -> Self {478 let mut board = HashMap::new();479 for region in value.regions.iter() {480 for index in ®ion.indices {481 board.insert(*index, None);482 }483 }484485 Self {486 board,487 regions: value.regions,488 dominoes: value.dominoes,489 solution: Vec::new(),490 }491 }492}493494fn main() {495 let mut args = std::env::args();496 let _ = args.next();497 let filename = args.next().expect("need a filename");498 let difficulty = args.next().expect("need a difficulty");499500 let input = parse(&filename);501 let puzzle = match difficulty.as_ref() {502 "easy" => input.easy,503 "medium" => input.medium,504 "hard" => input.hard,505 _ => panic!("unknown difficulty"),506 };507508 println!("{:?}", PuzzleSolveInfo::from(puzzle).solve());509}