Unordered map for naive c++ solution

Question 1

I believe the solution is saying to use one list. Pick the first tuple, and put its first name as the head of the list, and the westerly neighbor as the next item. Then, find the tuple that has that westerly neighbor as its first name (that, of course, is the hard part), and grab the westerly neighbor from that tuple and append it to the list. Repeat until you have can't find a tuple with the name of the last added person. Then you know you have reached the West Coast.

So, the first xc is essentially random. After that, xc is deterministic. The line that says

- while xc has westerly neighbour

is essentially saying "find that tuple that has the current westerly neighbor as the self name".

The latter part, of course, just applies the same logic in reverse, to fill up the chain going east.

Question 2

First Try

I'm doing this as an answer, because it's impossible to ask this as a comment. Also clarifying this is IMHO at least half of the answer

Is this meant in the following way?

identify an individual xc
append xc to empty list
while( xc has westerly neighbour )
{
    if( xc < westerly neighbour of xc )
    {
        append xc to list
    }
    // Do not understand this:
    // - xc < head of list
}
while( while xc has easterly neighbour )
{
    if( xc < easterly neighbour of xc )
    {
        prepend xc to list
    }
}

(This is just a try to get closer to a solution - I even did not think about the algorithm yet...)

Second Try

identify an individual xc
append xc to empty list

while( xc has westerly neighbour )
{
    xc := westerly neighbour of xc
    append xc to list
    xc := head of list

    while( xc has easterly neighbour )
    {
        xc := easterly neighbour of xc
        prepend xc to list
    }
}

It seams that this makes some sense: So you run through the list, collect all the westerly neighbors as far as possible and do this with all the easterly after this. So for each run trough the original list, the sorted list gets longer and longer.

Third Try

IMHO something is missing: if I interpret all the information available I come to the following solution. But this needs a lot more scans of the original tape: instead of the given 10.000 times it scans it about 750.000 times. Any ideas?

#include <vector>
#include <algorithm>
#include <iostream>
#include <list>

size_t constexpr max_men { 3000000 };

typedef std::tuple< int, int > neighbors_t;
typedef std::vector< neighbors_t > pool_t;

int main() {

  // Need a vector here for random_shuffle - but using it further down
  // just with sequencial methods.
  pool_t pool_list;
  for( size_t i { 0 }; i < max_men - 1; ++i ) {
    pool_list.push_back( std::make_tuple( i, i + 1) );
  }
  std::random_shuffle( pool_list.begin(), pool_list.end() );


  // Use the algorithm to get it sorted again

  // identify an individual xc:
  // Pick first from first tuple
  // append xc to empty list
  std::list<int> sorted_list;
  sorted_list.push_back( std::get<0>( pool_list.front() ) );

  // Count the number of tape scans
  size_t tape_scans { 0 };

  do {
    // Scan through the pool_list
    for( neighbors_t n : pool_list ) {

#if 0
      std::cout << "n [" << std::get<0>( n ) 
        << "] sorted_list [";
      for( int i : sorted_list ) {
        std::cout << i << " ";
      }
      std::cout << "]" << std::endl;
#endif

      // while( xc has westerly neighbour )
      // Found westerly neighbour
      if( std::get< 1 >( n ) == sorted_list.front() ) {
        // append xc to list
        sorted_list.push_front( std::get< 0 >( n ) );
      }
      if( std::get< 0 >( n ) == sorted_list.back() ) {
        // append xc to list
        sorted_list.push_back( std::get< 1 >( n ) );
      }
    } 
    ++tape_scans;
    std::cout << "Tape Scans needed [" << tape_scans 
          << "] sorted list size [" << sorted_list.size() << "]"
          << std::endl;
  } while( sorted_list.size() < max_men );

  std::cout << "Tape Scans needed [" << tape_scans << "]" << std::endl;

  return 0;
}