Edit

Luhn Number

Challenge: Luhn Number

The Luhn test is used by some credit card companies to distinguish valid credit card numbers from what could be a random selection of digits.

A Luhn number is a sequence of digits that passes the following test:

  1. Reverse the order of the digits.

  2. Take the first, third, and every odd-numbered digit in the reversed digits and sum them to form s1

  3. Taking the second, fourth, and every even-numbered digit in the reversed digits:

    1. Multiply each by two. Within each doubled digit, sum those digits (if the answer is greater than nine) to form partial sums.

    2. Sum the partial sums of the even digits to form s2

  4. If s1 + s2 ends in zero then the original number is in the form of a valid credit card number as verified by the Luhn test.

For example, if the trial number is 49927398716:

Reverse the digits:
  61789372994
Sum the odd digits:
  6 + 7 + 9 + 7 + 9 + 4 = 42 = s1
The even digits:
    1,  8,  3,  2,  9
  Two times each even digit:
    2, 16,  6,  4, 18
  Sum the digits of each multiplication:
    2,  7,  6,  4,  9
  Sum the last:
    2 + 7 + 6 + 4 + 9 = 28 = s2

s1 + s2 = 70 ends in zero, which means that 49927398716 passes the Luhn test

Your task for this challenge is as follows. First you will write a library file lib/luhn-number with a core containing an arm named +validate. +validate will be a gate that takes as input a $tape which is a sequence of digits, and returns either a %.y or %.n if the number is a Luhn number or not.

Example usage:

Next you will write a generator file gen/luhn-number which takes as input a $tape which consists of digits or the * character, such as:

It will return a (list tape) which contains all of the Luhn numbers that fit that format. The numbers should be in lexicographic order (smallest to largest by first digit, then second digit, and so on). You may choose to import and use your +validate arm, or perhaps use some other strategy.

Example usage:

Some notes:

  • We take the input as a $tape rather than a @ud because a potential credit card number can have leading zeros.

  • Note that in Hoon, we index starting from 0 -- so the first digit will be in the 0th index, second in 1st index, and so on.

  • This website may be of use for both checking if a number is Luhn and generating a list from missing digits: https://www.dcode.fr/luhn-algorithm

  • Don't worry about numbers with less than 2 digits, or improperly formatted input (with letters and spaces etc.). You can assume that the input tape will have the correct format.

Unit Tests

Following a principle of test-driven development, we compose a series of tests which allow us to rigorously check for expected behavior.

Solutions

These solutions were submitted by the Urbit community as part of a competition in ~2023.6. They are made available under the MIT License and CC0. We ask you to acknowledge authorship should you utilize these elsewhere.

Solution #1

By ~dozreg-toplud.

lib/luhn-number.hoon

gen/luhn-number.hoon

Solution #2

By ~pardun-nollev.

lib/luhn-number.hoon

gen/luhn-number.hoon

Solution #3

By ~motdeg-bintul

lib/luhn-number

gen/luhn-number

PreviousIslandsNextMinimum Path Sum

Last updated