RogerBW's Blog

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.