wiki-stern-diatomic-sequence.rs

1use figures::{ink, save, Board};2use mrlyrs::core::error::Result;3use mrlyrs::num::series::fibonacci;45const LEVEL: usize = 8;67fn stern(top: usize) -> Vec<usize> {8    let mut s = vec![0usize; top + 1];9    s[1] = 1;10    for n in 2..=top {11        s[n] = if n % 2 == 0 {12            s[n / 2]13        } else {14            s[n / 2] + s[n / 2 + 1]15        };16    }17    s18}1920fn main() -> Result<()> {21    let mut board = Board::square();22    let frame = board.frame(0.08);23    let s = stern(1 << LEVEL);24    let rows: Vec<&[usize]> = (0..LEVEL).map(|k| &s[1 << k..=2 << k]).collect();25    let peaks: Vec<usize> = rows26        .iter()27        .map(|row| *row.iter().max().unwrap_or(&0))28        .collect();29    assert_eq!(peaks, fibonacci(34)[1..].to_vec());30    for (k, row) in rows.iter().enumerate() {31        assert!(row.iter().eq(row.iter().rev()));32        assert_eq!(row.iter().sum::<usize>(), 3usize.pow(k as u32) + 1);33        if let Some(next) = rows.get(k + 1) {34            for (i, pair) in row.windows(2).enumerate() {35                assert_eq!(next[2 * i], pair[0]);36                assert_eq!(next[2 * i + 1], pair[0] + pair[1]);37            }38        }39    }40    let finest = frame.w / (1 << (LEVEL - 1)) as f64;41    let width = finest * 0.66;42    let span = frame.w - width;43    let band = frame.h / LEVEL as f64;44    let tall = band * 0.8;45    let mut bars = 0usize;46    let mut lit = 0usize;47    for (k, row) in rows.iter().enumerate() {48        let foot = frame.y + band * (k + 1) as f64 - (band - tall) / 2.0;49        for (i, &value) in row.iter().enumerate() {50            let hit = value == peaks[k];51            let height = tall * value as f64 / peaks[k] as f64;52            let x = frame.x + span * i as f64 / (1 << k) as f64;53            board.rect(54                x,55                foot - height,56                width,57                height,58                if hit { ink::yellow() } else { ink::blue() },59            );60            bars += 1;61            lit += hit as usize;62        }63    }64    assert_eq!(bars, 263);65    assert_eq!(lit, 15);66    save("wiki-stern-diatomic-sequence", &board)?;67    Ok(())68}