from Hacker News

Lattice Quadrilaterals on Project Euler

by aabalkan on 2/8/14, 7:46 PM with 19 comments

• by ClayFerguson on 2/8/14, 10:58 PM

  Mind blower #2: How many different shapes can a brain with 4 neurons recognize? 94. Evolution of vision neurons actually would have started out using a "chance built" circuit that could solve this 94-item 'recognition' problem. Then the DNA that solved the 94 would run repeatedly to recursively form the rest of the retina, giving the brain higher resolution, but using only one 94-pattern-solving DNA recursively. I think the major advancements in neural nets will come about once we start "wiring up" brains in interesting ways like this rather than the current "layer training" approach...The brain is recursive, and needs recursive wiring to be simulated.

• by thearn4 on 2/8/14, 9:09 PM

  Basically, you're looking for the rectangular equivalent of A189414 (http://oeis.org/A189414).

  Tricky problem, even for PE. I started to retool some earlier success with it towards a quasi-DP approach, but have since got caught up in other things.

• by throwaway_yy2Di on 2/8/14, 9:08 PM

  Suggestion: use rot13 if you say anything potentially spoiler-y.

• by susi22 on 2/8/14, 11:20 PM

  Btw, the problem was solved by 61 people so far.

  Random thoughts:

  I think the mod is just there to distract or for hinting that you shouldn't come up with a brute force method.

  Observations:

  1. Assume an infinite grid. Add 3 random points _not_ on a line. Clearly, they'll be a convex set (a triangle).

  2. Add a 4th point such that it is not on an existing line.

  You've now a quadrilateral.

  So for the case of Q(2,2) = 94 = choose(9,4) - 32. 32 is the number of points that would make 3 of the 4 points lie on a line.

  Come up with a recurrence relations and solve it.

• by ClayFerguson on 2/8/14, 10:49 PM

  Traveling Salesman Problem... Will this algorithm work?

  Algorithm:

  1) Take a square space and divide it into 4 squares.

  2) Find all 94 quadrilaterals that the 'nodes' can form.

  3) For each quadrilateral, that has points in common with the original, do recursion (I.e. go to step #1 for each of the 94)

  4) Keep repeating until some minimal square size (resolution) is reached.

  Find the path with the shortest 'Error' and that's an approximation to the traveling salesman problem.

  'Error' is defined as the sum of the distances of all travel waypoints to the nearest quadrilateral path line.

• by Bootvis on 2/8/14, 9:18 PM

  I've solved about 60 problems on Project Euler but I've no clue about problems where a mod suddenly shows up in the question. How do these type of questions work?