robshowsides
BAN USERThe paths from one checkpoint to the next do not need to be counted, since the number of different paths is simply the binomial coefficients nCr, where n is the total number of steps required (Manhattan distance) r is either the number of down steps or the number of right steps.
I could not figure out any reason why the dimensions of the grid would be useful (surely you don't need to check whether any given points are literally outside the entire grid, do you?)
def binom(n, r):
return factorial(n)/factorial(r)/factorial(n-r)
def count_paths(s, f, plist):
"""
s: (r, c) pair starting point
f: (r, c) pair end point
plist: list of pairs NOT INCLUDING s and f
"""
plist.sort() #sort the checkpoints
plist = [s] + plist + [f] #put start and end at beginning and end
for i in xrange(len(plist) - 1):
if plist[i+1][1] < plist[i][1] or plist[i+1][0] < plist[i][0]: #if any checkpoint is to the left of or above the previous point, return 0
return 0
ans = 1
for i in xrange(len(plist) - 1):
downs = plist[i+1][0] - plist[i][0]
rights = plist[i+1][1] - plist[i][1]
steps = downs + rights
ans *= binom(steps, downs)
return ans
test:
>>> count_paths((1,1), (5,4), [(2,1), (3,3)]) --> 9
@Alex This is Rob replying. A few thoughts. In the actual hypothetical context of flights, google tells me there are 17,678 commercial airports in the entire world, so surely no node in this ACTUAL question has even 10^4 edges. But if we generalize to the abstract problem without thinking about actual airports/flights, then the algorithm I wrote was (degree)^2, not (degree)^3. My first step is to pre-process the list of all flights into a dictionary (if not originally given as such). Then, if there are 10^6 flights out of x, and 10^6 flights into y, I check the 10^12 possible "middle links". Each lookup in the dict takes O(1) time, so the overall running time would be O(degree^2). There is certainly room for significant optimizations, depending on what the actual data is like. For example, if you find a direct flight or a two-edge flight in the first two rounds, then you can prune your search significantly when sifting through the three-edge possibilities.
#flights = [(('a','b'), 200) , (('c','d'), 300), (('a','c'), 150) , (('b','d'), 600), (('a','e'), 250), (('e','f'), 3), (('f','d'), 100), (('a','f'), 600)]
#out: find_cheapest_flight('a', 'd', f, out , inc) --> (353, [('a', 'e'), ('e', 'f'), ('f', 'd')])
def process_flights(flights):
flight_dict = dict(flights)
outgoing = dict() # key = a, value = [(b, 200), (c, 100)]
incoming = dict() # key = c, value = [(a, 100)]
for flight in flights:
origin, dest = flight[0]
fare = flight[1]
if origin in outgoing:
outgoing[origin].append((dest, fare))
else:
outgoing[origin] = [(dest, fare)]
if dest in incoming :
incoming [dest ].append((origin, fare))
else:
incoming [dest ] = [(origin, fare)]
return flight_dict, outgoing , incoming
def find_cheapest_flight(x, y, flight_dict, outgoing , incoming):
if x not in outgoing or y not in incoming:
print 'Sorry, no flights service those cities.'
return None
cheapest_route = []
cheapest_fare = 10**10
if (x,y) in flight_dict:
cheapest_route = [(x,y)]
cheapest_fare = flight_dict[(x,y)]
for flight in outgoing[x]:
city1, fare = flight
if (city1, y) in flight_dict:
if fare + flight_dict[(city1, y)] < cheapest_fare :
cheapest_fare = fare + flight_dict[(city1, y)]
cheapest_route = [(x, city1), (city1, y)]
for flight in incoming[y]:
city2, fare3 = flight
if (city1, city2) in flight_dict:
fare2 = flight_dict[(city1, city2)]
if fare + fare2 + fare3 < cheapest_fare :
cheapest_fare =fare + fare2 + fare3
cheapest_route = [(x, city1), (city1, city2), (city2, y)]
return cheapest_fare, cheapest_route
I'm pretty certain that the idea of a "flip" is what we might more naturally call a "swap" or an "exchange". So, the easy case is where the swaps do not chain together. For example,
abcd ==> badc takes two swaps: a<>b and c<>d
The trick comes in when the swaps chain together into cycles. For example:
abcd ==> bcda takes three swaps:
a<>b (bacd)
a<>c (bcad)
a<>d (bcda)
My code does two quick checks at the beginning: check if the strings at least have the same length. Then check if they contain the same counts of every letter (are anagrams).
If they are, then it basically becomes a directed graph, where every mismatch between string a and string b is an edge. I make an adjacency list in the form of a hashmap, and also keep a list of edges. The key method is loop_finder, which pops an edge, then follows the edges until it returns to the starting point. One thing to notice is that if the cycle has n edges, then that corresponds to n-1 swaps, NOT n.
TESTS:
input: ab ba
output: 1
input: abcd bcda
output: 3
input: aaabbcd dcaabab
output: 3
- robshowsides December 17, 2017