site.base_url }}/">The Bear's Den -->

The Bear's Den

Enter at your own risk

08 November 2024

Challenge 292

Play Twice

Task 1: Twice Largest
Task 2: Zuma Game

Task 1: Twice Largest

Submitted by: Mohammad Sajid Anwar

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.

Solution

Using PDL’s maximum_n_ind we find the indices of the two largest elements. Comparing the vector product of the corresponding values with (1, -2) against zero reveals the twice as big condition with the first index as the requested solution (if the condition is satisfied).

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

sub twice_largest {
    my $i = long @_;
    my $max2 = $i->maximum_n_ind(2);

    0 <= inner($i($max2), long(1, -2)) ? $max2((0)) : -1;
}

See the full solution to task 1.

Task 2: Zuma Game

Submitted by: Mohammad Sajid Anwar

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.

Solution

I should have taken the time to come to a more elaborate solution. But the challenge is overdue and I’d like to catch up.

Some considerations:

There is no use inserting a ball into a position where no neighboring ball has the same color as the inserted one.
It doesn’t matter if a ball is inserted in front, inside or following a group of balls having the same color. We’ll put it in front.
We can insert one ball from the hand into the board, clear a sequence of equally colored balls and recurse into a new game having this starting condition.
The recursive process stops when
- The board is empty
- The hand is empty
- The number of moves that lead to this point is not less than the current known minimum number of moves to clear the board.
The rules are not completely clear to me. (In the following examples, the ball just inserted from the hand is represented by a small letter.)
- Are we allowed to remove a group from the board without inserting a ball from the hand? ('AAA' -> '') My assumption: No.
- Are we allowed to remove more than one group from the board? ('AAAbBB' -> '') My assumption: No.
- Are we allowed to remove a group from the board, that does not contain the newly inserted ball? ('AAAbB' -> 'BB') My assumption: Yes.
The last assumption requires a special handling when removing a group of balls: When there is more than one possible group, we need to try all of them.

To improve the efficiency of the recursive branch-and-cut process, some additional criteria are needed.

With every move, at most one group of balls may be removed from the board. If we have less balls in the hand than there are different colors on the board, the board cannot be cleared.
If there are less than three balls of the same color on the board and there is no such colored ball in the hand, the board cannot be cleared.
If we made already $m$ moves at the current stage and there are $n$ different colors on the board, then at least $m + n$ moves are required to clear the board. This must be less than the currently known minimum for the possibility of an improvement.

And here it comes:

use strict;
use warnings;
use experimental 'signatures';
use List::Util 'sum';

our $lvl;
our $verbose = 1;

sub dbg {
    say '  ' x ($lvl - 1), @_ if $verbose;
}

sub zuma ($board, $hand, $moves, $min) {
    local $lvl = $lvl + 1;
    dbg("board: $board");
    dbg("hand:  ", map $_ x $hand->{$_}, keys %$hand);
    dbg("moves: $moves");
    dbg("min:   $min");
    my %board_content;
    $board_content{$_}++ for split //, $board;
    my $hand_count = sum values %$hand;
    my $color_count = scalar keys %board_content;
    dbg("cut: need at least ", $moves + $color_count, " moves to clear, ",
        "cannot improve $min"), return 'inf' if $moves + $color_count >= $min;
    dbg("need at least $color_count moves to clear, ",
        "have only $hand_count in hand"), return 'inf'
        if $hand_count < $color_count;
    my %singles;
    @singles{grep $board_content{$_} < 3, keys %board_content} = ();
    delete @singles{keys %$hand};
    dbg("cannot remove ", keys %singles), return 'inf' if %singles;
    my $prev = '';
    my $b;
    for my $i (0 .. length($board) - 1) {
        $b = substr $board, $i, 1;
        next if $b eq $prev;
        next unless $hand->{$b};
        my %hand = %$hand;
        $hand{$b}--;
        my $new_board = $board;
        dbg("insert $b at $i in $new_board");
        substr($new_board, $i, 0) = $b;
        my $else = 1;
        while ((my $match = $new_board =~ /((.)\2{2,})/g) || $else) {
            $else = 0;
            my $reduced_board = $new_board;
            if ($match) {
                dbg("remove $2 at $-[1]-$+[1] from $new_board");
                substr($reduced_board, $-[1], $+[1] - $-[1]) = '';
                dbg("board empty"), return $moves + 1 unless $reduced_board;
            } else {
                dbg("nothing removed from $new_board");
            }
            my $res = zuma($reduced_board, \%hand, $moves + 1, $min);
            dbg("got $res");
            dbg("new minimum $res"), $min = $res if $res < $min;
        }
    } continue {
        $prev = $b;
    }

    $min;
}

sub play_zuma ($board, $hand) {
    my %hand;
    $hand{$_}++ for split //, $hand;
    $lvl = 0;
    my $zuma = zuma($board, \%hand, 0, 'inf');
    $lvl = 1;
    dbg("minimum moves: $zuma");

    $zuma < 'inf' ? $zuma : -1;
}

See the full solution to task 1.

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.