## 17 replies

Last post Mar 09, 2012 02:12 PM by gerrylowry

Member

119 Points

110 Posts

### need solution to this problem in c#- help

hi all,

i came accross thisproblem from one web page, i have tried my best to resolve. i couldn't. i think i am lacking in the logic. can any one solve and tell me the logic with source code..

Problem is:

<div>Meeting Point (50 Points)</div> <div> </div>

There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house.
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
Find a common meeting place which minimises the sum of the travel times of all the persons.

Input Format:
N
The following N lines will contain two integers saying the x & y coordinate of the i-th person.

Output Format:
M M = min sum of all travel times;

Constraints:
N <= 10^5
The absolute value of each co-ordinate in the input will be atmost 109

HINT: Please use long long 64-bit integers;

```Input #00:
4
0 1
2 5
3 1
4 0

Output #00:
8

Explanation: Sums of travel times of the houses are 11, 13, 8 and 10. 8 is the minimum.
```
`Input #01:`
```6
12 -14
-3 3
-14 7
-14 -3
2 -12
-1 -6```
`Output #01:`
`54`
Ashokkumar

Contributor

2789 Points

1294 Posts

### Re: need solution to this problem in c#- help

It's basic math and basic looping.

It would be easier to understand if you drew a grid on a blank peice of paper with a pencil.

For the sake of comprehension, pretend the centermost cell is the closest to all random persons. Now randomly pick other cells and count  how many cells they're away from the center cell. Once you understand that, write the code for it.

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

is this a homework assignment:

#### ashok2009cse

can any one solve and tell me the logic with source code

probably mathematicians who specialize in graph theory could mentor you; you might have to write the code yourself

#### ashok2009cse

There is an infinite integer grid

it's unsolvable if it's infinite.

#### ashok2009cse

From any given cell, all 8 adjacent cells are reachable in 1 unit of time.

no, edge cells can reach fewer houses ... look at a chess board

N.B.:  let's use a chess board, home position, as an example,

rowas are 1 to 8; columns are a to h

let's say that both White bishops (c1 and f1) wish to meet with their count parts (c8 and f8) at d4

if your cells are squares of the same size, like the chessboard, then your problem is simple ...

however, since you do not know where the meeting will take place, in pseudo code, your logic would be something like this ...

(a) create an arrary (Int32, Int32) of n by m where n is the total number of cells (64), m are the number of participants

[0, 0] would be the distance for the c1 bishop to a1 (2);
[0, 1] would be the distance for the f1 bishop to a1 (5);
et cetera

b) you'd also need to store your path ... for c1 to a1, the path is c1==>b1==> a1

(c) NOTE:  a1 is the White Queen Rook's house ... you said someone's house so according to your problem definition, that someone might not be one of the people who wish to meet.

(d) your problem is simpler if the someone's house must be a home of one of the meeting participants ... for this restricted case, the distance for one participant will always be zero.  so you basically would compute the routes from everybody to everybody else ...

note:  in the case of the four bishops, any house will do because of the symmetry of their positions on the chessboard.

g.

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

graph theory shortest path algorithm

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Contributor

5024 Points

2404 Posts

### Re: need solution to this problem in c#- help

#### gerrylowry

it's unsolvable if it's infinite.

Not true. It's only unsolvable if N is infinite.

#### gerrylowry

no, edge cells can reach fewer houses ... look at a chess board

Again, not true. Because the grid is infinite, there are no edges. The chessboard doesn't help here at all.

For the OP, the exam questioner (or homework assigner, if you like) has made life easier for you, as you can trivially calculate the distance between any two homes as the larger of dX and dY (where dX is the difference in the X coordinates, and dY is the difference in the Y coordinates) due to the fact that the cost of moving diagonally is (artificially) the same as moving horizontally or vertically.

To calculate which is the optimal, simply

Set a variable (call it average distance) to 0.

Loop through all N participants.

For each, calculate the average (Mean, Median or Mode is up to you to think about) distance to all the other houses. If it's less than the variable above, remember it (and remember which house you're currently processing)

Now this is a brute force approach (if you like), so it is clearly inefficient as N tends to large numbers. But it doesn't require you to hold more than one house identifier and two distances in memory at any time, so it's very memory efficient. Unfortunately, gerrylowry's approach cannot work due to the infinite nature of  the grid.

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

@ DMW

#### DMW

gerrylowry "it's unsolvable if it's infinite."

Not true. It's only unsolvable if N is infinite.

the problem statement appears defective ...

the infinite grid may be a red herring.

The constraints are interesting.

N people constrained by N <= 10000 gives N == 0 | 1 | 2 | 3 | ... | 9998 | 9999 | 10000 since we can not have < 0 people.

N == 0 has no solution.

if we only meet at the home of a participant, N == 1 would meet in her/his own home, a distance of zero.a

OTOH, if the meeting home can be any home, given a infinity grid there is no solution ...

from cell c to cell c' is one unit,
from cell c to cell c'' is 2 units,
from cell c to cell c'" is 3 units,
from cell c to cell c'''' is 4 units,
from cell c to cell c''''' is 5 units,
from cell c to cell c'''''' is 6 units, ...

there will always be one cell further away from the previous cell in each of eight directions ...

... no solution     Q.E.D.

However, the O.P. stated a second constraint, no co-ordinate's absolute value > 10^9 ... imho, this is a bit of a silly constraint because the problem does not state the co-ordinate system to be used ... so let's invent one of our own:

x is the center of our Flatland-ish universe ...

```<=== oooo.ooooouooooo.oooo ===>
<=== ooooo.oooouoooo.ooooo ===>
<=== oooooo.ooouooo.oooooo ===>
<=== ooooooo.oouoo.ooooooo ===>
<=== oooooooo.ouo.oooooooo ===>
<=== ooooooooo.u.ooooooooo ===>
<=== llllllllllxrrrrrrrrrr ===>
<=== ooooooooo.d.ooooooooo ===>
<=== oooooooo.odo.oooooooo ===>
<=== ooooooo.oodoo.ooooooo ===>
<=== oooooo.ooodooo.oooooo ===>
<=== ooooo.oooodoooo.ooooo ===>
<=== oooo.ooooodooooo.oooo ===>```

from x we can move only in 8 directions (assuming our cells are uniform squares) ...

our directions are up, down, left, right, diagonally up left, diagonally up right, diagonally down left, and diagonally down right

this means that we can not always move in a straight line

so, our co-ordinate system much be a direction and a value

if x is at 0, 0, then we could have someone (harry) at 999 999 999 up

if x is at 0, 0, then we could have someone (mary) at 999 999 999 down

now, we have a problem ... (harry) and (mary) each meet the distance constraint (10^9) with x, but fail it with each other.

for simplicity, let's pretend that we have an edge corner, like a1 on the chessboard, and called it 0, 0 ... we can also have 0, 999 999 999 right and 0, 999 999 999 up ... the n,n diagonal would take us from 0, 0 to 999 999 999 diagonally up right, .... because we are measuring distance by cell count, 0, 0 to 999 999 999 up, 0, 0 to 999 999 999 diagonally up right, and 0, 0 to 999 999 999 right ALL seem to be the same distance, however, the diagonal (hypoteneuse) distance is larger (Pythagorous).

(again, keeping it less complex, every house would have to be in the centre of it's cell and every house would have to be the same size ... even that's a problem because the houses would have a front door, back door, and meybe one, even two side doors, but not likely also corner doors for people approaching diagonally).

back to the chessboard for a moment:  let''s move the white queen from d1 to a3;

d1, c1, b1, a1, a2, a3 == 5 cells away

d1, c2, b2, a3 == 3cells away

d1, c1, b1, a2, a3 == 4 cells away

of course, if we gave the queen a helicopter, she could fly directly to a3 but we'd have to add in the take off and landing distances because the queen's helicopter would not want to crash into other chess pieces on its way to a3.

i am not a mathemation .... however, it's reasonable to make some assumptions ...

(a) we will have 2 to 9999 houses distributed pseudo randomly in a 999 999 999 x 999 999 999 grid;

(b) we will not visit houses of strangers so we will ignore the houses on non-meeting participants

(c) our 999 999 999 x 999 999 999 grid is one of infinite 999 999 999 x 999 999 999 grids on our infinite super grid

(d) our problem is only solvable within the boundaries of any one or more 999 999 999 x 999 999 999 grids but if and only if we restrict the total number of grids to a finite number.

(e) the house(s) nearest the centre of the grid will not always be the ideal destination (back to the chessboard,  the black queen, if on d5 would have to travel towareds a1 if the other meeting participants were on a1, b1, and c2) ... occassionally, a home in the largest cluster of homes may turn out to be the best soulution.

(f) often, there will be multiple best solutions ... example, 4 participants, one each, at (0,0), (9,0), (0,9), and  (9,9).

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

@ DMW continuing my reply to you ...

#### DMW

Because the grid is infinite, there are no edges

(i) if the grid is infinite, there is no solution

(ii) f the grid is finite, there are edges

(iii) unlike folding our universe*, our grid is and will remain Flatland-ish for this problem

example:  http://astronomy.nmsu.edu/geas/lectures/lecture28/slide02.html
"Does the Universe have an Edge?"

i am not a methematician ... so  DMW, either there are no edges in our infinite grid or there are infinite edges ...

likely you are correct when you state "Because the grid is infinite, there are no edges".

g.

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Contributor

5024 Points

2404 Posts

### Re: need solution to this problem in c#- help

#### gerrylowry

the problem statement appears defective ...

the infinite grid may be a red herring.

gerry

Have you actually read the problem definition. It is really clear and really precise, and it is definitely solvable.

If you read the problem, you realise that

1. The universe is defined as a square grid of square cells. There is no need to try to invent a coordinate system, as one is defined.

2. Pythag doesn't apply. It VERY CLEARLY states that moving diagonally is IDENTICAL IN COST to moving horizontally or vertically. This means that the "distance" of moving from (0,0) to (5,5) is IDENTICAL to moving from (0,0) to (0,5) or (0,0) to (5,0).

3. The ABSOLUTE VALUE of a coordinate is 10^9 (or possibly 109, but I don't think so). There is no constraint as to the distance between houses.

4. The infinite distance that you refer to abve clearly doesn't apply, and there will be a definite solution, because you only need to work out the distance between the houses for the N people. The problem statement does NOT state that there is a house in every cell of the grid, so there is no need to calculate assuming that there is.

5. Introducing physical world concepts of front and back doors to houses is daft. It is clear from the problem statement that there is no orientation to the house, and that entering it from any direction is allowed, otherwise it would have been stated.

I really don't think that you're helping the OP by applying your own artificial constraints to a fairly well known and common algorithmic homework problem, albeit that the problem has absolutely nothing to do with ASP.NET(!). By announcing (incorrectly) that the problem statement is unsolvable or incorrect makes it much harder for the OP to tackle the problem and therefore complete their homework, as you're probably making them more, rather than less, confused.

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

@ DMW concluding my reply to you ...

Dave, your brute force method for the O.P. is an over simplification ... it fails when the pseudo random distribution offers multiple solutions, such as my example wthere there will be multiple best solutions ... example, 4 participants, one each, at (0,0)(9,0)(0,9)and  (9,9)

Likewise, 12 participants, one each, at ((0,0)(0,1)(1,0)), ((9,0), (9,1), (8,0)), ((1,9), (0,8)(0,9))and ((9,8), (8,9)(9,9)).

```9 ##......##
8 #........#
7 ..........
6 ..........
5 ..........
4 ..........
3 ..........
2 ..........
1 #........#
0 ##......##

0123456789```

g.

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

@ DMW

Hi Dave ... yes, i have read the problem definition many times from which i have concluded that the problem definition is defective because it allows for assumptions.

1. (a) the universe is definition by the O.P. as "an infinite integer grid".

(b) a co-ordinate system is not defined, only hinted at:

"The absolute value of each co-ordinate in the input will be at most 10^9"
{the O.P.'s choice of font size looks like 10_subscript 9;
i'm guessing the O.P. intended 10_superscript 9 ???}

2. Pythagoras could apply, i was giving Pythagorous as an example at to what i perceive as a flaw ...

```"eg: (x,y) can be reached from (x-1,y+1) in a single unit of time."
3,6                        2 , 7

9 ..........
8 ..........
7 ..o.......
6 ...o......
5 ..........
4 ..........
3 ..........
2 ..........
1 ..........
0 ..........

0123456789```

3. the problem definition, by constraining the ABSOLUTE VALUE of a coordinate is ipso facto constraining the distance.

4. one only needs "to work out the distance between the houses for the N people" BUT N can be 0 to 10000 houses ... i've made no assumption that every cell has a house (although every cell could have a house); from the set of ALL houses, at any given time, we will never select more that 10000 and those houses must be selected from houses within the implied distance constraint.

(we also are assuming varible speed because the problem definition speaks about uniform units of time rather that distance; thus moving diagonally from corner to corner takes the same time even though the Pythagorean distance is greater on the diagonal).

5. "daft" ??? ... maybe ... Dave, please note that this was introduced only to demonstate the weakness of the problem definition ... the problem definer imho should have left out houses and used something like "cell surface" instead.

----

Dave, the O.P.'s problem is looking for a c# solution and could be related to ASP.NET (albeit a stretch) if one is creating a web page to solve such problems.

As a former college teacher, and also as a tutor to university and college students, imho, when a problem is poorly defined, as this one is, the student needs to query the problem definer in order to have a clear problem statement

that may be difficult for the O.P. because the problem was simply found on some web page somewhere on the internet.

N.B.:  imho, the problem, as stated by the O.P., is unsolvable.

-----

thnx/gerry

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Contributor

5024 Points

2404 Posts

### Re: need solution to this problem in c#- help

#### gerrylowry

N.B.:  imho, the problem, as stated by the O.P., is unsolvable.

gerry

Why do you think that?

You know the coordinate of every "house".

(I know you don't believe there's a coordinate system, but everyone else will see it as a 2D grid, as confirmed by the sample input data.)

Therefore you can work out the distance or time (they're the same, in effect, as true distance doesn't matter) between every "house", just by looking at the larger value of deltaX or deltaY. I mean, forgive me if I'm wrong, but the input is just an array of X,Y coordinates up to 10000 in length. (Although I grant you that they don't specify that N > 0).

Therefore, for each house you can sum the times, given that N is not infinite, and that no coordinate can be infinite.

Therefore you can work out which of these is the lowest. Sure, there might be more than one that has the same value, but that doesn't matter; you can choose any of them.

Therefore the problem is eminently solvable.

I'm not sure why you talk about selecting houses and implied distance constraints. You never select a house - all the house information is clearly provided to you - and there is no implied distance constraint, merely an absolute constraint on what the coordinate values of X and Y will be for each of the N houses.

The trivial solution is just

struct House
{
public long X;
public long Y;
}

and given a read-in input translated to some House[]

House[] houses = // read in from input ;
long minTime = long.MaxValue;

for( int i = 0; i <  houses.Length; i++ )
{

long time = 0L;
for( int j = 0; j < houses.Length; j++ )
{

time += Math.Max( Math.Abs( houses[i].Y - houses[j].Y ), Math.Abs( houses[i].X - houses[j].X ) );
}

if( time < minTime )
minTime = time;

I don't really see what's so difficult in that (and no, I've invested nothing in making the algorithm efficient)!

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

Dave, the reason i think that the problem as stated is not solvable, is because of the stated "infinite" grid.

the problem should not imho mentioned the infinite grid because there is no reference point for any give grid slice.

N.B.:  if we choose a rectangle or square of cells within the grid, we can work with that slice.

The O.P. wrote:  "From any given cell, all 8 adjacent cells are reachable in 1 unit of time." BUT when we choose a grid slice, FWIW, we do introduce edges and corners.   corners have only three adjacent cells and non-corner edges have only five adject cells.

```a =. adjacent cell
c =. corner cell
e =. edge cell (non-corner)
x =. non-corner and non-edge cell

9 ..........
8 ......aaa.
7 ......axa.
6 aa....aaa.
5 ea........
4 aa........
3 ..........
2 ..........
1 aa........
0 ca.........

0123456789```

Dave, you wrote:  "there might be more than one that has the same value, but that doesn't matter; you can choose any of them."

Then, imho, the problem should state that any of the shortest solutions is acceptable.

of course, if Dave's house is one of any acceptable solution's, then an algoritm that spits out "Dave's house" will likely always spit out "Dave's house".

Have you tried your solution on this 10 x 10 example?:

Likewise, 12 participants, one each, at ((0,0)(0,1)(1,0)), ((9,0), (9,1), (8,0)), ((1,9), (0,8)(0,9))and ((9,8), (8,9)(9,9)).

```9 ##......##
8 #........#
7 ..........
6 ..........
5 ..........
4 ..........
3 ..........
2 ..........
1 #........#
0 ##......##
0123456789```

g.

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Contributor

5024 Points

2404 Posts

### Re: need solution to this problem in c#- help

#### gerrylowry

Then, imho, the problem should state that any of the shortest solutions is acceptable.

It does, very clearly. It states " find A common meeting place". Not THE common meeting place. A common meeting place.

#### gerrylowry

imho mentioned the infinite grid

It has to, to stop people doing daft things like attempting to allocate 2D arrays, and to stop them thinking about edges. I don't quite understand why you keep talking about edges and corners, because they are completely irrelevant to the problem (and they don't exist, of course, in an infinite grid).

What possible reason is there for looking at a slice? It can't help you in any way solve the problem, which is about finding shortest distances/times (pythag excepted) between cells.

#### gerrylowry

Have you tried your solution on this 10 x 10 example

Yes. The desired output answer, M, is 77. You can choose any one of EIGHT possible houses - not one of the four at 0,0  9,0, 0,9, 9,9. Which of the other eight doesn't matter, as the questioner merely wants A house that minimises the sum of the journey times.

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Contributor

5024 Points

2404 Posts

### Re: need solution to this problem in c#- help

One further thought, and I implied this earlier in an earlier post.

I don't consider my approach to be efficient. It is, I guess, O(n^2) in nature. Now if I was offering 50 marks for a question, then unless the marking system is pretty nuts I'd expect to be looking for another algorithm that is far more efficient than my brute force approach.

But that's why it's an exam question!

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

@ DMW

#### DMW

The desired output answer, M, is 77.

Dave, this is the question to be answer (see the O.P.):

Find a common meeting place which minimises the sum of the travel times of all the persons.

You have not shown the "common meeting place"

```9 ##......##
8 #........#
7 .......... <== no houses here
6 .......... <== no houses here
5 .......... <== no houses here
4 .......... <== no houses here
3 .......... <== no houses here
2 .......... <== no houses here
1 #........#
0 ##......##
0123456789```

12 participants, one each, at ((0,0)(0,1)(1,0)), ((9,0), (9,1), (8,0)), ((1,9), (0,8)(0,9))and ((9,8), (8,9)(9,9)).

g.

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Contributor

5024 Points

2404 Posts

### Re: need solution to this problem in c#- help

gerry

I will quote it for you

"Output Format:
M M = min sum of all travel times;"

M is 77. This is exactly what was asked, and this is confirmed PRECISELY by the sample data.

And please, please read my post. I stated EXTREMELY CLEARLY  that you can use ANY of the EIGHT, non-"corner" houses if you wish to define A COMMON MEETING PLACE as well. Pick one. IT DOESN"T MATTER WHICH! THEY ALL YIELD THE VALUE OF M at 77.

Why are you deliberately trying to make this difficult? I have provided a solution to the OP, and you are trying to obfuscate it. Why?

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Star

12990 Points

5547 Posts

### Re: need solution to this problem in c#- help

@ DMW,

Dave, i'm amazed that you think that i'm "deliberately trying to make this difficult".  Can you not admit that the problem is very poorly stated?

So, i'm not trying to obfuscate ... i'm doing what you, i, and our peers would do, i.e., i'm seeking clarification of what i as a professional programmer since 1967 perceive as a very muddy problem specification.  as a former community college teacher, i had to prepare examination questions ... not in a million years would i have made such a imho poorly worded question. For example, the part about an infinite grid which can imho be iinterpreted as an accidental or deliberate red herring, i do not know whether i'd put that in.  FWIW, to your credit, using your solution, after much thought, i see where that point may be relevant (it eliminates giving much thought to edge conditions),

i'm still troubled with "Find a common meeting place which minimises the sum of the travel times of all the persons."

i've been experimenting with your solution and modified it slightly (using LINQPad 4*).

N.B.:  this solution improperly ignores the condition of < 2 houses.

```void Main()
{   House[] houses;
houses = new House[12];
//              (0,0), (0,1), (1,0)
houses[ 0].X=0; houses[ 0].Y=0;
houses[ 1].X=0; houses[ 1].Y=1;
houses[ 2].X=1; houses[ 2].Y=0;
//              (9,0), (9,1), (8,0)
houses[ 3].X=9; houses[ 3].Y=0;
houses[ 4].X=9; houses[ 4].Y=1;
houses[ 5].X=8; houses[ 5].Y=0;
//              (1,9), (0,8), (0,9)
houses[ 6].X=1; houses[ 6].Y=9;
houses[ 7].X=0; houses[ 7].Y=8;
houses[ 8].X=0; houses[ 8].Y=9;
//              (9,8), (8,9), (9,9)
houses[ 9].X=9; houses[ 9].Y=8;
houses[10].X=8; houses[10].Y=9;
houses[11].X=9; houses[11].Y=9;
//  foreach (House house in houses) house.Dump();
long minTime = getResult(houses);
Console.WriteLine ("minimum cumulative travel time == {0} units", minTime);
}
public struct House { public long X; public long Y; public long computedTime; }

public long getResult(House[] houses)
{
long minTime = long.MaxValue;
long time;
Int32 housesToCheck = houses.Length;
// checking ALL the houses ... it would be better if would check just the first half
for( int i = 0; i <  housesToCheck; i++ )
{  time = 0L;
for( int j = 0; j < houses.Length; j++ ) // if we check half, the half must be checked against ALL
{   long timeInterval = Math.Max( Math.Abs( houses[i].Y - houses[j].Y ), Math.Abs( houses[i].X - houses[j].X ) );
time += timeInterval;
Console
.WriteLine ("i {0}, j {1} :: house {2},{3} :: house {4},{5} :: time {6}, cumulative {7}",
i, j, houses[i].X, houses[i].Y, houses[j].X, houses[j].Y, timeInterval, time );
} // for( int j = 0; j < houses.Length; j++ )
Console.WriteLine ("........................ {0}, {1}\r\n", time, minTime);
houses[i].computedTime = time;
if( time < minTime )      minTime = time;
} // for( int i = 0; i <  housesToCheck; i++ )
Console.WriteLine ("Meeting Place(s)");
foreach (House house in houses)
{
if (house.computedTime <= minTime) // should never be <
{
Console.WriteLine ("house {0},{1} :: time {2}", house.X, house.Y, house.computedTime);
}
}
Console.WriteLine ("Non-Meeting Place(s)");
foreach (House house in houses)
{
if (house.computedTime > minTime)
{
Console.WriteLine ("house {0},{1} :: time {2}", house.X, house.Y, house.computedTime);
}
}
return minTime;
}```

The last part of the output:

```Meeting Place(s)
house 0,1 :: time 77
house 1,0 :: time 77
house 9,1 :: time 77
house 8,0 :: time 77
house 1,9 :: time 77
house 0,8 :: time 77
house 9,8 :: time 77
house 8,9 :: time 77

Non-Meeting Place(s)
house 0,0 :: time 81
house 9,0 :: time 81
house 0,9 :: time 81
house 9,9 :: time 81

minimum cumulative travel time == 77 units```

g.

* if you do not have LINQPad 4:

TOOLS ... get yourself a FREE copy of LINQPad 4 (http://linqpad.net) .. Joe Albahari's LINQPad 4 is an awesome programmer's scratch pad that enables you to quickly check out code snippets you find in books and on web sites plus LINQPad also lets you rapidly experiment with c# ideas before committing them to vs2010.

LINQPad 4 supports c#, F#, SQL, vb.

first part of the output:

```i 0, j 0 :: house 0,0 :: house 0,0 :: time 0, cumulative 0
i 0, j 1 :: house 0,0 :: house 0,1 :: time 1, cumulative 1
i 0, j 2 :: house 0,0 :: house 1,0 :: time 1, cumulative 2
i 0, j 3 :: house 0,0 :: house 9,0 :: time 9, cumulative 11
i 0, j 4 :: house 0,0 :: house 9,1 :: time 9, cumulative 20
i 0, j 5 :: house 0,0 :: house 8,0 :: time 8, cumulative 28
i 0, j 6 :: house 0,0 :: house 1,9 :: time 9, cumulative 37
i 0, j 7 :: house 0,0 :: house 0,8 :: time 8, cumulative 45
i 0, j 8 :: house 0,0 :: house 0,9 :: time 9, cumulative 54
i 0, j 9 :: house 0,0 :: house 9,8 :: time 9, cumulative 63
i 0, j 10 :: house 0,0 :: house 8,9 :: time 9, cumulative 72
i 0, j 11 :: house 0,0 :: house 9,9 :: time 9, cumulative 81
........................ 81, 9223372036854775807

i 1, j 0 :: house 0,1 :: house 0,0 :: time 1, cumulative 1
i 1, j 1 :: house 0,1 :: house 0,1 :: time 0, cumulative 1
i 1, j 2 :: house 0,1 :: house 1,0 :: time 1, cumulative 2
i 1, j 3 :: house 0,1 :: house 9,0 :: time 9, cumulative 11
i 1, j 4 :: house 0,1 :: house 9,1 :: time 9, cumulative 20
i 1, j 5 :: house 0,1 :: house 8,0 :: time 8, cumulative 28
i 1, j 6 :: house 0,1 :: house 1,9 :: time 8, cumulative 36
i 1, j 7 :: house 0,1 :: house 0,8 :: time 7, cumulative 43
i 1, j 8 :: house 0,1 :: house 0,9 :: time 8, cumulative 51
i 1, j 9 :: house 0,1 :: house 9,8 :: time 9, cumulative 60
i 1, j 10 :: house 0,1 :: house 8,9 :: time 8, cumulative 68
i 1, j 11 :: house 0,1 :: house 9,9 :: time 9, cumulative 77
........................ 77, 81

i 2, j 0 :: house 1,0 :: house 0,0 :: time 1, cumulative 1
i 2, j 1 :: house 1,0 :: house 0,1 :: time 1, cumulative 2
i 2, j 2 :: house 1,0 :: house 1,0 :: time 0, cumulative 2
i 2, j 3 :: house 1,0 :: house 9,0 :: time 8, cumulative 10
i 2, j 4 :: house 1,0 :: house 9,1 :: time 8, cumulative 18
i 2, j 5 :: house 1,0 :: house 8,0 :: time 7, cumulative 25
i 2, j 6 :: house 1,0 :: house 1,9 :: time 9, cumulative 34
i 2, j 7 :: house 1,0 :: house 0,8 :: time 8, cumulative 42
i 2, j 8 :: house 1,0 :: house 0,9 :: time 9, cumulative 51
i 2, j 9 :: house 1,0 :: house 9,8 :: time 8, cumulative 59
i 2, j 10 :: house 1,0 :: house 8,9 :: time 9, cumulative 68
i 2, j 11 :: house 1,0 :: house 9,9 :: time 9, cumulative 77
........................ 77, 77

i 3, j 0 :: house 9,0 :: house 0,0 :: time 9, cumulative 9
i 3, j 1 :: house 9,0 :: house 0,1 :: time 9, cumulative 18
i 3, j 2 :: house 9,0 :: house 1,0 :: time 8, cumulative 26
i 3, j 3 :: house 9,0 :: house 9,0 :: time 0, cumulative 26
i 3, j 4 :: house 9,0 :: house 9,1 :: time 1, cumulative 27
i 3, j 5 :: house 9,0 :: house 8,0 :: time 1, cumulative 28
i 3, j 6 :: house 9,0 :: house 1,9 :: time 9, cumulative 37
i 3, j 7 :: house 9,0 :: house 0,8 :: time 9, cumulative 46
i 3, j 8 :: house 9,0 :: house 0,9 :: time 9, cumulative 55
i 3, j 9 :: house 9,0 :: house 9,8 :: time 8, cumulative 63
i 3, j 10 :: house 9,0 :: house 8,9 :: time 9, cumulative 72
i 3, j 11 :: house 9,0 :: house 9,9 :: time 9, cumulative 81
........................ 81, 77

i 4, j 0 :: house 9,1 :: house 0,0 :: time 9, cumulative 9
i 4, j 1 :: house 9,1 :: house 0,1 :: time 9, cumulative 18
i 4, j 2 :: house 9,1 :: house 1,0 :: time 8, cumulative 26
i 4, j 3 :: house 9,1 :: house 9,0 :: time 1, cumulative 27
i 4, j 4 :: house 9,1 :: house 9,1 :: time 0, cumulative 27
i 4, j 5 :: house 9,1 :: house 8,0 :: time 1, cumulative 28
i 4, j 6 :: house 9,1 :: house 1,9 :: time 8, cumulative 36
i 4, j 7 :: house 9,1 :: house 0,8 :: time 9, cumulative 45
i 4, j 8 :: house 9,1 :: house 0,9 :: time 9, cumulative 54
i 4, j 9 :: house 9,1 :: house 9,8 :: time 7, cumulative 61
i 4, j 10 :: house 9,1 :: house 8,9 :: time 8, cumulative 69
i 4, j 11 :: house 9,1 :: house 9,9 :: time 8, cumulative 77
........................ 77, 77

i 5, j 0 :: house 8,0 :: house 0,0 :: time 8, cumulative 8
i 5, j 1 :: house 8,0 :: house 0,1 :: time 8, cumulative 16
i 5, j 2 :: house 8,0 :: house 1,0 :: time 7, cumulative 23
i 5, j 3 :: house 8,0 :: house 9,0 :: time 1, cumulative 24
i 5, j 4 :: house 8,0 :: house 9,1 :: time 1, cumulative 25
i 5, j 5 :: house 8,0 :: house 8,0 :: time 0, cumulative 25
i 5, j 6 :: house 8,0 :: house 1,9 :: time 9, cumulative 34
i 5, j 7 :: house 8,0 :: house 0,8 :: time 8, cumulative 42
i 5, j 8 :: house 8,0 :: house 0,9 :: time 9, cumulative 51
i 5, j 9 :: house 8,0 :: house 9,8 :: time 8, cumulative 59
i 5, j 10 :: house 8,0 :: house 8,9 :: time 9, cumulative 68
i 5, j 11 :: house 8,0 :: house 9,9 :: time 9, cumulative 77
........................ 77, 77

i 6, j 0 :: house 1,9 :: house 0,0 :: time 9, cumulative 9
i 6, j 1 :: house 1,9 :: house 0,1 :: time 8, cumulative 17
i 6, j 2 :: house 1,9 :: house 1,0 :: time 9, cumulative 26
i 6, j 3 :: house 1,9 :: house 9,0 :: time 9, cumulative 35
i 6, j 4 :: house 1,9 :: house 9,1 :: time 8, cumulative 43
i 6, j 5 :: house 1,9 :: house 8,0 :: time 9, cumulative 52
i 6, j 6 :: house 1,9 :: house 1,9 :: time 0, cumulative 52
i 6, j 7 :: house 1,9 :: house 0,8 :: time 1, cumulative 53
i 6, j 8 :: house 1,9 :: house 0,9 :: time 1, cumulative 54
i 6, j 9 :: house 1,9 :: house 9,8 :: time 8, cumulative 62
i 6, j 10 :: house 1,9 :: house 8,9 :: time 7, cumulative 69
i 6, j 11 :: house 1,9 :: house 9,9 :: time 8, cumulative 77
........................ 77, 77

i 7, j 0 :: house 0,8 :: house 0,0 :: time 8, cumulative 8
i 7, j 1 :: house 0,8 :: house 0,1 :: time 7, cumulative 15
i 7, j 2 :: house 0,8 :: house 1,0 :: time 8, cumulative 23
i 7, j 3 :: house 0,8 :: house 9,0 :: time 9, cumulative 32
i 7, j 4 :: house 0,8 :: house 9,1 :: time 9, cumulative 41
i 7, j 5 :: house 0,8 :: house 8,0 :: time 8, cumulative 49
i 7, j 6 :: house 0,8 :: house 1,9 :: time 1, cumulative 50
i 7, j 7 :: house 0,8 :: house 0,8 :: time 0, cumulative 50
i 7, j 8 :: house 0,8 :: house 0,9 :: time 1, cumulative 51
i 7, j 9 :: house 0,8 :: house 9,8 :: time 9, cumulative 60
i 7, j 10 :: house 0,8 :: house 8,9 :: time 8, cumulative 68
i 7, j 11 :: house 0,8 :: house 9,9 :: time 9, cumulative 77
........................ 77, 77

i 8, j 0 :: house 0,9 :: house 0,0 :: time 9, cumulative 9
i 8, j 1 :: house 0,9 :: house 0,1 :: time 8, cumulative 17
i 8, j 2 :: house 0,9 :: house 1,0 :: time 9, cumulative 26
i 8, j 3 :: house 0,9 :: house 9,0 :: time 9, cumulative 35
i 8, j 4 :: house 0,9 :: house 9,1 :: time 9, cumulative 44
i 8, j 5 :: house 0,9 :: house 8,0 :: time 9, cumulative 53
i 8, j 6 :: house 0,9 :: house 1,9 :: time 1, cumulative 54
i 8, j 7 :: house 0,9 :: house 0,8 :: time 1, cumulative 55
i 8, j 8 :: house 0,9 :: house 0,9 :: time 0, cumulative 55
i 8, j 9 :: house 0,9 :: house 9,8 :: time 9, cumulative 64
i 8, j 10 :: house 0,9 :: house 8,9 :: time 8, cumulative 72
i 8, j 11 :: house 0,9 :: house 9,9 :: time 9, cumulative 81
........................ 81, 77

i 9, j 0 :: house 9,8 :: house 0,0 :: time 9, cumulative 9
i 9, j 1 :: house 9,8 :: house 0,1 :: time 9, cumulative 18
i 9, j 2 :: house 9,8 :: house 1,0 :: time 8, cumulative 26
i 9, j 3 :: house 9,8 :: house 9,0 :: time 8, cumulative 34
i 9, j 4 :: house 9,8 :: house 9,1 :: time 7, cumulative 41
i 9, j 5 :: house 9,8 :: house 8,0 :: time 8, cumulative 49
i 9, j 6 :: house 9,8 :: house 1,9 :: time 8, cumulative 57
i 9, j 7 :: house 9,8 :: house 0,8 :: time 9, cumulative 66
i 9, j 8 :: house 9,8 :: house 0,9 :: time 9, cumulative 75
i 9, j 9 :: house 9,8 :: house 9,8 :: time 0, cumulative 75
i 9, j 10 :: house 9,8 :: house 8,9 :: time 1, cumulative 76
i 9, j 11 :: house 9,8 :: house 9,9 :: time 1, cumulative 77
........................ 77, 77

i 10, j 0 :: house 8,9 :: house 0,0 :: time 9, cumulative 9
i 10, j 1 :: house 8,9 :: house 0,1 :: time 8, cumulative 17
i 10, j 2 :: house 8,9 :: house 1,0 :: time 9, cumulative 26
i 10, j 3 :: house 8,9 :: house 9,0 :: time 9, cumulative 35
i 10, j 4 :: house 8,9 :: house 9,1 :: time 8, cumulative 43
i 10, j 5 :: house 8,9 :: house 8,0 :: time 9, cumulative 52
i 10, j 6 :: house 8,9 :: house 1,9 :: time 7, cumulative 59
i 10, j 7 :: house 8,9 :: house 0,8 :: time 8, cumulative 67
i 10, j 8 :: house 8,9 :: house 0,9 :: time 8, cumulative 75
i 10, j 9 :: house 8,9 :: house 9,8 :: time 1, cumulative 76
i 10, j 10 :: house 8,9 :: house 8,9 :: time 0, cumulative 76
i 10, j 11 :: house 8,9 :: house 9,9 :: time 1, cumulative 77
........................ 77, 77

i 11, j 0 :: house 9,9 :: house 0,0 :: time 9, cumulative 9
i 11, j 1 :: house 9,9 :: house 0,1 :: time 9, cumulative 18
i 11, j 2 :: house 9,9 :: house 1,0 :: time 9, cumulative 27
i 11, j 3 :: house 9,9 :: house 9,0 :: time 9, cumulative 36
i 11, j 4 :: house 9,9 :: house 9,1 :: time 8, cumulative 44
i 11, j 5 :: house 9,9 :: house 8,0 :: time 9, cumulative 53
i 11, j 6 :: house 9,9 :: house 1,9 :: time 8, cumulative 61
i 11, j 7 :: house 9,9 :: house 0,8 :: time 9, cumulative 70
i 11, j 8 :: house 9,9 :: house 0,9 :: time 9, cumulative 79
i 11, j 9 :: house 9,9 :: house 9,8 :: time 1, cumulative 80
i 11, j 10 :: house 9,9 :: house 8,9 :: time 1, cumulative 81
i 11, j 11 :: house 9,9 :: house 9,9 :: time 0, cumulative 81
........................ 81, 77```

*** END ***

B-)  Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Star

12990 Points

5547 Posts