Riddler Express - 2/11/2022

trapezoidal.py

# please don't crucify me for this brutally inefficient method

import collections


def first_nth_trapezoidal(n):
    tz = collections.defaultdict(list)
    for i in range(1, 1001):
        for j in range(i + 1, 1001):
            candidate = list(range(i, j))
            if len(candidate) > 1:
                tz[sum(range(i, j))].append(candidate)
    key = min([k for k in tz if len(tz[k]) == n])
    print(f"First trapezoidal number of cardinality {n} is {key}: {tz[key]}")

    
# >>> for i in range(3, 7):
# ...     first_nth_trapezoidal(i)
# ...
# First trapezoidal number of cardinality 3 is 15: [[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]]
# First trapezoidal number of cardinality 4 is 81: [[5, 6, 7, 8, 9, 10, 11, 12, 13], [11, 12, 13, 14, 15, 16], [26, 27, 28], [40, 41]]
# First trapezoidal number of cardinality 5 is 45: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [5, 6, 7, 8, 9, 10], [7, 8, 9, 10, 11], [14, 15, 16], [22, 23]]
# First trapezoidal number of cardinality 6 is 729: [[14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40], [32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49], [77, 78, 79, 80, 81, 82, 83, 84, 85], [119, 120, 121, 122, 123, 124], [242, 243, 244], [364, 365]]

NOTE: I noticed in reducing my initial upper bound from 1001 to 101, I introduced a bug that caused candidate lists containing values greater than 100 to not appear, thus I incorrectly submitted an answer to the extra credit of 105 as the first sextuply trapezoidal number, when the correct answer is 729