Skip to content

Instantly share code, notes, and snippets.

@SaptakS

SaptakS/q1.py

Created September 4, 2015 16:47
Show Gist options
  • Save SaptakS/99cd0ca65ac78ba9b7c3 to your computer and use it in GitHub Desktop.
Save SaptakS/99cd0ca65ac78ba9b7c3 to your computer and use it in GitHub Desktop.
Download ZIP
Maze Problem (A.I.)
Raw
q1.py
from math import sqrt
import heapq
import itertools
class Node:
def __init__(self, x, y, cost):
self.x = x
self.y = y
self.cost = cost
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, i, j):
if self.grid[i][j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable(i, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
entry = [next_cost, count, Node(i, j+1, next_cost)]
heapq.heappush(newf, entry)
#down-right move
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
entry = [next_cost, count, Node(i + 1, j+1, next_cost)]
heapq.heappush(newf, entry)
#down move
if i + 1 < self.env.m and self.env.navigable(i + 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
entry = [next_cost, count, Node(i+1, j, next_cost)]
heapq.heappush(newf, entry)
#down-left move
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
entry = [next_cost, count, Node(i+1, j-1, next_cost)]
heapq.heappush(newf, entry)
#left move
if j - 1 >= 0 and self.env.navigable(i, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
entry = [next_cost, count, Node(i, j-1, next_cost)]
heapq.heappush(newf, entry)
#up-left move
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
entry = [next_cost, count, Node(i-1, j-1, next_cost)]
heapq.heappush(newf, entry)
#up move
if i - 1 >= 0 and self.env.navigable(i - 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
entry = [next_cost, count, Node(i-1, j, next_cost)]
heapq.heappush(newf, entry)
#up-right move
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
entry = [next_cost, count, Node(i-1, j+1, next_cost)]
heapq.heappush(newf, entry)
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = [start]
visited = []
while fringe:
next_fringe = fringe.pop(0)
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited and newf[2] not in fringe:
fringe.append(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
fringe.sort(key=lambda i: i.cost)
'''for kkk in fringe:
print (kkk.x, kkk.y, kkk.cost)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))])
e = Environment(grid, m, n)
for i in range(x):
a = Agent(query[i], e)
cost = a.solver()
print int(round(cost))
Raw
q2.py
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 03 10:16:00 2015
@author: SAPTAK
"""
from math import sqrt
import heapq
import itertools
class Node:
def __init__(self, x, y, cost, total=0):
self.x = x
self.y = y
self.cost = cost
self.total = total
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, i, j):
if self.grid[i][j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def heuristic(self, (x, y)):
(i, j) = (x, y)
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2))
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable(i, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down-right move
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i + 1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down move
if i + 1 < self.env.m and self.env.navigable(i + 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j, next_cost, total)]
heapq.heappush(newf, entry)
#down-left move
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#left move
if j - 1 >= 0 and self.env.navigable(i, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up-left move
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up move
if i - 1 >= 0 and self.env.navigable(i - 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j, next_cost, total)]
heapq.heappush(newf, entry)
#up-right move
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = [start]
visited = []
while fringe:
next_fringe = fringe.pop(0)
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited and newf[2] not in fringe:
fringe.append(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
fringe.sort(key=lambda i: i.total)
'''for kkk in fringe:
print (kkk.x, kkk.y, kkk.cost, kkk.total)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))])
e = Environment(grid, m, n)
for i in range(x):
a = Agent(query[i], e)
cost = a.solver()
print int(round(cost))
Raw
q3.py
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 03 10:42:50 2015
@author: SAPTAK
"""
from math import sqrt
import heapq
import itertools
class Pque:
def __init__(self):
self.queue = []
self.index = 0
def push(self, item):
heapq.heappush(self.queue, (item.total, item))
self.index += 1
def pop(self):
return heapq.heappop(self.queue)[-1]
class Node:
def __init__(self, x, y, cost, total=0):
self.x = x
self.y = y
self.cost = cost
self.total = total
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, now, nex):
(now_i,now_j) = now
(nex_i, nex_j) = nex
#check for diagonal
if(self.get_cost(now, nex) > 1.0):
#down-right
if nex_i == now_i + 1 and nex_j == now_j + 1 :
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i-1][nex_j] == 0 and self.grid[nex_i][nex_j-1] == 0:
return True
else:
return False
#down-left
if nex_i == now_i + 1 and nex_j == now_j - 1:
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i-1][nex_j] == 0 and self.grid[nex_i][nex_j+1] == 0:
return True
else:
return False
#up-right
if nex_i == now_i - 1 and nex_j == now_j + 1:
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i+1][nex_j] == 0 and self.grid[nex_i][nex_j-1] == 0:
#print "here", nex_i,nex_j
return True
else:
return False
#up-left
if nex_i == now_i -1 and nex_j == now_j - 1:
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i+1][nex_j] == 0 and self.grid[nex_i][nex_j+1] == 0:
return True
else:
return False
else:
if self.grid[nex_i][nex_j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def heuristic(self, (x, y)):
(i, j) = (x, y)
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2))
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable((i,j),(i, j + 1)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down-right move
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable((i,j),(i + 1, j + 1)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i + 1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down move
if i + 1 < self.env.m and self.env.navigable((i,j),(i + 1, j)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j, next_cost, total)]
heapq.heappush(newf, entry)
#down-left move
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable((i,j),(i + 1, j - 1)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#left move
if j - 1 >= 0 and self.env.navigable((i,j),(i, j - 1)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up-left move
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable((i,j),(i - 1, j - 1)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up move
if i - 1 >= 0 and self.env.navigable((i,j),(i - 1, j)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j, next_cost, total)]
heapq.heappush(newf, entry)
#up-right move
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable((i,j),(i-1, j + 1)):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = Pque()
fringe.push(start)
visited = []
while fringe.queue != []:
next_fringe = fringe.pop()
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited:# and newf[2] not in [x[1] for x in fringe.queue]:
fl = 0
for x in fringe.queue:
if x[1] == newf[2]:
fl = 1
break
if fl == 0:
fringe.push(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
#heapq.heapify(fringe)
#fringe.sort(key=lambda i: i.total)
'''print "Fr"
for kkk in fringe.queue:
print (kkk[1].x, kkk[1].y, kkk[1].cost, kkk[1].total)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))])
e = Environment(grid, m, n)
for i in range(x):
a = Agent(query[i], e)
cost = a.solver()
print int(round(cost))
Raw
q4.py
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 03 10:16:00 2015
@author: SAPTAK
"""
from math import sqrt
import heapq
import itertools
class Node:
def __init__(self, x, y, cost, total=0):
self.x = x
self.y = y
self.cost = cost
self.total = total
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, i, j):
if self.grid[i][j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def heuristic(self, (x, y)):
(i, j) = (x, y)
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2))
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable(i, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down-right move
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i + 1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down move
if i + 1 < self.env.m and self.env.navigable(i + 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j, next_cost, total)]
heapq.heappush(newf, entry)
#down-left move
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#left move
if j - 1 >= 0 and self.env.navigable(i, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up-left move
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up move
if i - 1 >= 0 and self.env.navigable(i - 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j, next_cost, total)]
heapq.heappush(newf, entry)
#up-right move
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = [start]
visited = []
while fringe:
next_fringe = fringe.pop(0)
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited and newf[2] not in fringe:
fringe.append(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
fringe.sort(key=lambda i: i.total)
'''for kkk in fringe:
print (kkk.x, kkk.y, kkk.cost, kkk.total)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append((int(k[0]), int(k[1])))
'''print query[0]
q = [query[0], (0,0)]
print q
'''
e = Environment(grid, m, n)
for i in range(x):
cost = 0
q1 = [query[i], (0,0)]
q2 = [(0,0), (0,n-1)]
q3 = [(0,n-1), (m-1,n-1)]
q4 = [(m-1,n-1), (m-1,0)]
a = Agent(q1, e)
cost += a.solver()
a = Agent(q2, e)
cost += a.solver()
a = Agent(q3, e)
cost += a.solver()
a = Agent(q4, e)
cost += a.solver()
print int(round(cost))
Raw
q5.py
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 03 12:19:19 2015
@author: SAPTAK
"""
from math import sqrt
import heapq
import itertools
class Node:
def __init__(self, x, y, cost, total=0):
self.x = x
self.y = y
self.cost = cost
self.total = total
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, i, j):
if self.grid[i][j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def heuristic(self, (x, y)):
(i, j) = (x, y)
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2))
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable(i, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down-right move
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i + 1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down move
if i + 1 < self.env.m and self.env.navigable(i + 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j, next_cost, total)]
heapq.heappush(newf, entry)
#down-left move
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#left move
if j - 1 >= 0 and self.env.navigable(i, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up-left move
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up move
if i - 1 >= 0 and self.env.navigable(i - 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j, next_cost, total)]
heapq.heappush(newf, entry)
#up-right move
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = [start]
visited = []
while fringe:
next_fringe = fringe.pop(0)
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited and newf[2] not in fringe:
fringe.append(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
fringe.sort(key=lambda i: i.total)
'''for kkk in fringe:
print (kkk.x, kkk.y, kkk.cost, kkk.total)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append((int(k[0]), int(k[1])))
'''print query[0]
q = [query[0], (0,0)]
print q
'''
e = Environment(grid, m, n)
for i in range(x):
minimum = 1000000
q1 = [query[i], (0,0)]
q2 = [query[i], (0,n-1)]
q3 = [query[i], (m-1,n-1)]
q4 = [query[i], (m-1,0)]
a = Agent(q1, e)
cost = a.solver()
if cost < minimum:
minimum = cost
a = Agent(q2, e)
cost = a.solver()
if cost < minimum:
minimum = cost
a = Agent(q3, e)
cost = a.solver()
if cost < minimum:
minimum = cost
a = Agent(q4, e)
cost = a.solver()
if cost < minimum:
minimum = cost
print int(round(minimum))
Raw
q6.py
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 03 12:20:24 2015
@author: SAPTAK
"""
from math import sqrt
import heapq
import itertools
from itertools import permutations
class Node:
def __init__(self, x, y, cost, total=0):
self.x = x
self.y = y
self.cost = cost
self.total = total
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, i, j):
if self.grid[i][j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def heuristic(self, (x, y)):
(i, j) = (x, y)
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2))
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable(i, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down-right move
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i + 1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down move
if i + 1 < self.env.m and self.env.navigable(i + 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j, next_cost, total)]
heapq.heappush(newf, entry)
#down-left move
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#left move
if j - 1 >= 0 and self.env.navigable(i, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up-left move
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up move
if i - 1 >= 0 and self.env.navigable(i - 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j, next_cost, total)]
heapq.heappush(newf, entry)
#up-right move
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = [start]
visited = []
while fringe:
next_fringe = fringe.pop(0)
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited and newf[2] not in fringe:
fringe.append(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
fringe.sort(key=lambda i: i.total)
'''for kkk in fringe:
print (kkk.x, kkk.y, kkk.cost, kkk.total)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
e = Environment(grid, m, n)
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append((int(k[0]), int(k[1])))
'''print query[0]
q = [query[0], (0,0)]
print q
'''
destinations = {'TL': (0,0),
'TR': (0, n-1),
'DR': (m-1, n-1),
'DL': (m-1, 0)}
desti_tags = ['TL', 'TR', 'DR', 'DL']
perm_list = list(permutations(desti_tags))
#print perm_list
for i in range(x):
minimum = 100000
for perm in perm_list:
cost = 0
q1 = [query[i], destinations[perm[0]]]
q2 = [destinations[perm[0]], destinations[perm[1]]]
q3 = [destinations[perm[1]], destinations[perm[2]]]
q4 = [destinations[perm[2]], destinations[perm[3]]]
a = Agent(q1, e)
cost += a.solver()
a = Agent(q2, e)
cost += a.solver()
a = Agent(q3, e)
cost += a.solver()
a = Agent(q4, e)
cost += a.solver()
if cost < minimum:
minimum = cost
print int(round(minimum))
Raw
q7.py
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 03 10:16:00 2015
@author: SAPTAK
"""
from math import sqrt
import heapq
import itertools
class Node:
def __init__(self, x, y, cost, total=0):
self.x = x
self.y = y
self.cost = cost
self.total = total
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, i, j):
if self.grid[i][j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def heuristic(self, (x, y)):
(i, j) = (x, y)
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2))
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable(i, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down-right move
'''if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i + 1, j+1, next_cost, total)]
heapq.heappush(newf, entry)'''
#down move
if i + 1 < self.env.m and self.env.navigable(i + 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j, next_cost, total)]
heapq.heappush(newf, entry)
#down-left move
'''if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j-1, next_cost, total)]
heapq.heappush(newf, entry)'''
#left move
if j - 1 >= 0 and self.env.navigable(i, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up-left move
'''if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j-1, next_cost, total)]
heapq.heappush(newf, entry)'''
#up move
if i - 1 >= 0 and self.env.navigable(i - 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j, next_cost, total)]
heapq.heappush(newf, entry)
#up-right move
'''if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j+1, next_cost, total)]
heapq.heappush(newf, entry)'''
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = [start]
visited = []
while fringe:
next_fringe = fringe.pop(0)
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited and newf[2] not in fringe:
fringe.append(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
fringe.sort(key=lambda i: i.total)
'''for kkk in fringe:
print (kkk.x, kkk.y, kkk.cost, kkk.total)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))])
e = Environment(grid, m, n)
for i in range(x):
a = Agent(query[i], e)
cost = a.solver()
cost = int(round(cost))
#print cost
if cost % 2 == 0:
print (cost/2), (cost/2)
else:
print (cost/2+1), (cost/2)
Raw
q8.py
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 04 02:53:49 2015
@author: SAPTAK
"""
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 03 10:16:00 2015
@author: SAPTAK
"""
from math import sqrt
import heapq
import itertools
class Node:
def __init__(self, x, y, cost, total=0):
self.x = x
self.y = y
self.cost = cost
self.total = total
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
class Environment:
def __init__(self, grid, m, n):
self.grid = grid
self.m = m
self.n = n
def navigable(self, i, j):
if self.grid[i][j] == 0:
return True
else:
return False
def get_cost(self, src, dest):
(src_i, src_j) = src
(dest_i, dest_j) = dest
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2))
class Agent:
def __init__(self, query, env):
(self.src_i, self.src_j) = query[0]
(self.dest_i, self.dest_j) = query[1]
self.env = env
def heuristic(self, (x, y)):
(i, j) = (x, y)
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2))
def next_fringes(self, present):
(i, j) = (present.x, present.y)
cost = present.cost
newf = []
counter = itertools.count()
#right move
if j + 1 < self.env.n and self.env.navigable(i, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down-right move
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i + 1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
#down move
if i + 1 < self.env.m and self.env.navigable(i + 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j, next_cost, total)]
heapq.heappush(newf, entry)
#down-left move
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i+1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#left move
if j - 1 >= 0 and self.env.navigable(i, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up-left move
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j-1, next_cost, total)]
heapq.heappush(newf, entry)
#up move
if i - 1 >= 0 and self.env.navigable(i - 1, j):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j, next_cost, total)]
heapq.heappush(newf, entry)
#up-right move
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1):
count = next(counter)
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1))
total = next_cost + self.heuristic((i,j))
entry = [total, count, Node(i-1, j+1, next_cost, total)]
heapq.heappush(newf, entry)
'''for f in nextf:
print f.x, f.y, f.cost'''
#nextf.sort(key=lambda x: x.cost)
return newf
def solver(self):
start = Node(self.src_i, self.src_j, 0)
fringe = [start]
visited = []
while fringe:
next_fringe = fringe.pop(0)
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j):
#print "found"
return next_fringe.cost
#for kk in visited:
#print "VIS" , kk.x, kk.y, kk.cost
#for kk in fringe:
#print "fr" , kk.x, kk.y, kk.cost
nextFringes = self.next_fringes(next_fringe)
#nextFringes.sort(key = lambda x: x.cost)
for newf in nextFringes:
if newf[2] not in visited and newf[2] not in fringe:
fringe.append(newf[2])
#print newf[1].x, newf[1].y, newf[1].cost
'''else:
print newf[1].x, newf[1].y, newf[1].cost, "Already"'''
visited.append(next_fringe)
fringe.sort(key=lambda i: i.total)
'''for kkk in fringe:
print (kkk.x, kkk.y, kkk.cost, kkk.total)'''
##input
k = raw_input().split()
m = int(k[0])
n = int(k[1])
grid = []
for i in range(m):
row = []
row = [int(x) for x in raw_input().split()]
grid.append(row)
#print grid
x = int(raw_input())
query = []
for i in range(x):
k = raw_input().split()
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))])
e = Environment(grid, m, n)
for i in range(x):
a = Agent(query[i], e)
cost = a.solver()
cost = int(round(cost))
#print cost
if cost % 2 == 0:
print ((cost/2) + (cost/2))
else:
print ((cost/2+1) + (cost/2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment