I’ve been doing the Weekly
Challenges. The
latest
involved fiddling with arrays and searching game states. (Note that
this ends today.)
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 element in the given array. If it
is return the index of the largest element or return -1
otherwise.
If this were time-critical I'd write each variant and optimise them
against each other, but as it is I use my intuition. The easiest way
to find out whether the largest element is at least twice as large as
every other element is to sort them and compare at known indices. Thus Perl:
sub twicelargest($a) {
my @p = sort {$::b <=> $::a} @{$a};
if ($p[0] >= 2 * $p[1]) {
Now I just need to find where that largest element was in the original
array, so I search through the array for it. (Some languages automate
this, but that's always seemed faintly perverse to me.)
while (my ($i, $c) = each @{$a}) {
if ($c == $p[0]) {
return $i;
}
}
}
Otherwise, return -1.
-1;
}
Task 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.
This can be simplified in practice by omitting "or on either end of
the row". (If the start of the row is "A", then inserting "A" before
or after it will have the same effect. If it is not "A", then
inserting A before it won't create a group of 3. Similarly at the end)
I did this with an exhaustive search in Rust, but lost any enthusiasm
for porting it to other languages (I've also been quite busy lately).
A game state is defined as a row of balls, a hand of balls (stored as
a counter hash), and the number of moves taken to get here.
#[derive(Debug)]
struct Gamestate {
row: Vec<char>,
hand: Counter<char>,
moves: u32,
}
fn zumagame(srow: &str, shand: &str) -> isize {
Set up a FIFO queue with the initial game state
let irow = srow.chars().collect::<Vec<char>>();
let ihand = shand.chars().collect::<Counter<char>>();
let mut queue: VecDeque<Gamestate> = VecDeque::new();
queue.push_back(Gamestate { row: irow, hand: ihand, moves: 0 });
Our initial goal value is "invalid". (When I'm trying to find a
maximum value, it's easy enough to set a thing to zero and then store
anything larger, but when like this it's a minimum value, it's nice
to have a variable which can be explicitly set to "not a valid
answer".)
let mut minball = None;
For as long as there's a game state on the queue, remove it and work
on it.
while let Some(state) = queue.pop_front() {
If there are no balls left in the row, we've reached the goal, so
check whether we have done it in fewer balls than before and if so
store that value.
if state.row.len() == 0 {
if minball.is_none() || minball.unwrap() > state.moves {
minball = Some(state.moves);
}
Otherwise, if there are any balls left in the hand, we can make a move
from here. (If there aren't, this state is a dead end and we won't
build anything more from it.)
} else if state.hand.len() > 0 {
Any new state we generate from here will have this new move number.
let mov = state.moves + 1;
For each valid position where we might insert a ball…
for loc in 0..state.row.len() {
Do we have a ball that matches the one to the left of where we're
inserting it? (Otherwise we won't bother.)
let bal = state.row[loc];
if state.hand.contains_key(&bal) {
Clone row and hand status, and move a ball from hand into row.
let mut row = state.row.clone();
let mut han = state.hand.clone();
han[&bal] -= 1;
if han[&bal] == 0 {
han.remove(&bal);
}
row.insert(loc, bal);
Then look at the row for groups of three or more, and reduce them, until we
can't find any more.
loop {
let mut changed = false;
let mut start = 0;
let mut c = row[0];
for i in 1..=row.len() {
if i == row.len() || row[i] != c {
if i - start > 2 {
row.splice(start..i, []);
changed = true;
break;
}
if i != row.len() {
start = i;
c = row[i];
}
}
}
if row.len() == 0 || !changed {
break;
}
}
Then push the new game state onto the queue.
queue.push_back(Gamestate { row, hand: han, moves: mov });
}
}
}
}
If we never generated a valid solution, return -1, otherwise return
the value.
if minball.is_none() {
-1
} else {
minball.unwrap() as isize
}
}
Full code on
github.