Получение значений из предыдущей «строки» в массиве 2D C

Question

Я работаю над 1D Game of Life (основываясь на правилах, изложенных здесь в Mathworld ). По сути, каждое поколение представлено в виде ряда нулей или единиц (мертвых или живых), а следующее поколение создается на основе двоичного представления аргумента командной строки «правила».

Например, правило 30 превращается в 00011110 (двоичное для 30), и это используется для определения, какие шаблоны битов будут порождать новые ячейки или отмирать сами в следующем поколении.

Чтобы запрограммировать это, мне нужно иметь доступ к битам в группах по три (чтобы применить правило) из предыдущей строки. Ниже приведен пример изображения (обратите внимание, что начальная строка всегда 0 с центральным 1):

00000100000  #seed row
11001011001  #generated from seed row
...........
11110010101  #n-th row, generated from n-1 row

Чтобы сгенерировать строку, я должен посмотреть на биты из строки выше в группах по три, а затем применить правило в качестве решения 1/0, live / die.

По сути, я планирую сопоставить 3-битную комбинацию и правило и использовать ее для вывода 0 или 1 для потомства. это общий алгоритм:

if three_bit_pattern == 'xxx' && rule[x] == 0/1 {print 0/1} else {print 1/0}

Часть программы, в которой у меня возникают трудности, связана с доступом к содержимому предыдущего ряда. Все мои попытки дают мусор или неверные данные.

Короче, как мне получить доступ к значениям предыдущего ряда в группах по три бита?

Строки создаются следующим образом:

int i, j, k;
int row = atoi(argv[1]) + 1;
int col = 2 * atoi(argv[1]) + 1;

int arr[col];
int output[col];

char rule[9]; //binary representation of rule (2^8 stores up to 255 + null term)
int2binary(atoi(argv[2]), &rule, 10);

for(i = 0; i < row; i++){
   for(j = 0; j < col; j++){
    if(i == 0){
        if(j == col / 2) //print 1 in center of first row
        arr[i] = 1;     
        else
        arr[i] = 0;
        printf("%d", arr[i]);
    }
    else{
        //output[i] = arr[i-1];
        output[i+1] = arr[i];
        output[i+2] = arr[i+1];
        output[i+3] = arr[i+2];
        printf("%s", output);
    }
    }//end inner for_loop
   printf("\n");
}//end outer for_loop

* *} Тысяча двадцать-один

Хорошо, я сделал это намного проще, и у меня будет два массива (один содержит предыдущий столбец, а другой - текущий). Я не понимаю, почему печать выходного массива приводит к появлению мусора? Является ли output [i] = arr [i] недопустимым выражением?

Answer 1

Вы не указали входы или выходы, которые могут повлиять на используемые структуры данных. Например, вам может потребоваться сохранить только две строки или даже одну строку, если вы распечатываете их по мере их вычисления. Похоже, вы планируете сохранить все строки в массиве.

Похоже, у вас логическая ошибка в начальной строке:

    if(firstTime == 1){
        if(j == row-1) //print 1 in center of first row
            arr[i][j] = 1;      
        else
            arr[i][j] = 0;
    }

должно быть

    if(i == 0){
        if(j == col / 2) //print 1 in center of first row
            arr[i][j] = 1;      
        else
            arr[i][j] = 0;
    }

или что-то еще проще.

Алгоритм генерации других строк не так уж и сложен.

1) построить число от 0 до 7, используя элементы строки выше.

2) Побит & 1 << (число из 1) с правилом для получения результата </p>

parent = 0;
if(j>0 && arr[i-1][j-1]) parent = 4;
if(arr[i-1][j]) parent += 2;
if(j<col-1 && arr[i-1][j+1]) parent += 1;

position = 1 << parent;
arr[i][j] = (rule & position)?1:0;

Есть несколько очевидных способов сделать это быстрее. Например, создайте родительский элемент для этого столбца на основе родительского элемента предыдущего столбца и ячейки справа вверху: & с 3, сдвиг влево, | с содержимым клетки. Единственная неприятная часть - это обработка первого и последнего столбцов отдельно.

РЕДАКТИРОВАТЬ В ОТВЕТ НА КОММЕНТАРИЙ:

Алгоритм имеет несколько естественных реализаций в целых числах с битовыми операциями, отсюда и идея «правила XX».

В своей основе выбор текущего пространства определяется тремя пробелами над ним. Есть 8 возможностей для этого. Мы можем думать о них как о 8 битах байта.

Каждое правило - это соответствие из набора из 8 возможностей множеству {0,1}. Есть 2 ^ 8 = 256 возможных соответствий или правил, которые совпадают с количеством возможных значений для байта.

Наиболее удобный способ обозначить правила - это число, показывающее, как именно должна заполняться текущая ячейка, как это определено родительскими ячейками. Например,

правило 30:

30 = 16 + 8 + 4 + 2 = 2 ^ 4 + 2 ^ 3 + 2 ^ 2 + 2 ^ 1

Таким образом, правило заключается в том, чтобы заполнить ячейку, если родительские ячейки:

4 = 100
3 = 011
2 = 010
1 = 001

Для другого примера, каково правило, которое просто копирует предыдущую строку?

В этом случае мы заполняем ячейку, если указанная выше ячейка заполнена, но соседние ячейки могут быть любыми:

010 = 2
011 = 3
110 = 6
111 = 7

Итак, это правило 2 ^ 2 + 2 ^ 3 + 2 ^ 6 + 2 ^ 7 = правило 4 + 8 + 64 + 128 = правило 204.

Надеюсь, алгоритм определения ячейки теперь имеет больше смысла.

1) определить номер шаблона родителей.

2) определить, является ли шаблон 2 ^ частью правила. Если это так, заполните ячейку.

Другой комментарий, который у меня был, это то, сколько вам нужно хранить. Если вы выводите данные по ходу работы, вам нужна только одна строка массива (то есть только одно измерение). Когда вы пересекаете строку, вы можете заменить записи значениями для следующей строки. Единственная трудность заключается в том, что вам нужно каким-то образом сохранить текущее значение, которое вы заменяете, чтобы использовать его при определении следующей ячейки.

Но вы можете сохранить это значение и уменьшить количество вычислений тем же приемом: оставьте последний родительский номер; & это с 3, чтобы удалить левого родителя; сдвиньте его влево на 1; | это с родителем справа. Это дает вам текущий родительский номер. Будьте внимательны, чтобы правильно обработать конечные записи массива, и все готово.

ДРУГОЕ РЕДАКТИРОВАНИЕ:

Сначала реализуйте предыдущую версию, но если вы действительно хотите сходить с ума от экономии места и еще больше напрячь свой разум, попробуйте сохранить строку в виде битовых значений целого числа вместо массива 1 и 0. Если вы хотите, чтобы строка была даже длиннее, чем число битов в long, тогда вам нужен массив целых чисел, содержащих биты, и некоторая сумасшедшая битовая манипуляция для обработки ячеек на границе двух таких целых чисел. Веселись!