nonogram_rs/algo/
chain.rs

1use crate::algo::{Error, PartCell};
2use std::ops::Range;
3
4/// Metadata about a chain of boxes.
5#[derive(Clone)]
6pub struct Chain<T> {
7    color: T,
8    len: usize,
9    start: usize,
10    end: usize,
11}
12
13impl<T> Chain<T> {
14    /// Constructs a new chain.
15    pub fn new(color: T, len: usize, start: usize, end: usize) -> Self {
16        Self {
17            color,
18            len,
19            start,
20            end,
21        }
22    }
23}
24
25impl<T: Copy + PartialEq> Chain<T> {
26    /// Returns the color.
27    pub fn color(&self) -> T {
28        self.color
29    }
30
31    /// Returns the start of the possible range.
32    pub fn start(&self) -> usize {
33        self.start
34    }
35
36    /// Sets the start of the possible range.
37    pub fn set_start(&mut self, start: usize) {
38        self.start = start;
39    }
40
41    /// Returns the end of the possible range.
42    pub fn end(&self) -> usize {
43        self.end
44    }
45
46    /// Sets the end of the possible range.
47    pub fn set_end(&mut self, end: usize) {
48        self.end = end;
49    }
50
51    /// Returns the range of cells which must be boxes.
52    pub fn known_cells(&self) -> Range<usize> {
53        let start = self.end - self.len;
54        let end = self.start + self.len;
55
56        start..end
57    }
58
59    /// Checks if the exact location of the chain has been found.
60    pub fn solved(&self) -> bool {
61        self.end - self.start == self.len
62    }
63
64    /// Updates the start of a the chain.
65    pub fn update_start(&mut self, line: &Vec<PartCell<T>>, end: usize) -> Result<(), Error> {
66        self.update_start_by_box_at_end(line, end);
67        self.update_start_by_adjacent(line)?;
68        self.update_start_by_gabs(line)
69    }
70
71    /// Mirror of [Chain::update_start].
72    pub fn update_end(&mut self, line: &Vec<PartCell<T>>, start: usize) -> Result<(), Error> {
73        self.update_end_by_box_at_start(line, start);
74        self.update_end_by_adjacent(line)?;
75        self.update_end_by_gabs(line)
76    }
77
78    /// The smallest start value of the previous chain before we need to backtrack.
79    pub fn min_prev_start(&self, same_color: bool) -> usize {
80        if same_color {
81            self.start + self.len + 1
82        } else {
83            self.start + self.len
84        }
85    }
86
87    /// The highest end value of the previous chain before we need to backtrack.
88    pub fn max_prev_end(&self, same_color: bool) -> usize {
89        if same_color {
90            self.end - self.len - 1
91        } else {
92            self.end - self.len
93        }
94    }
95
96    /// Finds a more precise start by looking at boxes on the right.
97    /// Boxes beyond the `end` parameter are ignored.
98    fn update_start_by_box_at_end(&mut self, line: &Vec<PartCell<T>>, end: usize) {
99        let start = self.start + self.len;
100
101        for i in (start..end).rev() {
102            if line[i] == self.color {
103                self.start = i + 1 - self.len;
104                return;
105            }
106        }
107    }
108
109    /// Mirror of [Chain::update_start_by_box_at_end].
110    fn update_end_by_box_at_start(&mut self, line: &Vec<PartCell<T>>, start: usize) {
111        let end = self.end - self.len;
112
113        for i in start..end {
114            if line[i] == self.color {
115                self.end = i + self.len;
116                return;
117            }
118        }
119    }
120
121    /// Finds a more precise start by looking at adjacent same colored boxes.
122    /// Fails if the range between start and end gets too small to fit the chain.
123    fn update_start_by_adjacent(&mut self, line: &Vec<PartCell<T>>) -> Result<(), Error> {
124        if self.start == 0 {
125            return Ok(());
126        }
127        let end = self.end - self.len;
128
129        for i in self.start..=end {
130            if line[i - 1] != self.color {
131                self.start = i;
132                return Ok(());
133            }
134        }
135        Err(Error::Invalid)
136    }
137
138    /// Mirror of [Chain::update_start_by_adjacent].
139    fn update_end_by_adjacent(&mut self, line: &Vec<PartCell<T>>) -> Result<(), Error> {
140        if self.end == line.len() {
141            return Ok(());
142        }
143        let start = self.start + self.len;
144
145        for i in (start..=self.end).rev() {
146            if line[i] != self.color {
147                self.end = i;
148                return Ok(());
149            }
150        }
151        Err(Error::Invalid)
152    }
153
154    /// Finds a more precise start by looking for a gab between spaces and other colored boxes.
155    /// Fails if the range between start and end gets too small to fit the chain.
156    fn update_start_by_gabs(&mut self, line: &Vec<PartCell<T>>) -> Result<(), Error> {
157        let mut count = 0;
158
159        for i in self.start..self.end {
160            count = match line[i] {
161                PartCell::Space => 0,
162                PartCell::Box { color } if color != self.color => 0,
163                _ => count + 1,
164            };
165            if count == self.len {
166                self.start = i + 1 - self.len;
167                return Ok(());
168            }
169        }
170        Err(Error::Invalid)
171    }
172
173    /// Mirror of [Chain::update_start_by_gabs].
174    fn update_end_by_gabs(&mut self, line: &Vec<PartCell<T>>) -> Result<(), Error> {
175        let mut count = 0;
176
177        for i in (self.start..self.end).rev() {
178            count = match line[i] {
179                PartCell::Space => 0,
180                PartCell::Box { color } if color != self.color => 0,
181                _ => count + 1,
182            };
183            if count == self.len {
184                self.end = i + self.len;
185                return Ok(());
186            }
187        }
188        Err(Error::Invalid)
189    }
190}
191
192#[cfg(test)]
193mod test {
194    use super::*;
195    use crate::algo::PartCell::*;
196
197    #[test]
198    fn chain_new() {
199        let c = Chain::new(4, 2, 3, 7);
200
201        assert_eq!(4, c.color());
202        assert_eq!(3, c.start());
203        assert_eq!(7, c.end());
204    }
205
206    #[test]
207    fn chain_set_start() {
208        let mut c = Chain::new(0, 0, 4, 0);
209
210        c.set_start(2);
211
212        assert_eq!(2, c.start());
213    }
214
215    #[test]
216    fn chain_set_end() {
217        let mut c = Chain::new(0, 0, 0, 2);
218
219        c.set_end(6);
220
221        assert_eq!(6, c.end());
222    }
223
224    #[test]
225    fn chain_known_cells() {
226        assert_eq!(4..6, Chain::new((), 4, 2, 8).known_cells());
227    }
228
229    #[test]
230    fn chain_solved() {
231        assert!(Chain::new((), 3, 6, 9).solved());
232        assert!(!Chain::new((), 4, 2, 7).solved());
233    }
234
235    #[test]
236    fn chain_update_start_check_by_box_at_end() {
237        let line = vec![Empty, Empty, Box { color: 1 }, Empty, Box { color: 1 }];
238        let mut c = Chain::new(1, 1, 0, line.len());
239
240        c.update_start(&line, 3).unwrap();
241
242        assert_eq!(2, c.start());
243    }
244
245    #[test]
246    fn chain_update_start_check_by_adjacent() {
247        let line = vec![Box { color: 1 }, Box { color: 1 }, Empty, Empty];
248        let mut c = Chain::new(1, 1, 1, line.len());
249
250        c.update_start(&line, line.len()).unwrap();
251
252        assert_eq!(3, c.start());
253    }
254
255    #[test]
256    fn chain_update_start_check_by_gabs() {
257        let line = vec![Space, Space, Empty, Empty];
258        let mut c = Chain::new(1, 1, 0, line.len());
259
260        c.update_start(&line, line.len()).unwrap();
261
262        assert_eq!(2, c.start());
263    }
264
265    #[test]
266    fn chain_update_end_check_by_box_at_start() {
267        let line = vec![Box { color: 1 }, Empty, Box { color: 1 }, Empty, Empty];
268        let mut c = Chain::new(1, 1, 0, line.len());
269
270        c.update_end(&line, 2).unwrap();
271
272        assert_eq!(3, c.end());
273    }
274
275    #[test]
276    fn chain_update_end_check_by_adjacent() {
277        let line = vec![Empty, Empty, Box { color: 1 }, Box { color: 1 }];
278        let mut c = Chain::new(1, 1, 0, 2);
279
280        c.update_end(&line, line.len()).unwrap();
281
282        assert_eq!(1, c.end());
283    }
284
285    #[test]
286    fn chain_update_end_check_by_gabs() {
287        let line = vec![Empty, Empty, Space, Space];
288        let mut c = Chain::new(1, 1, 0, line.len());
289
290        c.update_end(&line, line.len()).unwrap();
291
292        assert_eq!(2, c.end());
293    }
294
295    #[test]
296    fn chain_min_prev_start_same_color_false() {
297        let c = Chain::new(0, 2, 3, 0);
298
299        assert_eq!(5, c.min_prev_start(false));
300    }
301
302    #[test]
303    fn chain_min_prev_start_same_color_true() {
304        let c = Chain::new(0, 2, 3, 0);
305
306        assert_eq!(6, c.min_prev_start(true));
307    }
308
309    #[test]
310    fn chain_max_prev_end_same_color_false() {
311        let c = Chain::new(0, 2, 0, 7);
312
313        assert_eq!(5, c.max_prev_end(false));
314    }
315
316    #[test]
317    fn chain_max_prev_end_same_color_true() {
318        let c = Chain::new(0, 4, 0, 8);
319
320        assert_eq!(3, c.max_prev_end(true));
321    }
322
323    #[test]
324    fn chain_update_start_by_box_at_end_none() {
325        let line = vec![Space, Empty, Space, Empty];
326        let mut c = Chain::new(7, 2, 0, line.len());
327
328        c.update_start_by_box_at_end(&line, line.len());
329
330        assert_eq!(0, c.start());
331    }
332
333    #[test]
334    fn chain_update_start_by_box_at_end_one_box() {
335        let line = vec![Space, Empty, Space, Empty, Box { color: 7 }, Empty];
336        let mut c = Chain::new(7, 3, 0, line.len());
337
338        c.update_start_by_box_at_end(&line, line.len());
339
340        assert_eq!(2, c.start());
341    }
342
343    #[test]
344    fn chain_update_start_by_box_at_end_box_beyond_end() {
345        let line = vec![Space, Empty, Space, Empty, Box { color: 7 }, Empty];
346        let mut c = Chain::new(7, 3, 0, line.len());
347
348        c.update_start_by_box_at_end(&line, 4);
349
350        assert_eq!(0, c.start());
351    }
352
353    #[test]
354    fn chain_update_start_by_box_at_end_false_color() {
355        let line = vec![
356            Space,
357            Empty,
358            Space,
359            Box { color: 1 },
360            Box { color: 7 },
361            Box { color: 8 },
362        ];
363        let mut c = Chain::new(1, 3, 0, line.len());
364
365        c.update_start_by_box_at_end(&line, line.len());
366
367        assert_eq!(1, c.start());
368    }
369
370    #[test]
371    fn chain_update_start_by_box_at_end_multiple_boxes() {
372        let line = vec![
373            Space,
374            Empty,
375            Space,
376            Box { color: 7 },
377            Space,
378            Box { color: 7 },
379            Space,
380        ];
381        let mut c = Chain::new(7, 2, 0, line.len());
382
383        c.update_start_by_box_at_end(&line, line.len());
384
385        assert_eq!(4, c.start());
386    }
387
388    #[test]
389    fn chain_update_start_by_box_at_end_box_at_start() {
390        let line = vec![Space, Box { color: 7 }, Space, Empty, Space];
391        let mut c = Chain::new(7, 3, 0, line.len());
392
393        c.update_start_by_box_at_end(&line, line.len());
394
395        assert_eq!(0, c.start());
396    }
397
398    #[test]
399    fn chain_update_start_by_box_at_end_empty_range() {
400        let line = vec![Space, Empty, Space, Empty, Space];
401        let mut c = Chain::new(7, 3, 0, 4);
402
403        c.update_start_by_box_at_end(&line, 3);
404
405        assert_eq!(0, c.start());
406    }
407
408    #[test]
409    fn chain_update_end_by_box_at_start_none() {
410        let line = vec![Space, Empty, Space, Empty];
411        let mut c = Chain::new(7, 2, 0, line.len());
412
413        c.update_end_by_box_at_start(&line, 0);
414
415        assert_eq!(4, c.end());
416    }
417
418    #[test]
419    fn chain_update_end_by_box_at_start_one_box() {
420        let line = vec![Space, Box { color: 7 }, Space, Empty, Space, Empty];
421        let mut c = Chain::new(7, 3, 0, line.len());
422
423        c.update_end_by_box_at_start(&line, 0);
424
425        assert_eq!(4, c.end());
426    }
427
428    #[test]
429    fn chain_update_end_by_box_at_start_box_beyond_end() {
430        let line = vec![Space, Box { color: 7 }, Space, Empty, Space, Empty];
431        let mut c = Chain::new(7, 3, 0, line.len());
432
433        c.update_end_by_box_at_start(&line, 2);
434
435        assert_eq!(6, c.end());
436    }
437
438    #[test]
439    fn chain_update_end_by_box_at_start_false_color() {
440        let line = vec![
441            Box { color: 8 },
442            Box { color: 7 },
443            Box { color: 1 },
444            Space,
445            Empty,
446            Space,
447        ];
448        let mut c = Chain::new(1, 3, 0, line.len());
449
450        c.update_end_by_box_at_start(&line, 0);
451
452        assert_eq!(5, c.end());
453    }
454
455    #[test]
456    fn chain_update_end_by_box_at_start_multiple_boxes() {
457        let line = vec![
458            Space,
459            Box { color: 7 },
460            Space,
461            Box { color: 7 },
462            Space,
463            Empty,
464            Space,
465        ];
466        let mut c = Chain::new(7, 2, 0, line.len());
467
468        c.update_end_by_box_at_start(&line, 0);
469
470        assert_eq!(3, c.end());
471    }
472
473    #[test]
474    fn chain_update_end_by_box_at_start_box_at_start() {
475        let line = vec![Space, Empty, Space, Box { color: 7 }, Space];
476        let mut c = Chain::new(7, 3, 0, line.len());
477
478        c.update_end_by_box_at_start(&line, 0);
479
480        assert_eq!(5, c.end());
481    }
482
483    #[test]
484    fn chain_update_end_by_box_at_start_box_empty_range() {
485        let line = vec![Space, Empty, Space, Empty, Space];
486        let mut c = Chain::new(7, 3, 0, line.len());
487
488        c.update_end_by_box_at_start(&line, 2);
489
490        assert_eq!(5, c.end());
491    }
492
493    #[test]
494    fn chain_update_start_by_adjacent_fully_at_left() {
495        let line = vec![Box { color: 4 }, Box { color: 4 }, Empty, Empty];
496        let mut c = Chain::new(4, 2, 0, line.len());
497
498        c.update_start_by_adjacent(&line).unwrap();
499
500        assert_eq!(0, c.start());
501    }
502
503    #[test]
504    fn chain_update_start_by_adjacent_none() {
505        let line = vec![Empty, Empty, Empty, Empty, Empty];
506        let mut c = Chain::new(4, 2, 2, line.len());
507
508        c.update_start_by_adjacent(&line).unwrap();
509
510        assert_eq!(2, c.start());
511    }
512
513    #[test]
514    fn chain_update_start_by_adjacent_some_boxes() {
515        let line = vec![Box { color: 4 }, Box { color: 4 }, Empty, Empty, Empty];
516        let mut c = Chain::new(4, 2, 1, line.len());
517
518        c.update_start_by_adjacent(&line).unwrap();
519
520        assert_eq!(3, c.start());
521    }
522
523    #[test]
524    fn chain_update_start_by_adjacent_some_different_colored_boxes() {
525        let line = vec![Box { color: 2 }, Box { color: 1 }, Empty, Empty];
526        let mut c = Chain::new(4, 2, 1, line.len());
527
528        c.update_start_by_adjacent(&line).unwrap();
529
530        assert_eq!(1, c.start());
531    }
532
533    #[test]
534    fn chain_update_start_by_adjacent_some_spaces() {
535        let line = vec![Space, Space, Empty, Empty];
536        let mut c = Chain::new(4, 2, 1, line.len());
537
538        c.update_start_by_adjacent(&line).unwrap();
539
540        assert_eq!(1, c.start());
541    }
542
543    #[test]
544    fn chain_update_start_by_adjacent_boxes_err() {
545        let line = vec![Box { color: 4 }, Box { color: 4 }, Empty, Empty];
546        let mut c = Chain::new(4, 2, 1, line.len());
547
548        assert!(c.update_start_by_adjacent(&line).is_err());
549    }
550
551    #[test]
552    fn chain_update_start_by_adjacent_boxes_err_by_end() {
553        let line = vec![Box { color: 4 }, Box { color: 4 }, Empty, Empty, Empty];
554        let mut c = Chain::new(4, 2, 1, 4);
555
556        assert!(c.update_start_by_adjacent(&line).is_err());
557    }
558
559    #[test]
560    fn chain_update_end_by_adjacent_fully_at_right() {
561        let line = vec![Empty, Empty, Box { color: 4 }, Box { color: 4 }];
562        let mut c = Chain::new(4, 2, 0, line.len());
563
564        c.update_end_by_adjacent(&line).unwrap();
565
566        assert_eq!(line.len(), c.end());
567    }
568
569    #[test]
570    fn chain_update_end_by_adjacent_none() {
571        let line = vec![Empty, Empty, Empty, Empty, Empty];
572        let mut c = Chain::new(4, 2, 0, 4);
573
574        c.update_end_by_adjacent(&line).unwrap();
575
576        assert_eq!(4, c.end());
577    }
578
579    #[test]
580    fn chain_update_end_by_adjacent_some_boxes() {
581        let line = vec![Empty, Empty, Empty, Box { color: 4 }, Box { color: 4 }];
582        let mut c = Chain::new(4, 2, 0, 4);
583
584        c.update_end_by_adjacent(&line).unwrap();
585
586        assert_eq!(2, c.end());
587    }
588
589    #[test]
590    fn chain_update_end_by_adjacent_some_different_colored_boxes() {
591        let line = vec![Empty, Empty, Empty, Box { color: 2 }, Box { color: 1 }];
592        let mut c = Chain::new(4, 2, 0, 4);
593
594        c.update_end_by_adjacent(&line).unwrap();
595
596        assert_eq!(4, c.end());
597    }
598
599    #[test]
600    fn chain_update_end_by_adjacent_some_spaces() {
601        let line = vec![Empty, Empty, Empty, Space, Space];
602        let mut c = Chain::new(4, 2, 0, 4);
603
604        c.update_end_by_adjacent(&line).unwrap();
605
606        assert_eq!(4, c.end());
607    }
608
609    #[test]
610    fn chain_update_end_by_adjacent_boxes_err() {
611        let line = vec![
612            Empty,
613            Empty,
614            Box { color: 4 },
615            Box { color: 4 },
616            Box { color: 4 },
617        ];
618        let mut c = Chain::new(4, 2, 0, 4);
619
620        assert!(c.update_end_by_adjacent(&line).is_err());
621    }
622
623    #[test]
624    fn chain_update_end_by_adjacent_boxes_err_by_start() {
625        let line = vec![
626            Empty,
627            Empty,
628            Empty,
629            Box { color: 4 },
630            Box { color: 4 },
631            Box { color: 4 },
632        ];
633        let mut c = Chain::new(4, 2, 1, 5);
634
635        assert!(c.update_end_by_adjacent(&line).is_err());
636    }
637
638    #[test]
639    fn chain_update_start_by_gabs_nothing() {
640        let line = vec![Empty, Empty, Empty, Empty];
641        let mut c = Chain::new(4, 2, 2, line.len());
642
643        c.update_start_by_gabs(&line).unwrap();
644
645        assert_eq!(2, c.start());
646    }
647
648    #[test]
649    fn chain_update_start_by_gabs_spaces() {
650        let line = vec![Empty, Empty, Space, Empty, Space, Empty, Empty, Empty];
651        let mut c = Chain::new(4, 2, 1, line.len());
652
653        c.update_start_by_gabs(&line).unwrap();
654
655        assert_eq!(5, c.start());
656    }
657
658    #[test]
659    fn chain_update_start_by_gabs_boxes() {
660        let line = vec![Empty, Empty, Box { color: 4 }, Empty, Empty];
661        let mut c = Chain::new(4, 2, 1, line.len());
662
663        c.update_start_by_gabs(&line).unwrap();
664
665        assert_eq!(1, c.start());
666    }
667
668    #[test]
669    fn chain_update_start_by_gabs_different_colored_boxes() {
670        let line = vec![
671            Empty,
672            Empty,
673            Box { color: 2 },
674            Empty,
675            Box { color: 8 },
676            Empty,
677            Empty,
678            Empty,
679        ];
680        let mut c = Chain::new(4, 2, 1, line.len());
681
682        c.update_start_by_gabs(&line).unwrap();
683
684        assert_eq!(5, c.start());
685    }
686
687    #[test]
688    fn chain_update_start_by_gabs_err() {
689        let line = vec![Empty, Empty, Box { color: 2 }, Empty];
690        let mut c = Chain::new(4, 2, 1, line.len());
691
692        assert!(c.update_start_by_gabs(&line).is_err());
693    }
694
695    #[test]
696    fn chain_update_start_by_gabs_err_by_end() {
697        let line = vec![Empty, Empty, Box { color: 2 }, Empty, Empty];
698        let mut c = Chain::new(4, 2, 1, 4);
699
700        assert!(c.update_start_by_gabs(&line).is_err());
701    }
702
703    #[test]
704    fn chain_update_end_by_gabs_nothing() {
705        let line = vec![Empty, Empty, Empty, Empty];
706        let mut c = Chain::new(4, 2, 1, line.len());
707
708        c.update_end_by_gabs(&line).unwrap();
709
710        assert_eq!(line.len(), c.end());
711    }
712
713    #[test]
714    fn chain_update_end_by_gabs_spaces() {
715        let line = vec![Empty, Empty, Empty, Space, Empty, Space, Empty, Empty];
716        let mut c = Chain::new(4, 2, 0, 7);
717
718        c.update_end_by_gabs(&line).unwrap();
719
720        assert_eq!(3, c.end());
721    }
722
723    #[test]
724    fn chain_update_end_by_gabs_boxes() {
725        let line = vec![Empty, Empty, Box { color: 4 }, Empty, Empty];
726        let mut c = Chain::new(4, 2, 1, 4);
727
728        c.update_end_by_gabs(&line).unwrap();
729
730        assert_eq!(4, c.end());
731    }
732
733    #[test]
734    fn chain_update_end_by_gabs_different_colored_boxes() {
735        let line = vec![
736            Empty,
737            Empty,
738            Empty,
739            Box { color: 2 },
740            Empty,
741            Box { color: 8 },
742            Empty,
743            Empty,
744        ];
745        let mut c = Chain::new(4, 2, 1, 7);
746
747        c.update_end_by_gabs(&line).unwrap();
748
749        assert_eq!(3, c.end());
750    }
751
752    #[test]
753    fn chain_update_end_by_gabs_err() {
754        let line = vec![Empty, Box { color: 2 }, Empty];
755        let mut c = Chain::new(4, 2, 0, line.len());
756
757        assert!(c.update_end_by_gabs(&line).is_err());
758    }
759
760    #[test]
761    fn chain_update_end_by_gabs_err_by_start() {
762        let line = vec![Empty, Empty, Box { color: 2 }, Empty, Empty];
763        let mut c = Chain::new(4, 2, 1, 4);
764
765        assert!(c.update_end_by_gabs(&line).is_err());
766    }
767}
nonogram_rs/algo/chain.rs

nonogram_rs/algo/
chain.rs
