adventofcode

commit

4659c1dae09fd1aa649353618b3cfe86cf75cb9c

parent

791c7e1cb91b5745f234173dfb46eff7edb7d703

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2021-12-21 10:21

add elegant solution from reddit

https://neddit.ce9e.org/r/adventofcode/comments/rl6p8y/2021_day_21_solutions/hpeokw2/

Diffstat

1 files changed, 81 insertions, 0 deletions

diff --git a/2021/21/part2_simple.rs b/2021/21/part2_simple.rs

@@ -0,0 +1,81 @@
   -1     1 use std::env::args;
   -1     2 use std::fs::File;
   -1     3 use std::io::BufRead;
   -1     4 use std::io::BufReader;
   -1     5 
   -1     6 fn get_data() -> (u8, u8) {
   -1     7     let path = args().nth(1).unwrap();
   -1     8     let file = File::open(path).unwrap();
   -1     9 
   -1    10     let mut state = 0;
   -1    11     let mut player1 = 0;
   -1    12     let mut player2 = 0;
   -1    13 
   -1    14     for line in BufReader::new(file).lines() {
   -1    15         match state {
   -1    16             0 => {
   -1    17                 player1 = line.unwrap()[28..].parse::<u8>().unwrap();
   -1    18                 state = 1;
   -1    19             },
   -1    20             1 => {
   -1    21                 player2 = line.unwrap()[28..].parse::<u8>().unwrap();
   -1    22                 state = 2;
   -1    23             },
   -1    24             _ => unreachable!(),
   -1    25         }
   -1    26     }
   -1    27 
   -1    28     return (player1 - 1, player2 - 1);
   -1    29 }
   -1    30 
   -1    31 fn index(pos1: u8, pos2: u8, score1: u8, score2: u8) -> usize {
   -1    32     return usize::from(pos1)
   -1    33         + usize::from(pos2) * 10
   -1    34         + usize::from(score1) * 10 * 10
   -1    35         + usize::from(score2) * 10 * 10 * 21;
   -1    36 }
   -1    37 
   -1    38 fn play_dirac(pos1: u8, pos2: u8, score1: u8, score2: u8, mut cache: &mut [Option<(u64, u64)>; 10 * 10 * 21 * 21]) -> (u64, u64) {
   -1    39     // https://neddit.ce9e.org/r/adventofcode/comments/rl6p8y/2021_day_21_solutions/hpeokw2/
   -1    40     if score2 >= 21 {
   -1    41         return (0, 1);
   -1    42     }
   -1    43 
   -1    44     let i = index(pos1, pos2, score1, score2);
   -1    45     match cache[i] {
   -1    46         None => {},
   -1    47         Some(v) => return v,
   -1    48     }
   -1    49 
   -1    50     let mut wins1 = 0;
   -1    51     let mut wins2 = 0;
   -1    52 
   -1    53     for a in [1, 2, 3].iter() {
   -1    54         for b in [1, 2, 3].iter() {
   -1    55             for c in [1, 2, 3].iter() {
   -1    56                 let pos = (pos1 + a + b + c) % 10;
   -1    57                 let score = score1 + (pos + 1);
   -1    58                 // switch players
   -1    59                 let (w2, w1) = play_dirac(pos2, pos, score2, score, &mut cache);
   -1    60                 wins1 += w1;
   -1    61                 wins2 += w2;
   -1    62             }
   -1    63         }
   -1    64     }
   -1    65 
   -1    66     cache[i] = Some((wins1, wins2));
   -1    67 
   -1    68     return (wins1, wins2);
   -1    69 }
   -1    70 
   -1    71 fn main() {
   -1    72     let (pos1, pos2) = get_data();
   -1    73     let mut cache = [None; 10 * 10 * 21 * 21];
   -1    74     let (wins1, wins2) = play_dirac(pos1, pos2, 0, 0, &mut cache);
   -1    75 
   -1    76     if wins1 > wins2 {
   -1    77         println!("{}", wins1);
   -1    78     } else {
   -1    79         println!("{}", wins2);
   -1    80     }
   -1    81 }