# 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: EASY

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]
			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))