Christmas Story written in Scala

Mahmoud was wonderfully a wise man, he believed that he can change the world and spread love and happiness.

Every year at the end of December, he brought gifts to all couple of people who sent him their picture that expresses love, peace and gratitude.

Each couple is living at the same country and each of them should specify their unique id. It is possible that the same person existed at other pictures, this let them have pictures with each member of their family and their friends and all people who like.

Mahmoud doesn’t know in which countries every person is living but he has a magic ball that reveals magically the location of the countries, but it requires the number of distinct people who sent their pictures from each different country.

Afterwards he had to travel to every country and bring a single gift for every person, so he should be precise on counting from these pictures: the number of the different countries and the number of people who are living on each country.

Because he is very wise, he thought to make a program using Scala to solve this problem instead of computing this manually, as a first step he decomposed the problem into smaller steps:

1. Receive the pictures that contain the id of each person.
2. Compute the distinct people who are living at the same country.
3. Get the number of countries that Mahmoud should travel to, and the people who are living on each country in order to know from the magic ball which countries that he has to visit.

Data structure:

1. A person is identified by an id:

final case class Person(id: String)

Each country has its id and the people who are living there. ( Set[Person] : contains distinct people)

final case class Country(id: Long, population: Set[Person])

2. As a simple scenario, assuming that we have as an input a bench of couples: Iterator[(Person, Person)] and we want to return the countries, so the output would be: Vector[Country]

The function that we will implement is:

def getCountries(personIt: Iterator[(Person, Person)]): Vector[Country] = ???

Implementation

getCountries browses the personIt and stores the people who are living at the different countries and gather the people who are living at the same country. For example when someone A who already had pictures with different other people (they will be in a same group:group1), the person who took a picture with A will be included to group1 .

The people should be distinct we can define them in a Set[Person] and each Set[Person] describes the group of people who are living at the same country, in order to compute that we can define the following type:

type Result = Vector[Set[Person]]

Every iteration on personIt computes the result for the couple: (person1, person2) as following:

1. Lookup the group of people (in the stored result) that contains person1
2. Lookup the group of people (in the stored result) that contains person2
3. Add both of them ( person1, person2 ) to the same group with their neighbors. If they are new people they will be added as a new group of people of the vector result as new couple that are living in a new country. As a first result we will have: Vector(Set(person1, person2)) → 1 Country
4. If there is (person3, person1) , person3 will be added to the previous set because that person had a picture with a person that already exists, so we will have Vector(Set(person1, person2, person3)) → 1 Country
5. If there is new people (person4, person5) we wanna have: Vector(Set(person1, person2, person3), Set(person4, person5)) → 2 countries.

For example if person5 took a picture with person3, the result should be changed as following: Vector(Set(person1, person2, person3, person4, person5)) → 1 country

Other Example:

Example

The result should be a distinct combination. This is how could we update the result as described above:

def update(distinctCombination: Result,
           group1: Set[Person],
           group2: Set[Person],
           newPeople: Set[Person]): Result = {
  val combine = group1 ++ group2 ++ newPeople
  distinctCombination.filterNot(e => e == group1 || e == group2) :+ combine
}

• The group1 contains the people who are living at the same country as person1
• The group2 contains the people who are living at the same country as person2
• newPeople are the two people Set(person1, person2)
• combine is a set of person that will take the unique people on each set and also add the couple in case they didn’t exist in any group.
• before the combination is added to the result, we make sure to remove the group1 and group2 while they are now belong to the same family who are living at the same country that we have computed in combine.

As you see Mahmoud wanted to rely on the data type Set to remove the redundant elements. He preferred to use Functional programming and immutable data types so he implemented a recursive function that browses the iterator and builds the result on each iteration:

def loop(result: Result, personIt: Iterator[(Person, Person)]): Result = {
    if (personIt.hasNext) {
      val (person1, person2) = personIt.next()
      val set1 =
        result.find(_.contains(person1))
              .getOrElse(Set.empty[Person])
      val set2 =
        result.find(_.contains(person2))
              .getOrElse(Set.empty[Person])
      loop(Result.update(result, set1, set2, Set(person1, person2)), personIt)
    } else result
  }

Then getCountries calls the loop and build the information about each country:

def getCountries(personIt: Iterator[(Person, Person)]): Vector[Country] = {
 val result = loop(Vector.empty, personIt)
  result.zipWithIndex.map { case (r, i) => Country(i, r) }
}

Execution

You can checkout the code here

from: https://emojiisland.com/products/crystal-magic-ball-emoji-icon

At the end of December, Mahmoud take the value of:

val countries = getCountries(personIt)

Then he used the magic ball to prepare for his trip around the World.

He visited countries.size countries and gave gifts for every person:

countries.foreach(country => country.population.foreach(person => giveGift(🎁, person)))

All people were happy and grateful for the gifts and for having the nice memories, they lived in happiness and harmony. Finally Mahmoud achieved his goal and was ready to leave the universe.

Note: The first part of this story is real. Mahmoud is my grandfather, he died in 2016, he was a very wise person and he likes to see people happy and successful, he was amazing!