Skip to main content

Advent of PBT 2024 · Day 16

· 2 min read
Nicolas Dubien
Nicolas Dubien
fast-check maintainer

Christmas is at risk! In their rush to meet tight deadlines, Santa’s elves accidentally introduced bugs into critical algorithms. If these issues aren’t discovered in time, Christmas could be delayed for everyone worldwide!

Your mission is to troubleshoot these black-box algorithms using the power of fast-check.

The clock is ticking. Santa just pinged you with your next challenge: the elves’ algorithm for generating Santa Codes might have some hidden flaws. Can you use your debugging skills to uncover any issues and ensure the system works flawlessly? 🎄✨

Santa Code​

Santa came up with a creative twist on counting. Instead of using the traditional numeric sequence (1, 2, 3, 4, ...), he designed a system where each consecutive number differs from the previous one by exactly one bit.

For example, instead of the sequence 0, 1, 2, 3, the Santa Code sequence looks like this:

  • 0 → 00
  • 1 → 01
  • 3 → 11
  • 2 → 10

This approach ensures each number differs in only a single binary digit.

Santa tasked his elves with implementing an algorithm that takes an index and returns the corresponding Santa Code. The sequence starts like this:

  • Index 0 returns 0
  • Index 1 returns 1
  • Index 2 returns 3
  • Index 3 returns 2
  • Index 4 returns 6

Of course, the sequence goes well beyond these first few values, as you can imagine.

Hands on​

The elves implemented it in a "flawless way" as they told Santa. But Santa has his doubts. He’s asking for your help to confirm the algorithm works perfectly.

Your mission: Can you identify an integer input (within the range of 0 to 2**31 - 1, likely sufficient) that causes the elves’ implementation to produce an invalid result—something that doesn’t align with Santa's expectations?

Santa is counting on you to validate his system and find any hidden flaws! 🎅✨

import fc from 'fast-check';
import santaCode from './advent.js';

// declare santaCode(n: number): number;
test('helping Santa', () => {
  fc.assert(fc.property(fc.constant('noop'), (noop) => {
  }));
})

Open browser consoleTests

Open in CodeSandbox for more options: including typings...

note

Can’t access the online playground? Prefer to run it locally?
No problem! You can download the source file here.

Your answer​


Comments​