This is my response to The Weekly Challenge #290.
@ints.
$i and $j such that:
$i != $j
0 <= ($i, $j) < scalar @ints
$ints[$i] == 2 * $ints[$j]
Input: @ints = (6, 2, 3, 3)
Output: true
For $i = 0, $j = 2
$ints[$i] = 6 => 2 * 3 => 2 * $ints[$j]
Input: @ints = (3, 1, 4, 13)
Output: false
Input: @ints = (2, 1, 4, 2)
Output: true
For $i = 2, $j = 3
$ints[$i] = 4 => 2 * 2 => 2 * $ints[$j]
We do not actually need to consider the indices, just the values. So let us do just that.
The value approach may run into problems if we allow 0 (zero).
The given examples do not have zero (nor negative values for that matter) in them,
but I'll have a go at it anyway. Later on...
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int && @ints.elems > 0); # [1]
my @double = @ints.map: * * 2; # [2]
say so ( any(@ints) == any(@double) ); # [3]
[1] A slurpy array of integers, with at least one value.
[2] Get a version of the input, whith all the values doubled.
The first * is a reference to the current value, and the second
one is the multiplication operator.
[3]
Do any of the input values have the double
version in the modified array? This is the third rule. Note the so
Booelan coercer to reduce the result to a single Boolean value.
See docs.raku.org/routine/any for more information about any.
See docs.raku.org/routine/so for more information about so.
Running it:
$ ./double-exist 6 2 3 3
True
0$ ./double-exist 3 1 4 13
False
$ ./double-exist 2 1 4 2
True
Looking good.
Zero and negative values are ok(ish):
$ ./double-exist 1 -1
False
$ ./double-exist 1 0 -1 -2
True
$ ./double-exist 1 0 0 -1
True
0$ ./double-exist 1 0 -1
True
The last one is wrong, as the zero is a single value and the two indices are equal. This breaks the first rule.
Let us fix that:
File: double-exist-zero
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int && @ints.elems > 0);
if @ints.grep(* == 0).elems > 1 # [1]
{
say True; # [1a]
}
else
{
my @unique = @ints.unique.grep: * != 0; # [2]
my @double = @unique.map: * * 2;
say so ( any(@unique) == any(@double) );
}
[1] Do we have at least 2 zeros? Success if we do.
[2] ) The double any construct is a double loop in disguise.
We can optimize this by getting rid of duplicates (with unique) before
the comparison. This will speed up the program noticeably if the input array is
very big.
See docs.raku.org/routine/unique for more information about unique.
We have indeed solved the problem:
$ ./double-exist-zero 1 0 -1
False
$ ./double-exist-zero 1 0 0 -1
True
$ ./double-exist-zero 1 0 0 0 -1
True
This program is not so compact, but it does give the correct result. That should count for something...
$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.
It was originally posted on reddit.
Example 1:
Input: "17893729974"
Output: true
Payload is 4.
Digits from the right:
7 * 2 = 14, sum = 5
9 = 9
9 * 2 = 18, sum = 9
2 = 2
7 * 2 = 14, sum = 5
3 = 3
9 * 2 = 18, sum = 9
8 = 8
7 * 2 = 14, sum = 5
1 = 1
Sum of all values = 56, so 4 must be added to bring the total mod 10 to
zero. The payload is indeed 4.
Input: "4137 8947 1175 5904"
Output: true
Input: "4137 8974 1175 5904"
Output: false
Why treat the payload explicitly? We can leave it as a part of the number, and
just check the result against mod 10.
#! /usr/bin/env raku
unit sub MAIN ($str, :v($verbose)); # [1]
my @digits = $str.flip.comb.grep: * ~~ /<[0..9]>/; # [2]
say ": Digits (reverse): @digits[]" if $verbose;
my $total = 0; # [3]
@digits.push(0) unless @digits.elems %% 2; # [4]
for @digits -> $a, $b # [5]
{
my $sum = $b * 2; $sum = $sum.comb.sum if $sum > 9; # [6]
say ": $a = $a" if $verbose;
say ": $b * 2 = { $b * 2 }, total = $sum" if $verbose;
$total += $a; # [7]
$total += $sum; # [8]
}
say ! so $total mod 10; # [9]
[1] Just a string; no constraints. (Or; no strings attached.)
[2] Reverse the string (with flip), get an array
with the individual characters (with comb) and keep the digits only
(with grep).
See docs.raku.org/routine/flip for more information about flip.
[3] The total sum will end up here.
[4] We are going to iterate over two and two values at a time, so add a trailing zero (which will not impact the total) if we have an odd number of elements. This will prevent an execution error.
[5] Iterate over two and two elements at a time.
[6] The second one we double, and reduce to a single digit if larger than 9.
[7] Add the first digit.
[8] And the doubled second one.
[9] We modula operation will return zero on success. We coerce this to a Boolean
value (with so), and negate it (with !).
Running it:
$ ./luhns-algorithm 17893729974
True
$ ./luhns-algorithm "4137 8947 1175 5904"
True
$ ./luhns-algorithm "4137 8974 1175 5904"
False
Looking good.
With verbose mode:
$ ./luhns-algorithm -v 17893729974
: Digits (reverse): 4 7 9 9 2 7 3 9 8 7 1
: 4 = 4
: 7 * 2 = 14, total = 5
: 9 = 9
: 9 * 2 = 18, total = 9
: 2 = 2
: 7 * 2 = 14, total = 5
: 3 = 3
: 9 * 2 = 18, total = 9
: 8 = 8
: 7 * 2 = 14, total = 5
: 1 = 1
: 0 * 2 = 0, total = 0
True
$ ./luhns-algorithm -v "4137 8947 1175 5904"
: Digits (reverse): 4 0 9 5 5 7 1 1 7 4 9 8 7 3 1 4
: 4 = 4
: 0 * 2 = 0, total = 0
: 9 = 9
: 5 * 2 = 10, total = 1
: 5 = 5
: 7 * 2 = 14, total = 5
: 1 = 1
: 1 * 2 = 2, total = 2
: 7 = 7
: 4 * 2 = 8, total = 8
: 9 = 9
: 8 * 2 = 16, total = 7
: 7 = 7
: 3 * 2 = 6, total = 6
: 1 = 1
: 4 * 2 = 8, total = 8
True
$ ./luhns-algorithm -v "4137 8974 1175 5904"
: Digits (reverse): 4 0 9 5 5 7 1 1 4 7 9 8 7 3 1 4
: 4 = 4
: 0 * 2 = 0, total = 0
: 9 = 9
: 5 * 2 = 10, total = 1
: 5 = 5
: 7 * 2 = 14, total = 5
: 1 = 1
: 1 * 2 = 2, total = 2
: 4 = 4
: 7 * 2 = 14, total = 5
: 9 = 9
: 8 * 2 = 16, total = 7
: 7 = 7
: 3 * 2 = 6, total = 6
: 1 = 1
: 4 * 2 = 8, total = 8
False
Note the elegant syntax for iterating over more than one element at a
time (in [5]). I could have done this with gather/take, and that would
have removed the ugly trailing zero hack.
So, here it is, for comparison.
File: luhns-algorithm-gather
#! /usr/bin/env raku
unit sub MAIN ($str, :v($verbose));
my @digits = $str.flip.comb.grep: * ~~ /<[0..9]>/;
say ": Digits (reverse): @digits[]" if $verbose;
my $seq := gather
{
my $index = 0;
for @digits -> $sum is copy; # [1]
{
unless $index++ %% 2 { $sum *= 2; $sum = $sum.comb.sum if $sum > 9; }
take $sum;
}
}
my $total = $seq.sum;
say ! so $total mod 10;
[1] Iterating gives a read only value. We want to change it (locally), so we add
is copy.
Running it gives the expected result:
$ ./luhns-algorithm-gather 17893729974
True
$ ./luhns-algorithm-gather "4137 8947 1175 5904"
True
$ ./luhns-algorithm-gather "4137 8974 1175 5904"
False
And that's it.