I didn’t plan on doing this, but, as a result of wanting to make some improvements to my Heads-I-lose application, I ended up spending a couple of months (on and off) writing a polyline decoder. I originally planned to port one of the many existing implementations, but I struggled to marry up those bits of code with the algorithm so in the end I just stuck with the specification and worked step-by-step back through it. As a result I have something I understand, but, I suspect, much less concise than it could be.

It works (as far as I can tell), but some parts of it could certainly do with tidying up.

I may at some point break this out into its own repository if I figure out the whole rebar thing.

A few points of interest:

Step 11 - Converting ASCII values to their numeric value

Erlang handles this automagically in a couple of ways:

34> hd("a").
97
35> hd("b").
98
36> hd("c").
99
37> $a.
97
38> $b.
98
39> $c.
99
40> $a-63.
34

Step 9 - Converting to binary and padding to six figures

In Erlang you have to use io:format to “print” the number in a different format. I couldn’t figure out adding leading zeroes, so instead had to use a pad_to function. Things like this add to the verbosity of my solution:

pad_to(Length, Binary_string) when length(Binary_string) < Length ->
	Padded_binary_string = "0"++Binary_string,
	pad_to(Length, Padded_binary_string);
pad_to(Length, Binary_string) when length(Binary_string) == Length ->
	Binary_string.

Steps 5 and 3 - Inverting binary encodings

Seems a doddle in most languages. I.e. you take a binary number such as 10101 and invert it to 01010 by using a binary/bitwise not function. But in Erlang this doesn’t seem to work.

For example, in Ruby:

irb(main):009:0> "%b" % 50
=> "110010"
irb(main):010:0> ~50
=> -51
irb(main):011:0> "%b" % -51
=> "..1001101"

Not perfect (for what I want), but I can see how I could easily use that result get what I want as it has flipped the bits as you can see if you line the numbers up:

   110010
..1001101

But in Erlang:

25> bnot 50.
-51
26> hd(io_lib:format("~.2B", [-51])).
"-110011"
27> hd(io_lib:format("~.2B", [50])).
"110010"

Which just don’t tie up:

 110010
-110011

Although Erlang’s behaviour does match that of calc:

; base(2)
0b1010
; ~50
-0b110011
; 50
0b110010

Colour me terribly confused. So I had to come up with my own bin_flip function (which, with hind-sight, I should have called bit_flip) that takes a binary number and converts it to a string so that string can then be processed as a list and each bit flipped through simple inspection (if Head_bit =:= "0" -> ..., etc):

bin_flip(Binary_number) ->
	Binary_string = hd(io_lib:format("~.2B", [Binary_number])),
	bin_flip_(Binary_string, []).
bin_flip_([Head | Rest], Flipped_string) ->
	Head_bit = hd(io_lib:format("~c",[Head])),
	Flipped_bit = if Head_bit =:= "0" ->
		"1";
	true ->
		"0"
	end,
	bin_flip_(Rest, Flipped_bit++Flipped_string);
bin_flip_([], Flipped_string) ->
	lists:reverse(Flipped_string).

All Steps - Recursion

I found this very interesting implementation in Ruby that steps through the algorithm in quite a linear way (these are the actual decoding methods called) which makes for very clean, easy to read and follow code. Whereas in my implementation things are a bit harder to follow. For example, steps 11 back to 8 are wrapped in one function, six_bit_chunks, which itself is a recursive wrapper that calls six_bit_chunk which does the actual decoding of step 11, 10 and 9. And five_bit_chunks has nested recursion which means step 8 is called within step 7, which makes sense when stated like that because we are working backwards through the steps, but is perhaps harder to read on the screen as the first thing you see is “decoding step 7” yet you think “hang on, we haven’t done step 8 yet”.

I’m too tired as of late to judge whether that is because of Erlang and recursion or whether I’ve not implemented the algorithm as efficiently as can be done or whether I’m just talking nonsense.