Solution in Python to the HackerRank problem "Rod cutting"

hackerrank_rod_cutting.py

#
# HackerRank - Rod Cutting
#
# Given an array with the lengths of various metal rods, repeatedly perform the following:
#
#   1. Count the number of rods.
#   2. Find the rod(s) with the shortest length.
#   3. Discard any rod of that length.
#   4. Cut that shortest length from each of the longer rods. These are offcuts.
#   5. Discard all offcuts.
#   6. Repeat until there are no more rods.
# 
# Maintain an array of the numbers of rods at the beginning of each round of actions and return that array.
#
#
# Function Description
#
# Complete the function "rodOffcut".
#
# rodOffcut has the following parameter(s):
#
#    int lengths[n]: the starting lengths of each rod
#
# Returns:
#
#    int[]: the number of rods at the start of each turn
#
# Constraints
#
#    1 ≤ n ≤ 103
#    1 ≤ lengths[i] ≤ 103, where 0 ≤ i < n

import math
import os
import random
import re
import sys


def rodOffcut(lengths):
    new_lengths = lengths.copy()
    number_of_rods: List[int] = []

    while new_lengths:
        number_of_rods.append(len(new_lengths))

        cut_length = min(new_lengths)
        new_lengths = [l-cut_length for l in new_lengths if l > cut_length]

    return number_of_rods