The Largest Zuma with Raku

[313] Published 27. October 2024.

This is my response to The Weekly Challenge #292.

Challenge #292.1: Twice Largest

You are given an array of integers, @ints, where the largest integer is unique.

Write a script to find whether the largest element in the array is at least twice as big as every element in the given array. If it is return the index of the largest element or return -1 otherwise.

Example 1:

Input: @ints = (2, 4, 1, 0)
Output: 1

The largest integer is 4.
For every other elements in the given array is at least twice as big.
The index value of 4 is 1.

Example 2:

Input: @ints = (1, 2, 3, 4)
Output: -1

The largest integer is 4.
4 is less than twice the value of 3, so we return -1.

File: twice-largest

#! /usr/bin/env raku

unit sub MAIN (*@ints where all(@ints) ~~ UInt && @ints.elems > 1,  # [1]
               :v(:$verbose));

my $maxpairs = @ints.maxpairs;                                      # [2]
my $max-val  = $maxpairs[0].value;                                  # [3]
my $max-idx  = $maxpairs[0].key;                                    # [4]

die "Duplicate high value '$max-val'" if $maxpairs.elems > 1;       # [5]

say ": Source:  @ints[]" if $verbose;
say ": - max:   $max-val" if $verbose;

@ints.splice($max-idx, 1);                                          # [6]

my $max = @ints.max;                                                # [7]

say ": Non-max: @ints[]" if $verbose;
say ": - max:   $max" if $verbose;

say $max-val >= $max * 2                                            # [8]
  ?? $max-idx                                                       # [8a]
  !! -1;                                                            # [8b]

[1] Allowing unsigned inters only (with UInt) seems lika a good idea. At least two elements.

[2] We can use maxpairs to get the highest value, and it will also give us the index (which is usefult for getting rid of the value later on).

See docs.raku.org/routine/maxpairs for more information about maxpairs.

[3] Get the highest value.

[4] Get the index of the highest vale.

[5] This one will cause program termination if we have duplicates of the highest value. They will show up here, each (identical value) with their own (unique) index.

[6] Use splice to remove the higest value from the array, given the index.

See docs.raku.org/routine/splice for more information about splice.

[7] Get the highest value in the modified list; i.e. the second highest in the input.

[8] Does this value satisfy the twice as big rule? If so they all do (as the rest of them are lower than this value), and we print the index of the highest [8a]. If not, print the -1 error messsage.

Running it:

$ ./twice-largest 2 4 1 0
1

$ ./twice-largest 1 2 3 4
-1

Looking good.

With verbose mode:

$ ./twice-largest -v 2 4 1 0
: Source:  2 4 1 0
: - max:   4
: Non-max: 2 1 0
: - max:   2
1

$ ./twice-largest -v 1 2 3 4
: Source:  1 2 3 4
: - max:   4
: Non-max: 1 2 3
: - max:   3
-1

Challenge #292.2: Zuma Game

You are given a single row of colored balls, $row and a random number of colored balls in $hand.

Here is the variation of Zuma game as your goal is to clear all of the balls from the board. Pick any ball from your hand and insert it in between two balls in the row or on either end of the row. If there is a group of three or more consecutive balls of the same color then remove the group of balls from the board. If there are no more balls on the board then you win the game. Repeat this process until you either win or do not have any more balls in your hand.

Write a script to minimum number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return -1.

Example 1:

Input: $board = "WRRBBW", $hand = "RB"
Output: -1

It is impossible to clear all the balls. The best you can do is:
- Insert 'R' so the board becomes WRRRBBW. WRRRBBW -> WBBW.
- Insert 'B' so the board becomes WBBBW. WBBBW -> WW.
There are still balls remaining on the board, and you are out of balls
to insert.

Example 2:

Input: $board = "WWRRBBWW", $hand = "WRBRW"
Output: 2

To make the board empty:
- Insert 'R' so the board becomes WWRRRBBWW. WWRRRBBWW -> WWBBWW.
- Insert 'B' so the board becomes WWBBBWW. WWBBBWW -> WWWW -> empty.
2 balls from your hand were needed to clear the board.

Example 3:

Input: $board = "G", $hand = "GGGGG"
Output: 2

To make the board empty:
- Insert 'G' so the board becomes GG.
- Insert 'G' so the board becomes GGG. GGG -> empty.
2 balls from your hand were needed to clear the board.

First a Proof of Concept program, not actually doing the right thing:

File: zuma-game-poc

#! /usr/bin/env raku

subset BALLS of Str where { /^ (<[A .. Z]>)+ $/ };            # [1]

unit sub MAIN ($row  where $row ~~ BALLS,                     # [2]
               $hand where $hand ~~ BALLS,                    # [2a]
               :v(:$verbose));

my $row-bag  = $row.comb.Bag;                                 # [3]
my $hand-bag = $hand.comb.Bag;                                # [3a]

say ": Row (bag): $row-bag" if $verbose;
say ": Hand (bag): $hand-bag" if $verbose;

for $row-bag.sort({ $^a.value <=> $^b.value }) -> $ball-type  # [4]
	{
  say ": Ball { $ball-type.key }: Board: { $ball-type.value } + Hand: \
    { $hand-bag{$ball-type.key} }" if $verbose;

  if $ball-type.value + $hand-bag{$ball-type.key} < 3         # {5]
  {
    say ": Unable to get rid of '{ $ball-type.key }' balls; too few (total: \
      { $ball-type.value + $hand-bag{$ball-type.key} })." if $verbose;

    say -1;                                                   # [5a]
    exit;                                                     # [5b]
  }
}

say "Ok (so far)";                                            # [6]

[1] Let us assume that upercase letters is the thing, so we set up a custom type with subset to ensure that we only get that in the input.

[2] Use the custom type with where.

[3] Get a summary of ball colours and the number of them, using the Bag type. This is basically a hash with a frequency counter bolted on.

See docs.raku.org/routine/Bag for more information about Bag.

[4] Iterate over the balls in the row, sorted by frequency (highes tfirst).

[5] Do we have less than three balls, when we combine the row and hand? If so, we have failed. Say so [5a] and exit [5b].

[6] Failure to fail means success. So far.... As this is only a Proof of Concept.

Running it, with verbose mode:

$ ./zuma-game-poc -v WWRRBBWW WRBRW
: Row (bag): W(4) B(2) R(2)
: Hand (bag): W(2) B R(2)
: Ball B: Board: 2 + Hand: 1
: Ball R: Board: 2 + Hand: 2
: Ball W: Board: 4 + Hand: 2
Ok (so far)

$ ./zuma-game-poc -v G GGGG
: Row (bag): G
: Hand (bag): G(4)
: Ball G: Board: 1 + Hand: 4
Ok (so far)

Looking good. So far, that is...

This shows that the POC program is wrong:

$ ./zuma-game-poc -v ABABAB X
: Row (bag): B(3) A(3)
: Hand (bag): X
: Ball B: Board: 3 + Hand: 0
: Ball A: Board: 3 + Hand: 0
Ok (so far)

The numbers line up, but we are unable to get there as the balls have been sorted in a rather nasty way.

Then the program doing the actual task, where we use this basic rule on the row; in an infinite-ish loop

Are all the balls of the same colour adjacent? Remove them if we have at least three when combined with the hand

Some manual examples showing that this will work:

Board  | Hand   | Removed
----- -+--------+--------
ABC    | AABBCC | AAA
BC     | BBC    | BBB
C      | CC     | CCC
-      | -      | -

Board  | Hand   | Removed
-------+--------+--------
CABAAC | AABBC  | BBB
CAAAC  | AAC    | AAA
CC     | AAC    | CCC
-      | AA     | -

Board    | Hand   | Removed
---------+--------+--------
ABBCBBAA | AABBCC | CCC 
ABBBBA   | AABB   | BBBB
AA       | AABB   | AAA
.        | ABB    | -

File: zuma-game

#! /usr/bin/env raku

subset BALLS of Str where { /^ (<[A .. Z]>)+ $/ };

unit sub MAIN ($row  where $row  ~~ BALLS,
               $hand where $hand ~~ BALLS,
               :v(:$verbose));

my $row-bag  = $row.comb.BagHash;                                     # [1]
my $hand-bag = $hand.comb.BagHash;                                    # [1a]
my @row      = tokenizer($row);                                       # [2]
my $count    = 0;

while @row.elems                                                      # [3]
{
  my @new;                                                            # [4]

  if $verbose
  {
    say ": Row (grouped): @row[]"; 
    say ": Row (bag): $row-bag";
    say ": Hand (bag): $hand-bag";
  }

  my $count-inner = 0;                                                # [5]

  for @row -> $elem                                                   # [6]
  {
    my $length = $elem.chars;                                         # [7]
    my $char   = $elem.substr(0,1);                                   # [8]
    if $length == get_count($char) && $length + get_hand($char) >= 3  # [9]
    {
      say ": * Remove $elem ($length)" if $verbose;
      
      $row-bag{$char} = 0;                                            # [10]
      my $add = $length < 3 ??  (3 - $length) !! 0;                   # [11]
      $hand-bag{$char} -= $add;                                       # [12]

      $count += $add;                                                 # [13]
      $count-inner++;                                                 # [14]

      if $verbose
      {
        say ": * Remove $elem ($length from row + $add from hand)";
        say ":   Row (bag): $row-bag";
        say ":   Hand (bag): $hand-bag";
      }

    }
    else
    {
      say ": + Keep $elem" if $verbose;
      @new.push: $elem;                                               # [15]
    }
  }

  last if @new.elems == 0;                                            # [16]

  if $count-inner == 0                                                # [17]
  {
    say -1;                                                           # [17a]
    exit;                                                             # [17b]
  }

  @row = tokenizer(@new.join);                                        # [18]
}  

say $count;                                                           # [16a]

sub get_count ($char)                                                 # [19]
{
  return $row-bag{$char};
}
			  
sub get_hand ($char)                                                  # [19]
{
  return $hand-bag{$char};
}

sub tokenizer ($str)                                                  # [2b]
{
  return gather
  {
    my @chars = $str.comb;
    my $first = @chars.shift;
    my $count = 1;

    while @chars
    {
      my $second = @chars.shift;
      if $first ne $second
      {
        take $first x $count;
        $first = $second;
        $count = 1;
      }
      else
      {
        $count++;
      }
    }

    take $first x $count;
  }
}

[1] We use BagHash this time, the read-write version of the read only Bag. We are changing the values (in [10] and [12]).

See docs.raku.org/routine/BagHash for more information about BagHash.

[2] The "tokenizer" procedure has been recycled, without any changes, from the "strong-password" program in the Strong and Valid with Raku article, my response to The Weekly Challenge #287. It splits up the string into an array where each eleemt is a string that has one unique character; i.e. "ABBC" -> ("A", "BB", "C").

[3] As long as we have unfinished business (something in the row).

[4] Elements that we keep in each iteration will be added here, as we iterate over them in [6].

[5] Number of changes in the inner loop, to prevent en eternal loop doing nothing.

[6] Iterate over the non-removed elements in the row.

[7] The length of the current string.

[8] The actual character, taken from the first character in the string. (As there may be more than one, but they are all the same.)

[9] If the current block has all of the letters of this type in the hand, and we have at least three letters when we add the ones from the hand, then we can remove them.

[10] Remove the letters from the row (by setting the count to zero).

[11] Number of chracters to collect from the hand. We only have to fill up to three.

[12] Remove the letters from the hand.

[13] Count the letters taken from the hand.

[14] We have changed the row in this iteration.

[15] Not able to remove the element? Save it for the next iteration.

[16] Terminate the loop if we have emptied the row. This will then print the number of balls we have added [16a].

[17] Not changed anything in the inner loop? Then we cannot change anything. Report failure [17a] and exit [17b].

[18] Set up the new row, ready for the next iteration. We do it like this, so that e.g. ("A", "BBB", "A") -> ("AAA") after removal of BBB

[19] Perhaps nicer than doing the lookup directly, or perhaps not...

Running it:

$ ./zuma-game WRRBBW RB
-1

$ ./zuma-game WWRRBBWW WRBRW
2

$ ./zuma-game G GGGGG
2

Looking good.

With verbose mode:

$ ./zuma-game -v WRRBBW RB
: Row (grouped): W RR BB W
: Row (bag): R(2) B(2) W(2)
: Hand (bag): R B
: + Keep W
: * Remove RR (2)
: * Remove RR (2 from row + 1 from hand)
:   Row (bag): B(2) W(2)
:   Hand (bag): B
: * Remove BB (2)
: * Remove BB (2 from row + 1 from hand)
:   Row (bag): W(2)
:   Hand (bag): 
: + Keep W
: Row (grouped): WW
: Row (bag): W(2)
: Hand (bag): 
: + Keep WW
-1

$ ./zuma-game -v WWRRBBWW WRBRW
: Row (grouped): WW RR BB WW
: Row (bag): R(2) B(2) W(4)
: Hand (bag): W(2) R(2) B
: + Keep WW
: * Remove RR (2)
: * Remove RR (2 from row + 1 from hand)
:   Row (bag): B(2) W(4)
:   Hand (bag): W(2) R B
: * Remove BB (2)
: * Remove BB (2 from row + 1 from hand)
:   Row (bag): W(4)
:   Hand (bag): W(2) R
: + Keep WW
: Row (grouped): WWWW
: Row (bag): W(4)
: Hand (bag): W(2) R
: * Remove WWWW (4)
: * Remove WWWW (4 from row + 0 from hand)
:   Row (bag): 
:   Hand (bag): W(2) R
2

$ ./zuma-game -v G GGGGG
: Row (grouped): G
: Row (bag): G
: Hand (bag): G(5)
: * Remove G (1)
: * Remove G (1 from row + 2 from hand)
:   Row (bag): 
:   Hand (bag): G(3)
2

My manual examples work out:

 ./zuma-game -v ABC AABBCC
: Row (grouped): A B C
: Row (bag): C A B
: Hand (bag): C(2) B(2) A(2)
: * Remove A (1)
: * Remove A (1 from row + 2 from hand)
:   Row (bag): C B
:   Hand (bag): C(2) B(2)
: * Remove B (1)
: * Remove B (1 from row + 2 from hand)
:   Row (bag): C
:   Hand (bag): C(2)
: * Remove C (1)
: * Remove C (1 from row + 2 from hand)
:   Row (bag): 
:   Hand (bag): 
6

$ ./zuma-game -v CABAAC AABBC
: Row (grouped): C A B AA C
: Row (bag): A(3) B C(2)
: Hand (bag): C A(2) B(2)
: + Keep C
: + Keep A
: * Remove B (1)
: * Remove B (1 from row + 2 from hand)
:   Row (bag): A(3) C(2)
:   Hand (bag): C A(2)
: + Keep AA
: + Keep C
: Row (grouped): C AAA C
: Row (bag): A(3) C(2)
: Hand (bag): C A(2)
: + Keep C
: * Remove AAA (3)
: * Remove AAA (3 from row + 0 from hand)
:   Row (bag): C(2)
:   Hand (bag): C A(2)
: + Keep C
: Row (grouped): CC
: Row (bag): C(2)
: Hand (bag): C A(2)
: * Remove CC (2)
: * Remove CC (2 from row + 1 from hand)
:   Row (bag): 
:   Hand (bag): A(2)
3

$ ./zuma-game -v ABBCBBAA AABBCC
: Row (grouped): A BB C BB AA
: Row (bag): C B(4) A(3)
: Hand (bag): B(2) A(2) C(2)
: + Keep A
: + Keep BB
: * Remove C (1)
: * Remove C (1 from row + 2 from hand)
:   Row (bag): B(4) A(3)
:   Hand (bag): B(2) A(2)
: + Keep BB
: + Keep AA
: Row (grouped): A BBBB AA
: Row (bag): B(4) A(3)
: Hand (bag): B(2) A(2)
: + Keep A
: * Remove BBBB (4)
: * Remove BBBB (4 from row + 0 from hand)
:   Row (bag): A(3)
:   Hand (bag): B(2) A(2)
: + Keep AA
: Row (grouped): AAA
: Row (bag): A(3)
: Hand (bag): B(2) A(2)
: * Remove AAA (3)
: * Remove AAA (3 from row + 0 from hand)
:   Row (bag): 
:   Hand (bag): B(2) A(2)
2

But these will not work, as the algorithm is incapable of doing the first insert/remove:

Board   | Hand  | Removed
--------+-------+--------
ABBAB   | ABBB  | BBB
AAB     | ABB   | AAA
B       | BB    | BBB
-       | -     | -

Board     | Hand   | Removed
----------+--------+--------
AABABAB  | AAAAAA  | AAA   
AABBAB   | AAAA    | AAA
AABBBB   | AA      | BBBB
AA       | AA      | AA
-        | -       | -

$ ./zuma-game -v ABBAB ABBB
: Row (grouped): A BB A B
: Row (bag): A(2) B(3)
: Hand (bag): B(3) A
: + Keep A
: + Keep BB
: + Keep A
: + Keep B
-1

$ ./zuma-game -v AABABAB AAAAAA
: Row (grouped): AA B A B A B
: Row (bag): A(4) B(3)
: Hand (bag): A(6)
: + Keep AA
: + Keep B
: + Keep A
: + Keep B
: + Keep A
: + Keep B
-1

The examples given in the challenge work, so perhaps we are good...

I am out of time, so I'll have to leave it here anyway.

And that's it.

Links

About me
Keyword Index
Beginning Raku (book)
RSS Feed
Code (zip)
Reddit Comments