brute.rs

1use std::sync::atomic::{AtomicUsize, Ordering};23use crate::design::Design;45// GCD67fn gcd(mut a: u64, mut b: u64) -> u64 {8    while b != 0 {9        let rest = a % b;10        a = b;11        b = rest;12    }13    a14}1516fn walk(depth: u32, coords: &mut Vec<u64>, corners: &[Vec<u64>], found: &mut u64) {17    if depth == 0 {18        let mut common = coords[0];19        for value in coords.iter().skip(1) {20            common = gcd(common, *value);21        }22        if common == 1 {23            *found += 1;24        }25        return;26    }27    for corner in corners.iter() {28        for (slot, digit) in coords.iter_mut().zip(corner.iter()) {29            *slot = *slot * 3 + digit;30        }31        walk(depth - 1, coords, corners, found);32        for (slot, digit) in coords.iter_mut().zip(corner.iter()) {33            *slot = (*slot - digit) / 3;34        }35    }36}3738pub fn count(design: &Design, level: u32, threads: usize) -> u64 {39    let corners = design.corners();40    if level < 2 {41        let mut coords = vec![0u64; design.dimension];42        let mut found = 0u64;43        walk(level, &mut coords, &corners, &mut found);44        return found;45    }46    let fill = corners.len();47    let cursor = AtomicUsize::new(0);48    std::thread::scope(|scope| {49        let mut handles = Vec::new();50        for _ in 0..threads {51            let cursor = &cursor;52            let corners = &corners;53            handles.push(scope.spawn(move || {54                let mut found = 0u64;55                loop {56                    let task = cursor.fetch_add(1, Ordering::Relaxed);57                    if task >= fill * fill {58                        break;59                    }60                    let first = &corners[task / fill];61                    let second = &corners[task % fill];62                    let mut coords: Vec<u64> = first63                        .iter()64                        .zip(second.iter())65                        .map(|(a, b)| a * 3 + b)66                        .collect();67                    walk(level - 2, &mut coords, corners, &mut found);68                }69                found70            }));71        }72        handles.into_iter().map(|h| h.join().unwrap()).sum()73    })74}