d1000000 - Technical log

Apprentice 2022D

Overview

A straight is a list of integers x, x+1, …, x+(l−1), where l is the length of it. In this problem we have a list of N dice, every one of them with a Sn number of sides. We need to find the largest straight possible with the number of dice and with the number of sides of every one of them.

Context

The usual dice have 6 sides, a dk die has k sides, each of which shows a different integer 1 through k. For example, d6 has 6 sides (from 1 to 6), d64 has 64 sides (from 1 to 64). With this in mind, we have a collection of N dice, every “i” die is a dSi die, with Si sides from 1 to Si. The goal is to find the largest straight possible considering the number of dice and the sides of each die. As mentioned before, a straight is a list of integers x, x+1, …, x+(l−1), where l is the length of it. Having in mind the number of sides of every dice, not every die is capable to be part of the straight, because it doesn’t have enough sides to add to the straight. We are going to check it in the next section.

Solution

As mentioned before, not every die can be used in the straight because of its number of sides. For example, if we have the straight [1, 2, 3, 4], we need a die with at least 5 sides to add the number 5 to the straight. If we had a d4 die, it wouldn’t be used because it doesn’t have that 5 to continue with the straight.

With this in mind, the first step in the solution is to sort the list of dice in ascending order, this because it’s easier to the die to have enough sides to be used on the straight. Taking back the last example, maybe in the straight [1, 2, 3, 4] we are using a d5 die, that can be used as a 5 and then we can use our d4 die to take its place in the original straight and then the final straight would be [1, 2, 3, 4, 5].

In this case, in Java we have a function sort() for the Collections class, this function by default returns the list sorted in ascending order. It can be used to sort the collection in other kind of order but we don’t need that for this problem.

Starting the pseudocode:

max_length(S){
  sort(S)
}

Once the list is sorted, we start to iterate trough the length of the list, to check every dice that we have and we start to count the ones that can be used on the straight, this only asking if the number of sides from the actual die is greater than the last number in the straight, if the number is greater, the straight increases its length by 1, otherwise the straight length stays the same and we continue asking for the next die. Once we checked every dice in the list, we’ll have the final length of the largest straight possible with the list we had.

The final pseudocode would be:

max_length(S){
  sort(S)
  length = 0
  for si in s:
    if si > length: length ++
  return length
}

Alternative Solutions

Other possible solution to this problem is using the same logic but implementing a sort algorithm instead of using the function that the language give us. This in order to find a better time of execution of the program.