Page 4 of 7
Re: Google Code Jam
Posted: Sun Apr 09, 2017 5:45 am
by hyperpape
Ugh. I never ended up getting Bathroom Stalls, after spending about 3 hours working on it. My approach is roughly the same as the one in the analysis for the large one, but I have a bug that I was never able to track down. My answer gave me the right answers on every case that I was able to check, but was wrong on something else. I'll have to download solutions/someone else's code and find out which cases I'm answering wrong.
So I ended up with 20 points for answering Tidy Numbers.
One observation if I do this again: I spent more time fighting with maven and intellij than the top contestants spent solving any individual problem (it alternately wanted to compile using Java 1.5 and then refused to import JUnit for testing for reasons I don't understand).
Re: Google Code Jam
Posted: Sun Apr 09, 2017 11:36 am
by HermanHiddema
@hyperpape: I had a subtle off-by-one on my first implementation of bathroom stalls. I don't know if you're running into the same problem, but if you are, here are some cases I got wrong first time round: 500 stalls 117 people, 500 stalls 245 people and 1000 stalls 489 people
Re: Google Code Jam
Posted: Sun Apr 09, 2017 11:56 am
by Kirby
FWIW, checking every single empty bathroom stall and calculating distance from other stalls every single time still works fast enough to get the 5 points for the small problem set. I did this on Friday when I couldn't think of a good efficient implementation.
Re: Google Code Jam
Posted: Sun Apr 09, 2017 6:00 pm
by Solomon
Kirby wrote:I guess in the next round, we have to be fast, since there's a cut off. Personally I think that participating at a fitting schedule trumps playing at a less popular time.
Solving problems at 2am is a lot harder than during the day.
Oh, I'll certainly try my best in 1A and 1B as well which start at reasonable times (especially since I get Friday off, and 1A is on then). I'm just not too optimistic about getting through for those seeing past contest results. Plus I already wake up early every day (4am), so shifting it two hours behind for 1C shouldn't be too bad

.
Re: Google Code Jam
Posted: Sun Apr 09, 2017 7:42 pm
by Kirby
Solomon wrote:Plus I already wake up early every day (4am), so shifting it two hours behind for 1C shouldn't be too bad

.
Wow, I guess you can at least beat the traffic :-p
Re: Google Code Jam
Posted: Mon Apr 10, 2017 4:02 pm
by Kirby
I got the email for Round 1 today, and it says that "collaboration is strictly prohibited in Round 1".
So I guess we should hold off on commenting on any problems until after 1C.
Re: Google Code Jam
Posted: Mon Apr 10, 2017 4:38 pm
by Shaddy
It's funny that collaboration wasn't banned in the qualification round. By the way, what's everyone's nick on code jam? I'm shadonra on there.
Re: Google Code Jam
Posted: Mon Apr 10, 2017 5:27 pm
by Solomon
L19 (GCJ)
- apetresc (apetresc)
- gamesorry (SuperRabbit)
- HermanHiddema (herminator)
- hyperpape (hyperpape)
- Kirby (Kirby)
- Shaddy (shadonra)
- Solomon (tesuji)
Re: Google Code Jam
Posted: Mon Apr 10, 2017 7:24 pm
by jeromie
I haven't been around here much lately, but I am doing the code jam. I only got 25 points in the first round, but at least I get to move onto the second.
I actually had an O(1) solution for the bathroom stalls problem--I figured out how to solve the problem mathematically--but I failed the large set because my solution relied on floor / ceiling functions and I forgot to take into account that I would lose the least significant digits with numbers as large as 10**18.
I'm jeromie on Google as well as here.

Re: Google Code Jam
Posted: Tue Apr 11, 2017 2:22 pm
by Kirby
Since Shaddy did pretty well, I compared some of the source files I submitted to the ones that he submitted (I hope you don't mind, Shaddy - I only compared since you did a pretty good job).
Aside from simply being better at solving problems

, here are some differences I noticed, which maybe I should learn from to become a better programmer:
1.) My source code is much more verbose. Just comparing 'TidyNumbers', my source code is about twice as long. I have several more spaces, some unnecessary functions, and I use much longer variable names.
2.) Not a huge deal, but the logic I had for reading from and out to files was unnecessary. I like the idea of just using stdin and stdout - it cuts the program down to what's necessary to solve the problem.
3.) My approach to solving the problem appears to be less direct. I start typing out a high level outline of what I think needs to happen, and then when I get a little stuck, maybe I throw in a function call to solve that subproblem later. In contrast, it would be nicer to directly think of what needs to happen algorithmically right at the moment that I'm solving the problem.
Maybe it's easiest to say that I need to be more concise, and directly solve the problem. But perhaps this is just due to the fact that I didn't solve the problem entirely in my head before I sat down and started typing. It might come down to just being better at problem solving.
On the other hand, aiming to be more concise in presentation (shorter variable names, less spacing, etc.) is something that's easy to fix.
I'll try to work on these things for Round 1, assuming I'll be able to participate at the scheduled times. So far the best option seems to be Round 1A, although, it would be nicer if it were scheduled a couple of hours later.
Re: Google Code Jam
Posted: Tue Apr 11, 2017 2:44 pm
by Solomon
Kirby wrote:On the other hand, aiming to be more concise in presentation (shorter variable names, less spacing, etc.) is something that's easy to fix.
True, but you could also be that one guy (literally one guy) who wrote their solution in LOLCODE (anonimous's Tidy Numbers, passed both small and large):
Code: Select all
HAI 1.4
CAN HAS STDIO?
HOW IZ I CHECKDESCENDING YR NUM
I HAS A LAST ITZ 10
I HAS A TN
TN R NUM
I HAS A TTN
IM IN YR DESCLOOP UPPIN YR EYE WILE DIFFRINT TN AN 0
TTN R MOD OF TN AN 10
BOTH SAEM BIGGR OF LAST AN TTN AN LAST, O RLY?
YA RLY
TN R QUOSHUNT OF TN AN 10
LAST R TTN
NO WAI
FOUND YR FAIL
OIC
IM OUTTA YR DESCLOOP
FOUND YR WIN
IF U SAY SO
HOW IZ I TIDYING YR NUM
I HAS A DESC ITZ A TROOF
DESC R I IZ CHECKDESCENDING YR NUM MKAY
IM IN YR TIDYINGLP UPPIN YR EYE WILE BOTH SAEM DESC AN FAIL
NUM R DIFF OF NUM AN 1
DESC R I IZ CHECKDESCENDING YR NUM MKAY
IM OUTTA YR TIDYINGLP
FOUND YR NUM
IF U SAY SO
I HAS A NUMINP
I HAS A CURINP
I HAS A EYE ITZ 0
GIMMEH NUMINP
NUMINP IS NOW A NUMBR
IM IN YR CIRCLEZ UPPIN YR EYE TIL BOTH SAEM EYE AN NUMINP
GIMMEH CURINP
CURINP IS NOW A NUMBR
VISIBLE SMOOSH "Case #" AN SUM OF EYE AN 1 AN ":: " AN I IZ TIDYING YR CURINP MKAY MKAY
IM OUTTA YR CIRCLEZ
KTHXBYE
Re: Google Code Jam
Posted: Tue Apr 11, 2017 2:50 pm
by Kirby
Solomon wrote:True, but you could also be that one guy (literally one guy) who wrote their solution in LOLCODE
Haha... Gotta say, I think I don't mind not being that guy

Re: Google Code Jam
Posted: Tue Apr 11, 2017 3:35 pm
by Shaddy
Kirby wrote:Since Shaddy did pretty well, I compared some of the source files I submitted to the ones that he submitted (I hope you don't mind, Shaddy - I only compared since you did a pretty good job).
Aside from simply being better at solving problems

, here are some differences I noticed, which maybe I should learn from to become a better programmer:
1.) My source code is much more verbose. Just comparing 'TidyNumbers', my source code is about twice as long. I have several more spaces, some unnecessary functions, and I use much longer variable names.
2.) Not a huge deal, but the logic I had for reading from and out to files was unnecessary. I like the idea of just using stdin and stdout - it cuts the program down to what's necessary to solve the problem.
3.) My approach to solving the problem appears to be less direct. I start typing out a high level outline of what I think needs to happen, and then when I get a little stuck, maybe I throw in a function call to solve that subproblem later. In contrast, it would be nicer to directly think of what needs to happen algorithmically right at the moment that I'm solving the problem.
Maybe it's easiest to say that I need to be more concise, and directly solve the problem. But perhaps this is just due to the fact that I didn't solve the problem entirely in my head before I sat down and started typing. It might come down to just being better at problem solving.
On the other hand, aiming to be more concise in presentation (shorter variable names, less spacing, etc.) is something that's easy to fix.
I'll try to work on these things for Round 1, assuming I'll be able to participate at the scheduled times. So far the best option seems to be Round 1A, although, it would be nicer if it were scheduled a couple of hours later.
My source code isn't verbose because I'm writing code in mostly unaugmented vim and it's annoying to type out long variable names. I would try to use more descriptive variable names if typing them out were faster somehow. Most of the difference is probably just about solving the problem entirely before writing the code.
Re: Google Code Jam
Posted: Tue Apr 11, 2017 3:48 pm
by Shaddy
I read your Tidy Numbers and now I really feel silly. The way I did it was a little too tricky and there were bugs in my initial implementation - yours is much easier to write.
Re: Google Code Jam
Posted: Tue Apr 11, 2017 4:50 pm
by Kirby
Most of the difference is probably just about solving the problem entirely before writing the code.
Yes, this!
Strikingly similar to playing go, eh?