Can't advance past endIndex Swift

Question

Something wrong with String Index when checking and deleting symbols. How can I improve it?

func romanToInt(_ s: String) -> Int {
    let romanDigits = ["I" : 1,
                       "V" : 5,
                       "X" : 10,
                       "L" : 50,
                       "C" : 100,
                       "D" : 500,
                       "M" : 1000]
    let romanSums = ["IV" : 4,
                     "IX" : 9,
                     "XL" : 40,
                     "XC" : 90,
                     "CD" : 400,
                     "CM" : 900]
    var sum = 0
    var str = s
    var charIndex = str.startIndex
    for index in str.indices {
        if index != str.index(before: str.endIndex) {
            charIndex = str.index(after: index)
        } else {
            charIndex = str.index(before: str.endIndex)
        }
        let chars = String(str[index]) + String(str[charIndex])
        if romanSums[chars] != nil {
            print(chars)
            str.remove(at: charIndex)
            sum += romanSums[chars]!
            print(sum)
        } else {
            let char = String(str[index])
            print(char)
            sum += romanDigits[char]!
            print(sum)
        }
        print(str)
    }

    return sum
}

let check = romanToInt("MCMXCIV")

CONSOLE LOG:

M
1000
MCMXCIV
CM
1900
MCXCIV
XC
1990
MCXIV
IV
1994
MCXI
Fatal error: Can't advance past endIndex

possible duplicate of https://stackoverflow.com/questions/36949453/how-to-take-a-roman-numeral-string-and-convert-it-to-base10-digit/36949832?r=SearchResults&s=1|45.5005#36949832 — Leo Dabus, Mar 05 '19 at 20:58
@LeoDabus Your solution the fastest on LeetCode (32ms by removing the `guard` and `uppercased()` for speed) https://leetcode.com/problems/roman-to-integer/ — ielyamani, Mar 05 '19 at 22:06

Rob Napier · Answer 1 · 2019-03-05T21:13:07.277

for index in str.indices {
    ...
        str.remove(at: charIndex)

It is not valid to modify a string while you are iterating over it. str.indices is fetched one time here, and is no longer valid once you've modified the underlying string.

I'm sure there will be a lot of implementations of this because it's the kind of small, fun problem that attracts implementations. So why not? This just screams recursion to me.

let romanDigits: [Substring: Int] = ["I" : 1,
                                     "V" : 5,
                                     "X" : 10,
                                     "L" : 50,
                                     "C" : 100,
                                     "D" : 500,
                                     "M" : 1000]
let romanSums: [Substring: Int] = ["IV" : 4,
                                   "IX" : 9,
                                   "XL" : 40,
                                   "XC" : 90,
                                   "CD" : 400,
                                   "CM" : 900]

func romanToInt<S: StringProtocol>(_ s: S) -> Int
    where S.SubSequence == Substring {

    if s.isEmpty { return 0 }

    if let value = romanSums[s.prefix(2)] {
        return value + romanToInt(s.dropFirst(2))
    } else if let value = romanDigits[s.prefix(1)] {
        return value + romanToInt(s.dropFirst(1))
    } else {
        fatalError("Invalid string")
    }
}

let check = romanToInt("MCMXCIV")

Of course this doesn't really check for valid sequences, so it's kind of junk. "IIIIXXIII" is kind of gibberish, but it works. But it's in keeping with the original approach.

score 2 · Accepted Answer · answered Mar 05 '19 at 20:57

You are modifying the string you are iterating over, so your indices become invalid. Instead, you could add a skipChar boolean that says that you've already handled the next character and then skip that character by executing continue:

func romanToInt(_ s: String) -> Int {
    let romanDigits = ["I" : 1,
                       "V" : 5,
                       "X" : 10,
                       "L" : 50,
                       "C" : 100,
                       "D" : 500,
                       "M" : 1000]
    let romanSums = ["IV" : 4,
                     "IX" : 9,
                     "XL" : 40,
                     "XC" : 90,
                     "CD" : 400,
                     "CM" : 900]
    var sum = 0
    var str = s
    var charIndex = str.startIndex
    var skipChar = false

    for index in str.indices {
        if skipChar {
            skipChar = false
            continue
        }
        if index != str.index(before: str.endIndex) {
            charIndex = str.index(after: index)
        } else {
            charIndex = str.index(before: str.endIndex)
        }
        let chars = String(str[index]) + String(str[charIndex])
        if romanSums[chars] != nil {
            print(chars)
            skipChar = true
            sum += romanSums[chars]!
            print(sum)
        } else {
            let char = String(str[index])
            print(char)
            sum += romanDigits[char]!
            print(sum)
        }
        print(str)
    }

    return sum
}

let check = romanToInt("MCMXCIV")
print(check)

score 1 · Answer 3 · answered Mar 05 '19 at 21:16

Use reduce to make it flow here:

 func romanToInt(_ s: String) -> Int {
if s.isEmpty {return 0}

let romanDigits = ["I" : 1,
                   "V" : 5,
                   "X" : 10,
                   "L" : 50,
                   "C" : 100,
                   "D" : 500,
                   "M" : 1000]

let romanSums = ["IV" : 4,
                 "IX" : 9,
                 "XL" : 40,
                 "XC" : 90,
                 "CD" : 400,
                 "CM" : 900]
    return s.dropFirst().reduce((s.first!, romanDigits["\(s.first!)"]!)){

         return   ( $1,   //current char

                    $0.1 +   //previous sum

      (romanSums["\($0.0)\($1)"]     //add double value

     ?? ((romanDigits["\($1)"]!). +  romanDigits["\($0.0)"]!))  //or single value  and add duplicated

        -  romanDigits["\($0.0)"]!) // minus duplicated

     }.1

   }

   print(romanToInt("MCMXCIV")). //1994

ielyamani · Answer 4 · 2019-03-05T21:15:18.940

0

You are mutating str inside the loop, its end index is going change, in this case it gets lower than its original value. You can fix your code by checking that you haven't exceeded the endIndex on each iteration by using a while loop :

var index = str.startIndex
while index < str.endIndex {
    ...
    //Before the closing curly brace of the while loop
    index = str.index(after: index)
}

edited Mar 05 '19 at 21:15

answered Mar 05 '19 at 20:58

ielyamani

17,807
10
55
90

score 0 · Answer 5 · answered May 08 '19 at 18:47

I was trying to reproduce a crash reported by one my users with the same message Can't advance past endIndex but I was not able to do it. Your code helped me figure out that this error changed in later versions of swift.

Your same code would report cannot increment beyond endIndex with swift 4.x runtime libraries, and String index is out of bounds with 5.x. The exact version numbers for the changes I do not know. But I suspect it is 4.0.0 and 5.0.0.-

Can't advance past endIndex Swift

5 Answers5