Subj : Re: Compiler and an interpreter
To   : comp.programming
From : Jon Harrop
Date : Sat Aug 06 2005 07:38 pm

Gerry Quinn wrote:
> In article <42f4aec0$0$24005$ed2619ec@ptn-nntp-reader01.plus.net>,
> usenet@jdh30.plus.com says...
>> Gerry Quinn wrote:
>> How would you have coded the "nth" example differently in order to
>> "looking at the data structure with efficiency in mind"?
> 
> Can you define the problem?  I understand a periodic graph to be
> something like the unit cell of a crystal, but I don't see references
> to positions or distances anywhere in your code.

You have an infinite crystal with a cubic unit cell. Each atom is uniquely
identified by the int * int * int index of its cell and the int index
within the unit cell.

Given the sets of nearest neighbours for each atom in the unit cell, you
must write a function to compute the set of "n"th-nearest neighbours from
the "i"th atom in the unit cell at the origin. The nearest neighbours are
defined as int * int * int offset to the cell of the neighbour and the int
index of the neighbour within that cell.

The set of "n"th-nearest neighbours is defined as:

nth(i, 0) = {i}
nth(i, 1) = neighbours(i)
nth(i, n) = union(j in nth(i,n-1), nth(i, 1)) - nth(i, n-1) - nth(i, n-2)

where neighbours(i) gives the set of neighbours of "i".

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.