Sunday, 26 June 2016

Word Time 1KB

One of my inspirations for the Rotor Clock was the Instructables wordclock that tells the time (and temperature) based on a 16-by-16 grid of letters:


It looked very much like a puzzle to me, so I immediately set about trying to work out the minimum size of grid that could tell the time to an accuracy of one minute. I managed to get the grid down to 13-by-13:

TWENTYQUARTER
TWONETHIRTEEN
FOURTEENTHREE
SEVENTEENFIVE
TWELVEIGHTEEN
IDTENSIXTEENT
ELEVENINETEEN
MINUTESHALFTO
PASTBFOURNOON
MIDNIGHTWONED
THREELEVENSIX
FIVEIGHTENINE
SEVENZO'CLOCK

[I have a suspicion you can get it even smaller if you use tricks such as spelling words vertically; but, after a considerable amount of effort, I plumped for 13-by-13]

In my usual modus operandi, I then tried to optimise the heck out of the problem by hand and attempt to fit a solution into a one-kilobyte web page that works on Chrome, Firefox and Internet Explorer. For added frisson, I didn't allow myself to use non-ASCII characters nor the evil JavaScript "eval()" or its ilk. The result, World Time, takes up just 1023 bytes:


Here's a quick breakdown of the contents:

We can omit a large number HTML elements such as "DOCTYPE", "head" and "body" and dive straight into the style definitions, which are assumed by browsers to be CSS. We set all backgrounds to black, centre the table in the middle of the page and format each table cell so that a 13-by-13 grid takes up most of the viewport. The default text colour is set to very dark grey and a shadow effect is added to simulate "light bleed":


We then define a table that will hold the 169 grid characters and be accessed in the JavaScript via a identifier named "t". The string is split into 169 table cells (each one 10 characters of HTML) which are then divided into 13 rows:


Next we decode a 78-character string that has been btoa-encoded (so we adhere to our ASCII restriction). The 78 characters represent 39 pairs of offsets into the "t" grid. The first of each pair is the "start" offset (0 to 168); the second is the "end" offset plus one. These 39 pairs define tokens with even numbers identifying them thus:

           #00 = "O'CLOCK"
           #02 = "MINUTE"
           #04 = "MINUTES"
           #06 = "PAST"
           #08 = "TO"
           #10 = "HALF"
    #12 to #38 = "ONE" to "FOURTEEN" (upper portion)
           #40 = "QUARTER"
    #42 to #50 = "SIXTEEN" to "TWENTY"
           #52 = "MIDNIGHT"
    #54 to #74 = "ONE" to "ELEVEN" (lower portion)
           #76 = "NOON"

These 38 tokens constitute all the words used by the clock. See below for details of the call to "setInterval":


Next, we define a function "d()" that takes two arguments (the third argument declaration is just a short way of declaring a variable - see 140bytes for other such techniques), The first argument is the hour as an integer. The second argument is either "00" (the token for "O'CLOCK") or "" depending on requirements. The "d()" function therefore returns the hour as a string of two-digit tokens (e.g. "7400" for "ELEVEN O'CLOCK"). It has a special case for "MIDNIGHT" and "NOON" which never take the "O'CLOCK" suffix:


We define another function "g()" that takes an integer number of minutes (0 to 59) as its only argument. It returns a string of tokens representing the appropriate number of minutes as words (e.g. "(something) MINUTES" or "TWENTY (something) MINUTES", taking into consideration the exceptional cases for "ONE MINUTE", "QUARTER" and "HALF". Note that we're playing fast and loose with the type system here: the number 1202 will be converted to the string "1202" elsewhere in the program.


Next, we define an anonymous function (let's call it "storeColours") that takes one true argument ("b" is a local variable declaration again). This is called with the result of another anonymous function ("calculateColours") that takes three arguments: the current local hour, the current local minute and an empty dictionary. The "calculateColours" function constructs a full string of tokens that describe the current time. If the minute value is zero, we use the "d()" function to construct "MIDNIGHT", "NOON" or "(hour) O'CLOCK". If the minute value is less than or equal to thirty, it constructs "(something) PAST (hour)". Otherwise, if constructs "(something) TO (hour+1)". The string of tokens are split into two-digit numbers and looked up in the "s" table described above. For every letter in every word, "calculateColours" stores an HSL colour in the "c" dictionary keyed by the appropriate offset into the grid. The dictionary is then passed to "storeColours" which modifies the style text colour of each table cell in turn. Setting the colour to "" results in the text colour reverting to the colour defined in the CSS entry for "td" (i.e. very dark grey):


Finally, we invoke the "calculateColours" and "storeColours" function at most every 1000 milliseconds via the "setInterval" function mentioned above, and gracefully close the HTML tags.


A lot of the JavaScript compression came from Google Closure Compiler.

The result is a colourful clock that spells out the time in English words, uses a responsive HTML layout and takes the local timezone, changes in daylight savings and even leap-seconds into consideration.

UPDATE: 2016-06-29

I've managed to shave an additional ten bytes off the size and updated the page, but the structure and technique are essentially the same as above.

Sunday, 19 June 2016

Rotor Clock

There seems to be a bit of fad for clocks that spell out the time. There are even some online examples utilising a variety of languages. And jolly good they are too!

Spelling out the time in British English is fairly simple. Just take the local time and extract the minutes. If the value is less than thirty, express the time as

  (minutes) PAST (hour)

Otherwise, use

  (60-minutes) TO (hour+1)

There are some exceptional cases; if the minute value is zero, use

  (hour) O'CLOCK

Whereas minute values or 15, 30 and 45 are generally expressed as

  QUARTER PAST (hour)
  HALF PAST (hour)
  QUARTER TO (hour+1)

It turns out that, using the above scheme, the maximum number of characters needed to spell out the time is 32. For example:

  TWENTY SEVEN MINUTES PAST TWELVE

If we are a little bit lenient with the spacing between the words, we can prune the number of distinct characters in each position to ten (including space). This leads to an interesting configuration for a mechanical device that can spell out the time using 32 rotors of only 10 facets each.
With a little bit of CSS3 and HTML5, it's possible to produce a web page that brings such a device to life. If you further optimise the HTML, CSS and Javascript, you can present it in a single file of only 2191 bytes.

Sunday, 22 May 2016

A Short History of Long Ships

With the recent maiden voyage of "MS Harmony of the Seas," there's been a lot of talk in the press about large and long ships. So here's my attempt at a summary:

The blue whale is the largest extant animal.

La Santa María, launched in 1460, was largest of three ships used by Christopher Columbus to cross the Atlantic for the first time in 1492. She ran aground later in 1492.

The Nao Victoria, launched in 1519, was the first ship to circumnavigate the globe in 1522. She disappeared in 1570.

HMS Victory, launched in 1765, was Nelson's flagship at the Battle of Trafalgar in 1805. She is still in service.

SS Great Western, launched in 1837, was the largest passenger ship until 1839. She was broken up in 1856.

SS Great Britain, launched in 1843, was the longest passenger ship until 1854. She was finally scuttled in the Falklands in 1937.

SS Great Eastern, launched in 1858, was the longest ship built of any type until 1899. She was scrapped in 1889.

RMS Titanic, launched in 1911, was the largest ship afloat until she sunk on her maiden voyage in 1912.

RMS Queen Elizabeth, launched in 1938, was the largest (by displacement) passenger liner for almost fifty years. She finally caught fire and sunk in Hong Kong harbour in 1975.

USS Iowa, launched in 1942 and now a museum ship, is the longest battleship ever built. The Japanese Yamato was more massive, but slightly shorter.

The aircraft carrier USS Enterprise, launched in 1960, is the longest naval vessel ever built. She was decommissioned in 2012, but, being nuclear powered, she will take a long time to be completely dismantled.

SS France, launched in 1960, took over from RMS Queen Elizabeth as being the longest passenger ship. She was sold for scrap in 2005.

Batillus, launched in 1976, was the largest supertanker by gross tonnage ever built. She was scrapped in 1976.

Seawise Giant, launched in 1979, was the longest ship ever built. She was scrapped in 2010.

Dmitri Donskoi, launched in 1980, is a Typhoon-class submarine, the largest in the world. She is still in active service.

RMS Queen Mary 2, launched in 2003, is the largest ocean liner ever built. She is still in service.

Vale Brasil, launched in 2010, is the largest bulk carrier ever built. She is still in service.

Pieter Schelte, launched in 2013, is the largest vessel ever constructed in terms of gross tonnage, breadth and displacement. She is still in service.

MV Barzan, launched in 2014, is the largest container ship ever built. She is still in service.

MS Harmony of the Seas, launched in 2015, is the largest passenger ship in the world by gross tonnage. She entered service in May 2016.

The maximum length of ships in service is usually limited by canal sizes and port facilities.

See here for a larger image.

Sunday, 10 April 2016

JavaScript Flags 3

As mentioned in the previous post, the JavaScript Flags hobby project encodes the drawing instructions for each flag as a string. For examples, the Japanese flag is encoded as
"FwCrO+0+0+72"
This is split up into a sequence of instructions or commands using a regular expression match:

  ["F", "w"], 
  ["C", "r"], 
  ["O", "+0", "+0", "+72"] 
]
The first element of each instruction is always a single upper-case letter. The remaining elements are either lower-case letters usually indicating colours (see the previous post) or signed integers (expressed as strings). Often, the integers represent coordinates. No matter what the aspect ratio of the flag, the top-left corner is always (-120,-120) and the bottom-right is (+120,+120). Two hundred and forty was chosen because it fits into a byte (although that's not important for this JavaScript implementation of the flag renderer) and is highly divisible.

The command letters are as follows:

  • "A n" — Executes the next command in the sequence "n" times, rotating about the origin by (360 ÷ "n") degrees each time.
  • "x y path ..." — Draws a path made up of a mixture of straight-line and cubic Bezier segments and fills it with the current colour. See below.
  • "C c" — Sets the current colour to "c",
  • "f w" — Draws diagonal lines of width "w". If "f" is 1, a diagonal line from top-left to bottom-right is drawn. If "f" is 2, a diagonal line from top-right to bottom-left is drawn. And if "f" is 3, both diagonals are drawn.
  • "E sx sy" — Executes the next command with scaling about the origin. If either "sx" or "sy" are negative, executes the next command twice: once with scaling (abs(sx),abs(sy)) and once with scaling (sx,sy). Otherwise, just executes the next command with scaling (sx,sy).
  • "c" — Fills the entire canvas with solid colour "c".
  • "H c y0 y1" — Draws a full-width, horizontal block in colour "c" between y0 and y1, where y0 y1.
  • "J" — Draws a union flag in the top-left quadrant.
  • "M x y path ..." — Draws a mirrored path made up of a mixture of straight-line and cubic Bezier segments and fills it with the current colour. See below.
  • "O cx cy r" — Draws and fills with the current colour a circle of radius "r" centred at (cx,cy).
  • "n c[0] ..." — Draws "n" horizontal stripes. The colour of stripe "i" (where 0 ≤ i < n) is "c[i % m]" where "m" is the number of colour arguments, c.
  • "n c[0] ..." — Draws "n" vertical stripes. The colour of stripe "i" (where 0 ≤ i < n) is "c[i % m]" where "m" is the number of colour arguments, c.
  • "R x0 y0 x1 y1" — Draws and fills an axis-aligned rectangle with the current colour between (x0,y0) and (x1,y1).
  • "x y r" or "n r1 r2 x y a" — With three arguments, draws a five-pointed star filled with the current colour at (x,y) and radius "r". With six arguments, draws an "n"-pointed star filled with the current colour at (x,y), inner radius "r1" and outer radius "r2" all rotated by "a" degrees.
  • "x0 y1 x1 y0" — Draws and fills a right-angled, axis-aligned triangle whose hypotenuse is (x0,y0) to (x1,y1).
  • "c y0 y1" — Draws a full-height, vertical block in colour "c" between x0 and x1, where x0 x1.
  • "c w x" — Draws an axis-aligned cross of width "w" in colour "c". The vertical bar passed through the x-axis at "x", The horizontal bar is along the x-axis.
  • "Y n dx dy" — Executes the next command in the sequence "n" times, translating by (dx,dy) after each iteration.
  • "x0 y0 x1 y1" — Zooms in to a rectangle (x0,y0) and (x1,y1) where x0 < x1 and y0 < y1. All subsequent commands assume the 240-by-240 canvas is now (x0,y0) to (x1,y1).
The paths for the "B" and "M" commands start and finish at (x,y). The intervening points are prefixed by a lower-case letter:
  • "x y" — Lower-case "L" — A straight-line segment  from the previous point to (x,y).
  • "s x1 y1 x y" — Lower-case "S" — A smooth cubic Bezier segment from the previous point to (x,y) with control point (x1,y1).
  • "c x1 y1 x2 y2 x y" — Lower-case "C" — A general cubic Bezier segment from the previous point to (x,y) with control points (x1,y1) and  (x2,y2).
For the "M" command, the path is mirrored about a vertical axis centred on the final point of the explicitly-specified path. This allows emblems such as the double-headed Albanian eagle to be encoded very efficiently.

In summary, less than twenty commands encode the instructions for drawing most of the world's flags very effectively. The use of regular expression string splitting and function lookup maps in JavaScript makes the encoded strings short whilst keeping the decoding code equally concise,

Sunday, 13 March 2016

JavaScript Flags 2

As promised, I thought I'd take time to document some of the code behind my JavaScript flags hobby project. If you look at the data file for the flags, flagdata.js, you'll see a single JSONP-style JavaScript call:
Flags({
  AD:["Andorra",10/7,"..."],
  ...
  BL:["Saint-Barthelemy","FR"],
  ...
  JP:["Japan",3/2,"FwCrO+0+0+72"],
  ...
  ZW:["Zimbabwe",2,"..."]
});
The single argument is an object with ISO-3166 two-letter codes as keys and arrays of two or three elements as values. If the array has three elements, they are:
  1. The country or territory name, as a string;
  2. The flag's aspect ratio, as a rational floating-point number; and
  3. The instructions for drawing the flag, as a string (see below).
If the array has only two elements, they are:
  1. The country or territory name, as a string;
  2. The ISO-3166 code of the "parent" country whose flag this entry shares, as a two letter string.
The latter scheme allows "aliases" to be set up for flags that are shared by more than one territory:
  • France
  • Netherlands
  • Norway
  • United States of America
The instructions for drawing the flags as represented as a string. The pseudo-BNF of these instructions is as follows:
instructions ::= instruction ... 
instruction ::= command argument … 
command ::= 'A'..'Z' 
argument ::= number | colour 
number ::= sign digit ... 
sign ::= '+' | '-' 
digit ::= '0'..'9' 
colour ::= 'a'..'z'
It is therefore trivial to parse these instruction streams using regular expressions. For example, Japan has the following entry:
JP:["Japan",3/2,"FwCrO+0+0+72"]
The instruction stream can be split into individual instructions using:
instructions.match(/([A-Z][^A-Z]*)/g)
This produces an array:
["Fw", "Cr", "O+0+0+72"]
These three instructions can be further divided into numbers (which are always preceded with a sign) and single-letter colours:
instruction.match(/.\d*/g)
This produces an array for each instruction:
[
  ["F", "w"],
  ["C", "r"],
  ["O", "+0", "+0", "+72"]
]
The first element is thus always an upper-case letter and is used as the key into a map for commands. I'll discuss the meaning of each letter (command) next time. Subsequent elements in the instruction array are arguments to the command: numbers and/or colours. Colours are always lower-case letters:
a: #39F light-blue
b: #00F medium-blue
c: #009 dark-blue
g: #CCC grey
m: #630 brown
n: #000 black
o: #F60 dark-orange
p: #F90 light-orange
r: #F00 bright-red
s: #C00 medium-red
t: #900 dark-red
u: #060 dark-green
v: #090 medium-green
w: #FFF white
y: #FF0 yellow
But for now, we'll finish off the Japanese flag example by expanding the instruction arrays:
fill white
colour bright-red
circle +0 +0 +72
This would get translated by the JavaScript code in flags.js to the following pseudo-SVG:
svg viewbox="0 0 360 240" xmlns="http://www.w3.org/2000/svg"
  g stroke="none" transform="matrix(1.5,0,0,-1,180,120)"
    g
      rect fill="#FFF" height="240" width="240" x="-120" y="-120" /
      ellipse cx="+0" cy="+0" fill="#F00" rx="48" ry="+72" /
    /g
  /g
/svg

Sunday, 31 January 2016

JavaScript Flags 1

A few of my previous hobby projects have used a library of vector graphics approximations of the flags of the world. I decided to re-use that data in a JavaScript web page that draws those flags as SVG images.

In subsequent posts, I'll describe the data encoding for those flags and some of the compression techniques I used.


Vehicle Number Plates

One of my pet projects for the last few months has been to assemble a web page that decodes (mostly) European number plates, based on the information in Wikipedia.

There's no sane reason to put together such a page, and it's nigh on impossible to keep up-to-date and complete; but at least I've made a start. My long-term goal might have been to allow users to type in any sequence of letters and/or digits and have the web page tell them what that sequence might represent: vehicle number plates, international telephone numbers, credit card numbers, bank accounts, etc. (Ideal for many a protagonist in crime and mystery novels!) But that's a mammoth task: much better as a collaborative, crowd-sourced project.

The current page is a relatively simple client-side JavaScript program that just does regular expression matching and a few table lookups. All told, the compressed payload is about 128 kilobytes, the majority of which is taken up by a glyph grid image:


From top to bottom, the glyph sets are approximately:

  1. UK number plates since September 2001
  2. European numbers plates (FE-Schrift)
  3. UK number plates before September 2001

You may be wondering why the glyphs are red and not, say, black or white. It all comes down to the way the glyphs are coloured at "runtime". For the supported countries, we need to be able to display number plate glyphs in black, white, silver, dark red and yellow. We do this via CSS 3 filters. Alas, these filters have limited scope for "colourizing" monochrome images (except, perhaps the "sepia" function). So, instead, we start with pure red pixels (hue=0).

To achieve the various glyph colours, we simply manipulate "red" into the desired colour using the limited set of colour-transforming filter functions available to us. So, for black glyphs, we turn down the brightness to zero:

black { filter: brightness(0); }

For white, we invert black:

white { filter: brightness(0) invert(1); }

For silver, we turn down the brightness of white:

silver { filter: brightness(0) invert(1) brightness(70%); }

For dark red, we turn down the brightness of the original red:

dark-red { filter: brightness(50%); }

And for yellow, we rotate the hue of original red and ramp up the brightness:

yellow { filter: hue-rotate(60deg) brightness(5); }

None of these transformations have any impact on the alpha channel, so the glyph shape is always unmodified.