Сумма треугольника вниз с номерами без прайма с Swift 4

Question

Я знаю, что этот вопрос задавался ранее для разных языков программирования, и я пытался реализовать его с помощью Swift 4, но как только я отправил свой ответ, мне сказали, что мой ответ был неправильным, поэтому вот задача;

Вы получите вход TRIANGLE из файла, и вам нужно найти максимальную сумму чисел в соответствии с приведенными ниже правилами;

1. Вы начнете сверху и перейдете вниз к соседнему числу, как показано ниже.
2. Вам разрешено ходить только по диагонали.
3. Вы можете проходить только через NIM PRUME NUMBERS.

Согласно вышеприведенным правилам, максимальная сумма чисел сверху вниз в приведенном ниже примере равна 24.

var sampleString = """
                    1
                   8  4
                  2  6  9
                 8  5  9  3

Как вы можете видеть, у этого есть несколько путей, которые соответствуют правилу НЕ ПЕРВИЧНЫЕ ЧИСЛА; 1> 8> 6> 9, 1> 4> 6> 9, 1> 4> 9> 9 1 + 8 + 6 + 9 = 24. Как вы видите, 1, 8, 6, 9 - НЕ ПЕРВИЧНЫЕ ЧИСЛА, и если вы пройдете через них, вы получите максимальную сумму.

строка назначения:

var assignmentString = """
                         215
                       193 124
                      117 237 442
                    218 935 347 235
                  320 804 522 417 345
                229 601 723 835 133 124
              248 202 277 433 207 263 257
            359 464 504 528 516 716 871 182
          461 441 426 656 863 560 380 171 923
        381 348 573 533 447 632 387 176 975 449
      223 711 445 645 245 543 931 532 937 541 444
    330 131 333 928 377 733 017 778 839 168 197 197
  131 171 522 137 217 224 291 413 528 520 227 229 928
 223 626 034 683 839 53  627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"""

мой код:

func maxSumForTriangle(triangleString: String) {
    var temporaryIndex = 0
    var earlierIndex = 0
    var greatSum = 0
    var temporaryMaxInLine = 0
    let values = triangleString.components(separatedBy: .newlines).map {
        $0.components(separatedBy: .whitespaces).compactMap(Int.init)
    }
    print(values)
    print(values.count)

    for line in values {
        if line.count == 1 {
            greatSum += line[0]
            earlierIndex = line.count - 1
        } else {
            for number in line.enumerated() {
                if number.offset == earlierIndex || number.offset == earlierIndex + 1 {
                    //Check the number if its prime or not with the isPrime function we defined
                    if !isPrime(number.element) {
                        if number.element > temporaryMaxInLine {
                            temporaryMaxInLine = number.element
                            temporaryIndex = number.offset
                        }
                    }
                }
            }
            earlierIndex = temporaryIndex
            greatSum += temporaryMaxInLine
            temporaryMaxInLine = 0
        }
    }

    print(greatSum)
}

Что приводит к 7619, но потом я понял, где моя проблема; Я не проверяю все возможные пути, я просто проверяю наибольшее не простое число в каждой строке и продолжаю суммировать его.

Поэтому мне нужно найти другой подход к этой проблеме, чтобы моя функция могла проверять все возможные сценарии и возвращаться с наибольшей суммой

Я пока не могу понять, следует ли мне реализовать другую функцию, когда она снова вызывает себя, чтобы она могла проверять все возможные пути?

Извините за длинный вопрос, но я также хотел показать мою старую реализацию.

Answer 1

Это типичная проблема, которую можно решить с помощью «динамическое программирование» : идея это рассчитать максимально возможную сумму для каждый начиная точка в пирамиде.

И это становится простым, если мы начнем с нижнего ряда и продолжим вверх: Нам нужно только добавить к каждой записи больший из двух его нижних соседей. В конце, верхняя запись - желаемая максимальная сумма.

Принимая во внимание дополнительное условие о не простых числах, это может быть реализовано как

var values = triangleString.components(separatedBy: .newlines).map {
    $0.components(separatedBy: .whitespaces).compactMap(Int.init)
}

for row in values.indices.reversed() {
    for col in values[row].indices {
        if isPrime(values[row][col]) {
            values[row][col] = Int.min
        } else if row + 1 < values.endIndex {
            values[row][col] += max(values[row+1][col], values[row+1][col+1])
        }
    }
}

print(values[0][0])