every_5x5_nonogram.rs

use std::collections::hash_map::Entry;
use std::collections::HashMap;

fn to_clue(mut line: u64) -> Vec<u8> {
    // given a row/column in a nonogram solution, find its clue
    let mut ret = Vec::new();
    let mut acc = 0;
    while line > 0 {
        if (line & 1) > 0 {
            acc += 1;
        } else {
            if acc > 0 {
                ret.push(acc);
            }
            acc = 0;
        }
        line >>= 1;
    }
    if acc > 0 {
        ret.push(acc);
    }
    ret
}

fn precompute_canonicalizations() -> Vec<u64> {
    // for each possible row/column of 5 bits, map it to the first bit sequence with the same clue
    // (maybe itself)

    let mut m: HashMap<Vec<u8>, u64> = HashMap::new();
    let mut ret: Vec<u64> = Vec::new();
    for line in 0..32 {
        let clue = to_clue(line);
        match m.entry(clue) {
            Entry::Occupied(e) => ret.push(*e.get()),
            Entry::Vacant(e) => {
                e.insert(line);
                ret.push(line)
            }
        }
    }
    ret
}

fn first_column(sol: u32) -> u32 {
    (sol & 1) | ((sol >> 4) & 2) | ((sol >> 8) & 4) | ((sol >> 12) & 8) | ((sol >> 16) & 16)
    // doesn't seem faster:
    // ((sol & 0b100001000010000100001).wrapping_mul(0b10001000100010001) >> 16) & 0x1f
}

fn all_clues(canonicalizations: &Vec<u64>, sol: u32) -> u64 {
    // given a 25-bit solution, compute representatives for clues for each of the rows and columns
    // and concatenate them into a 50-bit result
    let r1 = canonicalizations[(sol & 0x1f) as usize];
    let r2 = canonicalizations[((sol >> 5) & 0x1f) as usize];
    let r3 = canonicalizations[((sol >> 10) & 0x1f) as usize];
    let r4 = canonicalizations[((sol >> 15) & 0x1f) as usize];
    let r5 = canonicalizations[((sol >> 20) & 0x1f) as usize];

    let c1 = canonicalizations[first_column(sol) as usize];
    let c2 = canonicalizations[first_column(sol >> 1) as usize];
    let c3 = canonicalizations[first_column(sol >> 2) as usize];
    let c4 = canonicalizations[first_column(sol >> 3) as usize];
    let c5 = canonicalizations[first_column(sol >> 4) as usize];

    r1 | (r2 << 5)
        | (r3 << 10)
        | (r4 << 15)
        | (r5 << 20)
        | (c1 << 25)
        | (c2 << 30)
        | (c3 << 35)
        | (c4 << 40)
        | (c5 << 45)
}

fn main() {
    let canonicalizations = precompute_canonicalizations();
    // mapping of (all clues concatenated) -> (# of solutions with those clues)
    let mut freqs: HashMap<u64, u8> = HashMap::new();

    for sol in 0..(1 << 25) {
        freqs
            .entry(all_clues(&canonicalizations, sol))
            .and_modify(|e| *e += 1)
            .or_insert(1);
    }

    // mapping (# of solutions with some clue-concatenation) -> (# of such clue-concatenations)
    let mut freq_freqs = HashMap::new();
    for (_, v) in freqs {
        freq_freqs.entry(v).and_modify(|e| *e += 1).or_insert(1);
    }

    let mut freq_table = freq_freqs.into_iter().collect::<Vec<(u8, i32)>>();
    freq_table.sort();

    for (k, v) in freq_table {
        println!("{k} {v}")
    }
}