Skip to content

Instantly share code, notes, and snippets.

@danielhuang
Last active February 4, 2025 02:20
Show Gist options
  • Save danielhuang/d842505c457ec17450723e8a0a24f6f3 to your computer and use it in GitHub Desktop.
Save danielhuang/d842505c457ec17450723e8a0a24f6f3 to your computer and use it in GitHub Desktop.
#![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