################################################
"""Do not look to much to the code below.
It's generic code to search for the path with the lowest cost.
Source: udacity.com"""
def lowest_cost_search(start, successors, is_goal, action_cost):
"""Return the lowest cost path, starting from start state,
and considering successors(state) => {state:action,...},
that ends in a state for which is_goal(state) is true,
where the cost of a path is the sum of action costs,
which are given by action_cost(action)."""
explored = set() # set of states we have visited
frontier = [ [start] ] # ordered list of paths we have blazed
while frontier:
path = frontier.pop(0)
state1 = final_state(path)
if is_goal(state1):
return path
explored.add(state1)
pcost = path_cost(path)
for (state, action) in successors(state1).items():
if state not in explored:
total_cost = pcost + action_cost(action)
path2 = path + [(action, total_cost), state]
add_to_frontier(frontier, path2)
return Fail
Fail = []
def final_state(path): return path[-1]
def path_cost(path):
'''Finds the total cost given a path'''
return path[-2][1] if len(path)>1 else 0
def add_to_frontier(frontier, path):
"Add path to frontier, replacing costlier path if there is one."
# (This could be done more efficiently.)
# Find if there is an old path to the final state of this path.
old = None
for i, p in enumerate(frontier):
if final_state(p) == final_state(path):
old = i
break
if old is not None and path_cost(frontier[old]) < path_cost(path):
return # Old path was better; do nothing
elif old is not None:
del frontier[old] # Old path was worse; delete it
## Now add the new path and re-sort
frontier.append(path)
frontier.sort(key = path_cost)
##############################################
"""START MAIN PROGRAM"""
def readints(fin):
'''Reads a line of ints in an array'''
return [int(i) for i in fin.readline().split()]
def build_world(fin):
'''Translates fin to a world with N cities and M roads '''
world = {}
N, M = readints(fin) #roads, cities
for town in range(N): #add towns
world[town] = {}
for road in range(M): #add roads
u, v, w = readints(fin) #town1, town2, road_length
world[u][v] = w #town1 -> town2
world[v][u] = w #town2 -> town1
return world
def travel(world, S, D):
'''Uses lowest_cost_search to find the shortest path from S to D in
world'''
successors = lambda city: world[city] #successors built in world
is_goal = lambda city: city == D
action_cost = lambda action: action
return lowest_cost_search(S, successors, is_goal, action_cost)
fin = open('t.txt', 'r')
world = build_world(fin)
S, D = readints(fin) #start, destination
Q, = readints(fin) #Q days
for day in range(Q):
u, v = readints(fin) #town1 <-> town2 blocked
#backup and delete road
back_up_cost = world[u][v]
del world[u][v]
del world[v][u]
##print travel(world, S, D)
print path_cost(travel(world, S, D))
#Restore road
world[u][v] = back_up_cost
world[v][u] = back_up_cost
On May 20, 2012 2:04 AM, "vivek dhiman" <[email protected]> wrote:
> I dont have any.
>
> Just tell me how wil u remember the path ?
> u will compute it again and again ?
>
> On Sun, May 20, 2012 at 3:50 AM, Βαγγέλης Μαμαλάκης <[email protected]>wrote:
>
>> the solution is not finished yet. it us working but not efficiently.
>> can you give more inputs/outputs?
>>
>> On 5/19/12, vivek dhiman <[email protected]> wrote:
>> > PASTEBIN IS banned in my country
>> >
>> > On Sat, May 19, 2012 at 2:19 PM, Βαγγέλης Μαμαλάκης
>> > <[email protected]>wrote:
>> >
>> >> Here is my code. add_to_frontier need refactoring to get faster.
>> >> I would appreciate a link with some more input outputs
>> >> http://pastebin.com/0syDhL2Y
>> >>
>> >> On 5/18/12, Βαγγέλης Μαμαλάκης <[email protected]> wrote:
>> >> > commented solution in python comming tomorrow. :)
>> >> > can you post the source of the challenge with more input outputs?
>> >> >
>> >> > On 5/18/12, Registered user <[email protected]> wrote:
>> >> >> can anyone plz tell how to use FASTOUTPUT to stdout.
>> >> >>
>> >> >> i have used here fast input but dont know how to use fastoutput. so
>> i
>> >> >> used System.out i know this is not the fast method to output...
>> >> >> anyone plz help...
>> >> >>
>> >> >> --
>> >> >> You received this message because you are subscribed to the Google
>> >> Groups
>> >> >> "Google Code Jam" group.
>> >> >> To post to this group, send email to [email protected].
>> >> >> To unsubscribe from this group, send email to
>> >> >> [email protected].
>> >> >> For more options, visit this group at
>> >> >> http://groups.google.com/group/google-code?hl=en.
>> >> >>
>> >> >>
>> >> >
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> Groups
>> >> "Google Code Jam" group.
>> >> To post to this group, send email to [email protected].
>> >> To unsubscribe from this group, send email to
>> >> [email protected].
>> >> For more options, visit this group at
>> >> http://groups.google.com/group/google-code?hl=en.
>> >>
>> >>
>> >
>> >
>> > --
>> > Regards
>> > Vivek Dhiman
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Google Code Jam" group.
>> > To post to this group, send email to [email protected].
>> > To unsubscribe from this group, send email to
>> > [email protected].
>> > For more options, visit this group at
>> > http://groups.google.com/group/google-code?hl=en.
>> >
>> >
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Google Code Jam" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/google-code?hl=en.
>>
>>
>
>
> --
> Regards
> Vivek Dhiman
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
