CODEWITHSUNDEEP
cimplementation
asterix
asterix

Reputation: 41

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);
}

Upvotes: 1

Views: 372

Answers (2)

user3629249
user3629249

Reputation: 16540

the following proposed code:

  1. cleanly compiles
  2. uses C header files rather than C++ header files
  3. performs the desired operation, but not the fastest possible algorithm
  4. is liberally commented

And now the proposed code:

#include <stdio.h>

int t1[8000];   // initially all zeros
int t2[8000];


int main( void )
{
    // setup initial conditions
    int numLitLights = 0;
    t1[0] = 1;


    // while stop condition not true
    while ( t1[7999] != 1 )
    {
        // make one pass through lamps
        // update values
        for (int j=0; j<7999; j++)
        {
            if( t1[j] )
            {
                t2[j+1] = ( t1[j+1] )? 0 : 1;
            }
        }

        // update original
        for( int j=0; j< 8000; j++ )
        {
            t1[j] = t2[j];
        }
    }

    // count lit lamps
    for(int j = 0; j < 8000; j++)
    {
       if( t1[j] )
       {
           numLitLights++;
       }
    }

    // output number of lit lamps
    printf( "number of lit lamps: %d\n", numLitLights );
} // end function: main

The result (number of lamps lit) is

1024

Upvotes: 2

chux
chux

Reputation: 153367

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

Upvotes: 3

Related Questions