Project Euler 425 - Prime Connection

Official link: https://projecteuler.net/problem=425

Thought Process

This was one of my favourite Project Euler problems! It was a really fun coding challenge for me as I could theorize a solution very quickly but it took a lot of optimizations' before I could get an answer in an acceptable time.

My idea was to create a graph where each node is a prime and there is an edge between 2 primes if they are connected, and the weight of this edge is the larger prime. They we find the path from 2 to every prime such that the maximal element of the path is minimized. If the maximal element of this path is greater than the prime itself then it is not a 2 relative.

Then the problem clearly becomes implementing 2 parts:

I implemented my graph as an Adjacency List with weights using dictionaries. For example the graph[2] = {2: [(3, 3), (5, 5), (7, 7)]} since 2 is connected to 3, 5, 7 and the weight of this edge is 3, 5, 7 respectively

At first I tried just directly comparing every prime with every prime but it takes way too long and far too many unnecessary comparisons are made. 

Instead, for each prime, p, I directly find all the possible changes, n, larger than the original prime that can be made (change every digit, and add every digit Infront), and if this change is prime I add the edge (n, n) to graph[p] and I add (p, n) to graph[n]. 

Below is my implementation of step 1.

Now for step 2, the algorithm to find these minimax paths.

After some research I found this page: https://stackoverflow.com/questions/18552964/finding-path-with-maximum-minimum-capacity-in-graph/18553217#18553217 which explains that a modified Dijkstra's Algorithm can solve it and it also showed me that this path finding problem is actually a variation of the Widest Path Problem.

Having previously implemented Dijkstra's Algorithm I modified it to solve the problem. I had to make a lot of changes to my previously implemented algorithm as before my graph was a list, now I wanted it to be a dictionary to be faster, secondly I had to implemented a proper priority queue as sorting the queue and popping the first element was way too slow.

If you're not interested in making your own heapsort algorithm you can use the heapq module. I have implemented a heapsort algorithm for one of my coding classes before, so I just copied the code over and finally I could solve the problem! 

Below I include my implementation using the heapq module.

Interactive Code

Input an integer (yourinput)

Code will output F(yourinput)