The Country Game

Have I ever told you about the country game ? I made it up in middle school.you name a county, say, Afghanistan. The next person has to name a country starting with the last letter of the country. So Nepal is next. And if you can’t come up with a name you lose!

We soon discovered a pattern. There were more countries ending in A than ones starting with A. This meant it was really easy to enter a loop where you named Serbia and then you get trapped with Albania, Afghanistan, Nepal, Lithuania… until you ran out of A. And worse many A countries also ended with A! Andorra, Albania. This was a common sink in the games.

I have had many questions about this game since. What is the longest possible chain? What is the shortest? What are different “sinks” you can fall into? What are the possible lose conditions?

Obviously this is just because it is country names. But imagine if we used different names of things… how would the game change?

Anyway one day when I am less bored I will write a little program to find this! I am sure I can use graph theory also.

Here is my idea:

We start by creating a graph of all the possible combinations - every letter-letter pair we have. e.g. A-A pairs, N-L pairs, etc. Each edge has a number assigned to it that is the number of countries left with that combo. Going through a country decreases the count by 1. If that number hits 0, that edge is no longer traversable. This could abstract away the need to track individual countries since they are ultimately interchangeable.

Get the terminal chains

          
          # this nested dictionary is an adjacency list
          # the key is the first letter of the country
          # in the nested dictionary, the key is the second letter of the country
          # the value is the number of times that transition appears
          
          # Albania, Andorra, Aghanistan
          # Lithuania
          # Nigeria, Nepal
          # Cuba
          
          graph = {
              'A': {'A': 2, 'N': 1},
              'L': {'A': 1},
              'N': {'A': 1, 'L': 1},
              'C': {'A': 1}
          }
          
          # recursive depth first search
          def dfs(current, graph, path_length):
              global max_length
              max_length = max(max_length, path_length)
          
              for neighbor in graph.get(current, {}):
                  if graph[current][neighbor] > 0:
                      graph[current][neighbor] -= 1
                      dfs(neighbor, graph, path_length + 1)            
                      # backtrack
                      graph[current][neighbor] += 1  
                      
          
          # Initialize
          max_length = 0
          
          
          # do dfs on each node
          for start in graph:
              dfs(start, graph, 0)
          
          print("Longest possible chain length:", max_length)
          

This works fine and will tell you the maximum possible length. However, I don't want to just know the longest possible length. I want to know what sequences I have to say to keep the game going as long as possible. I want to know the chain that leads to the longest possible length! In order to do this, we need a way to keep track of the chain being formed.

The following code works:

secondlist = []

def dfs(current, graph, path_length):
    global max_length
    global list
    max_length = max(max_length, path_length)

    # track whether we have valid moves left
    has_valid_moves = False

    # for each ending letter of the current country, do the following
    for neighbor in graph.get(current, {}):
        # if there are countries left with that transition, move on
        if graph[current][neighbor] > 0:
            # there are valid moves, so when we exit this for loop, do not add what we have in 'list' to secondlist!
            has_valid_moves = True
            # use up the transition to the neighbor
            graph[current][neighbor] -= 1
            # add the transition to the list
            list.append(str(current) + " -> " + str(neighbor))
            dfs(neighbor, graph, path_length + 1)
            
            # if we get to this point, then there is nothing left to explore and we gotta move back up
            # add '1' back to the count so we can try a different path without triggering the exit condition
            graph[current][neighbor] += 1  # backtrack            
            # remove while backtracking
            list.pop()
    if not has_valid_moves:
        # if the dfs loop broke and there are no valid moves left, that means we found a terminal chain. add to the secondlist
        # we need to put it after the break so that we don't add the backtracking ones
         secondlist.append(list.copy())


# Initialize
max_length = 0
list = []

# iterate through each starting letter
for member in graph:
    dfs(member, graph, 0)

print("Longest possible chain length:", max_length)

for member in secondlist:
    print(member, "Length: " + str(len(member)))
    

And with our toy example, we see all the possible games you can play using the countries we have available:

['A -> A', 'A -> A', 'A -> N', 'N -> A'] Length: 4
['A -> A', 'A -> A', 'A -> N', 'N -> L', 'L -> A'] Length: 5
['A -> A', 'A -> N', 'N -> A', 'A -> A'] Length: 4
['A -> A', 'A -> N', 'N -> L', 'L -> A', 'A -> A'] Length: 5
['A -> N', 'N -> A', 'A -> A', 'A -> A'] Length: 4
['A -> N', 'N -> L', 'L -> A', 'A -> A', 'A -> A'] Length: 5
['L -> A', 'A -> A', 'A -> A', 'A -> N', 'N -> A'] Length: 5
['L -> A', 'A -> A', 'A -> A', 'A -> N', 'N -> L'] Length: 5
['L -> A', 'A -> A', 'A -> N', 'N -> A', 'A -> A'] Length: 5
['L -> A', 'A -> A', 'A -> N', 'N -> L'] Length: 4
['L -> A', 'A -> N', 'N -> A', 'A -> A', 'A -> A'] Length: 5
['L -> A', 'A -> N', 'N -> L'] Length: 3
['N -> A', 'A -> A', 'A -> A', 'A -> N', 'N -> L', 'L -> A'] Length: 6
['N -> A', 'A -> A', 'A -> N', 'N -> L', 'L -> A', 'A -> A'] Length: 6
['N -> A', 'A -> N', 'N -> L', 'L -> A', 'A -> A', 'A -> A'] Length: 6
['N -> L', 'L -> A', 'A -> A', 'A -> A', 'A -> N', 'N -> A'] Length: 6
['N -> L', 'L -> A', 'A -> A', 'A -> N', 'N -> A', 'A -> A'] Length: 6
['N -> L', 'L -> A', 'A -> N', 'N -> A', 'A -> A', 'A -> A'] Length: 6

Note that this doesn't tell you the actual countries you can use. For example, the very first sequence, ['A -> A', 'A -> A', 'A -> N', 'N -> A'], actually has two possibilities. You can start with Albania and then move to Andorra, or you can start with Andorra and move to Albania. I'm not really interested in tracking the permutations of each game (not yet, at least), so I won't be writing on that, but I wanted to point it out.

Stumbling points

Mistakes were made! Figuring out the longest possible chain length was not hard as you can just use a standard depth-first search. But it was slipperier than I expected to be able to track which ones were the terminal chains and add those to a list. Some mistakes made were trying to append the list at backtracking (just ended up capturing everything while backtracking), and checking whether there were neighbors available in an else inside the for loop instead of exiting the for loop. I will write these another day.

Graph theory implications?

There were two questions that got me interested in exploring all of this. Question 1 was what was the longest game you could play. By turning it into a graph, we now have a way to answer this question. (I'm also sure that someone with more patience than I could use theorems from graph theory to mathematically prove something related to the length of the game! Maybe I'll tackle that in the future.) We can know the longest possible length as well as the sequence that will take you there.

The second question I had related to the question of A sinks. More countries end in the letter 'A' than start with 'A'. Worse, some of the countries that start with 'A' end in 'A' as well, such as Albania. This means that there are lots of ways to enter the 'A' node, but not a lot of ways to exit it. I called this a 'sink' at the time since it was easy to get in but hard to get out.

If you draw out the graph, it becomes easier to notice the condition for a sink. For our 'a' sink, we notice that the node points to itself. Moreover, it points to itself more than it has any exit nodes. # of self-directed edges > outward-bound edges. This is already troublesome. But if there were very few nodes that pointed to A, this wouldn't be an issue. However, there are many nodes that point to A. In fact, there may be more nodes that point to A than there are exits to A! So that's point two - # of nodes pointing to A > exits from A. And the third part is that of the possible endings, many of them (most?) point to A. So not only are there many nodes that point to A, there is a lot of weight and many edges pointing to A. It is almost inevitable that we end up looping back around A because there aren't many alternatives.

Now, this is just because we are playing with countries, and -ia is a common suffix for countries. I am sure we would discover new phenomena if looked at the names of Nobel prize winners, or Pokemon, or Billboard top 100 songs.