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

I have not solved this problem for project euler and am going off of the question and the solution you provided. In the case of the single function, the methodology presented was ultimately simple pattern finding. The solver broke the presented question into three parts, based on the types of triangles that were present from the intersections. It's a fairly standard aproach to this kind of problem, break the larger pattern down into smaller ones to make solving easier. The functions used to express the various forms of triangles I can only assume were generated with either a very acute pattern finding mind or some number theory / geometry. It is also beyond the scope of this explanation and my knowledge. This problem has nothing to do with programming. It's basically entirely mathematics. If you read through the site you liked you can see the logic that is gone through to reach the questions.

Answer 2

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.