I Hate Competitive Programming

Hello everyone,

Christmas is coming and everybody counts up from 1st to 25th of December. For many of us a habit that has become a cult is to eat a chocolate piece every day until the 25th of December. Other (more geeky) guys, prefer to write a bunch of code every day, instead of eating chocolates, and of course there are other guys like me, who want to do both… I know, sometimes it is very difficult to eat just one piece of chocolate, but, I can help you on that. There is no rule that you can’t have more than one Advent Calendar.

Advent Calendars

Thanks to Erick Wastl and his team, Advent of Code is a yearly programming contest existing since 2015 and please, don’t give a damn on the title of this article… I love this contest! There are beautiful scenarios with magic worlds and there is always a problem you have to solve, in order to help Santa in his difficult mission to make kids happy! But, I stand on the fact that if you really want to be competitive on some of these programming contests, you had better forget all about development principles and mess up your code. You have to crack down a handsome scenario and operate absolutely technocratically. Let’s have a look…

Puzzle description

Santa’s Reindeer need Magical Energy to deliver presents on Christmas day. They need our help on that… We have to solve 2 programming puzzles every day in order to provide them with 50 stars until 25th of December.

Summarizing the 1st day’s puzzles description

Santa’s Elves need to collect food from the jungle, a difficult mission as they need to do that on foot.

Each Elf inventories their supplies and the number of Calories for their food. In case they get hungry and need extra snacks, they should know which Elf carries the food with the most Calories. In order to avoid a mishap, Elves need to know the Total Calories of the top three Elves.

In the end, in order to get these two stars you need to answer the following questions:

1. How many Calories is the top Elf carrying?
2. How many Calories are the top three Elf carrying in total?

About input data

The input of the puzzle contains a list of food items (item Calories) for Elves. Each Elf separates their own inventory from the previous Elf’s inventory by a blank line:

Elf Inventory Example

So, in this case the Elf with the most Calories is the fourth one. Also, the sum of Calories of top three Elves is 45000 (24000 + 11000 + 10000).

Real Implementation

Looking at the puzzle’s description, a whole magic world spreads out in front of you. You can imagine a software which includes Santa, Reindeer, Elves, etc…

But, let’s focus on the real data exported by the puzzle description.

1. Santa’s Elves need to collect food
   - New class: Elf
   - Function to Elf class: collectFood()
   - Function to Elf class: releaseFood()
2. Elf inventories the number of Calories for their food
   - New class: FoodSupply
   - Elf parameter: List<FoodSupply>
3. Elf inventories the number of Calories for their food
   - FoodSupply parameter: numberOfCalories
   - Function to Elf class: calculateTotalCalories()
4. Should know which Elf carries the most Calories
   - New class: ElvesExpedition (for elf aggregated calculations)
   - ElvesExpedition parameter: List<Elf>
   - Function to ElvesExpedition class: sortElvesByTotalCalories()
5. How many calories is the top Elf carrying?
   - Function to ElvesExpedition class: calculateTopElfTotalCalories()
6. How many Calories are the top three Elves carrying in total?
   - Function to ElvesExpedition class: calculateTopThreeElvesTotalCalories()

So, in practice we can have the following class diagram:

Of course, looking at this approach we can easily think about some improvements. For example:

• Instead of calculateTopThreeElvesTotalCalories() we can have calculateTopElvesTotalCalories(numberOfElves: Integer)
• Instead of having sort functions in the Elves class, we can have a SortedList

class FoodSupply(val calories: Int)

class Elf {
  private val foodSupplies = mutableListOf<FoodSupply>()

  fun collectFood(foodSupply: FoodSupply) {
    foodSupplies.add(foodSupply)
  }

  fun releaseFood(foodSupply: FoodSupply) {
    foodSupplies.remove(foodSupply)
  }

  fun calcTotalCalories(): Int {
    return foodSupplies.sumOf { it.calories }
  }
}

class ElvesExpedition (elves: List<Elf>) {
  private val elves: List<Elf> = elves.sortedByDescending { it.calcTotalCalories() }

  fun calculateTopElfTotalCalories(): Int {
    return calculateTopElvesTotalCalories(1);
  }

  fun calculateTopElvesTotalCalories(numberOfElves: Int): Int {
    return elves.subList(0, numberOfElves).sumOf { it.calcTotalCalories() }
  }
}

And the Main code in order to run the specific example could be like:

fun main() {
  val elfList = Utils.getFileBufferedReader("input1.txt")
    .useLines { lines -> lines.fold(mutableListOf(Elf())) { elfList, line ->
      if (line.isNotEmpty()) {
        elfList.last().collectFood(FoodSupply(line.toInt()))
      } else {
        elfList.add(Elf())
      }

      elfList
    } }

  val elvesExpedition = ElvesExpedition(elfList)

  println(elvesExpedition.calculateTopElfTotalCalories())
  println(elvesExpedition.calculateTopElvesTotalCalories(3))
}

Competitive Implementation

In competitive programming you need to implement your solution quickly. In puzzle contests like that, where things should be implemented quickly, designing a software like the one that I described above doesn’t help because it needs time…

But, in competitive programming, all these beautiful scenarios are sidelined and can just be replaced by the citation of raw facts:

• Get a List of Integers
• Calculate Sums of sublists (sublists separated by empty line)
• Return the MAX value
• Return the SUM of the first three MAX values

In this case you don’t have to be accurate. You don’t have to think about classes, objects or relationships between classes and code improvements as well. Nothing like that. You just need to read the data and make the calculations. This could drive to a very quick implementation like the following:

fun main() {
  val sortedValues = Utils.getFileBufferedReader("input1.txt")
    .useLines { lines -> lines.fold(mutableListOf(0)) { acc, line ->
      if (line.isNotEmpty()) {
        acc[acc.size - 1] = acc.last() + line.toInt()
      } else {
        acc += 0
      }

      acc
    } }.sortedDescending()

  println(sortedValues[0])
  println(sortedValues[0] + sortedValues[1] + sortedValues[2])
}

This is it! Both implementations give the same result…

Conclusion

In conclusion, I would like to mention that of course development principals as well as clean and well-structured code are the key to create stable enterprise projects. As enterprise software evolves and tends to live long, maintainability and extendibility are mandatory for this case. However, another very important skill is to have a critical thinking. In the case of a code competition we need to keep things short and simple. Advent of code is a great exercise to train your critical way of thinking, extracting the information that you really need in order to simplify the puzzle and find a smart and quick solution without over-engineering your implementation.

References

Advent of code: https://adventofcode.com/
Images from Free SVG: https://freesvg.org/