A solution in Ruby to the Grand Final problem in the inaugural Codehire Cup held in September 2012 at the University of Adelaide.

In September 2012, Codehire held the inaugural Codehire Cup in Adelaide, featuring some relatively simple coding problems. Contestants could choose to use C#, Java, JavaScript, PHP, or Ruby to submit solutions through a web-based interface. Fastest contestant wins.

The Problem

The Grand Final problem read:

John meets a girl in a bar. He doesn’t know her but she’s knows him. She says that they have exactly 1 single facebook friend in common.

Write a program to help John narrow down the search for this girl. You have access to a friends graph in your input string.

You need to find all of the users that have exactly 1 friend in common with John.

Each friend is represented by a number with John’s number being 1. A connection (or friendship) is represented by two user numbers separated by a hyphen:

For example, users 1 and 2 are friends:

1-2

Use the input to find all users that have exactly 1 friend in common with John.

For example:

1-2,1-3,1-4,1-5,2-4,2-7,3-4,3-5,3-8,4-8,5-7,5-6,5-8,6-7,6-8,7-8

Should return the list of matching users in ascending order.

2,5,6

The Solution

The solution to this problem involves two simple steps. First, we parse the input string to get an array for each person containing that person’s friends. Then, we can compute the intersections of the array of John’s friends and each of the other arrays of friends using the built-in Ruby & operator, and select the people where the size of that intersection is 1.

map = Hash.new([])
input.scan /(\d+)-(\d+)/ do |a, b|
    map[a] += [b]
    map[b] += [a]
end

john = map.delete('1')
map.select! { |k, v| (v & john).size == 1 }
output << map.keys.sort.join(',')

More Codehire Cup Solutions

• Practice Challenge Solution
• Codehire Cup Preliminary Solution
• Cup Semi-final Solution
• Grand Final Solution