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++ )
{
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)).
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
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.
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.
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-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
"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?
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-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
Would you please share the link to the problem with us?
Note: although Dave and i have some degree of disagreement regarding the
statement of the problem, Dave's solution works (http://forums.asp.net/post/4869762.aspx).
Dave and i both agree that his solution could be more efficient; however, imho, Dave's solution is sufficient for getting 50 points (because of the way the problem has been stated) since Dave's solution fulfils the requirement.
again, for my benefit, ashok, please share the link to the problem with us.
Thank you.
Gerry
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
DMW
All-Star
15943 Points
2353 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 10:43 AM|LINK
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)!
Dave
gerrylowry
All-Star
20515 Points
5713 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 11:14 AM|LINK
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.
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)).
g.
DMW
All-Star
15943 Points
2353 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 01:57 PM|LINK
It does, very clearly. It states " find A common meeting place". Not THE common meeting place. A common meeting place.
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.
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.
Dave
DMW
All-Star
15943 Points
2353 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 02:31 PM|LINK
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!
Dave
gerrylowry
All-Star
20515 Points
5713 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 06:59 PM|LINK
@ DMW
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".
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.
DMW
All-Star
15943 Points
2353 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 08:30 PM|LINK
gerry
Please, please read the OP's question properly!
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?
Dave
gerrylowry
All-Star
20515 Points
5713 Posts
Re: need solution to this problem in c#- help
Mar 09, 2012 01:54 PM|LINK
@ 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:
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:
*** END ***
gerrylowry
All-Star
20515 Points
5713 Posts
Re: need solution to this problem in c#- help
Mar 09, 2012 02:12 PM|LINK
@ ashok2009cse
Would you please share the link to the problem with us?
Note: although Dave and i have some degree of disagreement regarding the statement of the problem, Dave's solution works (http://forums.asp.net/post/4869762.aspx).
aahok, at some point, i suggest that you mark Dave's answer (http://forums.asp.net/post/4869762.aspx) as "the answer" ...
Dave and i both agree that his solution could be more efficient; however, imho, Dave's solution is sufficient for getting 50 points (because of the way the problem has been stated) since Dave's solution fulfils the requirement.
again, for my benefit, ashok, please share the link to the problem with us.
Thank you.
Gerry