Shift and merge numbers as in 2048 game code

Question

I started to learn Rust last night. Given its parallelization capabilities, I thought a good starting point would be porting my C++ AI for 2048 to Rust.

This is the function implementing the shift of one line (from high to low indices) of the 2048 board, ported verbatim from C++. It is supposed to shift the numbers in the line and return the score made by that move.

static SCORE_MERGE_FACTOR: f32 = 1.2f32;

fn shift_line(line: [&mut u8, ..4]) -> u64 {
    let mut result: u64 = 0;
    let mut i = 0;
    while i < line.len() {
        let mut merged = false;
        if *line[i] != 0 &&
           i > 0 &&
           *line[i-1] == *line[i]
        {
            *line[i-1] += 1;
            *line[i] = 0;
            merged = true;
            result += *line[i-1] as u64;
        }
        if *line[i] == 0 {
            let mut shifted = false;
            let mut j = i+1;
            while j < line.len() {
                if *line[j] != 0 {
                    *line[i] = *line[j];
                    *line[j] = 0;
                    shifted = true;
                    break;
                }
                j += 1;
            }
            if !shifted || merged {
                i += 1;
            }
        } else {
            i += 1;
        }
    }

    (result as f32 * SCORE_MERGE_FACTOR).round() as u64
}

I would love a general review with respect to Rust's paradigms, but I feel especially uncomfortable for not using iterators and having to use mutable variables all over the place.

I also find these explicit casts quite cumbersome, are they really necessary?

Answer 1

With both scoring and merging

Oops! I did indeed neglect to include merging. This is my mistake; I'm not a big fan of returning values via mutable parameters, so I think my brain shut off. Fortunately, while working on the merging logic, I made the scoring logic shorter.

// Comment #1
fn compress_zeroes(line: [u8, ..4]) -> (u8, u8, u8, u8) {
    let mut nums: Vec<_> = line.iter().map(|x| *x).filter(|x| *x != 0).collect();
    nums.resize(4, 0);
    (nums[0], nums[1], nums[2], nums[3])
}

// Comment #2
fn score_line(line: [u8, ..4]) -> u64 {
    let line = compress_zeroes(line);
    let line = (line.0 as u64, line.1 as u64, line.2 as u64, line.3 as u64);

    let r = match line {
        (a, b, c, d) if a == b && c == d && a != 0 && c != 0 => a+1 + c+1,
        (a, b, _, _) if a == b && a != 0                     => a+1,
        (_, a, b, _) if a == b && a != 0                     => a+1,
        (_, _, a, b) if a == b && a != 0                     => a+1,
        _                                                    => 0,
    };

    (r as f32 * SCORE_MERGE_FACTOR).round() as u64
}

fn squish_line(line: [u8, ..4]) -> [u8, ..4] {
    let line = compress_zeroes(line);

    // Comment #3
    match line {
        (a, b, c, d) if a == b && c == d && a != 0 && c != 0 => [a+1, c+1, 0,   0],
        (a, b, c, d) if a == b && a != 0                     => [a+1, c,   d,   0],
        (a, b, c, d) if b == c && b != 0                     => [a,   b+1, d,   0],
        (a, b, c, d) if c == d && c != 0                     => [a,   b,   c+1, 0],
        (a, b, c, d)                                         => [a,   b,   c,   d],
    }
}

1. This is probably the best enhancement. Since we don't care about zero values, we can simply remove all the zeroes and then add them back at the end of the array. This removes 3 cases from each match statement!
2. Conceptually unchanged from the earlier solution, just smaller due to being able to ignore zeroes.
3. Similar to score_line, we use pattern matching to combine consecutive values that are the same (and non-zero). In this case, we need to track all of the values, so I changed up the naming a bit to leave each letter in the same position.

I definitely prefer having two distinct methods here. In the original, the method is called score_line, but it should actually be called score_and_merge_line. I think that added to my original confusion.

Original answer

There's a lot of code in the original to move things around, just to ignore all that and count how many squares would be merged. I made use of Rust's pattern matching to express the small number of interesting cases that exist in a given line.

fn score_line(line: [u8, ..4]) -> u64 {
    // Comment #1
    let a0 = line[0] as u64;
    let a1 = line[1] as u64;
    let a2 = line[2] as u64;
    let a3 = line[3] as u64;

    // Comment #2
    let r = match (a0, a1, a2, a3) {
        (a, b, c, d) if a == b && c == d && a != 0 && c != 0 => a+1 + c+1,
        (a, b, _, _) if a == b && a != 0 => a+1,
        (_, a, b, _) if a == b && a != 0 => a+1,
        (_, _, a, b) if a == b && a != 0 => a+1,
        (a, 0, b, _) if a == b && a != 0 => a+1, // Comment #3
        (a, 0, 0, b) if a == b && a != 0 => a+1,
        (_, a, 0, b) if a == b && a != 0 => a+1,
        _ => 0, // Comment #4
    };

    (r as f32 * SCORE_MERGE_FACTOR).round() as u64
}

1. We start by unpacking each of the 8-bit numbers and casting them to a larger type. When we add two squares together, it's possible to require more than 8 bits. A u16 would suffice here, but the original method returned a u64, so we will stick with that.
2. We've unpacked the array to separate variables, but we actually want to pattern match against all of them at once. We create a tuple to cram them all back together and match on that.
3. All the pattern match lines are similar, but this one has the most variety. a and b will be bound to the value of the number in the respective position in the tuple. _ means that we don't care about the value in that position, and 0 requires the literal value 0 in that position. We also use a pattern guard (if a == b...) to further restrict the pattern match to pairs of numbers that equal each other. The expression after the => will be the result of the match if that particular branch is chosen.
4. This is the catch-all branch, which is taken when none of the above branches are picked.

I think that this solution is improved from the original because:

1. Removed unneeded mutability. No variables are required to be mutated after they are created, which helps me as a programmer reason about the code better.
2. Removed unused functionality. The function is designed to return the score, it doesn't need to actually move numbers around into the future positions. This relates to the lack of mutability.
3. Pattern matching replaces what could be a complicated series of if-else checks with something that has more concise and has a visual component. The pattern matching looks like a line of numbers would.
4. There's no loops or nested loops. Again this helps me as a programmer see the logic clearer.

I tried to stay close to the original code in terms of types, but I would probably make a few more changes if I kept going:

1. Make a Line type or type alias.
2. Make a newtype or type alias to indicate that the u8 is to be interpreted as a power of two.
3. Use Option for missing values, instead of zero.
4. Remove the 1.2x factor, since I don't currently see the benefit of multiplying every value. If everything has the same weight, it doesn't affect anything.

Additionally, I believe there is a bug in the original code when two adjacent cells have 255. I found this because I compared this code against the original for every possible value. This only took a few minutes, so I believe my code is performant enough for the simple case.