We help the robot sorter in the mail

Short background

I talked some time ago with a familiar robot. He settled down temporarily to the Russian Post a letter sorter. The job is not dusty, looks at the index on the letter and puts them in the right hole. But there is a problem with letters that have a typo in the index. Finding the right index takes a lot of time and the beer has time to dry out.

A splinter in the head

After that conversation, enough time had passed, but the postal code dilemma did not go out of my head.

It would seem - what else can be improved here? Let's try to transform the appearance of the index numbers in such a way that even if one error occurs, it can be automatically detected and corrected.



It turns out you can improve.

Let's try to draw a new kind of digit 0 .

If it is interesting, why and why - I ask under cat.



While still at the university, at a lecture on discrete mathematics, I noticed that the Hamming distance between some written numbers is too small, that is, they differ only in "one stick". We will not go far for an example, it is 0 and 8 . It is enough to “rearrange” one wand, and one digit turns into another.

Further research

Are there any problems with similar numbers? After all, for this case, the greater the distance between the numbers - the easier it is for the robot to correct the error. We confine ourselves to one error in the figure. For example:



It can be seen that one stick is missing, however, it can be algorithmically determined what the mistake was and how to correct it.

')

Denote each stick of the skeleton number with a number (yes, such is a pun):



Let us assign each digit its own vector:

postindex[0]=[1,1,1,1,1,1,0,0,0]; postindex[1]=[0,0,0,0,1,1,1,0,0]; postindex[2]=[1,0,0,1,0,1,0,0,1]; postindex[3]=[1,0,0,0,0,0,1,1,1]; postindex[4]=[0,1,0,0,1,1,0,1,0]; postindex[5]=[1,1,0,1,1,0,0,1,0]; postindex[6]=[0,0,1,1,1,0,1,1,0]; postindex[7]=[1,0,1,0,0,0,1,0,0]; postindex[8]=[1,1,1,1,1,1,0,1,0]; postindex[9]=[1,1,0,0,0,1,0,1,1]; 

Now we calculate the Hamming distance between the numbers:

  0 1 2 3 4 5 6 7 8 9 '0': [ 0, 5, 4, 8, 4, 3, 5, 5, 1, 5 ] '1': [ 5, 0, 5, 5, 3, 6, 4, 4, 6, 6 ] '2': [ 4, 5, 0, 4, 6, 5, 7, 5, 5, 3 ] '3': [ 8, 5, 4, 0, 6, 5, 5, 3, 7, 3 ] '4': [ 4, 3, 6, 6, 0, 3, 5, 7, 3, 3 ] '5': [ 3, 6, 5, 5, 3, 0, 4, 6, 2, 4 ] '6': [ 5, 4, 7, 5, 5, 4, 0, 4, 4, 8 ] '7': [ 5, 4, 5, 3, 7, 6, 4, 0, 6, 6 ] '8': [ 1, 6, 5, 7, 3, 2, 4, 6, 0, 4 ] '9': [ 5, 6, 3, 3, 3, 4, 8, 6, 4, 0 ] 

It can be seen that the problem between 0 and 8 is the biggest (distance is only 1 unit), there is still a problem between 5 and 8 , there is a distance of 2, which is also not very good, especially for such a typo:



This irregularly shaped nine, by changing just one stick, can turn into 8 and 5 . (The fact that the figure is similar to another 9 is not considered, because 2 errors are needed there)

What can be done?

Let's try to begin to change the number 0 .



Too much like 9 . There will be the same problem as 5 and 8 .



Another option:



Similarly with 6 .



Incline zero:



It seems to be what you need. Checking:

  0 1 2 3 4 5 6 7 8 9 '0': [ 0, 3, 4, 4, 6, 9, 5, 3, 7, 5 ] '1': [ 3, 0, 5, 5, 3, 6, 4, 4, 6, 6 ] '2': [ 4, 5, 0, 4, 6, 5, 7, 5, 5, 3 ] '3': [ 4, 5, 4, 0, 6, 5, 5, 3, 7, 3 ] '4': [ 6, 3, 6, 6, 0, 3, 5, 7, 3, 3 ] '5': [ 9, 6, 5, 5, 3, 0, 4, 6, 2, 4 ] '6': [ 5, 4, 7, 5, 5, 4, 0, 4, 4, 8 ] '7': [ 3, 4, 5, 3, 7, 6, 4, 0, 6, 6 ] '8': [ 7, 6, 5, 7, 3, 2, 4, 6, 0, 4 ] '9': [ 5, 6, 3, 3, 3, 4, 8, 6, 4, 0 ] 

Everything is very good! With one of the numbers figured out.

Fight to the end

Now you need to come up with something for 5 and 8 . Say NO to Hamming distance less than three. Draw fives of varying degrees of deformity.



For the second option, the minimum Hamming distance for all digits is greater than two, but it is hard to call this deformity a five. We are thinking about other options.

Maybe you should use a completely shaded version as an eight?



Testing:

  0 1 2 3 4 5 6 7 8 9 '0': [ 0, 3, 4, 4, 6, 9, 5, 3, 5, 5 ] '1': [ 3, 0, 5, 5, 3, 6, 4, 4, 6, 6 ] '2': [ 4, 5, 0, 4, 6, 5, 7, 5, 5, 3 ] '3': [ 4, 5, 4, 0, 6, 5, 5, 3, 5, 3 ] '4': [ 6, 3, 6, 6, 0, 3, 5, 7, 5, 3 ] '5': [ 9, 6, 5, 5, 3, 0, 4, 6, 4, 4 ] '6': [ 5, 4, 7, 5, 5, 4, 0, 4, 4, 8 ] '7': [ 3, 4, 5, 3, 7, 6, 4, 0, 6, 6 ] '8': [ 5, 6, 5, 5, 5, 4, 4, 6, 0, 4 ] '9': [ 5, 6, 3, 3, 3, 4, 8, 6, 4, 0 ] 

Hooray! There are no twos in the matrix , Neo !

Final option

In this scheme of digits, one any made mistake can be automatically corrected.

Epilogue

I satisfied the result of my fabrications of a familiar robot, but he expressed fears that everyone would not be able to get used to this option right away. But I assured him that this change is necessary for the benefit of the Russians. Letters will reach faster and errors will be less. And if, nevertheless, people do not like this variant of writing the index numbers, then we will return the old scheme. In general, we win in any case.



UPD:

Habrayuzer jaguard offered a more elegant solution to the problem.