Penguencoding 4 Mystery Cache

The cache is not at the posted coordinates. Solve the puzzle below to find the final location.

Penguin Professor Patricia stumbled upon her friends Paul and Peter, exhausted on the floor, arguing over the benefits of their various encodings back when they were in the game. It was a sad discussion of simple tired minds, she thought. She attempted to interrupt them with her perspective, but they hardly noticed she was there. She thought Peter's last attempt was clever, but challenging and a bit ad hoc. So she set about explaining some more elegant methods of encoding coordinates. Perhaps some day they would stop arguing and see the brilliance of her ideas she thought. It is all about efficiency.

The first attempt she made was using a friend of hers' advice, one Professor Huffman. It was straightforward, but unfortunately took a lot of paper to explain. In this encoding, she explained to no one listening, one simply takes all of the possible characters that are needed to describe a string, and give them an encoding that is shortest for the most common characters, and longest for the least. According to this algorithm, you do the following steps to create a binary encoding for each symbol. Taking an example distribution of five characters A-E plus the space ('_'), with probability:

To determine symbol encodings, execute the following steps:

1. choose the two lowest probability symbols, or symbol nodes (described below); if there is a tie, choose the node first in alphanumeric sort
2. gather them together into a symbol node, with new node probability equal to the sum of the two gathered
3. repeat until a single node represents all symbols (with 100% probability)
4. for each node, assign binary representation (see below)
5. for the message, assign binary bits for each symbol in the string
6. for common representation, the result is often converted into a hexadecimal fraction

For this example, the node creation steps would be:

step 1 (combine, then re-sort)

step 2 (combine, then re-sort)

step 3 (combine, then re-sort)

step 4 (combine, then re-sort)

step 5 (final combine)

 
Updated: If there is a "tie" between two nodes, or a node and a symbol, use alphabetic sorting on the first symbol of the node, so (A:C) would sort before B, (D:E) would sort before (F:A), for instance.

The binary representation step reverses the node creation and assigns codes, post-pending (0:1) for the pairs that are unwound.

step 1, unwind final node

step 2, unwind any remaining nodes

step 3, unwind remaining nodes

step 4, unwind remaining nodes

step 5, print leaf nodes only

Now, if the message is ACE BAD DAD, the binary encoding would be

    011.0101.10.11.0100.011.00.11.00.011.00 or
    01101011011010001100110001100 or
    .01101011011010001100110001100 (2) or
    .6b68cc60 (16)

Now, Professor Patricia dealt with representing the coordinates. Given the possible characters that make up a coordinate string (she preferred to use the 22-character string of the form N00 00.000 W000 00.000), she calculated the statistical likelihood of each of the possible 16 symbols for any 22-character coordinate string as approximately the following:

 
After talking, calculating, and scribbling for a while, she looked on the ground and saw Paul and Peter still on the ground, now sleeping. She took her final scrap of paper and dropped it on the floor, discouraged.

You can validate your puzzle solution with certitude.

 
Congratulations to Team Ottlet for FTF, and pfalstad for FTS!