Robbie Hatley's Solutions, in Perl, for The Weekly Challenge #292 ("Twice Largest" and "Zuma Game")

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

The Weekly Challenge for the week of 2024-10-20 through 2024-10-26 is #292.

The tasks for challenge #292 are as follows:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 292-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 other
element in the array. If it is, return the index of the largest
element; else return -1.

Example 1:
   Input:  (2, 4, 1, 0)
   The largest integer is 4 (with index 1), and it as at-least
   twice as large as every other element, so return its index, 1.

Example 2:
   Input:  (1, 2, 3, 4)
   The largest integer is 4, but it's less than twice as large as
   the next-largest number, 3; so return -1.

This is just a matter of reverse-numeric-sorting the array then determining whether-or-not the largest element (0th element of sorted array) is at-least-twice-as-large-as the second-largest element (1st element of sorted array).

Robbie Hatley's Perl Solution to The Weekly Challenge 292-1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 292-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. Your goal is to clear all of
the balls from the row. 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 row. If
there are no more balls on 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 determine the minimum number of balls you need
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.

Example 1:
Input: $row = "WRRBBW", $hand = "RB"
It is impossible to clear all the balls. The best you can do is:
- Insert 'R' so the row becomes WRRRBBW. WRRRBBW -> WBBW.
- Insert 'B' so the row becomes WBBBW. WBBBW -> WW.
There are still balls remaining on the row,
and you are out of balls to insert,
so Output = -1.

Example 2:
Input: $row = "WWRRBBWW", $hand = "WRBRW"
To make the row empty:
- Insert 'R' so the row becomes WWRRRBBWW -> WWBBWW
- Insert 'B' so the row becomes WWBBBWW   -> WWWW -> empty
2 balls from your hand were needed to clear the row,
so Output = 2.

Example 3:
Input: $row = "G", $hand = "GGGGG"
To make the row empty:
- Insert 'G' so the row becomes GG.
- Insert 'G' so the row becomes GGG. GGG -> empty.
2 balls from your hand were needed to clear the row,
so Output = 2.

I don't know about "minimum" (which would require elaborate mathematical proofs), but I can certainly come up with an algorithm which makes "good effort" towards removing all the balls. I use this approach:

1. Sort hand in increasing order of abundance of each hand ball in row. (I do this because highly-abundant colors in row tend to self-destruct after less-abundant intermediaries are removed.)
2. Process all balls in sorted hand from left to right.
3. For each ball in hand:
   • If there are two contiguous balls of that color on row, insert to their right.
   • Else if there is 1 ball of that color on row, insert to its right.
   • Else don't use current hand ball (as this would be counterproductive).
   • Keep count of how many hand balls were added to row.
   • Remove any contiguous clusters of 3-or-more balls from hand.
   • Stop processing hand balls if row is now empty.
4. If row is now empty, we win, so return number of hand balls used;
   otherwise, we lose, so return -1.

Robbie Hatley's Perl Solution to The Weekly Challenge 292-2

That's it for challenge 292; see you on challenge 293!