Project Euler #163 understanding

Question

I spent quite a long time searching for a solution to this problem. I drew tons of cross-hatched triangles, counted the triangles in simple cases, and searched for some sort of pattern. Unfortunately, I hit the wall. I'm pretty sure my programming/math skills did not meet the prereq for this problem.

So I found a solution online in order to gain access to the forums. I didn't understand most of the methods at all, and some just seemed too complicated.

Can anyone give me an understanding of this problem? One of the methods, found here: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (Problem C) allowed for a single function to be used.

How did they come up with that solution? At this point, I'd really just like to understand some of the concepts behind this interesting problem. I know looking up the solution was not part of the Euler spirit, but I'm fairly sure I would not have solved this problem anyhow.

Answer 1

This is essentially a problem in enumerative combinatorics, which is the art of counting combinations of things. It's a beautiful subject, but probably takes some warming up to before you can appreciate the ninja tricks in the reference you gave.

On the other hand, the comments in the solutions thread for the problem indicate that many have solved the problem using a brute force approach. One of the most common tricks involves taking all possible combinations of three lines in the diagram, and seeing whether they yield a triangle that is inside the largest triangle.

You can cut down the search space considerably by noting that the lines are in one of six directions. Since a combination of lines that includes two lines that are parallel will not yield a triangle, you can iterate over line triples so that each line in the triple has a different direction.

Given three lines, calculate their intersection points. You will have three possibilities 1) the lines are coincident - they all intersect in a common point 2) two of the lines intersect at a point outside the triangle 3) all three points of intersection are distinct, and they all lie within the outer triangle

Just count the combos satisfying condition (3) and you are done. The number of line combos you have to test is O(n³), which is not prohibitive.

EDIT1: rereading your question, I get the impression you might be more interested in getting an explanation of the combinatorics solution/formula than an outline of a brute force approach. If that's the case, say so and I'll delete this answer. But I'd also say that the question in that case would not be suitable for this site.

EDIT2: See also a combinatorics solution by Bill Daly and others. It is mathematically a little gentler than the other one.