Project Euler 630 - Crossed Lines

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

Thought Process

There are a few key facts that simplify this problem greatly:

If 2 lines are not parallel they will intersect
Given 2 points, a line ax + by + c = 0 can be generated
- We use ax + by + c = 0 because if we use y = mx + b, we will run into precision errors

Using the above 2 points, this problem is simplified into being able to generate all the distinct slopes uniquely, and storing the number of parallel lines for each distinct slope

My code an definitely be optimised. I have 3 functions:

LineCreator(point1, point2)
- Takes in 2 points, creates a line and performs the process above to output a/g, b/g, and c/g
T(pointn)
- Performs the recursion until a list containing all the points has length 2*pointn
compute(x)
- Has a nested for loop, first loop goes through all points, second loop start at the next point till the end to generate all lines. These are stored in a set, essentially this process remove all duplicate lines. M = len(said set)
- Has a dictionary called gradients, go through all the lines and if a gradient (a,b) is in gradients then gradients[(a,b)] += 1, otherwise just gradients[(a,b)] = 1. This counts the number of lines which are parallel, for example if gradients[(1,2)] = 3, this means that there are 3 distinct lines with gradient a/b
- Finally step is to count the anwser

This is because, all the parallel lines will cross all others lines (M - m(i))

Interactive Code

Enter an integer (yourinput)

Code will output M(L(yourinput)) and S(L(yourinput)) Note: It gets quite slow after 900

Page updated

Google Sites

Report abuse