Lab 01

CSCI 1913 – Introduction to Algorithms, Data Structures, and Program Development

ISBN-13

ISBN-13 is a code (number) used to identify books. Each book has its own unique ISBN-13

It has a specific format, with the 13th digit (rightmost digit) being a validation digit

ISBN-13 – code algorithm

Here’s the algorithm for validating an ISBN:

  1. sum up all odd digits of the ISBN as sumodd (the leftmost digit is digit 1, odd)
  2. sum up the even digits of the ISBN as sumeven (the second leftmost digit is digit 2, even)
  3. compute \(total = sumodd + 3 ∗ sumeven\)
  4. if total is divisible by 10, then the ISBN is valid.

ISBN-13 – code algorithm

The number \(9780306406157\) would be processed as follows:

  • \(sumodd = 9 + 8 + 3 + 6 + 0 + 1 + 7 = 34\) (odd positions)
  • \(sumeven = 7 + 0 + 0 + 4 + 6 + 5 = 22\) (even positions)
  • \(total = 34 + 22 ∗ 3 = 34 + 66 = 100\)

Since 100 is divisible by 10, we know that this is a valid book number.

Functions to write

  • check_isbn13(isbn) – takes an integer (book number) as argument, and returns True if the isbn integer is a valid ISBN13
  • make_isbn13(book_number) – takes an integer (book number) as argument, and returns an equivalent valid ISBN 13 (returning the new book number as an integer)

You should probably write a helper function that given a book number it returns its total (\(total = sumodd + 3 ∗ sumeven\))

Iterating over an integer

There are many ways to interate over each single digit in an integer, here’s one option:

  • You can cast the integer into a string using the str() function and then write a for i in range(len(string)): loop to get the index for each digit
  • You need the index/position of each digit to determine if the digit is odd or even, remember that index 0 is a string is digit 1 (odd position)
  • You can also use the digits function and write a for digit in digits(isbn): loop

Examples for make_isbn13(integer)

make_isbn13(4) should return 42 because:

  • sumodd = 4 (first digit), sumeven = 2 (second digit), \(total = 4 + 3 ∗ 2 = 4 + 6 = 10\)

make_isbn13(7) should return should return 71 because:

  • sumodd = 7 (first digit), sumeven = 1 (second digit), \(total = 7 + 3 ∗ 1 = 4 + 6 = 10\)

Simple Approach

  • There could only be 10 possible options for the last digit
  • You must either add 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9 to the number
  • One of them must be valid – you can simply try them all until you find the valid one

Incorrect Mathematical Approach

You might be considering doing this:

(10 - total % 10) // 3

To make the number 12345 into a valid number, you need to add 1 to the end because:

  • sumodd = 1 + 3 + 5 = 9
  • sumeven = 2 + 4 = 6
  • total = 9 + 3 ∗ 6 = 9 + 18 = 27

The remainder of 27 divided by 10 is 7 and (10 - 7) // 3 = 1

But wait, this approach does NOT work for all cases

Incorrect Mathematical Approach

(10 - total % 10) // 3

To make the number 3 into a valid number, you need to add 9 because:

  • total = 3
  • total = 3 + 3 ∗ 9 = 3 + 27 = 30 (which is visible by 10)

The remainder of 3 (total) divided by 10 is 3 and (10 - 3) // 3 = 2

But the last digit should be 9 instead.