Comparing Two Arrays

ßHow would I compare the entirety of two arrays? ie Check if all the elements of array A are the same as array B?

Thanks, Cam

easiest way is to first compare their length, if not equal, then arrays are not equivalent, otherwise you should run through the elements of both arrays comparing one with each other. a simple (extremely simple) function to compare int arrays would be like this:

boolean array_cmp(int *a, int *b, int len_a, int len_b){
      int n;

      // if their lengths are different, return false
      if (len_a != len_b) return false;

      // test each element to be the same. if not, return false
      for (n=0;n<len_a;n++) if (a[n]!=b[n]) return false;

      //ok, if we have not returned yet, they are equal :)
      return true;
}

where:
a = first array
b = second array
len_a = number of elements (length) of array a
len_b = number of elements (length) of array b

the function itself will return ‘true’ if the arrays are the same, false otherwise
Then a sample usage would be as follow:

      int arr_a[] = {1, 4, 7, 1, 3};
      int arr_b[] = {1, 4, 7, 2, 3};

      if (array_cmp(arr_a, arr_b, 5, 5) == true){
            // do this if they are equal
      }else{
            // do this if they are different
      }

Exactly what I was looking for. Thanks for the quick reply!

I'm interested in the same thing (so I can tell when the "game of life" has reached a static pattern)

Is there any way of doing this without looping through the arrays? Like using 'memcmp' or something?

Even if there were such a function, internally it would be looping through the arrays. As far as the game of life goes, instead of comparing arrays, which seems inefficient both memory-wise and computationally, can't you clear a flag at the start of every update cycle and then set the flag if the cycle results in a change (i.e. when you're applying the rules and end up adding a cell or removing a cell, set the flag). At the end of the cycle, if the flag is still cleared, your system has reached a static pattern.

  • Ben

Unfortunately, the game of life often enters a 2-state static phase, where there are 2 'images' alternating after each turn. That's why I guess the flag trick won't work.

You might be able to get away with using a checksum-type value to identify static or repeating patterns. Use the current state of the cells to generate maybe a four-byte value (long) that represents the current state of the system. Then compare this value to the values for previous states to see if it is repeating. Note that with this technique, two different states might result in the same checksum, which could fool you into thinking you might have reached a static/repeating state when you haven't. To test for this, you would want to make sure that the checksum pattern repeats the same exact way multiple times.

From a programming perspective, this approach would be less intuitive and more complicated than just comparing the arrays, but from a performance perspective it would be much more efficient in terms of both speed and memory, and it would let you look for repeating patterns that have cycles longer than 2.

  • Ben

(Sorry this thread got started here - almost didn't want to add to it. but . . .)

Ben, thanks for your input. That's what I wound up doing and it works fine. Handi, you are right, but I am happy enough just catching the "blocks" and "beehives" and leaving the "propellers" etc. to go to the max. generations. At least something is moving.

I also considered assigning some type of value to each generation, and might try that in the future. Re memcmp: Just for the record, there is such a function. I would think it's much more optimized than a for loop, but still not as good as simply setting a flag.

Re memcmp: Just for the record, there is such a function. I would think it's much more optimized than a for loop, but still not as good as simply setting a flag.

Good to know. I'd be interested in seeing the assembly for memcmp vs a for loop (but I'm probably too lazy to do it myself). Maybe there is some cool trick with the AVR instructions that can let it be more efficient.

  • Ben

Re memcmp: Just for the record, there is such a function. I would think it’s much more optimized than a for loop, but still not as good as simply setting a flag.

Good to know. I’d be interested in seeing the assembly for memcmp vs a for loop (but I’m probably too lazy to do it myself). Maybe there is some cool trick with the AVR instructions that can let it be more efficient.

  • Ben

FWIW, no cool trick. here is the assembly

;----- loop ------
  for(int i=0; i < 16; i++)
     if(array1[i] != array2[i])
 11a:      98 81             ld      r25, Y
 11c:      f8 01             movw      r30, r16
 11e:      80 81             ld      r24, Z
 120:      98 17             cp      r25, r24
 122:      31 f0             breq      .+12           ; 0x130 <loop+0x26>

        Serial.print("different");  <- assembly code for this call removed for clarity

 130:      21 96             adiw      r28, 0x01      ; 1
 132:      0f 5f             subi      r16, 0xFF      ; 255
 134:      1f 4f             sbci      r17, 0xFF      ; 255
 136:      f1 e0             ldi      r31, 0x01      ; 1
 138:      ce 31             cpi      r28, 0x1E      ; 30
 13a:      df 07             cpc      r29, r31
 13c:      71 f7             brne      .-36           ; 0x11a <loop+0x10>

;------ memcmp -----------        
  if(memcmp(array1,array2, 16) != 0)
 13e:      40 e1             ldi      r20, 0x10      ; 16
 140:      50 e0             ldi      r21, 0x00      ; 0
 142:      6e e1             ldi      r22, 0x1E      ; 30
 144:      71 e0             ldi      r23, 0x01      ; 1
 146:      ce 01             movw      r24, r28
 148:      40 97             sbiw      r24, 0x10      ; 16
 14a:      0e 94 15 05       call      0xa2a      ; 0xa2a <memcmp>
 14e:      89 2b             or      r24, r25
 150:      31 f0             breq      .+12           ; 0x15e <loop+0x54>

        Serial.print("different");  <- assembly code for this call removed for clarity

00000a2a <memcmp>:
 a2a:      fb 01             movw      r30, r22
 a2c:      dc 01             movw      r26, r24
 a2e:      04 c0             rjmp      .+8            ; 0xa38 <memcmp+0xe>
 a30:      8d 91             ld      r24, X+
 a32:      01 90             ld      r0, Z+
 a34:      80 19             sub      r24, r0
 a36:      21 f4             brne      .+8            ; 0xa40 <memcmp+0x16>
 a38:      41 50             subi      r20, 0x01      ; 1
 a3a:      50 40             sbci      r21, 0x00      ; 0
 a3c:      c8 f7             brcc      .-14           ; 0xa30 <memcmp+0x6>
 a3e:      88 1b             sub      r24, r24
 a40:      99 0b             sbc      r25, r25
 a42:      08 95             ret

Thanks mem!

hi, would you mind posting me your code for the solution to looping game of life, im going insane now. damn alternating patterns. thanks. jay