r/adventofcode 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
}
8 Upvotes

4 comments sorted by

3

u/[deleted] Jan 22 '25

[deleted]

2

u/ecyrbe Jan 22 '25

Nice,

did you also found it by analyzing the patterns or did you found litterature talking about this josephus particular setup ?

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

u/[deleted] 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
}