PROJECT EULER · #0287
Quadtree Encoding (a Simple Compression Algorithm)
The quadtree encoding allows us to describe a
- the first bit deals with the complete
region; - "0" denotes a split:
the current region is divided into sub-regions of dimension ,
the next bits contains the description of the top left, top right, bottom left and bottom right sub-regions - in that order; - "10" indicates that the current region contains only black pixels;
- "11" indicates that the current region contains only white pixels.
Consider the following

This image can be described by several sequences, for example :
"001010101001011111011010101010", of length
"0100101111101110", of length
For a positive integer
- the pixel with coordinates
corresponds to the bottom left pixel, - if
then the pixel is black, - otherwise the pixel is white.
What is the length of the minimal sequence describing
Write-up coming later
The complete problem is available here. An approach, code, and answer will be added later.