Pages

CodeEval Strings and Arrows

Find how many arrows, '>>-->' or '<--<<', are in a passed string. Beware of overlapping arrows!
This is CodeEval problem #202, and here I show you my Python 3 solution to it.

A few test cases to clarify the problem:
def test_provided_1(self):
    self.assertEqual(2, solution('<--<<--<<'))

def test_provided_2(self):
    self.assertEqual(4, solution('<<>>--><--<<--<<>>>--><'))

def test_provided_3(self):
    self.assertEqual(0, solution('<-->>'))

def test_empty(self):
    self.assertEqual(0, solution(''))

def test_overlapping_right(self):
    self.assertEqual(3, solution('>>-->>-->>-->'))
The idea to solve the problem is neat and simple, just scan the input string looking for the patterns. Here is my solution:
ARROWS = ['>>-->', '<--<<']
ARROW_SIZE = 5


def solution(line):
    result = 0
    for i in range(len(line)): # 1
        candidate = line[i:i + ARROW_SIZE] # 2
        if candidate in ARROWS: # 3
            result += 1
    return result
1. Worst case scenario, I am going to loop on all the characters in the passed string looking for the patterns. Notice that I am working on indeces, in the next note I explain why.
2. I put in candidate the slice of the input line based on the current index. This is the usual way we create a substring in Python.
3. If the candidate matches an arrow, I increase the result.

For our purposes, that is, passing the CodeEval tests, this code is good enough. However, while I was writing it, I felt a bit sad I couldn't skip the loop counter when I identify a matching. Besides, I didn't get any use of the hint about the possible overlapping of arrows. The fact is we simply can't mess with it in a Python for loop, whatever we do to it, it is going to be reset by the for loop control statement.

In this case it is not a big concern, the performance loss is minimal. Still, if the arrows where much longer strings, it could be worthy using a while loop instead, like this:
def solution(line):
    result = 0
    i = 0
    while i < len(line):
        candidate = line[i:i + ARROW_SIZE]
        if candidate in ARROWS:
            result += 1
            i += ARROW_SIZE - 1 # 1
        else:
            i += 1 # 2
    return result
1. In a while loop I have full control on the looping variable. Here I use this feature to jump over the substring, starting the next check on its last character, for what we said about overlapping above.
2. Otherwise, we just pass to the next position in the string.

Both versions works fine for CodeEval, with about the same performance. First one is more readable, so I'd say it should be the preferred one.
As usual, I have pushed test cases and both solutions to GitHub.

No comments:

Post a Comment