UPC

From Rosetta Code
UPC is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task: Convert upc barcodes to decimal.

Specifically:

The UPC standard is actually a collection of standards -- physical standards, data format standards, product reference standards... Here, we focus on some of the data format standards, with an imaginary physical+electrical implementation which converts physical UPC barcodes to ascii, with spaces and # characters representing the presence or absence of ink.

Here, we have a representation of 10 different UPC-A bar codes read by our imaginary bar code reader:

         # #   # ##  #  ## #   ## ### ## ### ## #### # # # ## ##  #   #  ##  ## ###  # ##  ## ### #  # #       
        # # #   ##   ## # #### #   # ## #   ## #   ## # # # ###  # ###  ##  ## ###  # #  ### ###  # # #         
         # #    # # #  ###  #   #    # #  #   #    # # # # ## #   ## #   ## #   ##   # # #### ### ## # #         
       # # ##  ## ##  ##   #  #   #  # ###  # ##  ## # # #   ## ##  #  ### ## ## #   # #### ## #   # #        
         # # ### ## #   ## ## ###  ##  # ##   #   # ## # # ### #  ## ##  #    # ### #  ## ##  #      # #          
          # #  #   # ##  ##  #   #   #  # ##  ##  #   # # # # #### #  ##  # #### #### # #  ##  # #### # #         
         # #  #  ##  ##  # #   ## ##   # ### ## ##   # # # #  #   #   #  #  ### # #    ###  # #  #   # #        
        # # #    # ##  ##   #  # ##  ##  ### #   #  # # # ### ## ## ### ## ### ### ## #  ##  ### ## # #         
         # # ### ##   ## # # #### #   ## # #### # #### # # #   #  # ###  #    # ###  # #    # ###  # # #       
        # # # #### ##   # #### # #   ## ## ### #### # # # #  ### # ###  ###  # # ###  #    # #  ### # #         

Some of these were input upside down, and one has a timing error.

The task is to implement code to find the corresponding decimal representation of each, rejecting the error. Extra credit for handling the rows entered upside down (the other option is to reject them).

Notes:

Each digit is represented by 7 bits:

  0: 0 0 0 1 1 0 1
  1: 0 0 1 1 0 0 1
  2: 0 0 1 0 0 1 1
  3: 0 1 1 1 1 0 1
  4: 0 1 0 0 0 1 1
  5: 0 1 1 0 0 0 1
  6: 0 1 0 1 1 1 1
  7: 0 1 1 1 0 1 1
  8: 0 1 1 0 1 1 1
  9: 0 0 0 1 0 1 1

On the left hand side of the bar code a space represents a 0 and a # represents a 1. On the right hand side of the bar code, a # represents a 0 and a space represents a 1 (alternatively: spaces always represent zeros and # characters always represent ones, but the representation is logically negated -- 1s and 0s are flipped -- on the right hand side of the bar code).

The UPC-A barcode structure begins with at least 9 spaces (which our imaginary bar code reader unfortunately doesn't always reproduce properly), then has a '# #' sequence marking the start of the sequence, then has the six "left hand" digits, then has a ' # # ' sequence in the middle, then has the six "right hand digits" and finally ends with another '# #' end sequence and nine trailing spaces (which might be eaten by wiki edits and in any event were not quite captured correctly by our imaginary bar code reader).

Finally, the last digit is a checksum digit which may be used to help detect errors. Multiply each digit in the represented 12 digit sequence by the corresponding number in (3,1,3,1,3,1,3,1,3,1,3,1) and add products, and the sum (mod 10) must be 0 (must have a zero as its last digit) if the number has been read correctly.

Go[edit]

package main
 
import (
"fmt"
"regexp"
)
 
var bits = []string{
"0 0 0 1 1 0 1 ",
"0 0 1 1 0 0 1 ",
"0 0 1 0 0 1 1 ",
"0 1 1 1 1 0 1 ",
"0 1 0 0 0 1 1 ",
"0 1 1 0 0 0 1 ",
"0 1 0 1 1 1 1 ",
"0 1 1 1 0 1 1 ",
"0 1 1 0 1 1 1 ",
"0 0 0 1 0 1 1 ",
}
 
var (
lhs = make(map[string]int)
rhs = make(map[string]int)
)
 
var weights = []int{3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1}
 
const (
s = "# #"
m = " # # "
e = "# #"
d = "(?:#| ){7}"
)
 
func init() {
for i := 0; i <= 9; i++ {
lt := make([]byte, 7)
rt := make([]byte, 7)
for j := 0; j < 14; j += 2 {
if bits[i][j] == '1' {
lt[j/2] = '#'
rt[j/2] = ' '
} else {
lt[j/2] = ' '
rt[j/2] = '#'
}
}
lhs[string(lt)] = i
rhs[string(rt)] = i
}
}
 
func reverse(s string) string {
b := []byte(s)
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
return string(b)
}
 
func main() {
barcodes := []string{
" # # # ## # ## # ## ### ## ### ## #### # # # ## ## # # ## ## ### # ## ## ### # # # ",
" # # # ## ## # #### # # ## # ## # ## # # # ### # ### ## ## ### # # ### ### # # # ",
" # # # # # ### # # # # # # # # # # ## # ## # ## # ## # # #### ### ## # # ",
" # # ## ## ## ## # # # # ### # ## ## # # # ## ## # ### ## ## # # #### ## # # # ",
" # # ### ## # ## ## ### ## # ## # # ## # # ### # ## ## # # ### # ## ## # # # ",
" # # # # ## ## # # # # ## ## # # # # # #### # ## # #### #### # # ## # #### # # ",
" # # # ## ## # # ## ## # ### ## ## # # # # # # # # ### # # ### # # # # # ",
" # # # # ## ## # # ## ## ### # # # # # ### ## ## ### ## ### ### ## # ## ### ## # # ",
" # # ### ## ## # # #### # ## # #### # #### # # # # # ### # # ### # # # ### # # # ",
" # # # #### ## # #### # # ## ## ### #### # # # # ### # ### ### # # ### # # # ### # # ",
}
 
// Regular expression to check validity of a barcode and extract digits. However we accept any number
// of spaces at the beginning or end i.e. we don't enforce a minimum of 9.
expr := fmt.Sprintf(`^\s*%s(%s)(%s)(%s)(%s)(%s)(%s)%s(%s)(%s)(%s)(%s)(%s)(%s)%s\s*$`,
s, d, d, d, d, d, d, m, d, d, d, d, d, d, e)
rx := regexp.MustCompile(expr)
fmt.Println("UPC-A barcodes:")
for i, bc := range barcodes {
for j := 0; j <= 1; j++ {
if !rx.MatchString(bc) {
fmt.Printf("%2d: Invalid format\n", i+1)
break
}
codes := rx.FindStringSubmatch(bc)
digits := make([]int, 12)
var invalid, ok bool // False by default.
for i := 1; i <= 6; i++ {
digits[i-1], ok = lhs[codes[i]]
if !ok {
invalid = true
}
digits[i+5], ok = rhs[codes[i+6]]
if !ok {
invalid = true
}
}
if invalid { // Contains at least one invalid digit.
if j == 0 { // Try reversing.
bc = reverse(bc)
continue
} else {
fmt.Printf("%2d: Invalid digit(s)\n", i+1)
break
}
}
sum := 0
for i, d := range digits {
sum += weights[i] * d
}
if sum%10 != 0 {
fmt.Printf("%2d: Checksum error\n", i+1)
break
} else {
ud := ""
if j == 1 {
ud = "(upside down)"
}
fmt.Printf("%2d: %v %s\n", i+1, digits, ud)
break
}
}
}
}
Output:
UPC-A barcodes:
 1: [9 2 4 7 7 3 2 7 1 0 1 9] 
 2: [4 0 3 9 4 4 4 4 1 0 5 0] 
 3: [8 3 4 9 9 9 6 7 6 7 0 6] (upside down)
 4: [9 3 9 8 2 5 1 5 8 8 1 1] (upside down)
 5: Invalid digit(s)
 6: [3 1 6 3 1 3 7 1 8 7 1 7] (upside down)
 7: [2 1 4 5 7 5 8 7 5 6 0 8] 
 8: [8 1 8 7 7 8 8 4 1 8 1 3] (upside down)
 9: [7 0 6 4 6 6 7 4 3 0 3 0] 
10: [6 5 3 4 8 3 5 4 0 4 3 5] 

J[edit]

Implementation:

upcdigit=:".;._2]0 :0
0 0 0 1 1 0 1 NB. 0
0 0 1 1 0 0 1 NB. 1
0 0 1 0 0 1 1 NB. 2
0 1 1 1 1 0 1 NB. 3
0 1 0 0 0 1 1 NB. 4
0 1 1 0 0 0 1 NB. 5
0 1 0 1 1 1 1 NB. 6
0 1 1 1 0 1 1 NB. 7
0 1 1 0 1 1 1 NB. 8
0 0 0 1 0 1 1 NB. 9
)
 
upc2dec=:3 :0
if. 95~: #code=. '#'=dtb dlb y do._ return.end.
if. (11$1 0) ~: 0 1 2 45 46 47 48 49 92 93 94{ code do._ return. end.
digits=. <./([:,upcdigit i.0 1~:(3 50+/i.6 7) { ])"1 code,:|.code
if. 10 e.digits do._ return.end.
if.0 ~:10|digits+/ .* 12$3 1 do._ return.end.
)

Here, we perform some basic integrity checks and use a table lookup to identify the decimal digits.

Task example:

barcodes=:0 :0
# # # ## # ## # ## ### ## ### ## #### # # # ## ## # # ## ## ### # ## ## ### # # #
# # # ## ## # #### # # ## # ## # ## # # # ### # ### ## ## ### # # ### ### # # #
# # # # # ### # # # # # # # # # # ## # ## # ## # ## # # #### ### ## # #
# # ## ## ## ## # # # # ### # ## ## # # # ## ## # ### ## ## # # #### ## # # #
# # ### ## # ## ## ### ## # ## # # ## # # ### # ## ## # # ### # ## ## # # #
# # # # ## ## # # # # ## ## # # # # # #### # ## # #### #### # # ## # #### # #
# # # ## ## # # ## ## # ### ## ## # # # # # # # # ### # # ### # # # # #
# # # # ## ## # # ## ## ### # # # # # ### ## ## ### ## ### ### ## # ## ### ## # #
# # ### ## ## # # #### # ## # #### # #### # # # # # ### # # ### # # # ### # # #
# # # #### ## # #### # # ## ## ### #### # # # # ### # ### ### # # ### # # # ### # #
)
 
upc2dec;._2 barcodes
9 2 4 7 7 3 2 7 1 0 1 9
4 0 3 9 4 4 4 4 1 0 5 0
8 3 4 9 9 9 6 7 6 7 0 6
9 3 9 8 2 5 1 5 8 8 1 1
_ 0 0 0 0 0 0 0 0 0 0 0
3 1 6 3 1 3 7 1 8 7 1 7
2 1 4 5 7 5 8 7 5 6 0 8
8 1 8 7 7 8 8 4 1 8 1 3
7 0 6 4 6 6 7 4 3 0 3 0
6 5 3 4 8 3 5 4 0 4 3 5
 

The row which begins with _ is the damaged row. (If rescanning did not fix that problem, the operator would have to enter the code manually.)

It may be desirable to format the result differently, but that's currently not a part of the task definition.

Perl 6[edit]

sub decode_UPC ( Str $line ) {
constant @patterns1 = ' ## #', ' ## #', ' # ##', ' #### #', ' # ##',
' ## #', ' # ####', ' ### ##', ' ## ###', ' # ##';
constant @patterns2 = @patterns1».trans( '#' => ' ', ' ' => '#' );
 
constant %pattern_to_digit_1 = @patterns1.antipairs;
constant %pattern_to_digit_2 = @patterns2.antipairs;
 
constant $re = / ^ '# #' (@patterns1) ** 6
' # # ' (@patterns2) ** 6
'# #' $ /;
 
$line.trim ~~ $re
orelse return;
 
my @digits = flat %pattern_to_digit_1{ $0».Str },
%pattern_to_digit_2{ $1».Str };
 
return unless ( @digits Z* ( |(3,1) xx * ) ).sum %% 10;
 
return @digits.join;
}
 
my @lines =
' # # # ## # ## # ## ### ## ### ## #### # # # ## ## # # ## ## ### # ## ## ### # # # ',
' # # # ## ## # #### # # ## # ## # ## # # # ### # ### ## ## ### # # ### ### # # # ',
' # # # # # ### # # # # # # # # # # ## # ## # ## # ## # # #### ### ## # # ',
' # # ## ## ## ## # # # # ### # ## ## # # # ## ## # ### ## ## # # #### ## # # # ',
' # # ### ## # ## ## ### ## # ## # # ## # # ### # ## ## # # ### # ## ## # # # ',
' # # # # ## ## # # # # ## ## # # # # # #### # ## # #### #### # # ## # #### # # ',
' # # # ## ## # # ## ## # ### ## ## # # # # # # # # ### # # ### # # # # # ',
' # # # # ## ## # # ## ## ### # # # # # ### ## ## ### ## ### ### ## # ## ### ## # # ',
' # # ### ## ## # # #### # ## # #### # #### # # # # # ### # # ### # # # ### # # # ',
' # # # #### ## # #### # # ## ## ### #### # # # # ### # ### ### # # ### # # # ### # # ',
;
for @lines -> $line {
say decode_UPC($line)
// decode_UPC($line.flip)
// 'Invalid';
}
Output:
924773271019
403944441050
834999676706
939825158811
Invalid
316313718717
214575875608
818778841813
706466743030
653483540435

Phix[edit]

constant numbers = {"   ## #", -- 0
" ## #", -- 1
" # ##", -- 2
" #### #", -- 3
" # ##", -- 4
" ## #", -- 5
" # ####", -- 6
" ### ##", -- 7
" ## ###", -- 8
" # ##"} -- 9
 
procedure decode(string bar_code)
bar_code = trim(bar_code)
if length(bar_code)=95
and bar_code[1..3]="# #"
and bar_code[46..50]=" # # "
and bar_code[93..95]="# #" then
for reversed=false to true do
sequence r = {}
for i=1 to 12 do
integer st = iff(i<=6?i*7-3:i*7+2)
string number = bar_code[st..st+6]
if i>6 then number = substitute_all(number," #X","X #") end if
r &= find(number,numbers)-1
end for
if not find(-1,r) then
if remainder(sum(sq_mul(r,{3,1,3,1,3,1,3,1,3,1,3,1})),10) then
printf(1,"invalid checksum\n")
else
printf(1,"%v%s\n",{r,iff(reversed?" (upside down)","")})
end if
return
end if
bar_code = reverse(bar_code)
end for
end if
printf(1,"invalid\n")
end procedure
 
constant bar_codes = split("""
# # # ## # ## # ## ### ## ### ## #### # # # ## ## # # ## ## ### # ## ## ### # # #
# # # ## ## # #### # # ## # ## # ## # # # ### # ### ## ## ### # # ### ### # # #
# # # # # ### # # # # # # # # # # ## # ## # ## # ## # # #### ### ## # #
# # ## ## ## ## # # # # ### # ## ## # # # ## ## # ### ## ## # # #### ## # # #
# # ### ## # ## ## ### ## # ## # # ## # # ### # ## ## # # ### # ## ## # # #
# # # # ## ## # # # # ## ## # # # # # #### # ## # #### #### # # ## # #### # #
# # # ## ## # # ## ## # ### ## ## # # # # # # # # ### # # ### # # # # #
# # # # ## ## # # ## ## ### # # # # # ### ## ## ### ## ### ### ## # ## ### ## # #
# # ### ## ## # # #### # ## # #### # #### # # # # # ### # # ### # # # ### # # #
# # # #### ## # #### # # ## ## ### #### # # # # ### # ### ### # # ### # # # ### # #
""","\n",true)
for i=1 to length(bar_codes) do
decode(bar_codes[i])
end for
Output:
{9,2,4,7,7,3,2,7,1,0,1,9}
{4,0,3,9,4,4,4,4,1,0,5,0}
{8,3,4,9,9,9,6,7,6,7,0,6} (upside down)
{9,3,9,8,2,5,1,5,8,8,1,1} (upside down)
invalid
{3,1,6,3,1,3,7,1,8,7,1,7} (upside down)
{2,1,4,5,7,5,8,7,5,6,0,8}
{8,1,8,7,7,8,8,4,1,8,1,3} (upside down)
{7,0,6,4,6,6,7,4,3,0,3,0}
{6,5,3,4,8,3,5,4,0,4,3,5}

zkl[edit]

var lhd=Dictionary(), rhd=Dictionary();
[0..].zip(List(
"0 0 0 1 1 0 1", //--> "___##_#":0 "###__#_":0
"0 0 1 1 0 0 1",
"0 0 1 0 0 1 1",
"0 1 1 1 1 0 1",
"0 1 0 0 0 1 1",
"0 1 1 0 0 0 1",
"0 1 0 1 1 1 1",
"0 1 1 1 0 1 1",
"0 1 1 0 1 1 1",
"0 0 0 1 0 1 1") //--> "___#_##":9 "###_#__":9
).pump(Void,fcn([(n,bs)]){
bs-=" ";
lhd[bs.translate("01","_#")]=n;
rhd[bs.translate("10","_#")]=n;
});
 
fcn parseBarCode(barcode, one=True){ // --> 12 digits
upsideDown:='wrap{ // was I looking at this bar code upside down?
if(one and (r:=parseBarCode(barcode.reverse(),False))) return(r);
return(False);
};
 
var [const] start=RegExp(String("_"*9, "+#_#")), tail="_"*7;
if(not start.search(barcode)) return(upsideDown());
r,idx,d,mark := List(), start.matched[0][1], lhd, "_#_#_";
do(2){
do(6){
if(Void==(z:=d.find(barcode[idx,7]))) return(upsideDown());
r.append(z);
idx+=7;
}
if(barcode[idx,5] != mark) return(Void);
d,idx,mark = rhd, idx+5, "#_#__";
}
if(tail!=barcode[idx,7]) return(Void); // 9 trailing blanks? two checked above
r
}

Or, if you like way too long regular expressions:

var upcRE = RegExp(String("_"*9, "+#_#",
lhd.keys.concat("|","(",")")*6, "_#_#_",
rhd.keys.concat("|","(",")")*6, "#_#", "_"*9)),
digits=lhd.copy().extend(rhd);
 
fcn parseBarCode(barcode){ // --> 12 digits
if(not (upcRE.search(barcode) or upcRE.search(barcode.reverse()))) return(False);
upcRE.matched[1,*] // ( (a,b), "_#_####","_##___#", 10 more digit patterns )
.apply(digits.get)
}
barcodes:=
#<<<"
_________#_#___#_##__#__##_#___##_###_##_###_##_####_#_#_#_##_##__#___#__##__##_###__#_##__##_###_#__#_#_________
_________#_#_#___##___##_#_####_#___#_##_#___##_#___##_#_#_#_###__#_###__##__##_###__#_#__###_###__#_#_#_________
_________#_#____#_#_#__###__#___#____#_#__#___#____#_#_#_#_##_#___##_#___##_#___##___#_#_####_###_##_#_#_________
_________#_#_##__##_##__##___#__#___#__#_###__#_##__##_#_#_#___##_##__#__###_##_##_#___#_####_##_#___#_#_________
_________#_#_###_##_#___##_##_###__##__#_##___#___#_##_#_#_###_#__##_##__#____#_###_#__##_##__#______#_#__________
__________#_#__#___#_##__##__#___#___#__#_##__##__#___#_#_#_#_####_#__##__#_####_####_#_#__##__#_####_#_#____________
_________#_#__#__##__##__#_#___##_##___#_###_##_##___#_#_#_#__#___#___#__#__###_#_#____###__#_#__#___#_#_________
_________#_#_#____#_##__##___#__#_##__##__###_#___#__#_#_#_###_##_##_###_##_###_###_##_#__##__###_##_#_#__________
_________#_#_###_##___##_#_#_####_#___##_#_####_#_####_#_#_#___#__#_###__#____#_###__#_#____#_###__#_#_#_________
_______________#_#_#_####_##___#_####_#_#___##_##_###_####_#_#_#_#__###_#_###__###__#_#_###__#____#_#__###_#_#_________"
.split("\n");
#<<<
 
foreach n,barcode in ([1..].zip(barcodes)){
bc:=parseBarCode(barcode);
println("%2d: [%s]".fmt(n,bc and bc.concat(" ") or "Not valid"));
}
Output:
 1: [9 2 4 7 7 3 2 7 1 0 1 9]
 2: [4 0 3 9 4 4 4 4 1 0 5 0]
 3: [8 3 4 9 9 9 6 7 6 7 0 6]
 4: [9 3 9 8 2 5 1 5 8 8 1 1]
 5: [Not valid]
 6: [3 1 6 3 1 3 7 1 8 7 1 7]
 7: [2 1 4 5 7 5 8 7 5 6 0 8]
 8: [8 1 8 7 7 8 8 4 1 8 1 3]
 9: [7 0 6 4 6 6 7 4 3 0 3 0]
10: [6 5 3 4 8 3 5 4 0 4 3 5]