aoc

My solutions for the Advent of Code
git clone https://git.tronto.net/aoc
Download | Log | Files | Refs | README

b.rs (2463B)

      1 // Wow this is was terrible. Clearly you have to find out at which
      2 // exact frequency the shape repeats, but I could not find a good
      3 // way to estimate this apart from computing the first few (10^5)
      4 // rows and then manually checking.
      5 
      6 mod common;
      7 use common::*;
      8 
      9 fn line_to_u8(line: &[bool]) -> u8 {
     10     let mut r = 0;
     11     for i in 0..SCREEN_WIDTH {
     12         if line[i] { r |= 1 << i as u8; }
     13     }
     14     r
     15 }
     16 
     17 fn write_lines(screen: &Screen, v: &mut [u8]) {
     18     for i in 0..SCREEN_HEIGHT {
     19         v[i] = line_to_u8(&screen.cell[i]);
     20     }
     21 }
     22 
     23 fn isperiod(v: &[u8], l: usize) -> bool {
     24     const PERIOD_GUESS: usize = 10;
     25     const TIMES_MATCH: usize = 10;
     26 
     27     for i in 0..PERIOD_GUESS {
     28         for j in 1..TIMES_MATCH {
     29             if v[i] != v[i+j*l] { return false; }
     30         }
     31     }
     32     true
     33 }
     34 
     35 fn find_period(v: &[u8]) -> (usize, usize) {
     36     const PREP: usize = 1000;
     37     const PMAX: usize = 10000;
     38 
     39     for start in 0..PREP {
     40         for plen in 10..PMAX {
     41             if isperiod(&v[start..], plen) { return (start+1, plen); }
     42         }
     43     }
     44     panic!("No period of length < {} found with preperiod < {}",
     45         PMAX, PREP);
     46 }
     47 
     48 fn main() {
     49     const N: usize = 1000000000000;
     50 
     51     let mut screen = Screen::new();
     52     let rocks = get_rocks();
     53     let mut line = String::new();
     54     let _ = std::io::stdin().read_line(&mut line);
     55     let line = &line[0..line.len()-1]; // remove newline
     56 
     57     let mut i = 0;
     58     let mut t = 0;
     59     let mut vv = [0 as u8; SCREEN_HEIGHT];
     60     let mut ii = [0 as usize; SCREEN_HEIGHT];
     61     while screen.top < SCREEN_HEIGHT - 10 {
     62         screen.drop_rock(&rocks[i%5], &mut t, &line);
     63         ii[screen.top] = i;
     64         i += 1;
     65     }
     66     write_lines(&screen, &mut vv);
     67     let (prep, plen) = find_period(&vv);
     68 
     69     /* This part shows the period etc...
     70     println!("prep = {prep}, plen = {plen}");
     71     for j in 0..10 {
     72         for k in 0..4 {
     73             print!(" | t={:>4} i={:>4}", j+prep+k*plen, ii[j+prep+k*plen]);
     74         }
     75         println!();
     76     }
     77     */
     78 
     79     let i0 = ii[prep];
     80     let i1 = ii[prep+plen];
     81 
     82     let n = (N - i0) / (i1 - i0); // How many full repeats
     83     let t = n * plen + prep; // How tall is the thing after n full repeats
     84     // Remainder (unlike in the example case, it does not end with full repeat)
     85     let mut rem = 0;
     86     for j in 0..SCREEN_HEIGHT {
     87         if ii[j] >= i0 + (N - i0) % (i1 - i0) {
     88             rem = j-prep;
     89             break;
     90         }
     91     }
     92     println!("{}", t + rem - 1);
     93 }