Intel® Software Network

Hi everyone,  

   Welcome to the discussion forum for the GAME OF LIFE problem set.  Use this forum to ask clarifying questions from the contest organizers as well as to discuss the problem set with your peers.   We'll also be posting the winning solution in this forum.

Good luck!

 

I think that the main question here is the same as for the first problem: how much can we change the provided implementation? Is it legal to combine the proposed algorithm with some other techniques?

 

 

My guess is that the "algorithm" must be used as is.  Basically, TPTB say that there are two main algos for the problem: grid based and list based.  They want us to use the list based algo.  I imagine most everything else is up for grabs, except those bits of code that effect the output.

I noticed that they did not request timing data to be output this time ... sounds like a good job for a testing switch :-)

When is the deadline?

I suppose it's the same as always, which is 12 midnight (PST) on the 20'th day of the month.

Yes, the deadline is the same -- the 20th of January (midnight,  U.S. Pacific Time).   We've added this detail to the problem set description -- thanks for the reminder.

petert@dcn.nord.nw.ru:

I think that the main question here is the same as for the first problem: how much can we change the provided implementation? Is it legal to combine the proposed algorithm with some other techniques?

As with the first problem, the implementation language can be changed.  We've had entries in C, C++, C#, MC#, Java, and Delphi, so far.  The basic algorithm must remain the same.  That is the for-loop over the generations and the four functions that deal with the lists.  The implementation of the lists and how those are traversed (through the four access functions) can be modified as needed, the implementation of the Grid type can be modified as needed, and other changes for optimizations and threading are allowed.  The basic algorithms of the four functions handling the computations of the list traversals must still be there since these are the core of the list-based version.  (Good documentation will be helpful to point out the features from the provided code and how you implemented it.)

Unlike quicksort, I don't think that there any cutoff points that can be made with a different sorting algorithm, though. 

--clay 

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

Hey Clay,

After reading the code restrictions and your above comments; I've come to the following conclusions:

1. We must use:

• The Algorighm in the main program
• The Four Routines used to traverse the lists

2.  The Algorithm refers to:
while (gencount < gens) {
  gencount++;
  TraverseList(&maylive, Vivify);
  TraverseList(&maydie, Kill);
  ClearList(&maylive);
  ClearList(&maydie);
  TraverseList(&newlive, AddNeighbors);
  TraverseList(&newdie, SubtractNeighbors);
  ClearList(&newlive);
  ClearList(&newdie);
}

2. The Four Routines refer to:

• Vivify
• Kill
• AddNeighbors
• SubtractNeighbors

3. How The Four Routines are implemented can be changed, i.e. the function definitions; but we can't alter the function declarations. E.g.:
void AddNeighbors(Cell); //DONT Alter

void AddNeighbors(Cell)
{
  //Custom code
}

Problem Description:

The algorithm in the main program, as well as the four routines that are used to traverse the lists, must be used.

ClayB:

The basic algorithm must remain the same. That is the for-loop over the generations and the four functions that deal with the lists.

ClayB:

The implementation of the lists and how those are traversed (through the four access functions) can be modified as needed

ClayB:

The basic algorithms of the four functions handling the computations of the list traversals must still be there

Yes, those are the four routines of interest.  If you wanted to combine the traversal, the processing, and the clearing of the lists into a single routine (rather than three separate routines), that would be an acceptable change.  The declarations can be changed as needed.  For example, if you used the combination described above, you might pass the list structure as the parameter rather than a single cell structure.

What can't be changed is the processing done.  That is, for each item on the list, update the appropriate neighbor counts or modify the contents of the grid cells.  You can unroll the nested loops and do the processing "by hand," you can execute loops in the reverse order by decrementing the loop iterator, you can use if-then-else instead of a switch/case, or you can break up computations and assign them to threads.

I'm trying to not give advice or hints or be too restrictive on how you might choose to implement your solution, but the details of your choices for data structures, threading scheme, implementation language, and personal preferences will drive the required modifications from the example code given.

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

mad\cpbreshe:

you can use if-then-else instead of a switch/case, or you can break up computations and assign them to threads.

--clay

Can we remove Error call from a switch/case to condition compilation comment? When Debug is on it will be enabled, for final version it will be disabled. If yes, "if-then-else instead" looks interesting.

mt2:

Can we remove Error call from a switch/case to condition compilation comment?

Yes.  This was a code I'd done some years ago and I was trying to be real obvious with things that can be understood by a wide audience in a short time.  If you've got a simpler and better way to do the same things, there should be no problem.

--clay 

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

Hi Clay,

I assume that there's no problem with moving the various functions into class.

As I understand it, the main restriction is we need to use a list-based implementation. Also, it should more or less be similar to what was presented to us, i.e. traverse a list to take care of newly created cells, and newly dead cells.

Have I got that right?

That's right. 

As always, documentation pointing out what code/class/method was derived from what original function would not hurt.

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

Also, can we use blockRead etc. to optimize I/O?