Compressing a flag to 11 bits(read.vantezzen.io) |
Compressing a flag to 11 bits(read.vantezzen.io) |
I believe that is a "canton": https://en.wikipedia.org/wiki/Canton_(flag)
> In vexillography, the canton is a rectangular emblem usually placed in the upper hoist of a flag, usually occupying up to a quarter of a flag's area. The canton of a flag may be a flag in its own right. For instance, British ensigns have the Union Jack as their canton, as do their derivatives such as the national flags of Australia and New Zealand.
They say it's in the "upper hoist" because it's not per se the top left - If the flag is flying and you're seeing it from behind, it may be the top right. Either way it is the side closer to the flag pole, or whatever it's flying from. When shown on a computer screen or in print, usually it is the top left. Some flag codes require flags to be mirrored on the right side of vehicles or uniforms so that it always appears to be flying from the vehicle or person as they move forward.
fun stuff
1. Quantise colours to, say, 8 colours that you can confidently distinguish. Use a scheme that prefers "most commonly used" colours that actually appear in the flags.
2. Render each colour-quantised flag to a fixed-size bitmap, e.g., 100x50.
3. We seek a minimum-size subset of pixel locations P such that every pair of flags differs in colour at at least one of these pixel locations. This is the NP-complete problem Minimum Test Set [0] -- in fact, a slight generalisation, because the answer to each "test" (pixel location) is not yes or no but one of 10 colours. You could try to solve this by growing an exactly minimal solution using branch and bound, but this is likely to be too slow for such a large bitmap. Alternatively, I expect repeatedly running a heuristic that builds solutions by randomly adding any pixel location until all flags become distinguishable to be highly effective as there will likely be many equal-size optimal solutions, though of course you won't get an optimality guarantee this way.
4. At this point, since the 8 colours can be represented by 3 bits each, you basically have a 3|P|-bit "hash" that distinguishes all flags. If that is still bigger than log2(nFlags), you could shrink it further with standard minimal perfect hashing techniques.
ETA: There are a few ways to improve this. One thing you want is to choose relatively "stable" pixel locations that are not close to boundaries between colours on any flag, to avoid the problem of slightly different rasterisations of the same flag giving different answers (imagine if you were applying this to scanned photos of flags). To achieve this, you could compute, for each pixel location, a "stability value": The minimum distance in pixels to any differently-coloured pixel, across all flags. Then instead of considering all 100x50 pixel locations, you might consider only the 30 with the highest stability values. With such a small set of pixel locations to consider, it's feasible to consider all ~1 billion subsets of them, giving you a known-optimal solution.
There are 10 kinds of people in the world.
Those who understand binary and those who don't.
This would be superior to the 11-bit encoding presented here because it handles complexities such as coats of arms. It would also handle bizarre situations such as two countries having almost identical flags [2].
[1] https://en.wikipedia.org/wiki/List_of_countries_and_territor...
[2] https://www.worldatlas.com/articles/country-flags-that-resem...
Also, for compressing into 8 bits - is this not like saying "I can compress all of Shakespeare's plays in 6 bits" because there are ~39 plays, but then the size of the "shakespearezip" is just the sum of the works?
This encoding already goes too far towards “support the existing flags”.
As a simple example, look at the pattern of the flag of the Comoros (https://en.wikipedia.org/wiki/Flag_of_the_Comoros). Even using just the top colours (FTA: “red, then white, blue, yellow/gold, green, black and orange”), there already are 7 × 6 × 5 × 5 × 5 = 5,250 ways to colour it so that no two neighbouring colour bands are identical. That alone doesn’t fit into 12 bits.
Even limiting one to all colours different, there still are 7 × 6 × 5 × 4 × 3 = 2,520 colourings using the 7 most popular colours. That’s (just) over 11 bits.
And then, you still have to encode the crescent with the four stars.
The techniques here let you encode the currently existing flags but aren’t really enough to build a flag from scratch.
As a side note, the title is not accurate either because the method in the article can compress only one flag to 11 bits:
> Using this format, the average flag can be represented in 76 bits, with a median of 55 bits.
One can use Huffman encoding (the same encoding the article uses) to compress one of the flags to a single bit.
In fact, the article says
> With this (rather primitive) format I managed to encode 128 flags with varying success.
Which means that, actually, 7 bits would be enough.
So, this comment is (correctly) pointing out that requirements are imprecise.
You may find such "rules lawyering" obnoxious, but I think that in the real world tasks it is often useful to clarify such things, because it let's you avoid doing hard and complex work that is actually not needed.
I think that every experienced developer has this automatic response to reading a list of requirements: "here is a shortcut that will technically fulfill all the requirements. Please, either tell me that it is okay to do it, or update your requirements to close this loophole".
[0] https://read.vantezzen.io/miniflags#3d8e32040c2a808e8d95c8a0...
Obviously an arbitrary bitmap of dimensions that could be used for a recognizable flag would need orders of magnitude more storage. The constraint that we are representing a finite set of flags is what admits such a compact representation.
[1] https://www.unicode.org/Public/emoji/latest/emoji-sequences....
also then it's no different from a svg sprite
The UK flag is called the Union Flag (it's a flag and it is a union of various flags and possibly nations too!) but let's face it, given how many people think its called the Union Jack, it doesn't really matter.
If your flag pole at home is somewhat canted then I think you can call it a jackstaff, with a similar justification to the Royal Navy managing to designate their shore bases as ships. For example just up the road is HMS Heron (His Majesty's Ship: Heron).
The Union Flag/Jack is only the flag of the UK by convention and not law. It's a bit wooley, just like our Constitution but it still all works.
My point is that whilst I do enjoy this encoding scheme and it is jolly clever, reality is way more complicated. The UK's flag is pretty complicated but not alone. I'm pretty sure several flags have tassels, which I suppose strays into the coat of arms territory.
How hard do you want to squint!
I'm the kind of nerd who secretly wished to store many such bools in one integer and use the bitwise operators to query them, but restrained myself from ever doing this, since if I managed to sneak that through code review, the number of curses of my name would no doubt become so large (and so loud) over time that it would affect my employability.
To toggle a flag, you have to read the column, modify it, and write it back. If someone else does that to another flag at the same time, there’s a race that one of you might win, at the expense of the other flag’s new value.
Unless you employ a lock that would otherwise not be necessary.
[1] Part 1: https://www.youtube.com/watch?v=w5QSVhgrqVE
I think your article should use your own flags instead of the Unicode ones where possible :)
The globally distributed lookup table for Unicode flags takes 64 bits per search. You could point out that this is a tremendous waste of data for some flags :)
javascript:(function(){if(!document.getElementById('twemoji-styles')){const s=document.createElement('style');s.id='twemoji-styles';s.textContent='img.emoji{height:1em!important;width:1em!important;margin:0 .05em 0 .1em!important;vertical-align:-0.1em!important;display:inline!important;}';document.head.appendChild(s)}const r=()=>{const o={folder:'svg',ext:'.svg'};twemoji.parse(document.body,o);if(!window.__twemojiObserver){let t;const ob=new MutationObserver(()=>{clearTimeout(t);t=setTimeout(()=>{ob.disconnect();twemoji.parse(document.body,o);ob.observe(document.body,{childList:true,subtree:true});},300);});ob.observe(document.body,{childList:true,subtree:true});window.__twemojiObserver=ob;}};if(window.twemoji){r();}else{const sc=document.createElement('script');sc.src='https://cdn.jsdelivr.net/npm/@twemoji/api@latest/dist/twemoji.min.js';sc.crossOrigin='anonymous';sc.onload=r;document.head.appendChild(sc);}})();Well you see, it has to implement IStateful and IBooleanExpression, and both of those involve virtual methods so you have a vtbl pointer as well.
So that's 64+1 bits right there.
Then you also have the address-alignment requirements for that vtbl pointer, so practically speaking were talking 128 bits.
Or 80 bits of you're rolling dirty and say "screw it" to that alignment assumption.
Now if your on x86-64 and want to smuggle that bit value into the unused part of that "64" bit vtbl pointer, you could probably bring it down to just 64 bits overall I guess. Well probably want to let the compiler know about that though, before anyone tries actually using that vtbl pointer.
But, if we also need to make this accessible to Python, then...
I applaud the author holding aspect ratio as a priority to encode. It's jarring to see an otherwise correct and familiar flag stretched into an incorrect shape when flown or shown.
I noticed Rwanda seems to have the wrong aspect ratio, though you are able to encode that arbitrarily, no?
I suppose the next logical thing to do would be to train a language model to generate random flags, call it Artificial Flag Intelligence (AFI) and raise a $10m pre-seed at $100m post. :P
Perhaps every month I should bestow a Procrustean Award on some Show HN like this. I hereby proclaim the September 2026 Procrustean Award goes to vantezzen for their 11-bit flag-encoding.
I will also point out that flags change over time, and there may be more than one flag in use by an entity (the latter is something that Unicode ignores.)
And my favorite flag drama of the 2020s is when Wikipedia "discovered" that its Vatican Flag image was "wrong"... after distributing it far and wide: https://www.ewtnnews.com/world/us/wikipedia-had-the-wrong-va...
> In Greek mythology, Procrustes [...] was a rogue smith and bandit from Attica who attacked people by stretching them or cutting off their legs, so as to force them to fit the size of an iron bed.
> The word Procrustean is thus used by analogy to describe, for example, situations where an arbitrary standard is used to measure success, while completely disregarding obvious harm that results from the effort.
Strangely, the ZX81 BASIC manual mentions him in the context of "Procrustean strings"[0] - "To make sure this happens, the string that is being assigned to it is cut off on the right if it is too long, or filled out with spaces if it is too short - this is called Procrustean assignment after the inn-keeper Procrustes who used to make sure that his guests fitted the bed by either stretching them out on a rack or cutting their feet off."
[0] https://archive.org/details/zx-81-basic-programming/page/n59...
I'll admit, I was hoping for some geometric approximations for countries like Brazil, though.
The Brazilian flag is nominally "quite" simple: Green with a yellow/gold parallelogram/rhombus with a blue circle ... then there is the white band and stars. Absolute nightmare to classify.
I thought the UK flag was a bit of a challenge and I remember an art class 50 odd years ago, trying to paint the bloody thing. Little did I know at the time about how Aussies and Kiwi worriers and co would fare! Won't someone think of Hawaiians: their state flag is not something you depict for a quick laugh!
I suppose the US flag is arguably the hardest to depict: Those stars would take ages to draw/paint/dribble. I imagine kids get a box of stars to stick on their depictions in art classes in the US.
There are different aspect ratios too, plus there is the 'jack'. I don't care for AI but I do like SVG to be human readable to some extent, although I do like oklch colours, which are not something I consider 'human readable'.
Here I have the Scottish flag, the English one, a 'GB' flag which slaps one on top of the other with those Irish extras, to make a UK 'Jack' that waves badly because SVG filters are not something I am good at.
Excuse the SVG code:
<defs id="flags">
<symbol id="england" fill="white" clip-path="url(#flag-clip-two-by-one)">
<title>England</title>
<use href="#bounding-square"/>
<g id="st-george-cross" stroke="oklch(0.5472 0.242 22.16)" stroke-width="12">
<g id="england-flag-cross" transform="translate(60 60)">
<line id="england-flag-line" x1="-60" x2="60"/>
<use href="#england-flag-line" transform="rotate(90)"/>
</g>
</g>
</symbol>
<symbol id="gb" clip-path="url(#flag-clip-two-by-one)">
<title>United Kingdom</title>
<use fill="oklch(0.2873 0.139 259.18)" href="#saltire"/>
<g id="st-patrick-lhs" stroke-linecap="square">
<line id="st-patrick-red-line" x2="60" y1="32" y2="62" stroke="oklch(0.5472 0.242 22.16)"
stroke-width="4"/>
<use href="#st-patrick-red-line" transform="translate(0 124) scale(1 -1)"/>
</g>
<use href="#st-patrick-lhs" transform="translate(120 -4) scale(-1 1)"/>
<use stroke="white" stroke-width="20" href="#england-flag-cross"/>
<use href="#st-george-cross"/>
</symbol>
<symbol id="scotland">
<title>Scotland</title>
<g fill="oklch(0.5079 0.1766 247.88)" clip-path="url(#flag-clip-two-by-one)">
<g id="saltire">
<use href="#bounding-square"/>
<g transform="translate(60 60)">
<line id="saltire-white" x1="-60" x2="60" y1="-30" y2="30" stroke="white"
stroke-width="12"/>
<use href="#saltire-white" transform="scale(-1 1)"/>
</g>
</g>
</g>
</symbol>
<symbol id="union-jack">
<title>Union Jack</title>
<defs>
<filter id="flag-wave">
<feTurbulence type="fractalNoise" baseFrequency="0.0025" numOctaves="3"
result="flag-wave-fractal-noise" seed="42">
<animate attributeName="baseFrequency" values="0.0025;0.01;0.002;0.005;0.004;0.0025"
dur="12s" repeatCount="indefinite"/>
</feTurbulence>
<feDisplacementMap xChannelSelector="R" yChannelSelector="B" in="SourceGraphic"
in2="flag-wave-fractal-noise" result="flag-wave-fractal-source" scale="50"/>
<feGaussianBlur in="flag-wave-fractal-source" stdDeviation="0.4"/>
<feMorphology operator="dilate" radius="0.5"/>
</filter>
<radialGradient id="radial-glow">
<stop offset="0%" stop-color="white"/>
<stop offset="100%" stop-color="grey"/>
</radialGradient>
<linearGradient id="flagpole-gradient">
<stop offset="0%" stop-color="grey"/>
<stop offset="55%" stop-color="white"/>
<stop offset="90%" stop-color="darkgrey"/>
</linearGradient>
</defs>
<g transform="rotate(10)translate(25,10)">
<use href="#gb" transform="translate(7, -10)scale(0.75)" filter="url(#flag-wave)"/>
<circle r="3.5" fill="url(#radial-glow)" stroke="none"/>
<rect y="2.5" x="-2.5" width="5" height="120" stroke="none" fill="url(#flagpole-gradient)"/>
</g>
</symbol>
</defs>One problem though. The Union Jack is not symmetrical. This is tantamount to spelling someone's name incorrectly, and could be taken the wrong way, much like how some Americans would be offended if there weren't all the stars or stripes depicted.
<g xmlns="http://www.w3.org/2000/svg" clip-path="url(#cxr741hpqpxhvpg0uu2qvnr_0)">
<rect x="0" y="0" width="1" height="0.5" fill="#012169"/>
<line x1="0" y1="0.5" x2="1" y2="0" stroke="#fff" stroke-width="0.09"/>
<line x1="0" y1="0" x2="1" y2="0.5" stroke="#fff" stroke-width="0.09"/>
<line x1="0" y1="0.5" x2="1" y2="0" stroke="#c8102e" stroke-width="0.0375"/>
<line x1="0" y1="0" x2="1" y2="0.5" stroke="#c8102e" stroke-width="0.0375"/>
<rect x="0" y="0.2" width="1" height="0.1" fill="#fff"/>
<rect x="0.45" y="0" width="0.1" height="0.5" fill="#fff"/>
<rect x="0" y="0.22" width="1" height="0.06" fill="#c8102e"/>
<rect x="0.47" y="0" width="0.06" height="0.5" fill="#c8102e"/>
</g>
For 'human readable', if something is mirrored, the code should reflect that, with 'use' and transform 'scale(-1, 1)'. More groups could be used to contain elements that share the same colour or stroke.
In my 'hand coded' GB flag the weird offset-symmetry of the Northern Ireland 'red diagonals' is explained in SVG.
I am not that keen on CSS in SVG, however, for colours, I could be using CSS variables.
While in fairness the remaining flags seem like they would need more hard coded symbols, it’s still interesting as a procedural plausible flag generator.
We could also complain that the crescent is a complex primitive. Why not define it with three parameters: two circle radii with a center offset?
Choosing the primitives is hard and requires domain knowledge/taste, and finding a simple enough implementation solving for key usecases (e.g. decent coverage of maps, meaningful bit encoding) and descoping (e.g. deciding on no emblems) is also hard.
But I am personally impressed with the primitives the author created and the scope simplifications done to achieve it.
Often, when the Flag's depicted in kids' art, paints or paint pens are used, since 'negative space' stars would take forever to do with a blue marker or pencil but is quicker to paint on top of blue. And there's a great deal of artistic license used in terms of their size and color. Or on a small flag, just a lot of tiny white dots!
50 odd years later, I note that hardly any Brit owns or has ever owned a Union flag. Not only that but how many people would know if it is upside down!
The right way up is thick white stripe on the top edge, nearest to the pole.