asterix asterix - 28 days ago 7
C Question

simulation algorithm implementation in C/C++

Let a row of 8000 lamps. Initially, only the one located to the left is lit.
Then, every second, the following operation is performed: each lamp changes state (on or off) if the one on its left was lit a second before. The leftmost lamp stays on all the time. This operation is instantaneous.
The process stops when the lamp at the right end lights for the first time.
How many lights are on?

My following implementation of the problem is false, can you help me?

#include <cstdio>

int t[8001][2];

int main()
{
t[1][0] = 1;
t[1][1] = 1;
int cpt1 = 0, ip = 0;
while (t[8000][0] != 1 && t[8000][1] != 1)
{
ip++;
for (int j=2;j<8001;j++)
{
if(t[j-1][!(ip&1)])
t[j][(ip & 1)] = !t[j][!(ip & 1)];
}
}

for(int j = 1;j < 8001; j++)
cpt1 += t[j][1];

printf("cpt=%d\n", cpt1);
}

Answer Source

Code is missing an update when the left does not change.

Code simplified (zero based offset, use of bool) and corrected below

#include<stdbool.h>
#include<stdio.h>
#define N 8000

bool t[N][2];

int main(void) {
  t[0][0] = true;
  t[0][1] = true;
  int ip = 0;

  while (t[N - 1][0] == 0 && t[N - 1][1] == 0) {
    ip = !ip;
    for (int j = 1; j < N; j++) {
      if (t[j - 1][!ip]) {
        t[j][ip] = !t[j][!ip];
      } else {
        t[j][ip] = t[j][!ip];  // add
      }
    }
  }

  int cpt1 = 0;
  for (int j = 0; j < N; j++) {
    cpt1 += t[j][1];
  }
  printf("N=%d cpt=%d\n", N, cpt1);
  return 0;
}

Output

N=8000 cpt=2048