-
-
Save danielhuang/d842505c457ec17450723e8a0a24f6f3 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#![feature(portable_simd)] | |
use std::{ | |
array, | |
collections::{BTreeSet, HashSet}, | |
process::{abort, exit}, | |
simd::{ | |
cmp::{SimdPartialEq, SimdPartialOrd}, | |
num::{SimdFloat, SimdUint}, | |
LaneCount, Simd, SupportedLaneCount, | |
}, | |
sync::atomic::{AtomicU32, Ordering}, | |
thread::{self, available_parallelism}, | |
time::Instant, | |
}; | |
// all 9 digits are distinct | |
fn is_good_simd(mut x: u32) -> bool { | |
if x > 999999999 { | |
return false; | |
} | |
let a = x / 1000000; | |
let b = (x / 1000) % 1000; | |
let c = x % 1000; | |
let d = Simd::from_array([a, b, c, 0]); | |
let d0 = d % Simd::from_array([10, 10, 10, 10]); | |
let d1 = (d / Simd::from_array([10, 10, 10, 10])) % Simd::from_array([10, 10, 10, 10]); | |
let d2 = (d / Simd::from_array([100, 100, 100, 100])) % Simd::from_array([10, 10, 10, 10]); | |
let e0 = Simd::from_array([1, 1, 1, 0]) << d0; | |
let e1 = Simd::from_array([1, 1, 1, 0]) << d1; | |
let e2 = Simd::from_array([1, 1, 1, 0]) << d2; | |
let f = e0 | e1 | e2; | |
let g = f.reduce_or(); | |
g.count_ones() == 9 | |
} | |
fn is_good_many<const N: usize>(xs: Simd<u32, N>) -> u32 | |
where | |
LaneCount<N>: SupportedLaneCount, | |
{ | |
let mut seen = Simd::from_array([0u32; N]); | |
let mut x = xs; | |
for _ in 0..9 { | |
let after_div = x / Simd::splat(10); | |
let last_digit = x - (after_div * Simd::splat(10)); | |
let mask = Simd::from_array([1u32; N]) << last_digit; | |
seen |= mask; | |
x = after_div; | |
} | |
let unseen = Simd::from_array([0b1111111111; N]) - seen; | |
let unseen: Simd<f32, N> = unseen.cast(); | |
let unseen = unseen.to_bits(); | |
let bad = Simd::splat(0x7FFFFFu32) & unseen; | |
let bad = bad.simd_ne(Simd::splat(0)); | |
let bad = bad | xs.simd_gt(Simd::splat(999999999)); | |
bad.select(Simd::splat(0u32), Simd::splat(1u32)) | |
.reduce_sum() | |
} | |
fn is_good_plain(mut n: u32) -> bool { | |
let mut digits = 0u32; | |
for _ in 0..9 { | |
let last_digit = n % 10; | |
n /= 10; | |
digits |= (1 << last_digit); | |
} | |
assert!(n == 0); | |
digits.count_ones() == 9 | |
} | |
fn is_good_slow(n: u32) -> bool { | |
let digits: HashSet<_> = n.to_string().chars().collect(); | |
digits.len() == 9 | |
} | |
fn multiples(n: u32) -> impl Iterator<Item = u32> { | |
(1..) | |
.map(move |x| x * n) | |
.take_while(|x| *x <= 999999999) | |
.filter(|x| is_good_simd(*x)) | |
} | |
fn has_enough_good_multiples(n: u32) -> bool { | |
const BLOCK_SIZE: usize = 16; | |
const OFFSETS: [u32; BLOCK_SIZE] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; | |
let mut count = 0; | |
for offset in (0..).step_by(BLOCK_SIZE) { | |
if n * offset > 999999999 { | |
break; | |
} | |
let test = | |
Simd::from_array([n; BLOCK_SIZE]) * (Simd::splat(offset) + Simd::from_array(OFFSETS)); | |
count += is_good_many(test); | |
if count >= 9 { | |
return true; | |
} | |
} | |
false | |
} | |
fn has_enough_good_multiples_plain(n: u32) -> bool { | |
(1..) | |
.map(|x| x * n) | |
.take_while(|x| *x <= 999999999) | |
.filter(|x| is_good_plain(*x)) | |
.nth(8) | |
.is_some() | |
} | |
fn has_enough_good_multiples_simd(n: u32) -> bool { | |
(1..) | |
.map(|x| x * n) | |
.take_while(|x| *x <= 999999999) | |
.filter(|x| is_good_simd(*x)) | |
.nth(8) | |
.is_some() | |
} | |
fn has_enough_good_multiples_slow(n: u32) -> bool { | |
(1..) | |
.map(|x| x * n) | |
.take_while(|x| *x <= 999999999) | |
.filter(|x| is_good_slow(*x)) | |
.nth(8) | |
.is_some() | |
} | |
fn is_valid_col(board: &[u32], pos: usize, used: &mut HashSet<u8>) -> bool { | |
used.clear(); | |
for row in board.iter() { | |
let digit = ((row / 10u32.pow(8 - pos as u32)) % 10) as u8; | |
if !used.insert(digit) { | |
return false; | |
} | |
} | |
true | |
} | |
fn is_valid_box(board: &[u32], row: usize, used: &mut HashSet<u8>) -> bool { | |
used.clear(); | |
let box_row = row / 3; | |
for r in (box_row * 3)..=row { | |
let num = board[r]; | |
let start = (row % 3) * 3; | |
for i in start..start + 3 { | |
let digit = ((num / 10u32.pow(8 - i as u32)) % 10) as u8; | |
if !used.insert(digit) { | |
return false; | |
} | |
} | |
} | |
true | |
} | |
fn digit(n: u32, i: u32) -> u32 { | |
(n / 10u32.pow(8 - i)) % 10 | |
} | |
fn solve(board: &mut Vec<u32>, row: usize, m: &[u32], used: &mut HashSet<u8>) -> bool { | |
if board.len() == 9 { | |
return true; | |
} | |
for &num in m { | |
match row { | |
0 if digit(num, 7) != 2 => { | |
continue; | |
} | |
1 if digit(num, 8) != 5 => { | |
continue; | |
} | |
2 if digit(num, 1) != 2 => { | |
continue; | |
} | |
3 if digit(num, 2) != 0 => { | |
continue; | |
} | |
5 if digit(num, 3) != 2 => { | |
continue; | |
} | |
6 if digit(num, 4) != 0 => { | |
continue; | |
} | |
7 if digit(num, 5) != 2 => { | |
continue; | |
} | |
8 if digit(num, 6) != 5 => { | |
continue; | |
} | |
_ => {} | |
} | |
board.push(num); | |
let mut valid = true; | |
for col in 0..9 { | |
if !is_valid_col(&board, col, used) { | |
valid = false; | |
break; | |
} | |
} | |
if valid && row % 3 == 2 { | |
if !is_valid_box(board, row, used) { | |
valid = false; | |
} | |
} | |
if valid && solve(board, row + 1, m, used) { | |
return true; | |
} | |
board.pop().unwrap(); | |
} | |
false | |
} | |
fn main() { | |
let start = Instant::now(); | |
let gcd = AtomicU32::new(111111111); | |
thread::scope(|s| { | |
for _ in 0..available_parallelism().unwrap().get() { | |
s.spawn(|| loop { | |
let x = gcd.fetch_sub(1024, Ordering::Relaxed); | |
for x in (x - 1024)..x { | |
if has_enough_good_multiples(x) { | |
let m: Vec<_> = multiples(x).collect(); | |
let mut board = vec![]; | |
if solve(&mut board, 0, &m, &mut HashSet::new()) { | |
dbg!(start.elapsed()); | |
dbg!(x, &board, board[4]); | |
exit(0); | |
} | |
} | |
} | |
}); | |
} | |
}); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment