Thee million men write down their name and the person to their left and the person on the far left throws out his paper. Reconstruct the list.

A List takes a while. Don't try 3 million unless you have some time.

Up front we do NOT know the remaining man on left is 0. That is what we are looking for. The remaining here is 0 as the was test data easy to create.

public static void TAOCPthreeMillionMenTest()
{
int numberOfMen = 30000;  // test at less than 3 million or get killed
List<PairInt> pairs = new List<PairInt>(numberOfMen);
for (int i = 0; i < numberOfMen; i++)
{
}
// shuffle left
Random rand = new Random();
int temp;
int j;
//shuffl up
for (int i = numberOfMen - 1; i > 0; i--)
{
j = rand.Next(i + 1);
if (i != j)
{
temp = pairs[i].Rght;
pairs[i].Rght = pairs[j].Rght;
pairs[j].Rght = temp;
temp = pairs[i].Left;
pairs[i].Left = pairs[j].Left;
pairs[j].Left = temp;
}
}
foreach (PairInt pair in pairs)
{
//Debug.WriteLine(pair.Left + " " + pair.Rght);
if (pair.Left == pair.Rght)
Debug.WriteLine("pair.Left == pair.Rght");
}
Debug.WriteLine("");
Debug.WriteLine(TAOCPthreeMillionManLeft(pairs));
Debug.WriteLine("");
}
public static int TAOCPthreeMillionManLeft(List<PairInt> pairs)
{
List<PairInt> lineEmUp = new List<PairInt>();
int lineEmUpCountMax = 0;
int lineEmUpCountMaxCount = 0;
PairInt matchRght;
PairInt matchLeft;
int count = 0;
foreach (PairInt pair in pairs)
{
count++;
//Debug.WriteLine("new   " + pair.Left + " " + pair.Rght);
//foreach (PairInt exist in lineEmUp)
//{
//    Debug.WriteLine("exist " + exist.Left + " " + exist.Rght);
//}
//Debug.WriteLine("");
matchRght = lineEmUp.FirstOrDefault(x => x.Rght == pair.Left);
matchLeft = lineEmUp.FirstOrDefault(x => x.Left == pair.Rght);
if (matchRght != null)
{
if (matchLeft != null)
{
matchRght.Rght = matchLeft.Rght;
lineEmUp.Remove(matchLeft);
}
else
{
matchRght.Rght = pair.Rght;
}
}
else if (matchLeft != null)
{
matchLeft.Left = pair.Left;
}
else
{
if (lineEmUpCountMax < lineEmUp.Count)
{
lineEmUpCountMax = lineEmUp.Count;
lineEmUpCountMaxCount = count;
}
//Debug.WriteLine("lineEmUp.Count " + lineEmUp.Count);
}
}
// lineEmUp should have only one entry
if (lineEmUp.Count != 1)
{
Debug.WriteLine("");
Debug.WriteLine("lineEmUp.Count != 1");
foreach (PairInt pair in lineEmUp)
{
Debug.WriteLine(pair.Left + " " + pair.Rght);
}
Debug.WriteLine("");
}
return lineEmUp[0].Left;
}

public class PairInt
{
public int Left { get; set; }
public int Rght { get; set; }
public PairInt(int left, int rght)
{
Left = left;
Rght = rght;
}
}


I tried a double dictionary but could not make it work.

• Is this a programming-challage? Feb 2, 2017 at 8:08
• @t3chb0t Maybe some where but I read it as an example problem from a book Feb 2, 2017 at 8:10

Not sure if I get the problem, but one solution for reconstructing the original list (even 3.000.000 items) with a dictionary is:

public static void ReconstructList(List<PairInt> pairs)
{
var leftRightDict = pairs.ToDictionary(p => p.Left, p => p.Rght);
var idx = 0;
while (leftRightDict.TryGetValue(idx, out idx))
Console.WriteLine(idx);
}


Update:

The following code gets the ID of the left-most men:

public static void ReconstructList(List<PairInt> pairs)
{
var rightLefttDict = pairs.ToDictionary(p => p.Rght, p => p.Left);

• Ok, but then you can just start anywhere and go to the left-most men that has a value Left which does not exist as value for Rght for all PaitInt items. see updated answer Feb 2, 2017 at 15:57