Сдвиг и слияние чисел, как в коде игры 2048 года

Я начал изучать Ржавчу прошлой ночью. Учитывая его возможности параллелизации, я подумал, что хорошей отправной точкой будет перенос моего C ++ AI для 2048 в Rust.

Это функция, реализующая сдвиг одной строки (от высоких до низких) доски 2048, переносимой дословно из C ++. Предполагается сдвинуть числа в строке и вернуть счет, сделанный этим ходом.

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
}

Мне бы понравился общий обзор в отношении парадигм Rust, но мне особенно неудобно не использовать итераторы и использовать переменные переменные повсюду.

Я также считаю, что эти явные броски довольно громоздки, действительно ли они нужны?

32 голоса | спросил Jonas Wielicki 9 Maypm14 2014, 17:08:14

1 ответ


8

При подсчете и слиянии

Oops! Я действительно пренебрегал включением слияния. Это моя ошибка; Я не большой поклонник возвращения значений с помощью изменяемых параметров, поэтому я думаю, что мой мозг отключен. К счастью, работая над логикой слияния, я сделал логику оценки короче.

// 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. Это, вероятно, лучшее улучшение. Поскольку нас не интересуют нулевые значения, мы можем просто удалить все нули, а затем добавить их обратно в конец массива. Это удаляет 3 случая из каждого выражения match!
  2. Концептуально неизменен от более раннего решения, только меньше из-за возможности игнорировать нули.
  3. Подобно score_line, мы используем сопоставление шаблонов для объединения последовательных значений, которые являются одинаковыми (и ненулевыми). В этом случае нам нужно отслеживать значения all , поэтому я изменил наименование бит, чтобы оставить каждую букву в том же положении.

Я определенно предпочитаю иметь два разных метода. В оригинале метод называется score_line, но на самом деле его следует называть score_and_merge_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. Начнем с распаковки каждого из 8-битных чисел и их литья в более крупный тип. Когда мы добавляем два квадрата вместе, возможно потребовать больше 8 бит. A u16 хватитздесь, но исходный метод возвратил u64, поэтому мы будем придерживаться этого.
  2. Мы распаковали массив для разделения переменных, но на самом деле мы хотим сразу сопоставить шаблон со всеми из них. Мы создаем кортеж, чтобы скопировать их все вместе и сопоставить с ними.
  3. Все строки соответствия шаблонов аналогичны, но этот имеет наибольшее разнообразие. a и b будут привязаны к значению числа в соответствующей позиции в кортеже. _ означает, что мы не заботимся о значении в этой позиции, а 0 требует буквенного значения 0 в этой позиции. Мы также используем защиту шаблона (if a == b ...), чтобы еще больше ограничить соответствие шаблона парам чисел, которые равны друг другу. Выражение после => будет результатом соответствия match, если выбрана эта конкретная ветка.
  4. Это ветка catch-all, которая берется, когда ни одна из вышеупомянутых ветвей не выбрана.

Я думаю, что это решение улучшено от оригинала, потому что:

  1. Удалена ненужная изменчивость. Никакие переменные не требуются, чтобы быть мутированными после их создания, что помогает мне в качестве причины программиста о кодексе лучше.
  2. Удалены неиспользуемые функции. Функция предназначена для возврата оценки, ей не нужно действительно перемещать числа в будущие позиции. Это связано с отсутствием изменчивости.
  3. Соответствие шаблону заменяет то, что может быть сложной серией проверок if-else с более краткими и , с визуальным компонентом. Соответствие шаблону выглядит как строка чисел.
  4. Нет циклов или вложенных циклов. Опять же, это помогает мне, когда программист видит логическую ясность.

Я старался оставаться рядом с исходным кодом с точки зрения типов, но я бы, вероятно, сделал еще несколько изменений, если бы продолжал:

  1. Введите тип Line или введите псевдоним.
  2. Создайте псевдоним newtype или type, чтобы указать, что u8 должен интерпретироваться как сила двух.
  3. Используйте Option для отсутствующих значений вместо нуля.
  4. Измените коэффициент 1.2x, так как в настоящее время я не вижу преимущества умножения каждого значения. Если все имеет одинаковый вес, это ничего не влияет.

Кроме того, я считаю, что в исходном коде есть ошибка, когда две соседние ячейки имеют 255. Я нашел это, потому что я сравнивал этот код с оригиналом для каждого возможного значения. Это заняло всего несколько минут, поэтому я считаю, что мой код достаточно прост для простого случая.

ответил Shepmaster 26 FriEurope/Moscow2014-12-26T08:59:18+03:00Europe/Moscow12bEurope/MoscowFri, 26 Dec 2014 08:59:18 +0300 2014, 08:59:18

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132