Three Colours
by Raku

by Arne Sommer

Three Colours by Raku

[62] Published 11. March 2020.

This is my response to the Perl Weekly Challenge #51.

Challenge #51.1: 3 Sum

Given an array @L of integers. Write a script to find all unique triplets such that a + b + c is same as the given target T. Also make sure a <= b <= c.

Here is wiki page for more information.

Example:

@L = (-25, -10, -7, -3, 2, 4, 8, 10);
One such triplet for target 0 i.e. -10 + 2 + 8 = 0.

File: 3sum
unit sub MAIN (Int $target, *@int);                    # [1]

my @values = @int || (-25,-10,-7,-3,2,4,8,10);         # [2]

die "Integers only" unless all(@values) ~~ Int;        # [3]

for @values.combinations(3).grep(*.sum == $target).unique -> @curr  # [4]
### # 4a ## # 4b ########## # 4c ################ # 4d ###########
{
  say "Triplet: { @curr.sort.join(", ") } = $target";  # [5]
}

[1] The first value is the target, then we use a slurpy array to get the array of integers. Note that we cannot put a default value or a type constraint on a slurpy parameter, so that is the job for [2] and [3].

[2] A default value (actually 8 of them in an array), as given in the challenge. Note that we have to specify the target value (as I haven't specified a default value).

[3] Checking that all the values are integers, with the Junction Operator all.

[4] Take all the three element combinations [4b] of the input values [4a]. Only use those where the sum of the values are T [4c], and get rid of duplicates (with unique) [4d].

[5] Print the triplet, sorted. The sorting order really is irrelevant for the algorithm, but the challenge made a point out if it - so here it is.

The Junction Operator all can be used like this to check that all the values satisfy a constraint. See docs.raku.org/routine/all for more information. (There are other Junction Operators; any, all, one and none.)

Running it:

$ raku 3sum 0 
Triplet: -10, 2, 8 = 0
Triplet: -7, -3, 10 = 0

$ raku 3sum 0 -25 -10 -7 -3 2 4 8 10
Triplet: -10, 2, 8 = 0
Triplet: -7, -3, 10 = 0

$ raku 3sum 10 -25 -10 -7 -3 2 4 8 11
Triplet: -3, 2, 11 = 10

$ raku 3sum 10 11 -10 -7 -3 2 4 8 11 -25
Triplet: -3, 2, 11 = 10

$ raku 3sum 0 -100 100 -90 10 -10 90 0
Triplet: -100, 0, 100 = 0
Triplet: -100, 10, 90 = 0
Triplet: -90, -10, 100 = 0
Triplet: -90, 0, 90 = 0
Triplet: -10, 0, 10 = 0

Looking good, but we should check for duplicates:

$ raku 3sum 30 10 10 10 10 10
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30
Triplet: 10, 10, 10 = 30

Oops!

A Unique Problem

The problem is that unique uses the Value Identity Operator === to compare the values. The documentation (docs.raku.org/routine/===) says that it «Returns True if both arguments are the same object, disregarding any containerization.». Remember that everything in Raku is an object. That means that an array is also an object, and two different arrays are not the same object, even if they happen to have the same content.

We can fix that by using a more suitable comparison operator, as unique supports that. Reading the documentation (docs.raku.org/routine/unique) is a good idea, as it gives away the solution; the Equivalence Operator eqv. The documentation (docs.raku.org/routine/eqv) says that it «Returns True if the two arguments are structurally the same, i.e. from the same type and (recursively) contain equivalent values.» That is exactly what we need.

The amended program:

File: 3sum-eqv
unit sub MAIN (Int $target, *@int);

my @values = @int || (-25,-10,-7,-3,2,4,8,10);

die "Integers only" unless all(@values) ~~ Int;

for @values.combinations(3).grep(*.sum == $target).unique(:with(&[eqv]))
  -> @curr
{
  say "Triplet: { @curr.sort.join(", ") } = $target";
}

Note the special bracket syntax ([]) for specifying a custom operator. Without the brackets, «eqv» would be interpeted as a procedure name.

Running it:

$ raku 3sum-eqv 30 10 10 10 10 10
Triplet: 10, 10, 10 = 30

$ raku 3sum-eqv 0
Triplet: -10, 2, 8 = 0
Triplet: -7, -3, 10 = 0

Note that combinations in itself doesn't give duplicates. But duplicates in the input array will give duplicates in the result, and that is what happened in the «10 10 10 10 10» example.

The first example below is without duplicates, the second one has only duplicates, and the third one shows where the different a values come from:

> .combinations(3)
((a b c) (a b d) (a c d) (b c d))

> .combinations(3)
((a a a) (a a a) (a a a) (a a a))

> .combinations(3)
((a1 a2 a3) (a1 a2 a4) (a1 a3 a4) (a2 a3 a4))

Challenge #51.2: Colourful Number

Write a script to display all Colorful Number with 3 digits.

A number can be declare Colorful Number where all the products of consecutive subsets of digit are different.

For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique.

We don't actually need the number itself, only the individual digits, so three loops (one for each digit) is a good idea.

File: colnum-wrong
for 1 .. 9 -> $a       # [1]
{
  for 0 .. 9 -> $b     # [2]
  {
    for 0 .. 9 -> $c   # [3]
    {
      say "$a$b$c" if $a != $b != $c != $a * $b != $b * $c != $a * $b * $c;
        # [4]
    }
  }
}

[1] The first digit, starting with «1» as the first three-digit value is «100».

[2] The second digit.

[3] The, you guessed it, third digit.

[4] Print it if the products differ.

Running it:

$ raku colnum-wrong
213
214
...

There are 444 lines, so I have only shown the first two. And the very first value shows that we have a problem; 213 gives 2 and 2*1 which are identical - so 213 is not a valid answer.

The problem is that the comparison as written only compares two and two neighbouring values, and not all of them... (Hint: 1 != 2 != 1 --> True.)

The solution is to treat the comparison as a list, and look for duplicates. And Raku has an operator for that, repeated, which according to the documentation (docs.raku.org/language/independent-routines#routine_repeated) «returns a sequence of repeated values from the invocant/argument list. It takes the same parameters as unique, but instead of passing through any elements when they're first seen, they're only passed through as soon as they're seen for the second time (or more).»

File: colnum
for 1 .. 9 -> $a
{
  for 0 .. 9 -> $b
  {
    for 0 .. 9 -> $c
    {
      print "$a$b$c " # [2]
        unless ($a, $b, $c, $a * $b, $b * $c, $a * $b * $c).repeated;  # [1]
    }
  }
}
say "";               # [2a]

[1] This one slips duplicate values through, and the expression evaluates to True (as we are in Boolean context because of the unless), if we have any values in that list of duplicates.

[2] I have made the output more readable by printing the values on a single line (with print instead of say). Note the trailing space, and the explicit newline [2a] at the end.

Running it:

$ raku colnum
234 235 237 238 239 243 245 246 247 249 253 254 256 257 258 259 263 264 265 \
267 268 269 273 274 275 276 278 279 283 284 285 286 287 289 293 294 295 296 \
297 298 324 325 327 328 329 342 345 346 347 348 349 352 354 356 357 358 359 \
362 364 365 367 368 369 372 374 375 376 378 379 382 384 385 386 387 389 392 \
394 395 396 397 398 423 425 426 427 429 432 435 436 437 438 439 452 453 456 \
457 458 459 462 463 465 467 468 469 472 473 475 476 478 479 482 483 485 486 \
487 489 492 493 495 496 497 498 523 524 526 527 528 529 532 534 536 537 538 \
539 542 543 546 547 548 549 562 563 564 567 568 569 572 573 574 576 578 579 \
582 583 584 586 587 589 592 593 594 596 597 598 624 625 627 628 629 634 635 \
637 638 639 642 643 645 647 648 649 652 653 654 657 658 659 672 673 674 675 \
678 679 682 683 684 685 687 689 692 693 694 695 697 698 723 724 725 726 728 \
729 732 734 735 736 738 739 742 743 745 746 748 749 752 753 754 756 758 759 \
762 763 764 765 768 769 782 783 784 785 786 789 792 793 794 795 796 798 823 \
825 826 827 829 832 834 835 836 837 839 843 845 846 847 849 852 853 854 856 \
857 859 862 863 864 865 867 869 872 873 874 875 876 879 892 893 894 895 896 \
897 923 924 925 926 927 928 932 934 935 936 937 938 942 943 945 946 947 948 \
952 953 954 956 957 958 962 963 964 965 967 968 972 973 974 975 976 978 982 \
983 984 985 986 987 

I have added newlines above to make it readable.

There are 328 Colourful Numbers with 3 digits (out of 900 possible values), so they are not that special.

And that's it.