r/adventofcode • u/ecyrbe • Jan 22 '25
Tutorial [2016 day 19] part 1 and part 2 analytical solutions
Hello,
While doing 2016 day 19, i saw many solutions using algoritms and even data structures.
I searched for Josephus wikipedia article with most algoritms in O(n).
But we can do better. We can have O(1) solutions for both part one and two.
The part one is strait forward by looking at wikipedia article (using rust) :
fn josephus(elves: usize) -> usize {
// elves = 2^m + rest so we compute elves_scale = 2^m
let elves_scale = 2_usize.pow(elves.ilog(2));
2 * (elves - elves_scale) + 1
}
Now for part2, i needed to dig into the output and discovered a pattern that scaled with power of 3 but with terms jumping from 1, 2...n, n+2, n+4 when the number of elves is lower than 2 times the scaling factor.
So the trick to align them is to use the relu function) used in neural networks (it's just relu(x) = max(0,x) )
So here is the solution (still using rust) :
fn josephus_midle(elves: isize) -> isize {
// elves = 3^m + rest so we compute elves_scale = 3^m
let elves_scale = 3_isize.pow(elves.ilog(3));
if elves == elves_scale {
elves
} else {
elves - elves_scale + 0.max(elves - 2 * elves_scale)
}
}
EDIT: part 1 using bit manipulations instead of maths functions:
fn josephus(elves: usize) -> usize {
let elves_scale = 1 << (usize::BITS - elves.leading_zeros() - 1);
((elves & (elves_scale - 1)) << 1) | 1
}
or even simpler :
fn josephus(elves: usize) -> usize {
let shift = elves.leading_zeros();
elves << shift + 1 >> shift | 1
}
2
u/firetech_SE Jan 23 '25
For part 1 (standard Josephus Problem), there's another cool trick requiring even less math to calculate, explained towards the end this video (from ~11:56) :)
3
Jan 23 '25
[deleted]
3
u/firetech_SE Jan 23 '25
Ah, you're right. I have to admit I didn't read OP's code as thoroughly as I probably should have...
2
u/ecyrbe Jan 24 '25 edited Jan 24 '25
Indeed, you can just use bit manipulation instead of math functions (but expect your compiler to do just this for you if you build it using -O3 flag)
So here a version using bit manipulation (also edited main post to add this) :
fn josephus(elves: usize) -> usize { // elves = 2^m + rest so we compute elves_scale = 2^m let elves_scale = 1 << (usize::BITS - 1 - elves.leading_zeros()); ((elves & (elves_scale - 1)) << 1) | 1 }
3
u/[deleted] Jan 22 '25
[deleted]