10 ms·

Visual explanation of the last Google Codejam 2017 question

73 points by asrp 10y ago

hartator 10y ago
I wonder if there is a real cause and effect relationship between being good at this kind of games and being a good coder. I suspect not.
- bitcharmer 10y ago
  This has been discussed here before: https://news.ycombinator.com/item?id=9695102 https://news.ycombinator.com/item?id=9695102 I don't even bother replying to their recruiters any more. The interview process tells me more than enough about the company.
- ovi256 10y ago
  This is about hitting the high notes, as Joel Spolsky put it in his [post]. A lot of people are good software engineers and can wrote good software. To get Jeff Deans that write revolutionary software, we don't yet have a better method than training people in these abstract, very hard problems, making them compete and hoping for the best. As much as we software engineers / computer scientists believe we are special snowflakes, this exact same method is applied to most STEM PhD to professor tracks, mathematics, classic music instrument players, [athletes], and what have you. [post] https://www.joelonsoftware.com/2005/07/25/hitting-the-high-notes/ https://www.joelonsoftware.com/2005/07/25/hitting-the-high-n... [athletes] http://rittersp.com/wp-content/uploads/2014/03/Chambliss-Mundanity-of-Excellence.pdf http://rittersp.com/wp-content/uploads/2014/03/Chambliss-Mun... [musicians] http://www.nytimes.com/images/blogs/freakonomics/pdf/DeliberatePractice(PsychologicalReview).pdf http://www.nytimes.com/images/blogs/freakonomics/pdf/Deliber...
  - patrickmn 10y ago
    And, of course, being good at coding competitions doesn't mean that you're necessarily a good software engineer. The Jeff Deans are rare. "Hoping for the best" is pretty accurate.
- tedsanders 10y ago
  I suspect there is a real relationship. General intelligence is a real phenomenon. Being smart at one task indicates, though does not guarantee, that you'll be smart at another task. This is of course a different question than whether this test provides maximum predictiveness of future success. But it seems obvious to me that the test provides some information. It's really hard for a variable to be completely non-informative. Lastly, I think it's important for us to not be too defensive. I sense, perhaps incorrectly, that sometimes we don't want to give value to tests we are bad at, because doing so would imply we aren't as good as feel we are.
  - ijks 10y ago
    > doing so would imply we aren't as good as feel we are. Or to put it more pessimistically: even worse than we feel we are. Impostor syndrome and all that.
- user5994461 10y ago
  It ensures they have the basic: writing code. That you can learn alone on your computer when you are 15. That's entry level developer. The part where you make large software, working in teams, to serve real users, can only be learnt on a job. These competitions are not looking for anything fancy. They recruit juniors, they'll be trained on the job.
- ng12 10y ago
  I've interviewed and rejected many TopCoders and IOI competitors. Not sure why but it seems like a totally different skillset than software engineering.
- yodsanklai 10y ago
  I wonder too. I think it's like asking whether a math olympiad champion would make a great engineer. Certainly they have a lot of potential because they show extraordinary abilities, but there is much more to being a good coder than just being able to solve very short and extremely specific problems. I've been playing these games for a couple of years (initially, for interviews preparation), and it's been very instructive. The competition format makes it convenient and addictive. There's no doubt that I improved a lot on algorithms, data structures and on "small scale" coding. While this is useful, it is quite different than what you do when working on real projects.
  - Baeocystin 10y ago
    Math Olympiad Champion::Great Engineer as Excellent Sentence Diagrammer::Great Writer. Puzzles are fun, but it's best not to put too much predictive faith in them, because otherwise you're just affirming the consequent. Exceptional individuals are quite likely to be good at puzzles, but you cannot (in my experience) assume that because someone is good at puzzles, they have actual skill in solving real-world problems. I've worked with too many counterexamples.
  - nindalf 10y ago
    When I was preparing for interviews I found that the skill that overlapped between interview puzzles and everyday work was the "head interpreter" as I call it. Typically you end up relying on the IDE and the compiler telling you if what you're writing makes sense or not. Static analysis by the IDE would only tell you if you've made a syntax error, you would need to run a test to tell if what you've written makes logical sense too. So there's a couple of advantages if you can execute code in your head line by line while storing state as well. You can be slightly faster and more correct while coding yourself and while reviewing the code that others have written. Typically in the latter case you don't have the benefit of the compiler or running tests. In my anecdotal experience I found an improvement in my "head interpreter" after practising interview questions for a while because typically you're not allowed to execute your code. I can't say if any of the algorithms I learnt and practised helped, but this, in my opinion, made me slightly better at my day job.
kgwgk 10y ago
Their analysis in terms of chess pieces also helps: https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3 https://code.google.com/codejam/contest/3264486/dashboard#s=...
- deleted 10y ago
  [deleted]
- mlgh 10y ago
  Thank you! After reading blog-post I had zero understanding of what the problem is about and how they solve it. Tried to read again - no luck. Then I opened codejam link and saw that it's basically about placing maximum amount of bishops using maximum matching. (Other parts of problem are trivial) That's really sad that this pattern of bad explanations is so frequent in the internet.
conistonwater 10y ago
It's not really a maximum matching problem if a greedy algorithm works.
- anonymoushn 10y ago
  It's probably easier to come up with the reduction to maximum bipartite matching than to come up with a working greedy algorithm for bishops.
- asrp 10y ago
  Which greedy algorithm do you mean? I meant that bipartite matching was enough for getting the answer, not that the two are equivalent.
  - anonymoushn 10y ago
    There's a greedy algorithm explained at the bottom of this post: https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3 https://code.google.com/codejam/contest/3264486/dashboard#s=...
Achshar 10y ago
The more I scroll, the stupider I feel. Ugh.
- asrp 10y ago
  This wasn't my intention. I hope the feeling subsides! I did try to keep it short although some parts still (fortunately) shows how to come to those conclusion. That might give it the impression of being smart but the presentation is definitely selected among many idea and rearranged.
wslh 10y ago
Could this be easily solved with the Z3 theorem prover? Is Z3 an acceptable programming language for this code jam.
- njs12345 10y ago
  Looks like you would be allowed to use it: https://code.google.com/codejam/terms https://code.google.com/codejam/terms 'You may use any programming language to solve a Code Jam problem. However, for any round after the qualification round, the compiler, interpreter, libraries, and external services you use must be available such that anyone else can use it for free without a time limitation and without violating any rights of any person or entity'
dorianm 10y ago
Now I just need to understand flow networks: https://en.m.wikipedia.org/wiki/Flow_network https://en.m.wikipedia.org/wiki/Flow_network
- allenz 10y ago
  I think college lectures are still the best resource for learning problem solving. You might want to work through https://youtu.be/xWTc8xuHX00?list=PL-XXv-cvA_iDbtIylJDpPPJfaFweeaR-3&t=1111 https://youtu.be/xWTc8xuHX00?list=PL-XXv-cvA_iDbtIylJDpPPJfa...
  - dorianm 10y ago
    Thanks, I'm gonna see what can be applied to my own problems
stevebmark 10y ago
Is this trolling? I don't understand most of it and it ends in the middle of the unfollowable explanation.
- anonymoushn 10y ago
  After you reduce it to maximum bipartite matching you just use whatever stock algorithm for bipartite matching you want. Another comment links to the official writeup. The official writeup says that you can think about it as the "rook subproblem" and the "bishop subproblem" separately. This is the easiest way to think about it imo.
fidz 10y ago
How did you make the animation?
- asrp 10y ago
  I, um, recorded my screen while a loop was running to change values. Its a bit of a hack.
  - anonymoushn 10y ago
    What are you using to render the animation then?
    - asrp 10y ago
      I think Inkscape uses Cairo for rendering. So eventually Cairo. P.S., thanks for answering some of the questions in here! Guess I should reformulate that last part.
master_yoda_1 10y ago
I was also confused about algorithmic skill and software engineering skills. But I got clarification after working in industry for a while. 1) Most of the software engineering work is product development, just wrapping already existing algorithm and optimized computer program into apis and test and maintain it. 2) There are very few software engineering work involving writing algorithm and optimized computer program. One example, everyone here might have just used mysql database. But if you look into the code, you might see there are complex data structure, and algorithm are being used. https://github.com/mysql/mysql-server https://github.com/mysql/mysql-server Its a good thing to solve these kind of algorithmic problems.

73 points by asrp 10y ago

I wonder if there is a real cause and effect relationship between being good at this kind of games and being a good coder. I suspect not.

bitcharmer 10y ago
This has been discussed here before: https://news.ycombinator.com/item?id=9695102 https://news.ycombinator.com/item?id=9695102 I don't even bother replying to their recruiters any more. The interview process tells me more than enough about the company.
ovi256 10y ago
This is about hitting the high notes, as Joel Spolsky put it in his [post]. A lot of people are good software engineers and can wrote good software. To get Jeff Deans that write revolutionary software, we don't yet have a better method than training people in these abstract, very hard problems, making them compete and hoping for the best. As much as we software engineers / computer scientists believe we are special snowflakes, this exact same method is applied to most STEM PhD to professor tracks, mathematics, classic music instrument players, [athletes], and what have you. [post] https://www.joelonsoftware.com/2005/07/25/hitting-the-high-notes/ https://www.joelonsoftware.com/2005/07/25/hitting-the-high-n... [athletes] http://rittersp.com/wp-content/uploads/2014/03/Chambliss-Mundanity-of-Excellence.pdf http://rittersp.com/wp-content/uploads/2014/03/Chambliss-Mun... [musicians] http://www.nytimes.com/images/blogs/freakonomics/pdf/DeliberatePractice(PsychologicalReview).pdf http://www.nytimes.com/images/blogs/freakonomics/pdf/Deliber...
- patrickmn 10y ago
  And, of course, being good at coding competitions doesn't mean that you're necessarily a good software engineer. The Jeff Deans are rare. "Hoping for the best" is pretty accurate.
tedsanders 10y ago
I suspect there is a real relationship. General intelligence is a real phenomenon. Being smart at one task indicates, though does not guarantee, that you'll be smart at another task. This is of course a different question than whether this test provides maximum predictiveness of future success. But it seems obvious to me that the test provides some information. It's really hard for a variable to be completely non-informative. Lastly, I think it's important for us to not be too defensive. I sense, perhaps incorrectly, that sometimes we don't want to give value to tests we are bad at, because doing so would imply we aren't as good as feel we are.
- ijks 10y ago
  > doing so would imply we aren't as good as feel we are. Or to put it more pessimistically: even worse than we feel we are. Impostor syndrome and all that.
user5994461 10y ago
It ensures they have the basic: writing code. That you can learn alone on your computer when you are 15. That's entry level developer. The part where you make large software, working in teams, to serve real users, can only be learnt on a job. These competitions are not looking for anything fancy. They recruit juniors, they'll be trained on the job.
ng12 10y ago
I've interviewed and rejected many TopCoders and IOI competitors. Not sure why but it seems like a totally different skillset than software engineering.
yodsanklai 10y ago
I wonder too. I think it's like asking whether a math olympiad champion would make a great engineer. Certainly they have a lot of potential because they show extraordinary abilities, but there is much more to being a good coder than just being able to solve very short and extremely specific problems. I've been playing these games for a couple of years (initially, for interviews preparation), and it's been very instructive. The competition format makes it convenient and addictive. There's no doubt that I improved a lot on algorithms, data structures and on "small scale" coding. While this is useful, it is quite different than what you do when working on real projects.
- Baeocystin 10y ago
  Math Olympiad Champion::Great Engineer as Excellent Sentence Diagrammer::Great Writer. Puzzles are fun, but it's best not to put too much predictive faith in them, because otherwise you're just affirming the consequent. Exceptional individuals are quite likely to be good at puzzles, but you cannot (in my experience) assume that because someone is good at puzzles, they have actual skill in solving real-world problems. I've worked with too many counterexamples.
- nindalf 10y ago
  When I was preparing for interviews I found that the skill that overlapped between interview puzzles and everyday work was the "head interpreter" as I call it. Typically you end up relying on the IDE and the compiler telling you if what you're writing makes sense or not. Static analysis by the IDE would only tell you if you've made a syntax error, you would need to run a test to tell if what you've written makes logical sense too. So there's a couple of advantages if you can execute code in your head line by line while storing state as well. You can be slightly faster and more correct while coding yourself and while reviewing the code that others have written. Typically in the latter case you don't have the benefit of the compiler or running tests. In my anecdotal experience I found an improvement in my "head interpreter" after practising interview questions for a while because typically you're not allowed to execute your code. I can't say if any of the algorithms I learnt and practised helped, but this, in my opinion, made me slightly better at my day job.

kgwgk 10y ago

Their analysis in terms of chess pieces also helps: https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3 https://code.google.com/codejam/contest/3264486/dashboard#s=...

deleted 10y ago
[deleted]
mlgh 10y ago
Thank you! After reading blog-post I had zero understanding of what the problem is about and how they solve it. Tried to read again - no luck. Then I opened codejam link and saw that it's basically about placing maximum amount of bishops using maximum matching. (Other parts of problem are trivial) That's really sad that this pattern of bad explanations is so frequent in the internet.

conistonwater 10y ago

It's not really a maximum matching problem if a greedy algorithm works.

anonymoushn 10y ago
It's probably easier to come up with the reduction to maximum bipartite matching than to come up with a working greedy algorithm for bishops.
asrp 10y ago
Which greedy algorithm do you mean? I meant that bipartite matching was enough for getting the answer, not that the two are equivalent.
- anonymoushn 10y ago
  There's a greedy algorithm explained at the bottom of this post: https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3 https://code.google.com/codejam/contest/3264486/dashboard#s=...

Achshar 10y ago

The more I scroll, the stupider I feel. Ugh.

asrp 10y ago
This wasn't my intention. I hope the feeling subsides! I did try to keep it short although some parts still (fortunately) shows how to come to those conclusion. That might give it the impression of being smart but the presentation is definitely selected among many idea and rearranged.

wslh 10y ago

Could this be easily solved with the Z3 theorem prover? Is Z3 an acceptable programming language for this code jam.

njs12345 10y ago
Looks like you would be allowed to use it: https://code.google.com/codejam/terms https://code.google.com/codejam/terms 'You may use any programming language to solve a Code Jam problem. However, for any round after the qualification round, the compiler, interpreter, libraries, and external services you use must be available such that anyone else can use it for free without a time limitation and without violating any rights of any person or entity'

dorianm 10y ago

Now I just need to understand flow networks: https://en.m.wikipedia.org/wiki/Flow_network https://en.m.wikipedia.org/wiki/Flow_network

allenz 10y ago
I think college lectures are still the best resource for learning problem solving. You might want to work through https://youtu.be/xWTc8xuHX00?list=PL-XXv-cvA_iDbtIylJDpPPJfaFweeaR-3&t=1111 https://youtu.be/xWTc8xuHX00?list=PL-XXv-cvA_iDbtIylJDpPPJfa...
- dorianm 10y ago
  Thanks, I'm gonna see what can be applied to my own problems

stevebmark 10y ago

Is this trolling? I don't understand most of it and it ends in the middle of the unfollowable explanation.

anonymoushn 10y ago
After you reduce it to maximum bipartite matching you just use whatever stock algorithm for bipartite matching you want. Another comment links to the official writeup. The official writeup says that you can think about it as the "rook subproblem" and the "bishop subproblem" separately. This is the easiest way to think about it imo.

fidz 10y ago

How did you make the animation?

asrp 10y ago
I, um, recorded my screen while a loop was running to change values. Its a bit of a hack.
- anonymoushn 10y ago
  What are you using to render the animation then?
  - asrp 10y ago
    I think Inkscape uses Cairo for rendering. So eventually Cairo. P.S., thanks for answering some of the questions in here! Guess I should reformulate that last part.

master_yoda_1 10y ago

I was also confused about algorithmic skill and software engineering skills. But I got clarification after working in industry for a while. 1) Most of the software engineering work is product development, just wrapping already existing algorithm and optimized computer program into apis and test and maintain it. 2) There are very few software engineering work involving writing algorithm and optimized computer program. One example, everyone here might have just used mysql database. But if you look into the code, you might see there are complex data structure, and algorithm are being used. https://github.com/mysql/mysql-server https://github.com/mysql/mysql-server Its a good thing to solve these kind of algorithmic problems.