adventofcode

commit

e7a01cfebac1aea02cfbfdf4912e1741d6c49365

parent

9adf36531dc154ccf3144366f6f9938639460d05

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2023-12-12 17:51

perf: use smaller hash key

Diffstat

1 files changed, 14 insertions, 3 deletions

diff --git a/2023/12/solution.rs b/2023/12/solution.rs

@@ -29,6 +29,12 @@ fn parse_map(s: &str, fold: usize) -> Vec<(u128, usize)> {
   29    29     if count > 0 {
   30    30         map.push((run, count));
   31    31     }
   -1    32 
   -1    33     for (_, c) in map.iter() {
   -1    34         assert!(*c <= 128);
   -1    35     }
   -1    36     assert!(map.len() < 32);
   -1    37 
   32    38     return map;
   33    39 }
   34    40 
@@ -39,18 +45,23 @@ fn parse_runs(s: &str, fold: usize) -> Vec<usize> {
   39    45             runs.push(part.parse().unwrap());
   40    46         }
   41    47     }
   -1    48     assert!(runs.len() < 32);
   42    49     return runs;
   43    50 }
   44    51 
   -1    52 fn cache_key(i: usize, j: usize, x: usize) -> usize {
   -1    53     return (x << 10) | (j << 5) | i;
   -1    54 }
   -1    55 
   45    56 fn count(
   46    57     runs: &Vec<usize>,
   47    58     map: &Vec<(u128, usize)>,
   48    -1     cache: &mut HashMap<(usize, usize, usize), usize>,
   -1    59     cache: &mut HashMap<usize, usize>,
   49    60     i: usize,
   50    61     j: usize,
   51    62     x: usize,
   52    63 ) -> usize {
   53    -1     if let Some(result) = cache.get(&(i, j, x)) {
   -1    64     if let Some(result) = cache.get(&cache_key(i, j, x)) {
   54    65         return *result;
   55    66     }
   56    67 
@@ -89,7 +100,7 @@ fn count(
   89   100         sum += count(runs, map, cache, i, j + 1, 0);
   90   101     }
   91   102 
   92    -1     cache.insert((i, j, x), sum);
   -1   103     cache.insert(cache_key(i, j, x), sum);
   93   104 
   94   105     return sum;
   95   106 }