The first assignment of Rutgers University’s Introduction to Computer Science course (01:198:111) this fall included a barcode checksumming problem whose constraints made it a little confusing even for experienced programmers. The problem is referenced in the third weekly homework assignment, and some of us are still struggling to understand how to approach it. I’m going to go over a few of the techniques we can employ to solve the problem in a clean and efficient way without exposing a full-code solution, as this would be against the collaboration policy.

Problem Assessment

Let’s review the problem itself, then split it into as few approachable sub-tasks as possible.

Reviewing the Problem

Given a 12 or 13 digit barcode, your program should …

  1. Sum every “odd” digit of the barcode, starting from the right
  • Discard the ten’s digit and keep the one’s digit
  1. Sum every “even” digit of the barcode
  • Discard the ten’s digit and keep the one’s digit
  • Multiply the resulting digit by 3
  • Discard the ten’s digit of the resulting product
  1. Add the resulting digits from steps 1 and 2
  • Discard the ten’s digit and keep the one’s digit
  1. Display “ACCEPT” if the resultant digit is 0 or display “REJECT” otherwise

What does it mean to “discard the ten’s digit and keep the one’s digit”?

For example, we might have a number such as 32 of which we want to “get rid of” the 3 and hold onto the 2. The assignment hints at how to do this:

Hint 1: to extract the rightmost digit of a number use: COMPUTE digit AS number MODULUS 10

In Java, that looks something like this.

…
int number = 32;
int digit = 32 % 10;
…

Splitting Up the Problem

Deceivingly, the assignment suggests that steps 1 and 2 should be handled separately. First sum the odd digits and process the sum, then sum the even digits and process that sum. Handling the problem this way introduces lots of unnecessary inefficiency to your solution, though, and there’s a much cleaner way to go about it if we rearrange the entire approach like so:

  1. Collect the two sums, both odd and even, starting from the right
  2. Process the odd sum
  3. Process the even sum
  4. Compute the final digit
  5. Display whether or not the final digit is accepted or rejected

The most confusing step is number 1, which we’ll get into now.

Collecting Sums

As previously mentioned, splitting up the summing process, especially into two separate loops, introduces unnecessary complexity and inefficiency into your code, and we can come up with a really clean solution that instead combines the process of collecting both sums into one loop. The hints at the end of the assignment are crucial to understanding how to do this:

Hint 1: to extract the rightmost digit of a number use: COMPUTE digit AS number MODULUS 10 Hint 2: to remove the rightmost digit of a number use: COMPUTE number AS number / 10

In examples …

…
int number = 302130123;
// Extract the rightmost digit, i.e. take the number above and get out 3 alone
int digit = number % 10;
// Reduce the number by removing the rightmost digit via integer division by 10
int number = number / 10;
// or
int number /= 10;
…

This is so essential because the most efficient way to create the two sums is by …

  1. Extracting the rightmost digit and adding it to an oddSum
  2. Removing the rightmost digit, such that the new rightmost digit is the first digit to be added to the evenSum
  3. Extracting the new rightmost digit and adding it to the evenSum
  4. Removing the rightmost digit once again, such that we are ready to repeat this process from step 1

Obviously we’re going to try and loop these 4 steps, but let’s step through them with an example barcode to see how it works.

Beginning with the 13-digit barcode 9780470458310:

  1. Initialise two variables, oddSum and evenSum to 0
  2. Extracting the rightmost digit and adding it to oddSum:
  • 9780470458310 % 10 = 0, so oddSum has 0 added to it
  1. Removing the rightmost digit:
  • 9780470458310 /= 10 -> 978047045831
  1. Extracting the new rightmost digit and adding it to evenSum:
  • 978047045831 % 10 = 1, so evenSum has 1 added to it
  1. Removing the rightmost digit again
  • 978047045831 /= 10 -> 97804704583

Now we can loop this process with the newly modified barcode, since the current rightmost digit is an “odd” digit, and therefore should be added to the oddSum.

But when should our loop stop? Every time we run the 4 steps mentioned above, the barcode is modified, and is reduced by two digits. Our loop should stop when we run out of numbers to add to either sum. Let’s see what happens as we come closer to the end of the barcode.

Say we have cut our barcode down to 97:

  1. Extract the rightmost digit, 7, and add it to the oddSum
  2. Remove the rightmost digit, leaving our barcode equal to 9
  3. Extract the rightmost digit again, 9, and add it to the evenSum
  4. Remove the rightmost digit one last time, leaving our barcode equal to 0

What we find is that once we’ve processed every number in the barcode, the barcode will be left equal to 0. This means we can effectively loop the 4 instructions described above while the barcode does not equal 0. Thus, we have created the two sums we need to proceed with the problem.

Sum Processing

Processing the sums is comparatively easier than collecting them. We’re given two sets of instructions for processing each sum.

For the odd sum …

  1. Simply discard the ten’s digit and keep the one’s digit, i.e. % 10 the oddSum

For the even sum …

  1. Discard the ten’s digit and keep the one’s digit
  2. Multiply the one’s digit by 3
  3. Discard the ten’s digit of the resulting product and keep the one’s digit

And, finally, to compute the digit we actually need:

  1. Sum the two digits we got from the steps listed above
  2. Discard the ten’s digit and keep the one’s digit

Output

Output comes down to a single conditional and shouldn’t be too difficult to handle: if the “final” digit that we computed in the previous step is equal to 0, we should print out “ACCEPT”, and in any other case we should print out “REJECT”.

Conclusion

The solution we’ve devised is simple in retrospect, but the problem gives us lots of opportunities to overthink. Hopefully this inspection and explanation of the problem from week 1 enables you to quickly design a solution to the corresponding problem in week 3’s assignment.