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

## 17 replies

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

All-Star

15943 Points

2353 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
• Marked as answer by mbanavige on Mar 14, 2012 01:39 AM

All-Star

20577 Points

5721 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.

All-Star

15943 Points

2353 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

All-Star

15943 Points

2353 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

All-Star

20577 Points

5721 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.

All-Star

15943 Points

2353 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

All-Star

20577 Points

5721 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 ***

All-Star

20577 Points

5721 Posts