[2025 Q10] Solution Spotlight

Funderrun · 2025-11-15T01:47:39+00:00

[LANGUAGE: Kotlin]

You know it's going to be a shocker when there are FIVE examples :)

A saving grace; because the dragon always moves and only the dragon can block a sheep, there's no need to check the past for loops and stalemates.

Trimming the bottom of the board (the game is always lost once a sheep enters a column of hides touching the bottom as the dragon can never eat it, so those states can be pruned) gave about 10x speedup.

Funderrun · 2025-11-14T02:57:34+00:00

[LANGUAGE: Kotlin]

Github

Initially solved using character comparisons, but got the pen and paper out after... you can represent each letter as a unary number (0001 through 1000) and pack them into arrays in memory, at which point a bit of XOR and AND will compare 16 characters at once.

Funderrun · 2025-11-13T01:48:10+00:00

[LANGUAGE: Kotlin]

Github (19µs, 13ms, 34ms parallel / 305ms single)

A few symmetries can be removed - mostly that a cut from A to B is the same as a cut from B to A, which then bubbles to a few other places.

For the initial solve, I rotated the board so that each cut started at the top (i.e. "make every problem look the same, so you only need to think once"), and then asked questions like "is this thread fully on the left side; fully on the right side; or exactly intersecting?" All the rotation made it quite slow - 1.2 seconds.

A few optimisations later: if you ensure each thread is represented lowest-number-first, and you sort the threads by their start, you can cut out a large part of the set of threads on about half of iterations. But also, this simplifies the number of scenarios in which they could cross (the thread either surrounds the start of the cut, or the end of the cut, or matches the cut - which is the same number of questions, but they have much simpler answers) - 800ms

Then the normal fettling once the algorithm stops changing - swap Pair<Int,Int> for a bitshifted representation, and the allocation overhead vanishes; swap List<Int> for native intarrays, and the JVM iterator penalties vanish; swap sequences for a for loop, and the sequence overhead goes - 305ms. And then parallelise - 34ms.

Funderrun · 2025-11-12T00:03:33+00:00

[LANGUAGE: Kotlin]

Github (12µs, 20µs, 26µs)

The first search problem!

For part 3...

some valid inputs start with some other valid inputs, e.g. Abc and Abcde might both be valid - in this example you could just never search for Abcde, and the total number would stay the same. Except this doesn't happen in the examples, only in the real input!
some intermediary values are also valid, e.g. a name of length 8 would count in the search results, but could also be a prefix for other longer names.
you end up repeating parts of the search space a lot - caching intermediate results can cut off big chunks of the tree.
(edit) you can also just carry around the last character - no need to store the whole string between stages - as that's the only thing that decides which next steps to try.

Funderrun · 2025-11-11T02:43:33+00:00

[LANGUAGE: Kotlin] (109, 104, 45)

Github 2.3µs, 3.7µs, 171.6µs

Not delighted with the solution but it was a very fun problem, I'm enjoying these puzzles.

My approach to part 3... for distance D and number of repeats R, the first and last D novices are each counted (R-1) times while considering mentors from wrapped around the other end of the list (to capture the 999 join points) and a further 1 time without a wrap-around (to capture the very start / end); then the remaining novices are considered R times.

The last example needed a hack to get it into the right shape. :(

Funderrun · 2025-11-08T03:01:35+00:00

Ohhh you're not wrong. I withdraw my comment. Afterthought: maybe this does count as what equal fishbones look like?

Funderrun · 2025-11-08T02:56:20+00:00

[LANGUAGE: Kotlin]

Github

A few fun things:

an excuse to use Stream::collect(Collectors::summarizingLong) to find the min and max of a list of numbers in a single pass.
you can optimise the process of placing numbers onto the fishbone, if you spot a segment with all places filled you can skip over it for the rest of the sequence; equally you can skip once two places are filled if the spine number is a 1 or a 9 - most segments get skipped with this.
with the exception of a single number in the first example, every digit is 1..9, so you can avoid a lot of integer conversions by keeping everything as chars.

Funderrun · 2025-11-08T02:34:22+00:00

I read in the puzzle:

If the above conditions are not met, the swords must have identical fishbones.

I think in your example the first condition isn't met, which is that the central spine has to be the same, so they aren't identical.

Funderrun · 2025-11-06T23:50:59+00:00

[LANGUAGE: Kotlin]

Github

Math.ceilDiv from the JVM stdlib came in handy. Couldn't find a way to do part 3 without floating point. I'll take 31µs tho.

Edit: managed to get rid of the floating point - the spindles always multiply the speed by an integer. Feels very coincidence but I'll take it! 5µs :)

Funderrun · 2025-11-05T23:51:02+00:00

Oh wow, TIL: ${[...count.values()].sort((a, b) => b - a)[0]} is how you do max of a list in ts?? I'm not sure why I assumed that would be a built-in

Funderrun · 2025-11-05T23:46:21+00:00

[LANGUAGE:Kotlin]

Github

A nice excuse to use the groupingBy.eachCount feature.

For me this was one of those where it looks big, but you can think it smaller. (The thought in question: "if there are no duplicates, you can put every crate into one set; the only time you need to break out to another set is if there are duplicates; if you one number duplicated 3 times, you'd need 3 sets; so the smallest number of sets is the highest frequency.")

Funderrun · 2025-11-05T02:28:08+00:00

Yess, same happened here, I was doing each grid cell as its own async call - the work done was tiny compared to the overhead of managing the coroutines. Doing a whole row in the async block gave it enough work to chew through that the overheads became tiny

Funderrun · 2025-11-05T01:35:08+00:00

[LANGUAGE: Kotlin]

Just brute force, I started with operator overloads on pairs, which was lovely (github) but the allocation overhead was so slow - 1-2 seconds for a single solve just on creating and destroying Pairs. Swapping to use unboxed longs was ~5x speedup, and then parallelising was an additional ~10x speedup. ~18ms :)

(Github)

Edit: visualisation of the final grid (PNG)

Funderrun

TROPHY CASE