Working on The Witness: The Nebraska Problem | Hacker News Reader

Working on The Witness: The Nebraska Problem

mollyrocket.com

110 pointsvilhelm_s19 comments

This reminded me of the "rivers of white" effect in typesetting.

http://en.wikipedia.org/wiki/River_(typography)

I'm a little surprised there's no musings about Fibonacci or Prime numbers.

Certain real-world plants "use" Fibonacci sequences to avoid gaps in their leaf-coverage, which seems eerily reminiscent of OP's problem with covering up gaps using... ah, virtual plants.

As for primes, it seems to me like the typical corn-row problem comes about when there's a certain kind of periodicity in the layout.

So, did you read the article through to the end, because the solution is pretty elegant? Incidentally, the way plants get distributed is somewhat different from the way they distribute parts of themselves.

> So, did you read the article through to the end, because the solution is pretty elegant?

Yes, I read the entire thing (on my phone, even) before starting a reply... Why did you want to know?

> Incidentally, the way plants get distributed is somewhat different from the way they distribute parts of themselves

Certainly, but the OPs goal of "no repeated gaps along a line" only maps to one of those cases... AFAIK plants have no particular incentive to avoid the occasional line-segment as they compete for placement.

It seems like you were proposing a similar (i.e. Perturbed non-random) solution to what was eventually arrived at except that his solution directly derives from the goal.

This is a great "classic HN" post. Does anyone know of an archive of these sorts of "how I solved problem X"?

Yeah, HN

Hacker News is horrible for archiving, though. The affordances work against a strong community memory, unless there's a secret 'best of' list I don't know about.

The trouble with HN's archives is that most of the 1.5M stories [1] that have been submitted are junk, so it can be hard to track down the gold. At the same time, there's a great deal of gold there, including much that never got the attention it deserved. We've been toying with ideas about how to reclaim some of it.

[1] The number is 1,472,221 as of two minutes ago, if anyone cares.

I think the problem here is they were trying to solve two different problems, but were trying solutions that solve only one or the other at a time, and then complaining it made the other worse:

  1. It should not be possible to draw a rectangle wider than a certain diameter and length through the points (at any orientation).
  2. The distance between any point and the nearest neighbouring point must not exceed a specified threshold.

An easy way to sample points from a random distribution but with additional constraints applied would be to do rejection sampling - if a point doesn't meet the constraints, reject it and start again. For this to work, you would need to formulate your constraints based on the number of points accepted so far so you don't reject all the points (for example, sample the first few points randomly, and then sample the next points using rejection criteria based on a multiple of the theoretical minimum values of the distance between points / size of the rectangles for the number of points sampled so far).

This requires being able to efficiently work out the greatest distance between points and finding the largest rectangle of a given width. You could do the former with a quad-tree; if the new candidate point is too close to the nearest neighbour, reject it; if it is accepted, add it to the quad-tree. For the rectangles, you could optimise by creating a Fibonacci heap with the largest rectangle so far for each point - the largest rectangle will never get bigger as you add more points, so you should be able to do much better than O(n^2) time in the number of points (I haven't verified this, however) because you can skip checking most points most times.

If you read the series, you'll see that what you call "rejection sampling" is in fact the first thing that was tried, and it was set aside for performance reasons. Yes you can try to improve the perf of this kind of system, but the goal was to build something that would run with much less overhead than that. And this was accomplished, and it seems to me that the end result runs faster than any optimized version of the system you are proposing. So I'd be careful with dishing out what reads to me here like middlebrow dismissal.

Points for tenacity. And what an incredibly nice write-up, not so much for the problem solved but for the way in which it was eventually solved.

A great illustration of the cornerstone of the scientific method at work.

Too bad he didn't try low discrepancy sequences (http://en.wikipedia.org/wiki/Low-discrepancy_sequence) instead of random sequences to generate those fields.

As far as I can see, every single one of the examples on the Wikipedia page you linked suffers from some form of the Nebraska problem. Which makes sense, given the original author's comments in the "Why Such Abundant Failure?" section of the original article.

This website is incredibly frustrating to use. Whenever you resize the window, the scroll position resets to the top-left corner. On mobile browsers, this seems to happen at random, making the content nearly unreadable.

Without the punishing JavaScript: https://archive.today/5hO3F

For me it seemed to happen whenever I scrolled up. It was challenging to read through to the end.

In Chrome for Android, scrolling up causes the address bar to appear, which shrinks the viewport and triggers a resize event.

I sent an email to the author, and he was able to fix the script.

Funny. I came to the solution a minute into reading the article. I'm no graphics wiz or anything, it was all a matter of having the right inspiration...

Yesterday was my nephew's first birthday. My family had a basketball theme. In between superficial conversations I noticed the pattern on a cheap rubber basketball was made of dots that form overlapping, concentric circles. I thought the pattern was neat and it stuck with me...

Reply on news.ycombinator.com