Sorting with cellular automata

[Insectoid]

I've been poking around with cellular automata (CA) a bit lately and figured I'd try designing a sorting algorithm. Apparently they exist, but there's very little information on Google about them so I had to come up with a solution myself. I'm having an issue with it, but I'm sure it's a problem with my implementation, not my algorithm.

My algorithm is based on a 1-dimensional CA. Every cell has a value (the value to sort by) and an action. There are two phases per tick of the simulation- an action phase, where all cells choose an action, and a value phase, where each cell takes a new value based on its action and the actions of its neighbors. There are 4 actions: Move left, move right, stay, and wall. Walls interact with nothing and always select the wall action. They simply wall off the CA so cells can't spill out beyond the bounds.

The move actions (left and right) aren't really moves. A cell with the move left action will take on the value of its left neighbor. A cell with the move right action will take on the value of its right neighbor. However, they will only do this if the corresponding neighbor has the opposite action. Given cells A and B where A wants to move right and B wants to move left, both will complete the action (so B will have A's old value and A will have B's old value). This implements a swap. If A wants to move right and B wants to move right or stay or wall, then A will do nothing.

The stay action is a 'do-nothing' action. Unlike a wall, it can change to another action later on in the simulation.

Cells select an action based on their immediate neighbors. If the right neighbor is less than the current cell (for an ascending sort), it will select the move right action. Otherwise, if the left neighbor is greater, it will select the move left action. Note that cells prefer to move right if able. If it is sorted (left is less, right is greater) it will select the stay action. A wall will always select the wall action.

The list is sorted when all cells select wall or stay.

As far as I can tell, this should work (and my implementation does work, most of the time). Here is my implentation:

c:

#include <stdio.h> #include <time.h> #include <stdlib.h> #define RIGHT x+1 #define LEFT x-1 typedef struct _Cell {         int value;         int action; } Cell; int chooseAction (int x, Cell* array); int applyAction (int x, Cell* array); void printArray (Cell array[11]); void printArray2 (int activeArray, Cell array[2][11]); //actions: 0 = wall, 1 = stay, 2 = right, 3 = left int main (){ /* initialization */         srand (time(NULL));         Cell array[2][11];         //init array         array[0][0].value = 0;         array[0][0].action = 0;         array[0][10].value = 0;         array[0][10].action = 0;                 int activeArray = 0;         for (int x = 1; x < 10; x++) {                 array[0][x].value = x;                 array[0][x].action = 1;         }         //printArray2 (0, array);                 //shuffle initial array         for (int x = 1; x < 9; x++) { //does not move 1st or last values, because they are walls.                 int s = x;                 while (s == x) s = rand()%9+1;                 array[0][x].value ^= array[0][s].value;                 array[0][s].value ^= array[0][x].value;                 array[0][x].value ^= array[0][s].value;         }         //printArray (array[0]); /* actual program */         int count = 0;         bool finished = false;         int inactiveArray = activeArray * -1 + 1;         while (!finished) {                 finished = true;                                 //all cells choose an action                 for (int x = 0; x < 11; x++){                         //printf ("%d %d %d\n", x, array[activeArray][x].action, chooseAction (x, array[activeArray]));                         array[activeArray][x].action = chooseAction (x, array[activeArray]);                         if (array[activeArray][x].action > 1) finished = false;                 }                 printArray2 (activeArray, array);                 //Apply actions to inactive array                 for (int x = 0; x < 11; x++){ //all cells apply an action                         array[inactiveArray][x].value = applyAction (x, array[activeArray]);                 }                                 //swap active & inactive arrays                 activeArray = activeArray * -1 + 1;                 inactiveArray = activeArray * -1 + 1;                 //printArray (array[activeArray]);                         } } int chooseAction (int x, Cell* array) {         //if (x == 0) printf ("%d %d\n", array[x].value, array[x].action);         if (array[x].action == 0) return 0; //cell is a wall.         if (array[RIGHT].action != 0 && array[RIGHT].value < array[x].value) return 2; // move right         if (array[LEFT].action != 0 && array[LEFT].value > array[x].value) return 3; //move left         return 1; //stay } //Applies the value determined by the action of a cell in activeArray to the corresponding index in inactiveArray. int applyAction (int x, Cell* array) {         if (array[x].action <= 1) return array[x].value; //if cell is a wall or action is stay, no change.         if (array[x].action == 2){                 if (array[RIGHT].action == 3) return array[RIGHT].value; //swap to the right                 else return array[x].value; //no change         }         if (array[x].action == 3) {                 if (array[LEFT].action == 2) return array[LEFT].value; //swap to the left                 else return array[x].value; //no change         }         return array[x].value; } void printArray (Cell array[11]){         for (int x = 0; x < 11; x++){                 printf ("%d ", array[x].value);         }         printf ("\n"); } void printArray2 (int activeArray, Cell array[2][11]){         for (int x = 0; x < 11; x++){         //      if (array[activeArray][x].action == 3) printf ("-");                 printf ("%d%d ", array[activeArray][x].value, array[activeArray][x].action);         //      if (array[activeArray][x].action == 2) printf ("- ");         //      else printf (" ");         }         printf ("\n"); }

It still has a few debugging prints in it. I think I've commented them all out though.

The output of this is several lines of integers. Each line is one tick of the program (so every line should be more sorted). The integers each represent a cell. The first digit is that cell's value (between 0 and 9 inclusive) and the 2nd is the action that cell selected on that tick (0 = wall, 1 = stay, 2 = right, 3 = left). I said that walls should always be walls, and they should be, but the leftmost wall alternates between 0 (wall) and 1 (stay). This should never happen. The rightmost wall behaves correctly on my Mac, but on Windows it alternates between 0 and 2 (right). On mac, non-wall cells sometimes take on a wall action, which breaks the sort (other cells cannot move past them) so it quits before the list is sorted. This doesn't seem to happen on Windows (as far as I can tell, it actually sorts correctly on Windows every time, but it still doesn't work as expected). Even more interesting, on mac, the leftmost wall selects 32767 as its first action before alternating between 0 and 1. Nothing should ever select 32767, ever. That's not even a valid action code. Note that 32767 is the maximum 4-byte integer. I'm not sure if that's just random RAM it's picking up or if it's coming up with that value somehow.

Anyway, I'm guessing I'm trying to access array indices beyond the legal bounds somewhere or otherwise leaking memory, but I can't figure out where. The walls are initially assigned an action of 0 (wall) and everything else gets 1 (stay). Actions are assigned on the following line in the main function:

code:

array[activeArray][x].action = chooseAction(x, array[activeArray]);

The very first line in the chooseAction function checks if the cell is a wall, and if so, it assigns it the wall action code. This is the only place the wall action is ever assigned. No other cell should ever be assigned a wall action. Actions are never swapped, only values. The cross-platform behaviorial differences are very strange, but could be related to one machine being 32 bits vs 64 on the other (I think gcc is compiling to 32 bit on my mac, which sort of explains why it's giving maxint to the left wall on the first tick).

Anyway, can anyone figure out what the hell is going on here?

[DemonWasp]

I think your big problem is that you aren't initializing the 'action' field in your secondary array, meaning it's full of garbage (probably not actually random garbage either, but definitely different from machine to machine). If you make sure that's set to 0 for both end values and 1 otherwise, I think your program works fine (at least, it did on the one machine I tried it on).

If not, try using this as your formatting function:

c:

for ( int x = 0; x < 11; ++x ) {     printf ( "%1d ", array[activeArray][x].value ); } printf ( "\n" ); for ( int x = 0; x < 11; ++x ) {     printf ( "%c ", "|-><"[array[activeArray][x].action] ); } printf ( "\n" );

That should show the array values on one line with their next action beneath them.

[Insectoid]

Ah, that definitely is the cause of the maxint printout, but it shouldn't affect the actual logic since the actions are never queried until they are set. That doesn't explain why it fails on osx about 20% of the time, unless GCC is reordering instructions or something.

[DemonWasp]

Actually, the actions in array[1] are queried before being set. On the second iteration of your main loop, you assign array[1][x].action based on the current value of array[1][x].action , on the first line of chooseAction().

You might also access array[1][x-1].action if the first condition isn't met, which is probably bad news if you are at index 0. Similarly you could access past the end of the array.

Also, while 32767 is a maximum signed integer value, it's the maximum for a 2-byte integer. I would have assumed that this code was compiling with 4-byte integers (you can tell by querying sizeof(int)).

[Insectoid]

Aha, yeah, I realized this last night. Dunno how I missed it. It's always the most obvious bugs that are hardest to find.