Final month an instance of binary code was cleverly displayed on the door of 10 Downing Road, to advertise London Tech Week.
A binary code is a approach of encoding info (on this case, letters) within the binary digits 0 and 1, known as “bits”. In the usual encoding used on the PM’s door, each letter is represented by eight bits. The primary line spells L, the second T and the third W.
In the present day’s puzzle is a couple of completely different sort of binary code: one that’s used to compress knowledge in probably the most environment friendly approach potential.
1. ABACAB
Here’s a code for the letters A, B and C, during which every letter is represented by two bits.
A: 00
B: 01
C: 10
This code would translate the six-letter message ABACAB into 12-bits: 000100100001
Devise a binary code that interprets ABACAB right into a string consisting of solely 9 bits.
That’s it. I’m asking you design a binary code for A, B and C that encodes, or compresses, ABACAB into simply 9 bits, which is the fewest potential variety of bits.
To make clear: on this code, A, B and C every have their very own distinctive illustration in binary.
Additionally, the code should not be ambiguous. A code is ambiguous if the encoding of two completely different messages produce the identical bit string. For instance, a code during which A is 0, B is 1, and C is 01, just isn’t permitted as a result of this might imply that the encodings of each AB and C are “01” . Given any bit string, it have to be unambiguously decodable right into a message of As, Bs and Cs.
[UPDATE: combinations of letters, such as AB, BC, or AC, are not allowed their own codes. The only codes are for A, B and C.]
2. ABACADABA
Here’s a code for the letters A, B, C and D, during which every letter is represented by two bits.
A: 00
B: 01
C: 10
D: 11
This code would translate the message ABACADABA, which has 9 letters, right into a string consisting of 18 bits: 000100100011000100.
Devise a binary code that interprets ABACADABA right into a string consisting of solely 15 bits.
Similar guidelines as above. Each letter has its personal distinctive code, and these are the one codes. The code just isn’t ambiguous.
In the present day’s questions have been easy to state – and now have a well-known pedigree. In 1951, MIT professor Robert Fano, who together with Claude Shannon was one of many fathers of knowledge principle, gave the overall model of those inquiries to graduate pupil David Huffman:
Given a set of letters, numbers, or symbols, discover probably the most environment friendly technique to symbolize them utilizing a binary code.
Shannon and Fano had failed to search out a solution – however Huffman discovered it. Such a coding is now known as Huffman coding, and is broadly used to compress all kinds of information recordsdata.
The reply to each of right now’s puzzles is a Huffman coding. For those who remedy them, congratulations – you’re formally smarter than Robert Fano and Claude Shannon. You should have replicated the outcomes of one of many basic algorithms in info principle and laptop science. (And for those who don’t, you should have the pleasure of discovering the elegant answer to the issue.)
Normally, I reveal the solutions to my puzzles at 5pm UK, which is ten hours after I set the questions.
In the present day, nevertheless, I’m trialling a brand new format, during which the answer is posted AT THE SAME TIME. If you wish to learn the answer now, please click on the hyperlink right here.
NO SPOILERS PLEASE
As an alternative speak about binary coding, Genesis, the Steve Miller Band, phrases utilizing solely A, B, C and D, and possibly some suggestions about whether or not or not you like having the solutions right away.
Due to Pierre Chardaire, a retired laptop scientist, for assist with this puzzle.
I set a puzzle right here each two weeks on a Monday. I’m all the time on the look-out for nice puzzles. If you want to recommend one, e mail me.
I give college talks about maths and puzzles (on-line and in particular person). In case your college is please get in contact.
