News for hackers. Stuff that matters.
Re:Beat This Level, Get A Programming Job by rav on Saturday December 28, 2013 @05:10PM (#6976869)
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

Re:Beat This Level, Get A Programming Job by drdaeman on Saturday December 28, 2013 @06:20PM (#6977109)
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. :(

Re:Beat This Level, Get A Programming Job by thomasfedb on Saturday December 28, 2013 @05:47PM (#6977011)
Having found the same algorithm in a (different) review paper I almost implemented this for fun.

Sadly, JavaScript.

Re:Beat This Level, Get A Programming Job by sarreph on Saturday December 28, 2013 @06:22PM (#6977119)
Can we make "Sadly, Javascript." a motto for computer programming in 2014?

#SadlyJavascript

Re:Beat This Level, Get A Programming Job by nwinter on Saturday December 28, 2013 @05:52PM (#6977027)
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?
Re:Beat This Level, Get A Programming Job by triplepoint217 on Saturday December 28, 2013 @07:39PM (#6977442)
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)

Re:Beat This Level, Get A Programming Job by thomasfedb on Saturday December 28, 2013 @08:16PM (#6977627)
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. ;)

Re:Beat This Level, Get A Programming Job by drdaeman on Saturday December 28, 2013 @06:27PM (#6977129)
> write a Haskell -> JavaScript transpiler

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

Re:Beat This Level, Get A Programming Job by nwinter on Saturday December 28, 2013 @06:50PM (#6977229)
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.
Re:Beat This Level, Get A Programming Job by rav on Saturday December 28, 2013 @05:59PM (#6977053)
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.
Re:Beat This Level, Get A Programming Job by Morgawr on Saturday December 28, 2013 @08:21PM (#6977648)
Why not ClojureScript instead?

Could be fun.

Re:Beat This Level, Get A Programming Job by coolsunglasses on Sunday December 29, 2013 @03:54AM (#6978933)
Just add Fay.
Re:Beat This Level, Get A Programming Job by stcredzero on Sunday December 29, 2013 @12:18PM (#6980268)
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.)

Re:Beat This Level, Get A Programming Job by garrettdreyfus on Sunday December 29, 2013 @03:59PM (#6981362)
I did the same!
Re:Beat This Level, Get A Programming Job by funky_vodka on Saturday December 28, 2013 @05:41PM (#6976985)
I feel stupid now.
Re:Beat This Level, Get A Programming Job by darylteo on Saturday December 28, 2013 @08:36PM (#6977717)
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.

Re:Beat This Level, Get A Programming Job by rav on Sunday December 29, 2013 @07:48AM (#6979403)
> 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.