Task 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 other element in the given array. If it is, return the index of the largest element or return -1 otherwise.
Method Explanation
We can solve this problem in a single or two quick linear scans ($O(N)$ time and $O(1)$ extra space):
- Find the maximum: Locate the largest element
max_valand record its indexmax_index. - Condition verification: Traverse the array again. For every element at index $i \ne \text{max\_index}$, verify whether $\text{max\_val} \ge 2 \times \text{ints}[i]$. If any element violates this condition, return
-1immediately. - If all other elements satisfy the inequality, return
max_index.
Perl Implementation
sub twice_largest_index ($ints) {
($ints) = $INTS_CHECK->($ints);
return -1 if !@$ints;
return 0 if @$ints == 1;
my $max_val = $ints->[0];
my $max_index = 0;
for my $i ( 1 .. $#$ints ) {
if ( $ints->[$i] > $max_val ) {
$max_val = $ints->[$i];
$max_index = $i;
}
}
for my $i ( 0 .. $#$ints ) {
next if $i == $max_index;
return -1 if $max_val < 2 * $ints->[$i];
}
return $max_index;
}
Python Implementation
def twice_largest_index(ints: Sequence[int]) -> int:
"""Return index of largest element if at least twice as big as all other elements, else -1."""
if not ints:
return -1
max_value = max(ints)
max_index = ints.index(max_value)
for i, val in enumerate(ints):
if i != max_index and max_value < 2 * val:
return -1
return max_index
Task 2: Zuma Game
You are given a single row of colored balls, $board, and a random number of colored balls in $hand. You can pick any ball from your hand and insert it into any position on the board. If a group of three or more consecutive balls of the same color forms, remove it (recursively eliminating any new consecutive triples). Find the minimum number of balls to insert to clear the board, or return -1 if impossible.
Method Explanation
Since we need the minimum number of insertions, Breadth-First Search (BFS) is ideal:
- State representation: A state consists of
(board, hand_counts, steps). - Ball elimination: After inserting a ball at index $i$, repeated regex substitutions
s/(.)\1{2,}//gcollapse groups of 3+ consecutive identical characters until no more eliminations can take place. - State deduplication: We serialize the board along with a sorted canonical representation of the remaining hand inventory into a visited set to avoid redundant exploration.
- The first time BFS encounters an empty board string (
""), the associated step count is guaranteed to be minimal. If the queue is exhausted without clearing the board, we return-1.
Perl Implementation
sub eliminate ($board) {
my $changed = 1;
while ($changed) {
$changed = ( $board =~ s/(.)\1{2,}//g ) ? 1 : 0;
}
return $board;
}
sub find_min_steps ( $board, $hand ) {
( $board, $hand ) = $ARGS_CHECK->( $board, $hand );
my %hand_counts;
$hand_counts{$_}++ for split //, $hand;
my @queue = ( [ $board, \%hand_counts, 0 ] );
my %visited;
while (@queue) {
my $current = shift @queue;
my ( $current_board, $current_hand_ref, $steps ) = @$current;
my %current_hand = %$current_hand_ref;
return $steps if $current_board eq '';
my $hand_key = join( '', map { $_ . $current_hand{$_} } sort keys %current_hand );
my $state_key = "$current_board|$hand_key";
next if exists $visited{$state_key};
$visited{$state_key} = 1;
for my $i ( 0 .. length($current_board) ) {
for my $color ( sort keys %current_hand ) {
next if ( $current_hand{$color} // 0 ) <= 0;
my $new_board = substr( $current_board, 0, $i ) . $color . substr( $current_board, $i );
$new_board = eliminate($new_board);
my %new_hand = %current_hand;
$new_hand{$color}--;
delete $new_hand{$color} if $new_hand{$color} == 0;
my $new_hand_key = join( '', map { $_ . $new_hand{$_} } sort keys %new_hand );
my $new_state_key = "$new_board|$new_hand_key";
next if exists $visited{$new_state_key};
push @queue, [ $new_board, \%new_hand, $steps + 1 ];
}
}
}
return -1;
}
Python Implementation
def eliminate(board: str) -> str:
"""Eliminate consecutive groups of three or more identical balls from the board."""
pattern = re.compile(r"(.)\1{2,}")
changed = True
while changed:
board, num_subs = pattern.subn("", board)
changed = num_subs > 0
return board
def find_min_steps(board: str, hand: str) -> int:
"""Find minimum number of balls to insert from hand to clear board, or -1."""
hand_counts: dict[str, int] = {}
for c in hand:
hand_counts[c] = hand_counts.get(c, 0) + 1
queue: deque[tuple[str, dict[str, int], int]] = deque()
queue.append((board, hand_counts.copy(), 0))
visited: set[tuple[str, tuple[tuple[str, int], ...]]] = set()
while queue:
current_board, current_hand, steps = queue.popleft()
if not current_board:
return steps
hand_key = tuple(sorted(current_hand.items()))
state_key = (current_board, hand_key)
if state_key in visited:
continue
visited.add(state_key)
for i in range(len(current_board) + 1):
for color in sorted(current_hand.keys()):
if current_hand[color] <= 0:
continue
new_board = current_board[:i] + color + current_board[i:]
new_board = eliminate(new_board)
new_hand = current_hand.copy()
new_hand[color] -= 1
if new_hand[color] == 0:
del new_hand[color]
new_hand_key = tuple(sorted(new_hand.items()))
new_state_key = (new_board, new_hand_key)
if new_state_key in visited:
continue
queue.append((new_board, new_hand, steps + 1))
return -1