Find the missing link

Question

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++)
 {
 pairs.Add(new PairInt(i, i + 1));
 }
 // 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
 {
 lineEmUp.Add(pair);
 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.

• t3chb0t: Is this a programming-challage?
• paparazzo: @t3chb0t Maybe some where but I read it as an example problem from a book

Answer 1

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);
 // just start with any men
 var right = pairs[0].Rght;
 while (rightLefttDict.TryGetValue(right, out right)) {}
 Console.WriteLine(right);
}

• paparazzo: I don't follow this
• JanDotNet: That method reconstructs the initial created list. It creates a dictionary where the keys are the IDs of the mens who sit left and the values are the IDs of the mens who sit right. Starting with 0 (the most left men), it gets the id of the men right to the current one and use it to get the next men...
• paparazzo: But this starts with you must know what it is you are looking for. We don't know the user on the far left is idx = 0 - that is what we are looking for. It was 0 as that was a convenient way for me to create the test case.
• JanDotNet: 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
• paparazzo: Ouch that was easy and makes sense. I got too focused on one path. I am going to leave it unanswered for a day just to get more feedback.