Google Code Jam

[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).

[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

[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.

[Solomon]

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 .

[Kirby]

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

[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.

[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.

[Solomon]

L19 (GCJ)

• apetresc (apetresc)
• gamesorry (SuperRabbit)
• HermanHiddema (herminator)
• hyperpape (hyperpape)
• Kirby (Kirby)
• Shaddy (shadonra)
• Solomon (tesuji)

[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.

[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.

[Solomon]

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

[Kirby]

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

[Shaddy]

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.

[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.

[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?