Hacker News Reader

Comment by rav | Hacker News Reader

Since there's just a single instance, you can find the optimal solution manually and write a 29-line program that specifies the 29 rectangles in the optimal solution.

The general version of this problem can be termed "the minimum dissection of a rectilinear region" and can be solved optimally using a sweep-line and computing the maximal independent set in a bipartite graph as described in section 7.1 of [1].

Now if you'll excuse me, I'm gonna have some fun implementing this result in JavaScript.

[1] Hiroshi Imai, Takao Asano: Efficient algorithms for geometric graph search problems (1986) https://dl.acm.org/citation.cfm?id=14098 http://epubs.siam.org/doi/pdf/10.1137/0215033

View on HN

Here's the concept, neatly illustrated: http://stackoverflow.com/a/6634668/116546

(Offtopic rant) Guess, I'm not really suited for programming. When I read I remembered I've heard about an algorithm for such tasks, Googled the details up to freshen my memory, and things instantly became boring. :(

Having found the same algorithm in a (different) review paper I almost implemented this for fun.

Sadly, JavaScript.

Can we make "Sadly, Javascript." a motto for computer programming in 2014?

#SadlyJavascript

Would you have played if you could choose Python or CoffeeScript, or would we have to be epic and write a Haskell -> JavaScript transpiler to pass go?

Yes, I would be more likely to play in Python, though I guess I do need to bite the bullet and learn javascript at some point.

If you can integrate haste or fay and let people play in Haskell that would be indeed be epic, and I would definitely use it (as haskell is my learning project at the moment)

I would have played in Python, Ruby, or C++. I almost played in CoffeeScript by compiling it myself.

I don't know Haskell, but I would have considered learning it if it was offered. ;)

> write a Haskell -> JavaScript transpiler

There are at least three of them already - UHC's JS backend, Haste and Fay.

Oh cool, I'll check those out tonight (and a bunch of Python parsers people have pointed me at). CodeCombat's challenge is to transform other languages into a Mozilla AST so that we can apply our crazy transpilation stuff to it. So anything that makes that easier brings us closer to supporting those languages in our levels.

I would be happy if I was able to submit C++ or Python. I am very familiar with the data structures in their standard libraries, and implementing this in JavaScript is very tedious in comparison.

Why not ClojureScript instead?

Could be fun.

Just add Fay.

I came up with a general O(n^2) algorithm that yields 30 rectangles, which is one off from the optimal answer according to you. Actually, it's only O(n^2) because I'm exhaustively searching an array instead of indexing by xy coordinates in nested hashes, which would yield O(n).

Basically, it just fills the spaces with rectangles, expanding horizontally. Then I look for "stacks" of vertical adjacent rectangles and combine them.

(EDIT: Goes to show that you can get pretty good though non-optimal results by taking the low hanging fruit and optimizing a bit.)

I did the same!

I feel stupid now.

Don't be. These kinds of problems are algorithmic problems and have very little bearing on your capabilities as a developer from an engineering perspective.

For me, its like saying someone who is poor at physics makes a poor accountant.

While a fun exercise, I feel that it doesn't actually test for actual programming ability as it actually requires the programmer to be familiar with this particular subset of algorithms first (something that isn't entirely fundamental imho). I do not believe many jobs require the skillset that this problem tests for.

For example, I had very little idea how to approach this problem in an optimal way. But once I read the comment above I figured out a pretty brute force method. You can get 34 by just joining contiguous segments in each column with segments in their neighbouring columns if they have the same row and height. With some trimming I managed to get 30... not really sure if 29 is actually possible actually, I can't find where I can cut down on 1 more.

Edit: found it. Very tricky edge case with my algorithm. Happy with 30.

> While a fun exercise, I feel that it doesn't actually test for actual programming ability as it actually requires the programmer to be familiar with this particular subset of algorithms first (something that isn't entirely fundamental imho).

I don't think you are required to know this particular subset of algorithms first -- I certainly did not, and it took me about half an hour of searching around the net until I found the right terms to use.

Perhaps max cardinality bipartite matching is something I know from my first year at CS, but I didn't know its application to this problem before I had read through several different answers on StackExchange.

Reply on news.ycombinator.com