Swift 4实现仅经非质数的三角形向下最大路径和问题求助

Hey there! I get it—you tried implementing the maximum path sum problem (with the twist of only moving through non-primes) in Swift 4 and hit a wrong answer. Let’s break down where you might have stumbled, then build a correct, clean solution together.

First, Let’s Recap the Problem Rules #

From a triangle of numbers read from a file:

• Start at the top
• Move only down or diagonally down-right
• Only traverse non-prime numbers
• Find the maximum sum of such a path

Key Pitfalls That Cause Wrong Answers #

Before diving into code, let’s cover the most common mistakes that trip people up:

• Incorrect prime checking: Forgetting that 1 is not a prime, or mishandling edge cases like 2 (the only even prime) or small numbers.
• Bad dynamic planning setup: Either using a top-down approach that misses unreachable paths (primes block the path), or mismanaging the DP state transitions.
• File parsing errors: Mishandling whitespace, empty lines, or non-integer values in the input file.
• Ignoring unreachable paths: If a position is a prime, it can’t be part of any valid path—so its DP value should mark it as unpassable (not just 0, which would skew the sum).

Step-by-Step Swift 4 Implementation #

1. Solid Prime Checking Function #

First, let’s write a reliable isPrime(_:) function. This is critical—get this wrong, and everything else falls apart:

func isPrime(_ n: Int) -> Bool {
    guard n >= 2 else { return false } // 0, 1 are non-prime
    guard n != 2 else { return true }
    guard n % 2 != 0 else { return false } // Even numbers >2 are non-prime
    let sqrtN = Int(Double(n).squareRoot())
    for i in stride(from: 3, through: sqrtN, by: 2) {
        if n % i == 0 {
            return false
        }
    }
    return true
}

Note: This handles all edge cases correctly—1 returns false, 2 returns true, even numbers >2 are immediately rejected, and we only check odd divisors up to the square root for efficiency.

2. Parse the Input File #

Next, we need to read the triangle from a file and convert it into a 2D array of integers:

func parseTriangle(from fileURL: URL) throws -> [[Int]] {
    let content = try String(contentsOf: fileURL)
    let lines = content.components(separatedBy: .newlines)
        .filter { !$0.trimmingCharacters(in: .whitespaces).isEmpty } // Skip empty lines
    
    return lines.map { line in
        line.components(separatedBy: .whitespaces)
            .filter { !$0.isEmpty }
            .compactMap { Int($0) }
    }
}

This skips empty lines and handles any extra whitespace in each line, converting valid strings to integers.

3. Dynamic Programming (Bottom-Up Approach) #

A bottom-up DP approach is perfect here because we can build up the maximum sum starting from the bottom row, working our way up. For each non-prime number, we add the maximum sum from the two positions below it. For primes, we mark the position as unreachable with Int.min:

func maxNonPrimePathSum(in triangle: [[Int]]) -> Int {
    guard !triangle.isEmpty else { return 0 }
    
    // Create a mutable copy of the triangle to store DP values
    var dp = triangle
    
    // Start from the second-to-last row and move up
    for i in (0..<triangle.count - 1).reversed() {
        for j in 0..<triangle[i].count {
            let currentNumber = triangle[i][j]
            
            if isPrime(currentNumber) {
                // Prime number can't be part of a valid path
                dp[i][j] = Int.min
            } else {
                // Get the maximum sum from the two possible next positions
                let leftSum = dp[i+1][j]
                let rightSum = dp[i+1][j+1]
                
                // Only add if the next positions are reachable (not Int.min)
                let maxBelow = max(leftSum, rightSum)
                dp[i][j] = maxBelow == Int.min ? Int.min : currentNumber + maxBelow
            }
        }
    }
    
    // The top of the DP array holds the maximum sum (if reachable)
    let result = dp[0][0]
    return result == Int.min ? 0 : result // If top is prime, return 0 (no valid path)
}

Why bottom-up? It avoids recursion overhead and makes it easy to handle unreachable paths. We modify a copy of the triangle in place to save space—no need for a separate DP array.

4. Putting It All Together #

Here’s how you’d call these functions to solve the problem:

do {
    // Replace with your file URL
    let fileURL = URL(fileURLWithPath: "/path/to/your/triangle.txt")
    let triangle = try parseTriangle(from: fileURL)
    let maxSum = maxNonPrimePathSum(in: triangle)
    print("Maximum non-prime path sum: \(maxSum)")
} catch {
    print("Error reading file: \(error.localizedDescription)")
}

Let’s Debug Your Possible Issues #

If you’re still getting a wrong answer, check these:

1. Prime check fail: Test isPrime(1) (should be false), isPrime(2) (true), isPrime(9) (false), isPrime(17) (true) to confirm your function works.
2. DP transition error: Make sure you’re only adding the max of the two below positions if those positions are reachable (not Int.min). If both below positions are primes, the current position becomes unreachable too.
3. File parsing: Print out the parsed triangle to ensure it matches your input exactly—extra spaces or empty lines can create mismatched row lengths, leading to index out of bounds errors.
4. Top is prime: If the top number is a prime, the result will be 0 (since no path exists)—make sure your problem expects this behavior.

内容的提问来源于stack exchange，提问作者emrepun