# Rust, (12, 11)

This is basically a line-by-line port of Jonathan Allen's answer, with is already very good. Thanks! I wrote this to practice some Rust.

It uses the [nohash-hasher](https://crates.io/crates/nohash-hasher) crate for extremely fast HashMap lookups, with take up the vast majority of the time.

[Try it online on rustexplorer.com](https://www.rustexplorer.com/b#LyoKW2RlcGVuZGVuY2llc10Kbm9oYXNoLWhhc2hlciA9ICIwLjIuMCIKKi8KCiMhW3dhcm4oY2xpcHB5OjphbGwpXQoKdXNlIHN0ZDo6Y29sbGVjdGlvbnM6Omhhc2hfbWFwOjpFbnRyeTsKdXNlIHN0ZDo6Y29sbGVjdGlvbnM6OlZlY0RlcXVlOwp1c2Ugc3RkOjp0aW1lOjpJbnN0YW50OwoKdXNlIG5vaGFzaF9oYXNoZXI6OntJbnRNYXAsIEludFNldH07CgpmbiBjb3VudF9maXhlZF9kaXN0YW5jZShzOiAmc3RyLCBrOiB1MzIpIC0+IHVzaXplIHsKICAgIGxldCBuID0gaTMyOjpmcm9tX3N0cl9yYWRpeCgmZm9ybWF0ISgiMXtzfSIpLCAyKS51bndyYXAoKTsKICAgIGxldCBtdXQgZGlzdGFuY2VzID0KICAgICAgICBJbnRNYXA6OndpdGhfY2FwYWNpdHlfYW5kX2hhc2hlcigxIDw8IChzLmxlbigpICsgayBhcyB1c2l6ZSksIERlZmF1bHQ6OmRlZmF1bHQoKSk7CiAgICBkaXN0YW5jZXMuaW5zZXJ0KG4sIDApOwogICAgbGV0IG11dCBxdWV1ZSA9IFZlY0RlcXVlOjpmcm9tKFsobiwgcy5sZW4oKSldKTsKICAgIC8vIGNhcGFjaXR5IGlzIGp1c3QgZXhwZXJpbWVudGF0aW9uCiAgICBsZXQgbXV0IHZhbGlkID0gSW50U2V0Ojp3aXRoX2NhcGFjaXR5X2FuZF9oYXNoZXIoMSA8PCAoayArIDEpLCBEZWZhdWx0OjpkZWZhdWx0KCkpOwogICAgd2hpbGUgbGV0IFNvbWUoKGN1cnJlbnQsIGJpdF9jb3VudCkpID0gcXVldWUucG9wX2Zyb250KCkgewogICAgICAgIGxldCBuZXh0X2Rpc3QgPSBkaXN0YW5jZXMuZ2V0KCZjdXJyZW50KS51bndyYXAoKSArIDE7CiAgICAgICAgbGV0IG11dCBwb3cgPSAwOwogICAgICAgIGZvciBlIGluIDAuLmJpdF9jb3VudCB7CiAgICAgICAgICAgIGxldCBsZWZ0ID0gY3VycmVudCA+PiBlOwogICAgICAgICAgICBsZXQgbGVmdF8xID0gbGVmdCA8PCAxOwogICAgICAgICAgICBwb3cgPSAxIDw8IGU7CiAgICAgICAgICAgIGxldCByaWdodCA9IGN1cnJlbnQgJSBwb3c7CiAgICAgICAgICAgIGxldCBicDEgPSBiaXRfY291bnQgKyAxOwogICAgICAgICAgICBmb3IgKG5leHQsIG5leHRfYml0X2NvdW50KSBpbiBbCiAgICAgICAgICAgICAgICAoKGxlZnQgPj4gMSA8PCBlKSB8IHJpZ2h0LCBiaXRfY291bnQgLSAxKSwKICAgICAgICAgICAgICAgIChjdXJyZW50IF4gcG93LCBiaXRfY291bnQpLAogICAgICAgICAgICAgICAgKChsZWZ0XzEgPDwgZSkgfCByaWdodCwgYnAxKSwKICAgICAgICAgICAgICAgICgoKGxlZnRfMSB8IDEpIDw8IGUpIHwgcmlnaHQsIGJwMSksCiAgICAgICAgICAgIF0gewogICAgICAgICAgICAgICAgbWF0Y2ggZGlzdGFuY2VzLmVudHJ5KG5leHQpIHsKICAgICAgICAgICAgICAgICAgICBFbnRyeTo6VmFjYW50KHZlKSA9PiB7CiAgICAgICAgICAgICAgICAgICAgICAgIHZlLmluc2VydChuZXh0X2Rpc3QpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBFbnRyeTo6T2NjdXBpZWQoXykgPT4gY29udGludWUsCiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiBuZXh0X2Rpc3QgPCBrIHsKICAgICAgICAgICAgICAgICAgICBxdWV1ZS5wdXNoX2JhY2soKG5leHQsIG5leHRfYml0X2NvdW50KSk7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIHZhbGlkLmluc2VydChuZXh0KTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgZm9yIG5leHQgaW4gW3BvdyA8PCAyIHwgY3VycmVudCwgMyA8PCBiaXRfY291bnQgXiBjdXJyZW50XSB7CiAgICAgICAgICAgIG1hdGNoIGRpc3RhbmNlcy5lbnRyeShuZXh0KSB7CiAgICAgICAgICAgICAgICBFbnRyeTo6VmFjYW50KHZlKSA9PiB7CiAgICAgICAgICAgICAgICAgICAgdmUuaW5zZXJ0KG5leHRfZGlzdCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBFbnRyeTo6T2NjdXBpZWQoXykgPT4gY29udGludWUsCiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgbmV4dF9kaXN0IDwgayB7CiAgICAgICAgICAgICAgICBxdWV1ZS5wdXNoX2JhY2soKG5leHQsIGJpdF9jb3VudCArIDEpKTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIHZhbGlkLmluc2VydChuZXh0KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHZhbGlkLmxlbigpCn0KCmZuIG1haW4oKSB7CiAgICBsZXQgc3RhcnQgPSBJbnN0YW50Ojpub3coKTsKICAgIGxldCBtdXQgcyA9IFN0cmluZzo6d2l0aF9jYXBhY2l0eSgzMik7CiAgICBzLnB1c2goJzAnKTsKICAgIGxldCBtdXQgdiA9IDA7CiAgICB3aGlsZSBzLmxlbigpIDw9IDEyIHsKICAgICAgICAvLyBhcHByb3ggMiBtaW51dGVzIGZvciBwcm9maWxpbmcKICAgICAgICBmb3IgayBpbiAxLi4ocy5sZW4oKSArIDEpIHsKICAgICAgICAgICAgcHJpbnRsbiEoInt9IHt9IHt9Iiwgcy5sZW4oKSwgaywgY291bnRfZml4ZWRfZGlzdGFuY2UoJnMsIGsgYXMgdTMyKSk7CiAgICAgICAgfQogICAgICAgIHMucHVzaChbJzEnLCAnMScsICcwJywgJzAnXVt2ICUgNF0pOwogICAgICAgIHYgKz0gMTsKICAgICAgICBwcmludGxuISgie30iLCBzKQogICAgfQogICAgcHJpbnRsbiEoInt9IHNlY29uZHMiLCBzdGFydC5lbGFwc2VkKCkuYXNfc2Vjc19mMzIoKSk7Cn0K). Runs an unoptimized debug build, so don;t rely on it for measurements.

```rust
#![warn(clippy::all)]

use std::collections::VecDeque;
use std::collections::hash_map::Entry;
use std::time::Instant;

use nohash_hasher::{IntMap, IntSet};

fn count_fixed_distance(s: &str, k: u32) -> usize {
    let n = i32::from_str_radix(&format!("1{s}"), 2).unwrap();
    let mut distances = IntMap::with_capacity_and_hasher(1 << (s.len() + k as usize), Default::default());
    distances.insert(n, 0);
    let mut queue = VecDeque::from([(n, s.len())]);
    // capacity is just experimentation
    let mut valid = IntSet::with_capacity_and_hasher(1 << (k + 1), Default::default());
    while let Some((current, bit_count)) = queue.pop_front() {
        let next_dist = distances.get(&current).unwrap() + 1;
        let mut pow = 0;
        for e in 0..bit_count {
            let left = current >> e;
            let left_1 = left << 1;
            pow = 1 << e;
            let right = current % pow;
            let bp1 = bit_count + 1;
            for (next, next_bit_count) in [
                ((left >> 1 << e) | right, bit_count - 1),
                (current ^ pow, bit_count),
                ((left_1 << e) | right, bp1),
                (((left_1 | 1) << e) | right, bp1)
            ] {
                match distances.entry(next) {
                    Entry::Vacant(ve) => {
                        ve.insert(next_dist);
                    }
                    Entry::Occupied(_) => continue,
                }
                if next_dist < k {
                    queue.push_back((next, next_bit_count));
                } else {
                    valid.insert(next);
                }
            }
        }

        for next in [pow << 2 | current, 3 << bit_count ^ current] {
            match distances.entry(next) {
                Entry::Vacant(ve) => {
                    ve.insert(next_dist);
                }
                Entry::Occupied(_) => continue,
            }
            if next_dist < k {
                queue.push_back((next, bit_count + 1));
            } else {
                valid.insert(next);
            }
        }
    }
    valid.len()
}

fn main() {
    let start = Instant::now();
    let mut s = String::with_capacity(32);
    s.push('0');
    let mut v = 0;
    while s.len() <= 12 { // approx 2 minutes for profiling
        for k in 1..(s.len() + 1) {
            println!("{} {} {}", s.len(), k, count_fixed_distance(&s, k as u32));
        }
        s.push(['1', '1', '0', '0'][v % 4]);
        v += 1;
        println!("{}", s)
    }
    println!("{} seconds", start.elapsed().as_secs_f32());
}
```