This week’s Riddler Classic features another classic character from probability problems: the goat. They’re not hiding behind doors this time though, they’re looking for a home!

Here’s the text of the puzzle, and my solution below.

A goat tower has 10 floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor.

One by one, each goat walks up the tower to its preferred room. If the floor is empty, the goat will make itself at home. But if the floor is already occupied by another goat, then it will keep going up until it finds the next empty floor, which it will occupy. But if it does not find any empty floors, the goat will be stuck on the roof of the tower.

What is the probability that all 10 goats will have their own floor, meaning no goat is left stranded on the roof of the tower?

The answer is ~0.236. I reached the solution using Monte Carlo simulations, but for a twist, ran them in Python to get practice outside of R. I’m certainly much more experienced in R than Python, so forgive me if I did anything too silly…

We’ll start by loading in necessary libraries and setting some parameters. I wanted to add the option to vary the number of floors and goats in the problem in case anyone is interested in seeing how these changes affect the solution.

import random
import numpy

# parameters
random.seed(20220625)
N_floors = 10
N_goats = 10
sims = 1000000
full_building_results = [""]*sims

We will store the main result—how many goats found a home—into the list full_building_results, and reach the answer by counting the number of times this result was equal to 10 divided by the number of simulations, here, one million (the program runs fairly quickly).

I also wanted to extract a few other quantities of interest: the average number of goats that ended up stuck on the roof, the average number of goats that ended up in their preferred room, and the average number of goats that ended up in a room, but one that was not their preferred room.

stuck_goat_results = [""]*sims
happy_goat_results = [""]*sims
satisfied_goat_results = [""]*sims

We will repeat the entire program sims times, so everything is enclosed in a loop:

for s in range(0,sims):
  print("Simulation", s, "//", (s/sims)*100, "% complete")

Next we will define two lists of lists: the list that contains information about the goats, goats, and the list that contains information about the building, building. The goats object will contain, for each goat, their floor preference and their “status”: whether they got their preferred floor, or got a room that was not on their preferred floor, or ended up stuck on the roof. The building object describes each of the floors and whether or not they are occupied. Obviously, all the floors start off empty. Notice that i indexes goats and j indexes floors.

 # define floors
  floors = range(0,N_floors)
  
  # define goats' floor preferences
  goat_prefs = choices(floors, k = N_goats)
  
  # define goat status
  goat_status = ['' for i in goat_prefs]
  goat_room = ['' for i in goat_prefs]
  
  # zip into goat list
  goats = list(zip(goat_prefs, goat_status, goat_room))
  
  for i in range(0,N_goats):
    goats[i] = list(goats[i])
  
  # define floor status
  status = ['empty' for j in floors]
  
  # zip into building list
  building = list(zip(floors, status))
  
  for j in range(0,N_floors):
    building[j] = list(building[j])

Now we’re into the meat of the program. Here, I define a function that will mimic the process of each goat approaching the building and checking the floor. Over each floor in the building, the first goat will check if the floor is occupied, and if not, make itself at home. If not, it will check each floor above—without being able to go back down—for a space. It will take the first open floor it sees above its preferred floor. If there are no open floors, then it will be stuck on the roof.

# define function that will check for each goat where it should go
  def goat_check_function(i):
    for j in range(0,N_floors): # over all floors
      for x in range(1,N_floors): # to check other floors when desired floor is full
        if (goats[i][0] == building[j][0]) and (building[j][1] == 'empty'):
          building[j][1] = 'full'
          goats[i][1] = 'happy in room'
          goats[i][2] = j
        elif (goats[i][1] == '') and (goats[i][0] == building[j][0]) and (building[j][1] == 'full') and (j < (10-x)) and (building[j+x][1]) == 'empty':
              building[j+x][1] = 'full'
              goats[i][1] = 'occupying room'
              goats[i][2] = j+x

Applying this function for each goat yields a result for a single simulation.

# run function for goats
  for i in range(0,N_goats): goat_check_function(i)

Although the default goat status of '' is equivalent to being stuck on the roof at the end of the simulation (since if a goat does not occupy a room it must be stuck on the roof) I update the status for clarity.

  # anyone without a home is stuck on the roof :(
  for i in range(0,N_goats):
    if (goats[i][1] == ''):
      goats[i][1] = 'stuck on roof!'
      goats[i][2] = ''

Finally, we can count if the building is full fairly easily, by checking the building status directly as done here, or by seeing if zero goats were stuck on the roof. Other quantities of interest are calculated accordingly.

# count if building is full
  floor_status = [j[1] for j in building]
  full_building_results[s] = floor_status.count('full')
  
  # goat statistics
  goat_status = [i[1] for i in goats]
  stuck_goat_results[s] = goat_status.count('stuck on roof!')
  happy_goat_results[s] = goat_status.count('happy in room')
  satisfied_goat_results[s] = goat_status.count('occupying room')

print("Full building probability:", (full_building_results.count(10)/sims))
print("Stuck goat mean:", numpy.mean(stuck_goat_results))
print("Happy goat mean:", numpy.mean(happy_goat_results))
print("Satisfied goat mean:", numpy.mean(satisfied_goat_results))

As mentioned, only approximately 23.6% of the time was the building full. On average, about $\frac{4}{3}$ goats were stuck, $\frac{17}{3}$ found the home they were happiest with, and $3$ found a home that wasn’t their first preference. Sounds like this town should reform its zoning.