Task — Zuma game

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

Your goal is to clear all of the balls from $row. You may 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 colour you can then remove them from the row. If there are no more balls in the row 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 minimise number of balls you have to insert to clear all the balls from the row. If you cannot clear all the balls from the row using the balls in your hand, return -1.

Examples

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.

Analysis

Another interesting challenge. From the examples it appears that there are at least 4 possible colours, but I have generalised the problem by allowing any of [A-Za-z0-9] as 'colour' identifiers.

Like many such challenges, this one is probably easier for the human eye and brain to solve - in many cases - than a computer program, but the computer gets there in the end.

I pondered a number of rules that could be used to identify starting positions which can't have a solution. For example, if the row contains two Gs and the hand has none, then clearly there is no way to clear the Gs from the row. So my solution has a sub impossible that gets some of those out of the way. Another observation is that if the hand contains a colour that is not (or no longer) present in the row, then that ball need not be considered further.

However, there is a point beyond which such considerations do not apply, and I resorted to a recursive solution which looks at - approximately - all possible orders of playing each ball in the hand in each position in the row. It's approximate because there are some considerable shortcuts. For example, it's only necessary to consider each uniquely-coloured ball in the hand, and only to place it before or after each run of one or more similarly-coloured balls in the row.

Another frustration is that just finding a solution is not enough: we need to find all possible solutions and then select the one requiring the fewest moves.

I also felt it sensible to keep track of the moves being made so that as well as stating the minimum number of moves, I could also list them.

And that's it. It works well if the size of hand is up to, say, 7 or 8, but slows down considerably beyond that.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-10-21
use utf8;     # Week 292 - task 2 - Zuma game
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

my ($best, $end, $best_trace);

zuma_game('WRRBBW', 'RB');
zuma_game('WWRRBBWW', 'WRBRW');
zuma_game('G', 'GGGGG');
zuma_game('RRGGBBYYPPOO', 'RGBYPO');
zuma_game('11223344556654321', '76');
zuma_game('abcdefghhgfedcba', 'hgfedcba');

sub zuma_game {
    
    my ($row, $hand);
    
    ($row, $hand) = @_;
    
    # start game
    say qq[\nInput:  \$row = '$row', \$hand = '$hand'];
    
    # eliminate impossible row/hand combos
    unless (impossible($row, $hand)) {
    
        # play the game
        $best = 9999;
        $end = '¦';
        zuma_game_play($row, $hand, 0, "$row $hand, ");
        
        # analyse result
        ($row, $hand) = $end =~ m|(.*)¦(.*)|;
        if ($row eq '' and $best != 9999) {
            say qq[Output: $best move] . ($best == 1 ? '' : 's');
            say qq[   row '$1' hand '$2'] while $best_trace =~ m|([A-Z0-9]+) ([A-Z0-9]+),|gi;
            say qq[   row '' hand '$hand'];
        } else {
            say qq[Output: -1];
        }
    }
}

sub impossible {
    
    my ($row, $hand, $c, %rows, %hands);
    
    # eliminate obviously impossible hand/row combinations
    ($row, $hand) = @_;
    $rows{$_} ++ for split(//, $row);
    $hands{$_} ++ for split(//, $hand);
    for $c (keys %rows) {
        
        # if char occurs once in row and zero or once in hand ...
        if ($rows{$c} == 1 and (not defined $hands{$c} or $hands{$c} == 1)
        
            # ... or twice in row but not at all in hand
            or $rows{$c} == 2 and not defined $hands{$c}) {
                
            # no solution exists
            say qq[Output: -1];
            return 1;
        }
    }
    return 0;
}

sub zuma_game_play {
    
    my ($n, $row, $hand, $so_far, $l_row, $l_hand, $h, $h_colour, %tried_colour, $new_hand,
        $new_row, $r, $hand_char, %tried, $trace);
    
    ($row, $hand, $so_far, $trace) = @_;
    
    # abandon this trial as we already have an as-good or better one
    return if $so_far >= $best;
    
    # clear out 3+ segments from $row
    do {
        $n = $row =~ s|(.)\1\1+||g;
    } until ($n == 0);
    
    # are we done?
    $l_row = length($row);
    $l_hand = length($hand);
    if ($l_row == 0) {
        
        # yes!
        if ($so_far < $best) {
            $best = $so_far;
            $end = qq[¦$hand];
            $best_trace = $trace;
            return;
        }
    }
    
    # can't pursue this line of testing as nothing is left in hand
    return if $l_hand == 0;
    
    # try moving any useful ball from hand to row
    %tried_colour = ();
    for $h (0 .. $l_hand - 1) {
        
        # try each colour only once, and only if it exists in row
        $hand_char = substr($hand, $h, 1);
        next unless $row =~ m|$hand_char|;
        next if $tried_colour{$hand_char};
        $tried_colour{$hand_char} = 1;
        
        # create new trial hand by removing char from hand ...
        $new_hand = $h == 0 ? '' : substr($hand, 0, $h);
        $new_hand .= substr($hand, $h + 1) unless $h + 1 == $l_hand;
        
        # ... and putting it in all sensible positions in trial row
        for $r (0 .. $l_row) {
            next unless substr($row, $r, 1) eq $hand_char;
            next if $r > 0 and substr($row, $r, 1) eq substr($row, $r - 1, 1);
            $new_row = '';
            $new_row .= substr($row, 0, $r) unless $r == 0;
            $new_row .= $hand_char;
            $new_row .= substr($row, $r);
            next if $tried{qq[$new_row¦$new_hand]};
            $tried{qq[$new_row¦$new_hand]} = 1;
            
            # and keep going
            zuma_game_play($new_row, $new_hand, $so_far + 1, qq[$trace $new_row $new_hand, ]);
        }
    }
}

Output

Input:  $row = 'WRRBBW', $hand = 'RB'
Output: -1

Input:  $row = 'WWRRBBWW', $hand = 'WRBRW'
Output: 2 moves
   row 'WWRRBBWW' hand 'WRBRW'
   row 'WWRRRBBWW' hand 'WBRW'
   row 'WWBBBWW' hand 'WRW'
   row '' hand 'WRW'

Input:  $row = 'G', $hand = 'GGGGG'
Output: 2 moves
   row 'G' hand 'GGGGG'
   row 'GG' hand 'GGGG'
   row 'GGG' hand 'GGG'
   row '' hand 'GGG'

Input:  $row = 'RRGGBBYYPPOO', $hand = 'RGBYPO'
Output: 6 moves
   row 'RRGGBBYYPPOO' hand 'RGBYPO'
   row 'RRRGGBBYYPPOO' hand 'GBYPO'
   row 'GGGBBYYPPOO' hand 'BYPO'
   row 'BBBYYPPOO' hand 'YPO'
   row 'YYYPPOO' hand 'PO'
   row 'PPPOO' hand 'O'
   row '' hand ''

Input:  $row = '11223344556654321', $hand = '76'
Output: 1 move
   row '11223344556654321' hand '76'
   row '112233445566654321' hand '7'
   row '' hand '7'

Input:  $row = 'abcdefghhgfedcba', $hand = 'hgfedcba'
Output: 8 moves
   row 'abcdefghhgfedcba' hand 'hgfedcba'
   row 'abcdefghhhgfedcba' hand 'gfedcba'
   row 'abcdefgggfedcba' hand 'fedcba'
   row 'abcdefffedcba' hand 'edcba'
   row 'abcdeeedcba' hand 'dcba'
   row 'abcdddcba' hand 'cba'
   row 'abcccba' hand 'ba'
   row 'abbba' hand 'a'
   row '' hand ''