# Story

John found a path to a treasure, and while searching for its precise location he wrote a list of directions using symbols `"^"`, `"v"`, `"<"`, `">"` which mean `north`, `east`, `west`, and `east` accordingly. On his way John had to try many different paths, sometimes walking in circles, and even missing the treasure completely before finally noticing it.

___

## Task

Simplify the list of directions written by John by eliminating any loops.

**Note**: a loop is any sublist of directions which leads John to the coordinate he had already visited.

___

## Examples

```
simplify("<>>")        ==  ">"
simplify("<^^>v<^^^")  ==  "<^^^^"
simplify("")           ==  ""
simplify("^< > v
    ^   v
> > C > D > >
^   ^   v
^ < B < <
    ^
    A
```

John visits points `A -> B -> C -> D -> B -> C -> D`, realizes that `-> C -> D -> B` steps are meaningless and removes them, getting this path: `A -> B -> (*removed*) -> C -> D`.

```
    ∙ ∙ ∙
    ∙   ∙
> > C > D > >
^   ∙   ∙
^ < B ∙ ∙
    ^
    A
```

Following the final, simplified route John visits points `C` and `D`, but for the first time, not the second (because we ignore the steps made on a hypothetical path), and he doesn't need to alter the directions list anymore.

Difficulty: introductory

Starter code:

def simplify(path):
	

Solutions:
def simplify(p):
    new_p=[(0,0)]
    new_str=''
    x=0
    y=0
    for i in p:
        if i == '<':
            x-=1
        elif i == '>':
            x+=1
        elif i == '^':
            y+=1
        elif i == 'v':
            y-=1
        if (x,y) not in new_p:
            new_p.append((x,y))
            new_str+=i
        else:
            for j in new_p[::-1]:
                if j != (x,y):
                    new_p.pop()
                    new_str=new_str[:-1]
                else:
                    break
    return new_str

def simplify(s):
    d, r, c = {"^": (-1, 0), "v": (1, 0), "<": (0, -1), ">": (0, 1)}, {(0, 0): ""}, (0, 0)
    for z in s:
        x, y = d[z]
        nc = (c[0] + x, c[1] + y)
        r[nc] = r[nc] if nc in r and r[c].startswith(r[nc]) else r[c] + z
        c = nc
    return r[c]

def simplify(path):
    location = (0,0)
    new_path = path
    new_path_locations = [location]
    
    for d in path:
        if d == '<': location = (location[0]-1, location[1])
        elif d == '>': location = (location[0]+1, location[1])
        elif d == 'v': location = (location[0], location[1]+1)
        else: location = (location[0], location[1]-1)
        
        if location in new_path_locations:
            i = new_path_locations.index(location)
            
            remove_length = len(new_path_locations) - i
            
            new_path_locations = new_path_locations[:i+1] # leave the current location
            
            new_path = new_path[:i] + new_path[i+remove_length:]
        
        else: new_path_locations.append(location)
    
    return new_path

def simplify(path):
    x, y, coords = 0, 0, [(0, 0)]
    for c in path:
        x += 1 if c == ">" else -1 if c == "<" else 0
        y += 1 if c == "^" else -1 if c == "v" else 0
        if (x, y) in coords:
            i = coords.index((x, y))
            path, coords = path[:i] + path[len(coords):], coords[:i]
        coords.append((x, y))
    return path


M = {'^':-1, 'v':1, '<':-1j, '>':1j}
def rem(D, k): del D[k]

def simplify(path):
    D, z, res = {0:0}, 0, list(path)
    for i,c in enumerate(path, 1):
        z += M[c]
        if z in D:
            for j in range(D[z], i): res[j] = None
            [rem(D, k) for k,v in list(D.items()) if v > D[z]]
        else: D[z] = i
    return ''.join(filter(None, res))

def simplify(p):
    x = 0
    y = 0
    r = [(0,0)]
    for i in p:
        if i == '<':  x -= 1
        if i == '>':  x += 1
        if i == '^':  y += 1
        if i == 'v':  y -= 1
        if (x,y) in r:
            p = p[:r.index((x,y))] + p[len(r):]
            r = r[:r.index((x,y))]            
        r.append((x,y))
    
    return p

def simplify(path):
    array = [(0, 0)]
    for elem in path:
        if elem == "^":
            array.append((array[-1][0], array[-1][1] + 1))
        elif elem == "v":
            array.append((array[-1][0], array[-1][1] - 1))
        elif elem == ">":
            array.append((array[-1][0] + 1, array[-1][1]))
        else:
            array.append((array[-1][0] - 1, array[-1][1]))
    for i in range(0, len(array) - 1):
        for j in range(len(array) - 1, i + 1, -1):
            if array[i] == array[j]:
                array = array[:i] + [None for i in range((j - i))] + array[j:]
    res = [path[i] for i in range(len(path)) if array[i] is not None]
    return "".join(res)

def simplify(s):
    been = [(0,0)]
    i,j = 0,0
    d = {'<': (-1,0),'>':(1,0),'^':(0,1),'v':(0,-1)}
    t = s
    for p in s:
        x,y = d.get(p)
        i,j = i+x,j+y
        if (i,j) in been:
            idx = been.index((i,j))
            t = t[:idx] + t[len(been):]
            been = been[:idx]
        been.append((i,j))
    return t

def simplify(path):
    moves = {'^': (0, 1), 'v': (0, -1), '<': (-1, 0), '>': (1, 0)}
    rev_moves = {(0, 0): '', (0, 1): '^',  (0, -1): 'v',  (-1, 0): '<',  (1, 0): '>'}
    x, y = 0, 0
    visited = [(0, 0)]
    for p in path:
        mov = moves[p]
        x1, y1 = x+mov[0], y+mov[1]
        if not (x1, y1) in visited:
            visited.append((x1, y1))
        else:
            idx = visited.index((x1, y1))
            visited = visited[0:idx+1]
        x, y = x1, y1
    last = (0, 0)
    res = ''
    for p in visited:
        dx, dy = p[0]-last[0], p[1]-last[1]
        res += rev_moves[(dx, dy)]
        last = p
    return res

D = {'^': (1, 0), 'v': (-1, 0), '>': (0, 1), '<': (0, -1)}

def simplify(s):
    q, c, w = set(), (0, 0), [(0, 0)]
    for i, k in enumerate(s):
        p = D[k]
        c = (c[0]+p[0], c[1]+p[1])
        if c in w:
            j = w.index(c)
            w[j:i+1] = [-1] * (i-j+1)
            q |= set(range(j, i+1))
        w.append(c)
    return ''.join(x for i, x in enumerate(s) if i not in q)