The UPC-A bar code encodes 12 decimal digits in alternating “dark”and “light” bars as 15 patterns SLLLLLLMRRRRRRE where S is the start pattern 101 (1 indicates “dark” and 0 indicates “light”), M is the middle pattern 01010 and E is the end pattern 101. Each L is a left pattern corresponding to one of the first 6 digits and each R is a right pattern corresponding to one of the last 6 digits. The width of each bar is a multiple of a fixed value (the X dimension). Again a 1 indicates a “dark” band and 0 indicates a “light” band. The tick marks above the bar code illustration indicate the start of each code. There are 3 + 5 + 3 + 12*7 = 95 bands total. In addition there must be at least 9 “light”bands at either end of the bar code.
The last decimal digit in the code is a check sum digit which is computed as follows:
CheckSum = 3*(digit1 + digit3 + digit5 + digit7 +
digit9 + digit11) + digit2 + digit4 +
digit6 + digit8 + digit10.
Code = CheckSum Mod(10);
If Code = 0, check digit = 0. Other wise, check digit = (10 – Code).
A bar code scanner could use a camera to take a narrow image across the bar code and deduce the on/off pattern of bands as below:
if the code was scanned right side up or the following if it was scanned upside down:
Again, the tick marks above each image indicate the start of each code.
Unfortunately, the images are not always this clear due to lack of contrast or reflections off shiny material, as shown here:
When scanning the image, it is not always clear whether a particular band is dark or light. It is often still possible to determine the bar code even if we do not know exactly whether a particular band is “dark” or “light”. First, only 20 of 128 possible 7-bit digit codes are used. Second, only codes with a correct check digit are valid. Finally, even if several codes match, it is unlikely that more than one will be in the database for a particular application. For this problem we will use a ‘?’ to indicate uncertainty in the value of a particular band. The start (S), middle (M) and end (E) codes must match in order for a match to be considered valid.
Write a program which takes as input a string of 95 characters, ‘0’, ‘1’, or ‘?’ and outputs all valid UPC-A digit strings which could scan to that sequence of band values in either direction.