Skip to main content

Advent of PBT 2024 · Day 14

· 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 reached out with a new challenge: the elves’ compression algorithm for children's letters might have some flaws. Can you identify edge cases that break the system and ensure everything works smoothly? 🎄🔧

Memory efficient storage​

With children’s letters piling up year after year, Santa asked his elves to design a basic compression algorithm to save storage space. The goal? Efficiently reduce the size of repetitive patterns in text while keeping the content readable and reversible.

The elves devised a straightforward yet effective approach and shared the core concept with Santa:

  • Identify consecutive characters
  • Replace with a count-character pair

For example: "hello" becomes "1h1e2l1o". While not particularly efficient for this example, the elves emphasize that this algorithm is just one piece of a larger, more advanced compression system they plan to implement.

Hands on​

The elves completed the task promptly and even provided a matching reverse function. However, Santa has concerns. He suspects there might be edge cases leading the system to fail. Your mission: find a text that causes issues for the system and prove that there’s a bug.

Christmas depends on your testing skills. Don’t let Santa down! 🎅🔧

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

// declare type Compressor = { compress: (text: string) => string; decompress: (compressed: string) => string };
// declare function buildCompressor();
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​