0
\$\begingroup\$

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.

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

1 Answer 1

1
\$\begingroup\$

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);
}
\$\endgroup\$
5
  • \$\begingroup\$ I don't follow this \$\endgroup\$
    – paparazzo
    Feb 2, 2017 at 14:48
  • \$\begingroup\$ 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... \$\endgroup\$
    – JanDotNet
    Feb 2, 2017 at 15:20
  • \$\begingroup\$ 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. \$\endgroup\$
    – paparazzo
    Feb 2, 2017 at 15:40
  • \$\begingroup\$ 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 \$\endgroup\$
    – JanDotNet
    Feb 2, 2017 at 15:57
  • \$\begingroup\$ 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. \$\endgroup\$
    – paparazzo
    Feb 2, 2017 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.