benny-and-gifts-marcheasy-3

View Russian Translation

Little pig Benny has just taken a shower. Now she is going to buy some gifts for her relatives. But the problem is that Benny doesn't know how to reach to the gift shop. Her friend Mike has created a special set of instructions for her. 
A set of instructions is a string which consists of letters {'L', 'R', 'U', 'D'}. 

For simplicity, let's assume that Benny is staying at point (0, 0) on the infinite plane. She consistently fulfills all the instructions written by Mike. Let's assume that now she is staying at point (X, Y).  Then depending on what is the current instruction she moves in some direction: 
'L' -- from  (X, Y) moves to point (X, Y - 1)
'R' -- from  (X, Y) moves to point (X, Y + 1)
'U' -- from  (X, Y) moves to point (X - 1, Y)
'D' -- from (X, Y) moves to point (X + 1, Y)

The weather is cold because it's winter now. Initially, all points are snowy. But if Benny have already visited some point at any time this point becomes icy (because Benny has just taken a shower). Every time, when Benny makes a step into icy points she slips and falls down.

You are given a string S which denotes a set of instructions for Benny. Your task is to calculate how may times she will fall down.

Input format

Single line contains string S.

Output format

Output how many times Benny will fall down.

Constraints

- 1 ≤
S
≤ 10^5
SAMPLE INPUT
RRULDL

SAMPLE OUTPUT
2

Explanation

Benny's route consists of points 

0 0 (becomes icy) --> 0 1 (becomes icy) --> 0 2 (becomes icy) --> -1 2 (becomes icy) --> -1 1 (becomes icy) --> 0 1 (is icy) --> 0 0 (is icy)

So Benny made two steps into icy points.

Source: hackerearth | Difficulty: EASY
Tags: Sorting


Solutions:
# Hacker Earth
# Problem Statement
# 'L' -- from (X, Y) moves to point (X, Y - 1)
# 'R' -- from (X, Y) moves to point (X, Y + 1)
# 'U' -- from (X, Y) moves to point (X - 1, Y)
# 'D' -- from (X, Y) moves to point (X + 1, Y)

# Import libraries
import sys
import pdb

def findBennyFallCount(myCommand):
	# initialization
	fallCount = 0
	currentX = 0
	currentY = 0
	visitedLocaiton = {}
	visitedLocaiton[currentX] = []
	visitedLocaiton[currentX].append(currentY)
	
	# process the command
	for cmd in myCommand:
		# update current location based on the command received
		if cmd == 'L':
			currentY -= 1
		if cmd == 'R':
			currentY += 1
		if cmd == 'U':
			currentX -= 1
		if cmd == 'D':
			currentX += 1
		else:
			pass
		# Update visited location and fall count
		if currentX in visitedLocaiton:
			if currentY in visitedLocaiton[currentX]:
				fallCount += 1
			else:
				visitedLocaiton[currentX].append(currentY)
		else:
			visitedLocaiton[currentX] = []
			visitedLocaiton[currentX].append(currentY)
	return(fallCount)


def getOneLine(inFile):
	if inFile != "":
		return(inFile.readline().rstrip())
	return(sys.stdin.readline().rstrip())


def main():
	
	# Toggle mode of input
	# inFile = open("input5.txt", 'r')
	inFile = ""
	
	# number of cases
	myCommand = getOneLine(inFile)
	
	# Result string
	result = findBennyFallCount(myCommand)
	result = str(result)
	
	# print the output
	sys.stdout.write(result)
	if inFile != "":
		inFile.close()
	
	
main()

# Simple test case
# RRULDL


"""

	'L' -- from (X, Y) moves to point (X, Y - 1)
	'R' -- from (X, Y) moves to point (X, Y + 1)
	'U' -- from (X, Y) moves to point (X - 1, Y)
	'D' -- from (X, Y) moves to point (X + 1, Y)
"""

navigator = {
	"L": lambda x,y: (x,y -1),
	"R": lambda x,y: (x, y+1),
	"U": lambda x,y: (x -1, y),
	"D": lambda x,y: (x+1, y),
}

# tests = {
#     "RDUUDLRLDLDLDLRUUDLRLDDURUUUUUDUDUDDDDRLLLLLLRRRRLLL": 33,
#     "RRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDLLLLLLLLLLLLRLRLRLRLRLDUDUDUDUDUDURURLDLDLRLDLRLDLRUDRLDRRRDURDLRD": 55
# }
# import pprint

def navigate(instrs):
	path_map = {}
	# slips = 0
	x,y = 0,0
	path_map[(x,y)] = 0
	for instr in instrs:
		# print("({}, {}) -> ".format(x, y))
		point = navigator[instr](x,y)
		if point in path_map:
			path_map[point] +=1
		else:
			path_map[point] = 0

		x,y = point

	# pprint.pprint(path_map)
	slips = sum(path_map.values())
	return slips


if __name__ == '__main__':
	# print(navigate("RRULDL") ==2)
	x = input("")
	print(navigate(x))
	# print(x)
	# for k,v in tests.items():
	#     print(navigate(k) == v)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
dict={}
x,y=0,0
dict[x,y]=1
count =0
s = input()
for c in s:
	if c == 'L':
		y -=1
		if (x,y) in dict:
			count +=1
		else:
			dict[x,y]=1
	elif c == 'R':
		y +=1
		if (x,y) in dict:
			count +=1
		else:
			dict[x,y]=1
	elif c == 'U':
		x -=1
		if (x,y) in dict:
			count +=1
		else:
			dict[x,y]=1
	elif c == 'D':
		x +=1
		if (x,y) in dict:
			count +=1
		else:
			dict[x,y]=1
print(count)	
		
			


if __name__ == '__main__':
	S = input()
	V = set()
	x, y = 0, 0
	V.add((x, y))
	icyFall = 0

	for i in S:
		if i == 'L':
			x, y = x, y - 1
			if (x, y) in V:
				icyFall += 1
			V.add((x, y))

		elif i == 'R':
			x, y = x, y + 1
			if (x, y) in V:
				icyFall += 1
			V.add((x, y))

		elif i == 'U':
			x, y = x - 1, y
			if (x, y) in V:
				icyFall += 1
			V.add((x, y))

		elif i == 'D':
			x, y = x + 1, y
			if (x, y) in V:
				icyFall += 1
			V.add((x, y))
	print(icyFall)


string = input().strip()
points_visited = set()
x, y, res = 0, 0, 0
points_visited.add((0, 0))

#print x, y
for ins in string:
	if ins == 'R':
		y += 1
	elif ins == 'L':
		y -= 1
	elif ins == 'U':
		x -= 1
	elif ins == 'D':
		x += 1
	if (x, y) not in points_visited:
		points_visited.add((x, y))
		#print '%d %d is snowy' % (x, y)
	else:
		res += 1
		#print '%d %d is icy' % (x, y)
	#print x, y
print(res)


string = input()
iceList = [[0,0]]
X,Y = 0,0
counter = 0
strlen = 0
for move in string:
	strlen += 1
	if move == 'L':
		Y -= 1
	elif move == 'R':
		Y += 1
	elif move  == 'U':
		X -= 1
	elif move == 'D':
		X  += 1
	iceList.append([X,Y])
iceList =  sorted(iceList)
for e in range(len(iceList)-1):
	if iceList[e] == iceList[e+1]:
		counter += 1
print(counter)




'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
x, y = 0, 0
visited = set()
S = input()
falls = 0
 
for s in S:
	visited.add((x,y))
 
	if s == 'L':
		y -= 1
	if s == 'R':
		y += 1
	if s == 'U':
		x -= 1
	if s == 'D':
		x += 1
	if (x,y) in visited:
		falls += 1
 
print(falls)


"""

	'L' -- from (X, Y) moves to point (X, Y - 1)
	'R' -- from (X, Y) moves to point (X, Y + 1)
	'U' -- from (X, Y) moves to point (X - 1, Y)
	'D' -- from (X, Y) moves to point (X + 1, Y)
"""

navigator = {
	"L": lambda x,y: (x,y -1),
	"R": lambda x,y: (x, y+1),
	"U": lambda x,y: (x -1, y),
	"D": lambda x,y: (x+1, y),
}

# tests = {
#     "RDUUDLRLDLDLDLRUUDLRLDDURUUUUUDUDUDDDDRLLLLLLRRRRLLL": 33,
#     "RRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDLLLLLLLLLLLLRLRLRLRLRLDUDUDUDUDUDURURLDLDLRLDLRLDLRUDRLDRRRDURDLRD": 55
# }
# import pprint

def navigate(instrs):
	path_map = {}
	# slips = 0
	x,y = 0,0
	path_map[(x,y)] = 0
	for instr in instrs:
		# print("({}, {}) -> ".format(x, y))
		point = navigator[instr](x,y)
		if point in path_map:
			path_map[point] +=1
		else:
			path_map[point] = 0

		x,y = point

	# pprint.pprint(path_map)
	slips = sum(path_map.values())
	return slips


if __name__ == '__main__':
	# print(navigate("RRULDL") ==2)
	x = input("")
	print(navigate(x))
	# print(x)
	# for k,v in tests.items():
	#     print(navigate(k) == v)


arr = {(0,0)}

s = input()
l = len(s)
c=0

x,y = 0,0

for i in range(l):
	if s[i] == 'L':
		y = y-1
		
	elif s[i] == 'R':
		y = y+1

	elif s[i] == 'U':
		x = x-1

	elif s[i] == 'D':
		x = x+1
		
	arr.add((x,y))

c = l-len(arr)+1
print(c)


st=input()

arr=["0,0"]
le=len(st)
x=0
y=0
for i in range(le):
	
	if(st[i]=='U'):
		x-=1
	elif(st[i]=='D'):
		x+=1
	elif(st[i]=='R'):
		y+=1
	else:
		y-=1

	temp=str(x)+","+str(y)
	arr.append(temp)
#print arr
se=set(arr)
le1=len(se)
print(le-le1+1)


S=input()
count=0

pos=[0,0]
l={}
l[tuple(pos)]=1
for move in S:
	#print 'move:', move
	if move=='L':        
		pos[1] -= 1
		if tuple(pos) in l:
			count+=1
			#print 'count, pos:',count, pos
		else:
			l[tuple(pos)]=1
			#print 'l:', l
	elif move=='R':
		#print 'pos:',pos
		pos[1] += 1
		#print 'pos:',pos
		if tuple(pos) in l:
			#print 'R true',l
			count+=1
			#print 'count, pos:',count, pos
		else:
			#print 'R false'
			l[tuple(pos)]=1
			#print 'l:', l
	elif move=='U':
		pos[0] -= 1
		if tuple(pos) in l:
			count+=1
			#print 'count, pos:',count, pos
		else:
			l[tuple(pos)]=1
			#print 'l:', l
	else:
		pos[0] += 1
		if tuple(pos) in l:
			count+=1
			#print 'count, pos:',count, pos
		else:
			l[tuple(pos)]=1
			#print 'l:', l
print(count)


def foo(s):
	a = set([(0,0)])
	p = (0, 0)
	f = 0
	for i in s:
		if i == 'U':
			if (p[0]-1, p[1]) in a:
				f += 1
			p = (p[0]-1, p[1])
			a.add(p)
		elif i == 'D':
			if (p[0]+1, p[1]) in a:
				f += 1
			p = (p[0]+1, p[1])
			a.add(p)
		elif i == 'L':
			if (p[0], p[1]-1) in a:
				f += 1
			p = (p[0], p[1]-1)
			a.add(p)
		elif i == 'R':
			if (p[0], p[1]+1) in a:
				f += 1
			p = (p[0], p[1]+1)
			a.add(p)
	return f
	
s = input()
print((foo(s)))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def move(seq,x,y):
	if seq=='L':
		y-=1
	elif seq=='R':
		y+=1
	elif seq=='U':
		x-=1
	else:
		x+=1
	return x,y	

seq=list(input().strip())
x=0
y=0
ice=set()
ice.add((0,0))
count=0
for i in range(len(seq)):
	x,y=move(seq[i],x,y)
	if (x,y) in ice:
		count+=1
		#print x,y,"in ice"
	else:
		ice.add((x,y))
		#print x,y,"NOT in ice"
print(count)		
#print ice


s = input()
points=[]

points.append([0,0])

x=0
y=0
f=0
for i in s:
	if i == 'L':
		y=y-1
	elif i == 'R':
		y=y+1
	elif i == 'U':
		x=x-1
	elif i == 'D':
		x=x+1
	
	points.append([x,y])	

points.sort()
#print points
pre = points[0]
for i in range(1,len(points)):
	#print "com[aring ",points[i]," with ",pre
	if points[i] ==  pre:
		f+=1
	pre = points[i]	
	
print(f)



# https://www.hackerearth.com/march-easy-16/algorithm/benny-and-gifts-marcheasy-3/

x, y = 0, 0
visited = set()
S = input()
falls = 0

for s in S:
	visited.add((x,y))

	if s == 'L':
		y -= 1
	if s == 'R':
		y += 1
	if s == 'U':
		x -= 1
	if s == 'D':
		x += 1
	if (x,y) in visited:
		falls += 1

print(falls)


s = list(input().rstrip())
cords = {}
x, y = 100000, 100000
cords.update({(x,y):0})
for d in s:
	if d == 'R':
		y += 1
	elif d == 'L':
		y -= 1
	elif d == 'U':
		x -= 1
	else:
		x += 1
	if (x,y) in cords:
		cords[(x,y)]+=1
	else:
		cords.update({(x, y): 0})
print(sum(cords.values()))        




'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
s = input()
s = s.strip()
#print s
hash = {}
n = len(s)
ans = 0
pos = (0,0)
hash[pos] = 1
for i in range(n):
	if s[i] == 'L':
		new_pos = (pos[0], pos[1]-1)
		if new_pos in hash:
			ans += 1
		else:
			hash[new_pos] = 1
		pos = new_pos
	elif s[i] == 'R':
		new_pos = (pos[0], pos[1]+1)
		if new_pos in hash:
			ans += 1
		else:
			hash[new_pos] = 1
		pos = new_pos
	elif s[i] == 'U':
		new_pos = (pos[0]-1, pos[1])
		if new_pos in hash:
			ans += 1
		else:
			hash[new_pos] = 1
		pos = new_pos
	elif s[i] == 'D':
		new_pos = (pos[0]+1, pos[1])
		if new_pos in hash:
			ans += 1
		else:
			hash[new_pos] = 1
		pos = new_pos
print(ans)