RabbitFarm

2024-10-14

Double Luhn

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1: Double Exist

You are given an array of integers, @ints. Write a script to find if there exist two indices $i and $j such that:

  1. $i≠$j
  2. 0 ≥ $i < size @ints and 0 ≥ $j < size @ints
  3. $ints[$i] = 2 ∗ $ints[$j]

The majority of the work can be done in a few lines. If there is a more elegant way to do this, it escaped me when I was writing this code!

⟨nested loop to determine if the conditions hold 1 ⟩≡


sub double_exist{
my(@a) = @_;
do{
my $i = $_;
do{
my $j = $_;
if($i != $j){
return 1 if $a[$i] == 2 * $a[$j];
}
} for 0 .. @a - 1;
} for 0 .. @a - 1;
return 0;
}
◇

Fragment referenced in 2.

The rest of the code just tests this function.

"ch-1.pl" 2≡


⟨preamble 3 ⟩
⟨nested loop to determine if the conditions hold 1 ⟩
⟨main 4 ⟩
◇

⟨preamble 3 ⟩≡


use v5.40;
◇

Fragment referenced in 2, 7.

⟨main 4 ⟩≡


MAIN:{
say double_exist 6, 2, 3, 3;
say double_exist 3, 1, 4, 13;
say double_exist 2, 1, 4, 2;
}
◇

Fragment referenced in 2.

Sample Run
$ perl perl/ch-1.pl 
1 
0 
1

Part 2: Luhn’s Algorithm

You are given a string $str containing digits (and possibly other characters which can be ignored). The last digit is the payload; consider it separately. Counting from the right, double the value of the first, third, etc. of the remaining digits. For each value now greater than 9, sum its digits. The correct check digit is that which, added to the sum of all values, would bring the total mod 10 to zero. Return true if and only if the payload is equal to the correct check digit.

This can also be done in relatively few lines. There are no real special cases here.

⟨loop and evaluate the check sum 5 ⟩≡


sub luhn{
my($digits) = @_;
my @digits = $digits =~ m/([0-9])/g;
my $sum = 0;
my $check = pop @digits;
{
my $x = pop @digits;
my $y = pop @digits;
if(defined $x && defined $y){
$sum += $y + sum_digits 2 * $x;
}
else{
$sum += sum_digits 2 * $x;
}
redo if @digits;
}
return 1 if 0 == ($sum + $check) % 10;
return 0;
}
◇

Fragment referenced in 7.

For convenience we’ll put the summing of digits for numbers > 10 in a separate function.

⟨sum digits for numbers > 10 6 ⟩≡


sub sum_digits{
my($x) = @_;
if($x >= 10){
my @a = split //, $x;
return $a[0] + $a[1];
}
return $x;
}
◇

Fragment referenced in 7.

The rest of the code drives some tests.

"ch-2.pl" 7≡


⟨preamble 3 ⟩
⟨sum digits for numbers > 10 6 ⟩
⟨loop and evaluate the check sum 5 ⟩
⟨main 8 ⟩
◇

⟨main 8 ⟩≡


MAIN:{
say luhn q/17893729974/;
say luhn q/4137 8947 1175 5904/;
say luhn q/4137 8974 1175 5904/;
}
◇

Fragment referenced in 7.

Sample Run
$ perl perl/ch-2.pl 
1 
1 
0

References

The Weekly Challenge 290
Generated Code

posted at: 01:19 by: Adam Russell | path: /perl | permanent link to this entry

The Weekly Challenge 290 (Prolog Solutions)

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1: Double Exist

You are given an array of integers, @ints. Write a script to find if there exist two indices $i and $j such that:

  1. $i≠$j
  2. 0 ≥ $i < size @ints and 0 ≥ $j < size @ints
  3. $ints[$i] = 2 ∗ $ints[$j]

This is a nice problem for Constraint Logic Programming. The solution is contained in just a single predicate which uses GNU Prolog’s finite domain (FD) constraint solver.

⟨find the values as specified 1 ⟩≡


double_exist(L, I, J):-
length(L, Length),
fd_domain([I, J], 1, Length),
I #\= J,
fd_element(I, L, X),
fd_element(J, L, Y),
X #= 2 * Y,
fd_labeling([I, J]).
◇

Fragment referenced in 2.

The rest of the code just wraps this predicate into a file.

"ch-1.p" 2≡


⟨find the values as specified 1 ⟩
◇

Sample Run
$ gprolog --consult-file prolog/ch-1.p 
| ?- double_exist([6, 2, 3, 3], I, J). 
 
I = 1 
J = 3 
 
yes 
| ?- double_exist([3, 1, 4, 13], I, J). 
 
no 
| ?- double_exist([2, 1, 4, 2], I, J). 
 
I = 1 
J = 2 ? 
 
(1 ms) yes 
| ?- double_exist([2, 1, 4, 2], I, J). 
 
I = 1 
J = 2 ? ; 
 
I = 3 
J = 1 
 
yes 
| ?-

Part 2: Luhn’s Algorithm

You are given a string $str containing digits (and possibly other characters which can be ignored). The last digit is the payload; consider it separately. Counting from the right, double the value of the first, third, etc. of the remaining digits. For each value now greater than 9, sum its digits. The correct check digit is that which, added to the sum of all values, would bring the total mod 10 to zero. Return true if and only if the payload is equal to the correct check digit.

This is essentially a list processing problem and is quite amenable to a DCG solution. Here I just use some ordinary predicates though.

⟨compute 3 ⟩≡


luhn(L):-
reverse(L, [Check|T]),
luhn(Check, T, DigitSums),
sum_list(DigitSums, S0),
M is (S0 + Check) mod 10, !,
M == 0.

luhn(_, [], []).
luhn(Check, [H0, H1|T], [DigitSum|DigitSums]):-
DS is H0 * 2,
sum_digits(DS, Sum),
DigitSum is Sum + H1,
luhn(Check, T, DigitSums).
luhn(Check, [H|T], [[DigitSum|DigitSums]]):-
DS is H * 2,
sum_digits(DS, Sum),
DigitSum is Sum,
luhn(Check, T, DigitSums).

◇

Fragment referenced in 5.

For convenience we’ll have a predicate for summing the digits of numbers > 10.

⟨sum digits 4 ⟩≡


sum_digits(N, Sum):-
N < 10,
Sum = N.
sum_digits(N, Sum):-
number_chars(N, [C0, C1]),
number_chars(N0, [C0]),
number_chars(N1, [C1]),
Sum is N0 + N1.

◇

Fragment referenced in 5.

Finally, let’s assemble our completed code into a single file.

"ch-2.p" 5≡


⟨sum digits 4 ⟩
⟨compute 3 ⟩
◇

Sample Run
$ gprolog prolog/ch-2.p 
| ?- luhn([1, 7, 8, 9, 3, 7, 2, 9, 9, 7, 4]). 
 
yes 
| ?- luhn([4, 1, 3, 7, 8, 9, 4, 7, 1, 1, 7, 5, 5, 9, 0, 4]). 
 
yes 
| ?- luhn([4, 1, 3, 7, 8, 9, 7, 4, 1, 1, 7, 5, 5, 9, 0, 4]). 
 
no 
| ?-

References

The Weekly Challenge 290
Generated Code

posted at: 00:32 by: Adam Russell | path: /prolog | permanent link to this entry