Задачи №1-№20

Задача №1

Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.

Найдите сумму всех чисел меньше 1000, кратных 3 или 5.

Алгоритм:

Метод getSumOfNumbersDividedBy3Or5 вычисляет сумму всех чисел, меньших n, которые делятся на 3 или 5.

Он делит работу на три части:

getSumOfNumbersLessThanNDividedByK(n, 3) - вычисляет сумму всех чисел, меньших n, которые делятся на 3.
getSumOfNumbersLessThanNDividedByK(n, 5) - вычисляет сумму всех чисел, меньших n, которые делятся на 5.
getSumOfNumbersLessThanNDividedByK(n, 3 * 5) - вычисляет сумму всех чисел, меньших n, которые делятся на 15 (то есть на 3 и 5 одновременно).

Затем он складывает суммы первых двух и вычитает сумму третьей, чтобы избежать двойного подсчета чисел, которые делятся на 3 и 5 одновременно.

Метод getSumOfNumbersLessThanNDividedByK вычисляет сумму всех чисел, меньших n, которые делятся на k. Он использует формулу арифметической прогрессии для вычисления суммы.

Код:

def getSumOfNumbersDividedBy3Or5(n: Int): Long =
  val sum3  = getSumOfNumbersLessThanNDividedByK(n, 3)
  val sum5  = getSumOfNumbersLessThanNDividedByK(n, 5)
  val sum15 = getSumOfNumbersLessThanNDividedByK(n, 3 * 5)
  sum3 + sum5 - sum15

private def getSumOfNumbersLessThanNDividedByK(n: Long, k: Long): Long =
  val l = (n - 1) / k
  k * l * (l + 1) / 2
  
getSumOfNumbersDividedBy3Or5(10) // 23

Задача №2

Задача №2 - Even Fibonacci Numbers

Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2, первые 10 элементов будут:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Найдите сумму всех четных элементов ряда Фибоначчи, не превышающих четырех миллионов.

Алгоритм:

Метод count реализует алгоритм для вычисления суммы четных чисел Фибоначчи, которые не превышают 4000000.

Внутри метода count определен метод loop, который является рекурсивным и использует аннотацию @tailrec, что означает, что он является хвостовым (tail recursive), что позволяет компилятору оптимизировать его так, чтобы не было проблем с использованием большого количества рекурсивных вызовов.

Аргументы метода loop:

a - первое число в последовательности Фибоначчи.
b - второе число в последовательности Фибоначчи.
sum - сумма четных чисел Фибоначчи.

Внутри метода loop есть условный оператор if, который проверяет следующие условия:

Если b больше 4000000, то метод возвращает sum.
Если b четное число, то метод вызывает сам себя с обновленными значениями a, b и sum. Здесь a принимает значение b, b принимает значение a + b (следующее число в последовательности Фибоначчи), и sum увеличивается на b (текущее четное число Фибоначчи).
Если b нечетное число, то метод вызывает сам себя с обновленными значениями a и b, но sum остается без изменений.

Код:

def count(): Long =
  @tailrec
  def loop(a: Long, b: Long, sum: Long): Long =
    if b > 4000000 then sum
    else if b % 2 == 0 then loop(b, a + b, sum + b)
    else loop(b, a + b, sum)

  loop(1, 2, 0)

Задача №3

Задача №3 - Largest Prime Factor

Простые делители числа 13195 - это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143, являющийся простым числом?

Алгоритм:

Метод largestPrimeFactor возвращает самый большой простой множитель числа n.

Внутри метода largestPrimeFactor определен метод loop, который является рекурсивным.

Аргументы метода loop:

number - число, для которого ищется самый большой простой множитель.
i - текущий множитель.
max - самый большой найденный простой множитель.

Внутри метода loop есть условный оператор if, который проверяет следующие условия:

Если i * i больше number, то метод возвращает максимум из number и max. Это означает, что мы достигли конца проверки и number, если он больше 1, сам является простым числом, которое может быть его самым большим простым множителем.
Если number делится на i без остатка, то метод вызывает сам себя со следующими значениями number, i и max: number делится на i, i остается неизменным (number / i тоже может делиться на i), и max принимает значение i (текущий простой множитель).
Если number не делится на i, то метод вызывает сам себя с неизменёнными значениями number и max. i увеличивается на 1, чтобы проверить следующий множитель.

Код:

def largestPrimeFactor(n: Long): Long =
  @tailrec
  def loop(number: Long, i: Long, max: Long): Long =
    if i * i > number then math.max(number, max)
    else if number % i == 0 then loop(number / i, i, i)
    else loop(number, i + 1, max)

  loop(n, 2, 1)
  
largestPrimeFactor(13195L) // 29

Задача №4

Задача №4 - Largest Palindrome Product

Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел – 9009 = 91 × 99.

Найдите самый большой палиндром, полученный умножением двух трехзначных чисел.

Алгоритм:

getLargestPalindrome(n: Int): Int: Метод находит самый большой палиндром, который является произведением двух n-значных чисел.
- Он начинает с вычисления начального и конечного чисел, которые могут быть n-значными. Например, если n равно 2, то начальное число будет 10 (\(10^{1}\)) и конечное число будет 99 (\(10^{2} - 1\)).
- Затем он использует двойной цикл for для перебора всех возможных произведений двух n-значных чисел и проверяет, является ли произведение палиндромом с помощью метода isPalindrome.
- Все найденные палиндромы сохраняются в списке palindromes.
- Наконец, возвращает максимальное значение из списка palindromes.
isPalindrome(number: Long): Boolean: Метод проверяет, является ли число палиндромом.
- Если число равно 0, то оно является палиндромом.
- Если число больше 0 и последняя цифра не равна 0, то метод использует рекурсивную функцию loop для проверки, является ли число палиндромом.
- Внутри loop, если k (остаток числа) меньше или равен reverted (перевернутое число), то метод проверяет, равны ли k и reverted (случай четного количества цифр в проверяемом числе) или k и reverted без последней цифры (случай нечетного количества цифр в проверяемом числе). Если это так, то число является палиндромом.
- Если k больше reverted, то метод вызывает сам себя с обновленными значениями k и reverted. k делится на 10, reverted умножается на 10 и добавляется последняя цифра k.

Код:

def getLargestPalindrome(n: Int): Int =
  val start  = math.pow(10, n - 1).toInt
  val finish = math.pow(10, n).toInt - 1

  val palindromes =
    for
      i <- start to finish
      j <- i to finish
      if isPalindrome(i * j)
    yield i * j

  palindromes.max

def isPalindrome(number: Long): Boolean =
  number == 0 || number > 0 && number % 10 != 0 && {
    @tailrec
    def loop(k: Long, reverted: Long): Boolean =
      if k <= reverted then
        k == reverted || k == reverted / 10
      else
        loop(k / 10, reverted * 10 + k % 10)

    loop(number, 0)
  }
    
getLargestPalindrome(2) // 9009

Задача №5

Задача №5 - Smallest Multiple

2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.

Какое самое маленькое число делится нацело на все числа от 1 до 20?

Алгоритм:

Методы предназначены для нахождения наименьшего числа, которое делится без остатка на все числа от 1 до n.

getSmallestNumberWhichDivisibleByRange(n: Int): Long - этот метод находит наименьшее число, которое делится без остатка на все числа от 1 до n. Он использует функцию foldLeft для обхода всех чисел от 2 до n и нахождения их наименьшего общего кратного (НОК).
primeFactorsWithPow(n: Long): Map[Long, Int] - метод находит простые множители числа n и их степени. Он использует хвостовую рекурсивную функцию loop для поиска множителей.

Работа метода primeFactorsWithPow следующая:

Метод определяет внутри себя функцию loop, которая принимает три аргумента: n - число, для которого ищутся простые множители, i - текущий множитель, с которого начинается поиск, и acc - аккумулирующий ассоциативный массив, в котором хранятся найденные множители и их степени.
Внутри функции loop есть условия для выхода из рекурсии:
- Если i * i больше n, то проверяется, равно ли n единице. Если равно, то возвращается acc. Если не равно, то n добавляется в ассоциативный массив со степенью на 1 больше, чем n в него входит.
- Если n делится на i без остатка, то на следующей итерации делим n на i, i не меняется и i добавляется в ассоциативный массив со степенью на 1 больше, чем текущее вхождение.
- Если ни одно из условий не выполнено, то i увеличивается на единицу и функция вызывает саму себя с обновленными аргументами.
После определения функции loop, она вызывается с начальными аргументами: n - само число, i - 2 (первый простой множитель), и acc - пустая карта.

Код:

def getSmallestNumberWhichDivisibleByRange(n: Int): Long =
  (2 to n)
    .foldLeft(Map.empty[Long, Int]) { case (acc, i) =>
      val number = primeFactorsWithPow(i)
      val keys   = acc.keySet.union(number.keySet)
      keys.map { key =>
        key -> math.max(acc.getOrElse(key, 0), number.getOrElse(key, 0))
      }.toMap
    }
    .foldLeft(1L) { case (acc, (m, p)) => acc * math.pow(m, p).toLong }

def primeFactorsWithPow(n: Long): Map[Long, Int] =
  @tailrec
  def loop(n: Long, i: Long, acc: Map[Long, Int]): Map[Long, Int] =
    if i * i > n then
      if n == 1 then acc else acc + (n -> (acc.getOrElse(n, 0) + 1))
    else if n % i == 0 then loop(n / i, i, acc + (i -> (acc.getOrElse(i, 0) + 1)))
    else loop(n, i + 1, acc)

  loop(n, 2, Map.empty[Long, Int])

getSmallestNumberWhichDivisibleByRange(10) // 2520

Задача №6

Задача №6 - Sum Square Difference

Сумма квадратов первых десяти натуральных чисел равна \(1^{2} + 2^{2} + ... + 10^{2} = 385\).

Квадрат суммы первых десяти натуральных чисел равен \((1 + 2 + ... + 10)^{2} = 55^{2} = 3025\).

Следовательно, разность между суммой квадратов и квадратом суммы первых десяти натуральных чисел составляет 3025 − 385 = 2640.

Найдите разность между суммой квадратов и квадратом суммы первых ста натуральных чисел.

Алгоритм:

Метод getDifference(n: Int): Long вычисляет разницу между квадратом суммы первых n натуральных чисел и суммой квадратов этих чисел. Для начала, метод вычисляет сумму первых n натуральных чисел с помощью формулы арифметической прогрессии sum = n * (n + 1) / 2. Затем метод вычисляет сумму квадратов первых n натуральных чисел с помощью формулы n * (n + 1) * (2 * n + 1) / 6. Наконец, метод возвращает разницу между квадратом суммы и суммой квадратов.

Код:

def getDifference(n: Int): Long =
  val sum = n * (n + 1) / 2
  sum * sum - (n * (n + 1) * (2 * n + 1) / 6)
  
getDifference(10) // 2640

Задача №7

Задача №7 - 10001st Prime

Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-е простое число - 13.

Какое число является 10001-м простым числом?

Алгоритм:

Следующий код создает ленивый список простых чисел и извлекает из него первые 10001 простых чисел.

lazy val lazyPrimes: LazyList[Int] = ... - определение ленивой переменной lazyPrimes, которая представляет собой ленивый список целых чисел.
2 #:: LazyList.from(3) - создание ленивого списка, который начинается с числа 2, за которым следует ленивый список чисел, начиная с 3.
.filter: x => ... - фильтрация ленивого списка. Функция проверяет каждое число x, чтобы увидеть, является ли оно простым.
val sqrtOfPrimes = lazyPrimes.takeWhile(p => p <= math.sqrt(x)) - создание нового ленивого списка sqrtOfPrimes, который содержит все простые числа, меньшие или равные квадратному корню из x.
sqrtOfPrimes.forall(p => x % p != 0) - проверка, что x не делится на ни одно из простых чисел, которые меньше или равны его квадратному корню. Если x не делится на ни одно из этих чисел, то оно является простым, и фильтр возвращает true.
val primes = lazyPrimes.take(10001).toVector - извлечение первых 10001 простых чисел в виде вектора. Индексация начинается с 0, поэтому 10001-е простое число доступно по primes(10000).

Код:

lazy val lazyPrimes: LazyList[Int] =
  2 #:: LazyList
    .from(3)
    .filter: x =>
      val sqrtOfPrimes = lazyPrimes.takeWhile(p => p <= math.sqrt(x))
      sqrtOfPrimes.forall(p => x % p != 0)
      
val primes = lazyPrimes.take(10001).toVector

primes(5) // 13

Задача №8

Задача №8 - Largest Product in a Series

Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9*9*8*9=5832.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

Найдите наибольшее произведение тринадцати последовательных цифр в данном числе.

Алгоритм:

def getLargestProduct(number: String, count: Int): Long = ... - определение функции getLargestProduct, которая принимает строку number и целое число count, и возвращает наибольшее произведение count последовательных цифр в number.
number.split("0") - разбиение строки number на подстроки по 0. Для того чтобы исключить из рассмотрения подстроки, содержащие нули (в них значение продукта равно 0).
.map(getLargestProductWithoutZero(_, count, 0)) - применение функции getLargestProductWithoutZero к каждой подстроке, полученной в результате разбиения.
getLargestProductWithoutZero(number: String, count: Int, max: Long): Long = ... - определение функции getLargestProductWithoutZero, которая принимает строку number (без нулей), целое число count и текущее максимальное значение max, и возвращает наибольшее произведение count последовательных цифр в number.
if number.length < count then ... - если длина number меньше count, то функция возвращает 0. Нет count последовательных цифр в number.
else if number.length == count then ... - если длина number равна count, то функция возвращает произведение всех цифр в number - есть только один вариант count последовательных цифр в number.
else ... - в противном случае функция вычисляет произведение первых count цифр в number, обновляет max, если это значение больше текущего max, и вызывает саму себя с number без первой цифры и обновленным max.

В результате выполнения этого кода функция getLargestProduct вернет наибольшее произведение count последовательных цифр в number, игнорируя подстроки, содержащие нули.

Код:

val number =
  "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

def getLargestProduct(number: String, count: Int): Long =
  number
    .split("0")
    .map(getLargestProductWithoutZero(_, count, 0))
    .max

@tailrec
def getLargestProductWithoutZero(
    number: String,
    count: Int,
    max: Long
): Long =
  if number.length < count then 0
  else if number.length == count then
    number.map(_.getNumericValue.toLong).product
  else
    val first  = number.take(count).map(_.getNumericValue.toLong).product
    val newMax = math.max(max, first)
    getLargestProductWithoutZero(number.tail, count, newMax)
    

getLargestProduct(number, 4) // 5832

Задача №9

Задача №9 - Special Pythagorean Triplet

Тройка Пифагора - три натуральных числа a < b < c, для которых выполняется равенство \(a^{2} + b^{2} = c^{2}\).

Например, \(3^{2} + 4^{2} = 9 + 16 = 25 = 5^{2}\).

Существует только одна тройка Пифагора, для которой a + b + c = 1000. Найдите произведение abc.

Алгоритм:

Метод pythagoreanTripletsWithGivenSum принимает на вход параметр sum - сумма трёх чисел, которые должны быть частью Пифагоровой тройки. Если sum нечетное, то метод возвращает пустой список (из-за свойства: В точности одно из чисел a и b нечётно, c всегда нечётно). В противном случае, метод ищет все тройки чисел a, b и c, которые удовлетворяют условиям Пифагоровой тройки (\(a^{2} + b^{2} = c^{2}\)) и сумме \(a + b + c = sum\).

Также, он использует генераторы для поиска всех возможных троек чисел, которые удовлетворяют условиям. Генератор a <- 3L to ((sum - 3) / 3) перебирает все возможные значения a в диапазоне от 3 до (sum - 3) / 3. Затем, для каждого a, генератор b <- (a + 1) to ((sum - a - 1) / 2) перебирает все возможные значения b в диапазоне от a + 1 до (sum - a - 1) / 2. И наконец, c вычисляется как sum - a - b.

Если a, b и c удовлетворяют условиям Пифагоровой тройки, то они добавляются в результирующую последовательность.

Этот метод эффективен только на небольших значениях сумм. Более эффективный метод приведен в пояснении к задаче или на странице "Последовательности" раздела "Алгоритмы".

Код:

case class PythagoreanTriplet(a: Long, b: Long, c: Long)

def pythagoreanTripletsWithGivenSum(sum: Long)
    : IndexedSeq[PythagoreanTriplet] =
  if sum % 2 == 1 then IndexedSeq.empty
  else
    for
      a <- 3L to ((sum - 3) / 3)
      b <- (a + 1) to ((sum - a - 1) / 2)
      c = sum - a - b
      if a * a + b * b == c * c
    yield PythagoreanTriplet(a, b, c)

Задача №10

Задача №10 - Summation of Primes

Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел меньше двух миллионов.

Алгоритм:

sieveOfEratosthenes - реализует алгоритм "Решето Эратосфена" для нахождения всех простых чисел до заданного числа n. Алгоритм работает следующим образом:
- Создается булевый массив result размером n + 1, где каждый элемент инициализируется как true, что означает, что все числа считаются простыми, пока не будут выявлены как составные.
- Числа 0 и 1 по определению не являются простыми, поэтому их значение в массиве result меняется на false.
- Затем происходит обработка четных чисел, начиная с 4, и все числа, кратные 2, также помечаются как составные, устанавливая соответствующие элементы массива result в false.
- Далее алгоритм перебирает все нечетные числа от 3 до квадратного корня из n, и если число является простым (result(i) равно true), то все его кратные помечаются как составные.
- В конце метод возвращает полученный массив result, где true означает, что число простое.
getSumOfPrimes - использует метод sieveOfEratosthenes для получения массива простых чисел до заданного предела limit, затем суммирует все простые числа в этом диапазоне.

Код:

def getSumOfPrimes(limit: Int): Long =
  val primes = sieveOfEratosthenes(limit)
  primes.indices.foldLeft(0L)((acc, i) => if primes(i) then acc + i else acc)

def sieveOfEratosthenes(n: Int): Array[Boolean] =
  val result = Array.fill(n + 1)(true)
  result(0) = false
  result(1) = false
  (4 to n by 2).foreach: j =>
    result(j) = false
  for
    i <- 3 to math.sqrt(n).toInt by 2
    if result(i)
    j <- i to n / i
  do
    result(j * i) = false
  result

getSumOfPrimes(10) // 17

Задача №11

Задача №11 - Largest Product in a Grid

В таблице 20×20 (внизу) четыре числа на одной диагонали выделены жирным.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

Произведение этих чисел 26 * 63 * 78 * 14 = 1788696.

Каково наибольшее произведение четырех подряд идущих чисел в таблице 20×20, расположенных в любом направлении (вверх, вниз, вправо, влево или по диагонали)?

Алгоритм:

Загружаем матрицу из строки, представляющей собой сетку чисел, разделенных пробелами и переносом строк.
Определяем размеры матрицы (количество строк и столбцов).
Определяем функцию maxFourProduct, которая находит максимальное произведение четырех последовательных чисел в последовательности. Эта функция использует хвостовую рекурсию для последовательного уменьшения размера последовательности и поиска максимального произведения.
Находит максимальное произведение четырех последовательных чисел в каждой строке матрицы.
Находит максимальное произведение четырех последовательных чисел в каждом столбце матрицы.
Находит максимальное произведение четырех последовательных чисел в каждой диагонали матрицы.
Находит максимальное произведение четырех последовательных чисел в каждой обратной диагонали матрицы.
Находит максимальное значение из всех найденных максимумов.

В результате, код находит максимальное произведение четырех последовательных чисел в любом направлении (горизонтально, вертикально или по диагонали) в заданной матрице.

Код:

val source =
  "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"
val matrix: Array[Array[Int]] =
  source.split("\n").map(_.split(" ").map(_.toInt))

val m: Int = matrix.length
val n: Int = matrix.head.length

@tailrec
def maxFourProduct(row: Seq[Int], max: Int = 0): Int =
  if row.length < 4 then max
  else maxFourProduct(row.tail, math.max(row.take(4).product, max))

val maxInRows = matrix.map(maxFourProduct(_)).max

val columns =
  (0 until n).map(j => (0 until m).map(i => matrix(i)(j)))
val maxInColumns = columns.map(maxFourProduct(_)).max

val diagonals =
  (0 until n).map(j => (0 until (n - j)).map(i => matrix(i)(j + i))) ++
    (1 until m).map(i => (0 until (m - i)).map(j => matrix(i + j)(j)))
val maxInDigs = diagonals.map(maxFourProduct(_)).max

val oppDiagonals =
  (0 until n).map(j => (0 to j).map(i => matrix(i)(j - i))) ++
    (1 until m).map(i =>
      ((n - 1) to (i + n - m) by -1).map(j => matrix(i + n - 1 - j)(j))
    )
val maxInOppDigs = oppDiagonals.map(maxFourProduct(_)).max

val maxInMatrix =
  math.max(
    math.max(maxInRows, maxInColumns),
    math.max(maxInDigs, maxInOppDigs)
  )

Задача №12

Задача №12 - Highly Divisible Triangular Number

Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-е треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Перечислим делители первых семи треугольных чисел:

1: 1

3: 1, 3

6: 1, 2, 3, 6

10: 1, 2, 5, 10

15: 1, 3, 5, 15

21: 1, 3, 7, 21

28: 1, 2, 4, 7, 14, 28

Как мы видим, 28 - первое треугольное число, у которого более пяти делителей.

Каково первое треугольное число, у которого более пятисот делителей?

Алгоритм:

getFirstTriangleNumbersWithBigCountOfDivisors(limit: Int): Long - метод находит первое треугольное число, имеющее больше делителей, чем заданный предел. Метод использует хвостовую рекурсию для последовательного вычисления треугольных чисел и проверки их на количество делителей.
triangleNumber(n: Long): Long - метод вычисляет n-ое треугольное число, используя формулу n * (n + 1) / 2.
countOfDivisors(number: Long): Long - метод вычисляет количество делителей заданного числа. Он использует метод primeFactorsWithPow для получения простых множителей числа и затем считает количество делителей, используя формулу количество делителей равно произведению всех (a + 1), где a - степень каждого простого множителя в разложении числа.
primeFactorsWithPow(n: Long): Map[Long, Int] - описание метода приведено в описании алгоритма Problem 5.

Код:

def getFirstTriangleNumbersWithBigCountOfDivisors(limit: Int): Long =
  @tailrec
  def loop(i: Int): Long =
    val t     = triangleNumber(i)
    val count = countOfDivisors(t)
    if count > limit then t else loop(i + 1)

  loop(1)

def triangleNumber(n: Long): Long = n * (n + 1) / 2

def countOfDivisors(number: Long): Long =
  primeFactorsWithPow(number).values.foldLeft(1L): (mul, a) =>
    mul * (a + 1)

def primeFactorsWithPow(n: Long): Map[Long, Int] =
  @tailrec
  def loop(n: Long, i: Long, acc: Map[Long, Int]): Map[Long, Int] =
    if i * i > n then
      if n == 1 then acc else acc + (n -> (acc.getOrElse(n, 0) + 1))
    else if n                           % i == 0 then
      loop(n / i, i, acc + (i -> (acc.getOrElse(i, 0) + 1)))
    else loop(n, i + 1, acc)

  loop(n, 2, Map.empty[Long, Int])
  
getFirstTriangleNumbersWithBigCountOfDivisors(5) // 28

Задача №13

Задача №13 - Large Sum

Найдите первые десять цифр суммы следующих ста 50-значных чисел.

37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 ...

Алгоритм:

Строка numbers содержит длинную строку чисел, разбитую на строки длиной 50 символов.
Метод split("\n") разделяет строку на отдельные строки по символу новой строки \n.
Каждая строка преобразуется в BigInt, чтобы избежать проблем с переполнением при суммировании больших чисел.
Сумма всех чисел вычисляется с помощью метода sum.

Код:

val numbers = "37107287533902102798797998220837590246510135740250\n46376937677490009712648124896970078050417018260538\n..."

val count = numbers
  .split("\n")
  .withFilter(_.nonEmpty)
  .map(num => BigInt(num))
  .sum

Задача №14

Задача №14 - Longest Collatz Sequence

Следующая повторяющаяся последовательность определена для множества натуральных чисел:

\(n \to n/2\) (n - четное)

\(n \to 3n + 1\) (n - нечетное)

Используя описанное выше правило и начиная с 13, сгенерируется следующая последовательность: \(13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.\)

Получившаяся последовательность (начиная с 13 и заканчивая 1) содержит 10 элементов. Хотя это до сих пор и не доказано (проблема Коллатца (Collatz)), предполагается, что все сгенерированные таким образом последовательности оканчиваются на 1.

Какой начальный элемент меньше миллиона генерирует самую длинную последовательность?

Примечание: Следующие за первым элементы последовательности могут быть больше миллиона.

Алгоритм:

Следующий код реализует алгоритм для вычисления длины последовательности Коллатца для заданного числа.

Определяется final case class CollatzNumber(cacheLimit: Int), который принимает один параметр cacheLimit - максимальное число, для которого будет вычисляться последовательность Коллатца.
Внутри класса создается массив cache для кэширования уже вычисленных длин последовательностей Коллатца.
В методе collatz(n: Long) проверяется, есть ли уже вычисленное значение для числа n в кэше. Если n больше или равно cacheLimit, то вычисляется последовательность Коллатца для n. Если n меньше cacheLimit, то проверяется, есть ли уже вычисленное значение в кэше. Если его нет, то вычисляется и сохраняется в кэш.
В методе nextCollatz(n: Long) вычисляется следующее число в последовательности Коллатца для n. Если n четное, то следующим числом будет n / 2, иначе - (3 * n + 1) / 2 (перепрыгиваем через шаг, т.к. 3 * n + 1 - четное для нечетного n).

В итоге, код вычисляет длину последовательности Коллатца для числа 13, используя кэширование для уменьшения количества повторных вычислений.

Код:

final case class CollatzNumber(cacheLimit: Int):
  private val cache: Array[BigInt] = new Array[BigInt](cacheLimit)
  cache(1) = BigInt(1L)

  def collatz(n: Long): BigInt =
    if n >= cacheLimit then nextCollatz(n)
    else
      val m = n.toInt
      if Option(cache(m)).isEmpty then cache(m) = nextCollatz(n)
      cache(m)

  private def nextCollatz(n: Long): BigInt =
    if n % 2 == 0 then collatz(n / 2) + 1
    else collatz((3 * n + 1) / 2) + 2
      
val collatzNumber = CollatzNumber(1000000)
collatzNumber.collatz(13) // 10

Задача №15

Задача №15 - Lattice Paths

Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего угла сетки.

Сколько существует таких маршрутов в сетке 20×20?

Алгоритм:

Метод getGridRoads(n: Int) вычисляет количество возможных путей из верхнего левого угла сетки до нижнего правого угла сетки, которая представляет собой квадрат размера n x n.

Создается двумерный массив grid размера (n + 1) x (n + 1), где n - размер сетки.
Все элементы последней строки и последнего столбца массива grid инициализируются значением 1, так как из них в нижний правый угол можно попасть только в одном направлении - вправо или вниз.
Для каждой ячейки, находящейся выше последней строки и левее последнего столбца, вычисляется количество путей, которыми можно добраться из неё до цели, как сумма количества путей ячеек, расположенных справа и снизу от текущей.
В конце метода возвращается количество путей из верхнего левого угла сетки до нижнего правого угла.

Код:

def getGridRoads(n: Int): Long =
  val grid = new Array[Array[Long]](n + 1)
  grid.indices.foreach(i => grid(i) = new Array[Long](n + 1))
  for
    j <- n to 0 by -1
  do
    grid(n)(j) = 1
    grid(j)(n) = 1
  for
    i <- n - 1 to 0 by -1
    j <- n - 1 to 0 by -1
  do
    grid(i)(j) = grid(i + 1)(j) + grid(i)(j + 1)
  grid(0)(0)
    
getGridRoads(2) // 6

Задача №16

Задача №16 - Power Digit Sum

\(2^{15} = 32768\) сумма цифр этого числа равна 3 + 2 + 7 + 6 + 8 = 26. Какова сумма цифр числа \(2^{1000}\)?

Алгоритм:

Код:

val count = BigInt(2).pow(1000).toString.map(_.getNumericValue).sum

Задача №17

Задача №17 - Number Letter Counts

Если записать числа от 1 до 5 английскими словами (one, two, three, four, five), то используется всего 3 + 3 + 5 + 4 + 4 = 19 букв.

Сколько букв понадобится для записи всех чисел от 1 до 1000 (one thousand) включительно?

Примечание: Не считайте пробелы и дефисы. Например, число 342 (three hundred and forty-two) состоит из 23 букв, число 115 (one hundred and fifteen) - из 20 букв. Использование "and" при записи чисел соответствует правилам британского английского.

Алгоритм:

Следующий код представляет собой объект NumbersDescription, преобразующий числа в их текстовое описание на английском языке.

Объект NumbersDescription содержит следующие компоненты:

private val hundred: Long, ..., private val trillion: Long - константы, представляющие собой разные величины чисел.
def inEnglish(number: Long): Option[String] - метод, который преобразует число в его текстовое описание.
private def constructEnglish(n: Long, base: Long): Option[String] - вспомогательный метод, который используется для создания текстового описания чисел в диапазоне от 1 до 999, умноженного на основание (тысяча, миллион и т.д.).
private def toBasicEnglishNumbers(n: Long): Option[String] - метод, который преобразует числа от 0 до 999 в их текстовые эквиваленты.

Код:

object NumbersDescription:
  private val hundred: Long     = 100
  private val thousand: Long    = 1000
  private val million: Long     = 1000000
  private val billion: Long     = million * thousand
  private val trillion: Long    = billion * thousand
  private val quadrillion: Long = trillion * thousand

  def inEnglish(number: Long): Option[String] =
    number match
      case n if n < 21 || (n < hundred && n % 10 == 0) =>
        toBasicEnglishNumbers(n)
      case n if n < hundred && n % 10 > 0 =>
        for
          f <- toBasicEnglishNumbers((n / 10) * 10)
          r <- toBasicEnglishNumbers(n % 10)
        yield s"$f-$r"
      case n if n < thousand    => constructEnglish(n, hundred)
      case n if n < million     => constructEnglish(n, thousand)
      case n if n < billion     => constructEnglish(n, million)
      case n if n < trillion    => constructEnglish(n, billion)
      case n if n < quadrillion => constructEnglish(n, trillion)
      case _                    => None

  private def constructEnglish(n: Long, base: Long): Option[String] =
    val rest = n % base
    val restText =
      if rest == 0 then Some("")
      else if base == hundred then inEnglish(rest).map(n => s" and $n")
      else inEnglish(rest).map(n => s" $n")
    for
      f  <- inEnglish(n / base)
      s  <- toBasicEnglishNumbers(base)
      th <- restText
    yield s"$f $s$th"

  private def toBasicEnglishNumbers(n: Long): Option[String] =
    n match
      case 0              => Some("")
      case 1              => Some("one")
      case 2              => Some("two")
      case 3              => Some("three")
      case 4              => Some("four")
      case 5              => Some("five")
      case 6              => Some("six")
      case 7              => Some("seven")
      case 8              => Some("eight")
      case 9              => Some("nine")
      case 10             => Some("ten")
      case 11             => Some("eleven")
      case 12             => Some("twelve")
      case 13             => Some("thirteen")
      case 14             => Some("fourteen")
      case 15             => Some("fifteen")
      case 16             => Some("sixteen")
      case 17             => Some("seventeen")
      case 18             => Some("eighteen")
      case 19             => Some("nineteen")
      case 20             => Some("twenty")
      case 30             => Some("thirty")
      case 40             => Some("forty")
      case 50             => Some("fifty")
      case 60             => Some("sixty")
      case 70             => Some("seventy")
      case 80             => Some("eighty")
      case 90             => Some("ninety")
      case 100            => Some("hundred")
      case 1000           => Some("thousand")
      case 1000000        => Some("million")
      case 1000000000     => Some("billion")
      case 1000000000000L => Some("trillion")
      case _              => None
end NumbersDescription

val count = (1 to 1000).flatMap(i => inEnglish(i)).map(_.count(_.isLetter)).sum

Задача №18

Задача №18 - Maximum Path Sum I

Начиная в вершине треугольника (см. пример ниже) и перемещаясь вниз на смежные числа, максимальная сумма до основания составляет 23.

3

7 4

2 4 6

8 5 9 3

То есть, 3 + 7 + 4 + 9 = 23.

Найдите максимальную сумму пути от вершины до основания следующего треугольника:

75

95 64

17 47 82

18 35 87 10

20 04 82 47 65

19 01 23 75 03 34

88 02 77 73 07 63 67

99 65 04 28 06 16 70 92

41 41 26 56 83 40 80 70 33

41 48 72 33 47 32 37 16 94 29

53 71 44 65 25 43 91 52 97 51 14

70 11 33 28 77 73 17 78 39 68 17 57

91 71 52 38 17 14 91 43 58 50 27 29 48

63 66 04 68 89 53 67 30 73 16 69 87 40 31

04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Алгоритм:

def calculateMaxRoad(triangle: Array[Array[Long]]): Long - метод вычисляет максимальную сумму пути от вершины треугольника до основания. Он проходит по треугольнику снизу вверх, начиная с предпоследней строки, и для каждого числа в строке выбирает максимальное из двух возможных чисел ниже (слева и справа) и добавляет его к текущему числу. Это позволяет накапливать максимальную сумму для каждого числа на пути от вершины к основанию.

Код:

def toTriangle(source: String): Array[Array[Long]] =
  source.split("\n").map(_.split(" ").map(_.toLong))

def calculateMaxRoad(triangle: Array[Array[Long]]): Long =
  for
    i <- triangle.length - 2 to 0 by -1
  do
    triangle(i).indices.foreach: j =>
      triangle(i)(j) += math.max(triangle(i + 1)(j), triangle(i + 1)(j + 1))

  triangle(0)(0)

val simpleTriangle = "3\n7 4\n2 4 6\n8 5 9 3"
calculateMaxRoad(toTriangle(simpleTriangle)) // 23

Задача №19

Задача №19 - Counting Sundays

Дана следующая информация (однако, вы можете проверить ее самостоятельно):

1 января 1900 года - понедельник.

В апреле, июне, сентябре и ноябре 30 дней.

В феврале 28 дней, в високосный год - 29.

В остальных месяцах по 31 дню.

Високосный год - любой год, делящийся нацело на 4, однако последний год века (ХХ00) является високосным в том и только том случае, если делится на 400.

Сколько воскресений выпадает на первое число месяца в двадцатом веке (с 1 января 1901 года до 31 декабря 2000 года)?

Алгоритм:

isALeapYear(year: Int): Boolean - функция, которая определяет, является ли год високосным.
getDayOfMonths(year: Int, month: Int): Int - функция, которая возвращает количество дней в месяце.
DayOfWeek - перечисление, которое определяет дни недели.
getFirstSunsCount(year: Int, start: DayOfWeek): (Int, DayOfWeek) - функция, которая считает количество воскресений, которые были в первый день месяца в заданном году, начиная с заданного дня недели.
В конце кода есть блок, который использует foldLeft для подсчета количества воскресений в первый день месяца в диапазоне лет от 1901 до 2000. Результат сохраняется в переменной count.

Код:

def isALeapYear(year: Int): Boolean =
  (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0)

def getDayOfMonths(year: Int, month: Int): Int =
  month match
    case 4 | 6 | 9 | 11 => 30
    case 2              => if isALeapYear(year) then 29 else 28
    case _              => 31

enum DayOfWeek:
  case Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday

def getFirstSunsCount(year: Int, start: DayOfWeek): (Int, DayOfWeek) =
  (0 to 11).foldLeft((0, start)) { case ((acc, prev), i) =>
    val newAcc = if prev == DayOfWeek.Sunday then acc + 1 else acc
    val next =
      DayOfWeek.fromOrdinal((prev.ordinal + getDayOfMonths(year, i + 1)) % 7)
    (newAcc, next)
  }

val (_, start) = getFirstSunsCount(1900, DayOfWeek.Monday)
val (count, _) =
  (1901 to 2000).foldLeft((0, start)) { case ((acc, prev), year) =>
    val (days, nextStart) = getFirstSunsCount(year, prev)
    (acc + days, nextStart)
  }

Задача №20

Задача №20 - Factorial Digit Sum

\(n!\) означает \(n \times (n-1) \times ... \times 3 \times 2 \times 1\).

Например, \(10! = 10 \times 9 \times ... \times 3 \times 2 \times 1 = 3628800\), и сумма цифр в числе \(10!\) равна \(3 + 6 + 2 + 8 + 8 + 0 + 0 = 27\).

Найдите сумму цифр в числе \(100!\).

Алгоритм:

Следующее выражение вычисляет сумму цифр факториала числа 100.

Код:

def factorial(n: Int): BigInt =
  (2 to n).foldLeft(BigInt(1))(_ * _)
  
val count = factorial(100).toString.map(_.getNumericValue).sum

Ссылки: