Beat This Level, Get A Programming Job | Hacker News Reader

Beat This Level, Get A Programming Job

blog.codecombat.com

69 pointsnwinter73 comments

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

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.

CodeCombat is just acting like a recruiter here. Do they have any advantage over traditional recruiters that may be more highly connected?

Beat this level, and we'll send your resume to some companies that are hiring. And those companies will pay us a hefty commission.

This is a good point. Traditional recruiters have different ways of knowing how good you are at programming (often they don't). By starting with your Gridmancer competency, we can potentially find and qualify you for opportunities that traditional credentials couldn't. (And we're not going to send candidates who aren't good enough to higher-skill positions.)

One weakness is that we don't have a good way of measuring how much software development (as opposed to core programming skill) you have. In this sense, we don't yet have an advantage over traditional recruiters.

Traditional recruiters do have better connections, for now, but we are going really high-hustle for this initial batch of players, so it's not like we're just sending off resumes.

Is the general consensus now that core programming skills and being good at math are the same thing? Because after taking a look at this challenge it appears to be a math problem that requires mathematical knowledge and barely any programming knowledge.

Did you even try it? You can get pretty far by just tinkering. I came up with a O(n) algorithm that gets me 30 rectangles just by playing around. In general, you can get "pretty good" results just by taking low hanging fruit then optimizing.

Glad I'm not the only one who thought this. Exercises like these have a very poor accuracy if it is used it to test for developers.

See above. Could be testing for problem solving ability and willingness to try.

I'm skeptical of this whole approach. I've done a ton of these code challenges (ranging from literally FizzBuzz level up to stuff involving dynamic programming, recursion, and NP-complete problems) on CodeEval, and it's never gotten me anywhere close to a new job (though some of them were kind of fun). What makes you think your code challenges are any better than theirs for this particular purpose?

I was thinking the exact same thing. I was really excited when I discovered codeEval, but after solving a few of the 'hard' challenges on there it became clear to me that hiring managers were looking for more well-rounded programmers with demonstrated experience in software development (something I've been working on through my own post-academic studies), not someone who can whip out a solid recursive algorithm to solve a brain teaser.

And it makes perfect sense to me, the former is more likely to be actually useful in the day-to-day of a software engineering position, and the latter might only come in handy once in a blue-moon, or for more mathematics heavy domain-specific positions that require less code ejaculation and more optimization anyway.

It's actually even worse in my case. I do have 1.5 years of actual engineering experience at a real company. That tells me that CodeEval (and maybe "code challenges" in general) have at most very little and at worst negative signal value. (Well, either that or I'm a terrible engineer, but I think they would have fired me long before a year and a half if that were the case.)

Is there a problem with recruiters working harder to find the best candidate/job fit? It's a nice change from having to compete (or work with!) people rammed into the wrong sorts of jobs.

Worst case you can have fun with the levels and just not worry about the job bits.

Only the very darkest realm would deprive its wizards of the mighty printf spell! To what Silicon demon legion did you pledge fealty to summon this coding abomination upon an unsuspecting land? Winter is truly coming at last.

(Otherwise pretty neat)

I know, I know. Try this.say() for a poor man's replacement.

We haven't improved it much because we are going to make an awesome timeless debugger, where you just hover over the variables to see their values at any point in time as well as scrubbing forward and backward through your entire program's execution (like jsdares does), all without any breakpoints, but haven't quite got it yet.

Honestly, it's almost impossible to make a good solution to this without console.log. We need some way to inspect the undocumented grids and rectangles you've given us.

Why? All you need to know is the grid width\height, and whether a grid coord is empty. All of which is shown in the example.

My solution required marking each coord as non-empty when I dropped a rect on it. I was able to hack something that worked (non-zero-len string stuffed into the structure), but I'd much rather know what the structure was instead of guessing.

p.s. 29 ha ha

To those playing: if you want to be able to find your code again later, go to the CodeCombat home page and sign up for a free account! Sorry, we derped out and didn't put any signup form accessible from the Gridmancer level.

Also, we're sorry that we left you without good debugging tools: https://news.ycombinator.com/item?id=6976883 -- this is the #1 problem uncovered today. We will retreat in tearful shame to our code lairs until we can blow your minds with our timeless debugger.

You are amazing players--so many good solutions here. Thanks for playing! To those who sent in solutions and are looking for dev opportunities, we'll be in touch this weekend to see what we can do and learn about what you're looking for.

Also, we're sorry that we left you without good debugging tools

I just thought that was part of the challenge. (See if you can get by with scientific method and printf debugging.) The biggest problem I had was that the environment kept freezing. However, copy-pasting into the window from emacs worked fine.

Submit the solution using the contact button at the bottom (didn't signed up)?

That's fine, too--we'll have your code, but you may not (after you change browser sessions). Well, until we reply to your email.

I can't play using Safari 7.0.1 on OS X 10.9.1. (And by "can't play", I mean I see the "CodeCombat requires a modern browser to play" screen.)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_9_1) AppleWebKit/537.73.11 (KHTML, like Gecko) Version/7.0.1 Safari/537.73.11

Sorry about that. The fix is deploying right now.

> there aren't enough programmers to meet the demand.

There aren't enough good programmers to meet the demand for low paid programmers.

This seems pretty incredible that CodeCombat has already reached the point where they're placing people into jobs. It's supposed to be Codecademy's goal [1] to do that eventually but they've been around much longer.

1. http://bits.blogs.nytimes.com/2011/09/14/codecademy-offers-f...

There's a pretty big difference in audience in these two examples. Codecademy is targeting people who have no, or nearly no, experience programming and trying to turn them into programmers. CodeCombat's normal stuff appears to be in the same vein, but this specific challenge is something only a fairly experienced programmer is likely to solve. It's easy to place great programmers. Not so easy to take someone, make them a good programmer, and then get them a job.

We are doing it in a way that won't scale: George is just going to hustle to make the placements. Codecademy might have a different problem to solve, too: the players we're placing through this level are mostly people with existing skills who like a fun challenge, not players who have gotten there from scratch through the site's content (like all Codecademy users). It'll be a while before we have enough content to take raw beginners to the required skill levels.

SOLVED.

-29 rectangles

-O(N) worst-case complexity

-Under 200 lines

https://gist.github.com/foxly/8168624 http://imgur.com/PXcUEHz

Shoutout to the gents at codecombat -- this is what hustle looks like.

These guys have been busting tail ever since the initial DDOS; I'm really rooting for them to make it big.

Thanks guys! Happily serving more concurrents right now at 10% CPU than during that first big traffic spike that took us down.

A better way to look at the object's structure/values would help a lot. Seems like the first step would be to generate a list of vertices from the 2d array of tiles.

Just curious - would anyone here currently hiring consider the winning candidates any more than they would from a (reputable) recruiter?

I'm not trying to be a cynic - I really hope this works and solves a real problem. This is honest feedback from someone has and will continue to evaluate talent for technical teams - proof of algorithmic ability is only one tick mark of the dozens needed.

We're not sure ourselves; we're testing the waters with this level to find out exactly that. And if it looks like this monetization strategy has legs, we'll aim to expand what we can provide to companies so we can be more compelling.

We'll be interested to hear what others think about this too!

The blog post talks about minimizing count(rects) but the in-game comment only mentions having better than one rect per floor tile.

This second requirement is much simpler. One only needs to merge a single two rects into one rect to fulfil it. I assume this is a bug?

Edit: Sorry I didn't read the original post well enough the first time. It gives the more practical goal of 40 rects or less.

I'll change the default code comments. We were much less ambitious before our playtesters blew my algorithm out of the water.

It covers all of the little coins!

  this.addRect(0, 0, 200, 200);

Clever! In an ideal world, we'd have logic to prevent incorrect configurations so rectangles couldn't touch walls. There would also be ogres dying and explosions and battle music and such related to the efficiency of your algorithm--you know, actual gameplay mechanics, like our other levels. Didn't have time to get those in yet, though.

It would be very nice to have a console.log/dir style function that would let you inspect objects/arrays. (Makes debugging significantly easier).

Also, any chances of expanding beyond California?

You are so right, I am ashamed. See also this comment: https://news.ycombinator.com/item?id=6976883

We could try doing placements outside of California later, but for now we don't have much of a network outside of the SF Bay Area. (We're quite young as a startup.)

One question, why does this.addRect use the center of a rectangle to define it rather than a vertex? It makes attempting dealing with "native" rectangles rather awkward.

That's how all the CodeCombat game engine works (things are positioned by their center points), so because this challenge was taken from an algorithm used in two places in the engine, it maintains that. I know it makes it a bit more complicated to write the code, but it's a lot easier for us to then snatch the winning solution to make CodeCombat faster!

Hi. I took this challenge, asked for help in finding a job, and heard nothing back.

I could really use help as my resume is mostly Flash/Actionscript related work, which is not in demand, and it's difficult to convince the "filtering" HR reps that my skills are applicable to other languages. So if this proves that I can code, then I should be able to get a job?

'this' is quirky when you make your own functions. also Starcraft II runs more smoothly on my computer, no joke

This was a great way for me to get back into programming after the holiday break. Your optimal number seems off, though; I ended up with a solution in 27 rects:

http://imgur.com/hAOLUaD

try it again without overlapping the rects.

It was all fun and games until chrome crashed and lost the code I was writing.

Why do you need 20+ screenshots of the game screen within less than a second?

We, uh, don't! That sounds like a bug that I would love to slay. Can you give me some more info?

[nothing wrong, except my brain]

This is for our multiplayer game list, which we haven't quite turned on for non-admins yet: https://www.dropbox.com/s/n956u62zdlghqjw/Screenshot%202013-...

But it should only take one screenshot every 30 seconds, and only when something changes, so this is a bug! I will fix. Thanks so much!

> "But it should only take one screenshot every 30 seconds"

The bug is in my reporting tool I just realized. Yes, it reports only each time the screen change. Sorry about that. About multiplayer, understood, make sense.

Oh, okay. I thought I had a performance improvement at hand, so I was excited! Thanks for digging into that.

40? That doesn't even seem to be a challenge. Are you sure you want to recommend people that can't get the optimal solution?

Why can't someone make a test account first, and then replay the best answer much more quickly with their real account?

Deleted comment

You have a fun time? (You have to ask us to place you; we're not going to spam anyone who plays and doesn't reach out.)

You can pat yourself on the back.

Reply on news.ycombinator.com