Last active
April 3, 2019 13:45
-
-
Save EnzDev/92187770a4e52f212febf92c51bee054 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Parse an input with some currencies conversions and use Dijkstra to find a path to convert | |
| from functools import reduce | |
| """ Input should look like this : | |
| FROM_CUR;AMOUNT;TO_CUR | |
| Number of conversions | |
| FROM_CUR;TO_CUR;UNIT_CONVERSION | |
| FROM_CUR;TO_CUR;UNIT_CONVERSION | |
| FROM_CUR;TO_CUR;UNIT_CONVERSION | |
| eg: | |
| EUR;912.12;USD | |
| 4 | |
| EUR;CAD;1.12 | |
| CAD;JPY;119 | |
| CAD;AUD;0.98 | |
| AUD;USD;1.28 | |
| Dijkstra algorithm will be applied to the conversion graph (number of conversion required). | |
| Using the prev dictionary we retrace the path to reach our currency and reduce the conversion rates. | |
| """ | |
| # First line : Get the fields | |
| from_, value, to_ = input().split(";") | |
| # For the number of line, read each rate | |
| raw_table = [input() for _ in range(int(input()))] | |
| # Create a conversion table with their inverse (1/rate) | |
| conversion = [{"from": x[0], "to": x[1], "val": float(x[2])} for x in [_.split(";") for _ in raw_table]] | |
| conversion.extend([{"from": c["to"], "to": c["from"], "val": round(1/c["val"], 4)} for c in conversion]) | |
| # Dijkstra distance and prev dicts | |
| dist = dict() | |
| prev = dict() | |
| # Usable vertices set | |
| v_set = set() | |
| # Fill the set and dictionaries with our conversion table | |
| for v in {c["from"] for c in conversion}: | |
| dist[v] = float("inf") | |
| prev[v] = None | |
| v_set = v_set | {v} | |
| # Starting point is 0 far away from itself | |
| dist[from_] = 0 | |
| # Dijkstra algorithm (Read the distances from the closest available vertex) | |
| while len(v_set) > 0: | |
| u = min(v_set, key=lambda v: dist[v]) # Select closest | |
| v_set.remove(u) # Remove from the available vertex set | |
| for neigh in [n["to"] for n in conversion if n["from"] == u]: # Get the current vertex neighbours | |
| alt = dist[u] + 1 # Using a distance of 1 because it represent a conversion step | |
| if alt < dist[neigh]: | |
| dist[neigh] = alt | |
| prev[neigh] = u | |
| # The compute array will contain each needed rate (Just need the product to have the final rate) | |
| compute = [] | |
| z = to_ | |
| while prev[z] is not None: # Iterate over the prevs to trace the route | |
| before = prev[z] | |
| compute.append([do["val"] for do in conversion if do["from"] == before and do["to"] == z][0]) | |
| z = before | |
| print(int(value) * reduce(lambda acc, v: acc*v, compute, 1)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment