« first day (1533 days earlier)      last day (3310 days later) » 

1:00 AM
@TheNumberOne have you started problem B?
 
I think its fascinating, but can't come up with an efficient solution
 
:/
Only about 1 in 4 have gotton it correct.
 
They purposely neglected to put in some important test cases :P
 
are you just looking at it, or have you done it @Sp3000
 
1:02 AM
Doing it :)
Just finished A
 
A was trivial
 
:P
 
I think I have an algorithm.
 
do you take the sqrt of the maximum?
oh, actually, that won't work
 
1:11 AM
Woop failed and I know why - are we allowed to discuss for qualification?
 
yes
A tough case is having two high numbers
say 1, 500, 500
 
Tougher case: 9
 
split into thirds
take two turns
 
Yeah :/
 
So much for my algorithm :/
 
1:14 AM
You probably had the same idea as me then, if you're saying that :P
 
Ah. I think I have another algorithm.
 
Oh I see what Nathan meant by square root now (delayed reaction)
 
same
 
oh! I think I have a good algorithm
declare a number "num_plates"
start it out with the current number of plates
now, while num_plates is smaller than the maximum of all of the plates
increment it by 1
and distribute the pancakes among the plates
that'll tell you the number of turns it'll take
 
1:24 AM
the distribution is the hard part
 
correct
however, you shouldn't redistribute from n-1 plates
but start with the original number of plates
 
1:35 AM
I think I have it. Is 5 correct for testcase 9 ?
 
yes
try 9 9
 
should be 7
 
Hmm I have an idea, let's see how it goes :)
Woo it worked
 
1:41 AM
awesome
on the actual test cases?
 
Yeah, small
 
nice job
 
I'm too scared to try large yet though, so maybe more test cases are in order :P
 
do 500 501 times
or 500
or 499
all of them should result in 500
 
Yep they do
 
1:50 AM
and 498 times should return 499
 
How does 498 times return 499?
 
oh, nevermind
I wasn't thinking right
what if you have 250 500s
and 249 500s
 
249 gives 499, 250 gives 500
That's more like it
btw 10 15 -> 8
 
split both once
 
equals 9
Partition into 5 5s.
 
2:02 AM
But the splitting only costs 1 + 2 = 3 minutes ;)
 
Exactly.
 
Oh right, the equals 9 was at Nathan
 
A* might be plausible if I could find a smart lower limit.
But that's probably not the right way.
 
oh, I didn't properly think though 15
 
A*'s probably overkill :P And would probably time out for large
 
2:07 AM
Why does this remind me of multi-threading :)
 
So what is this Google jelly or whatever that people are doing?
 
Thanks, El Numero Uno.
Reading A right now
 
@Sp3000 What's 27 27 ?
 
15
I believe
 
2:20 AM
I can get 13, I think.
Yes, I can. On paper.
 
13 yes
 
A was trivial?
 
You guys are a hell of a lot smarter than me.
 
read it again
I really don't think its that hard
 
2:22 AM
:|
 
it took me a couple of reads to understand, but the solution is pretty straightforward
 
2:39 AM
hey doorknob!
are you participating in google code jam?
 
@Doorknob: ^
 
@NathanMerrill No, wasn't even aware it was going on right now
 
problem B is fairly tough
hey @Sp3000 do you find the partitions of an integer?
 
Nope
 
so, I start by sorting the plate counts. Then I start n = 0, increasing by one each round. I partition n in a sorted order. Then I split the Mth plate count K times where K is the Mth partition
 
2:49 AM
What do you mean by "partition n in a sorted order"?
 
so 2 1 1 instead of 1 2 1
 
Is this partitions as in integer partitions, or...?
 
yes
sorry
 
There's a lot of partitions for any given n though...
 
true
you have a more efficient method?
(for distributing the plates)
 
2:52 AM
:( my program is two off for 249 500s
It thinks the answer is 501.
 
Technically I don't distribute the plates though... whistles I sure hope this works fine for large
 
@Sp3000 I've thought about this problem, and I can conceive of a solution that doesn't distribute plates
wait...
 
Yay! I achieved 499.
 
3:08 AM
Try: 50 100 150 200
 
Ugh. It is now not working for 27 27.
 
nvm :(
 
@Sp3000 44 ?
 
i got 41
(Split 2/4/6/8)
 
Isn't that 45 ?
 
3:20 AM
Takes 1 + 3 + 5 + 7 = 16 to split, then +25
 
3:48 AM
ok, @Sp3000 I have a new algorithm, curious if it makes sense
I start with n = 1
take the first n plates, and sum them up
oh, nevermind
it doesn't work
 
4:12 AM
@Sp3000 I have one that works for that and all other inputs I've tested. Any more tests?
Actually, since he's gone, I think I'll try my luck.
I failed.
 
 
2 hours later…
5:57 AM
@AlexA. I round the bill up to a whole number then add dollars
same reasoning as you
 
 
2 hours later…
7:53 AM
hi @Sieg
 
8:25 AM
@Lembik I sieg you.
 
8:46 AM
@Sieg what was your question about my question?
 
Didn't understand what to output.
 
just a number per n
 
Per n of what?
 
or do you mean you don't understand which number to output?
" For each integer n from 1 upwards, output the number of n by n matrices with entries which are 0 or 1 which are permutations of some Hankel matrix following the definition above."
which part is unclear?
 
"For each integer n from 1 upwards," sounds like "from 1 to infinity"
Not that I understand the rest of it either.
 
8:50 AM
@Sieg right.. it is n from 1 to infinity
@Sieg then there is a section called "Time limit"
@Sieg let's go through each unclear part one by one :)
please choose one
 
Aaaaaaah, now I understand.
 
great... on to the next unclear part :)
as no one is commenting on the question I am tempted to post it
although I don't want to annoy @MartinBüttner :)
 
Nope, I understand it all now.
The wording is just a bit weird.
 
@Sieg which part of the wording is weird?
I am happy to unweird it :)
 
.... I tried to give a better wording and ended up with even more unclear one.
But eah, it's the
" For each integer n from 1 upwards, output the number of n by n matrices with entries which are 0 or 1 which are permutations of some Hankel matrix following the definition above."
 
8:57 AM
I have at least given two answer for people to check
@Sieg shall I just post it now?
 
I'm not an authority here, but I would recommend adding the first few values for testing purposes.
 
I added two :)
I didn't add the third as I am a little worried I might get it wrong!
 
I also would recommend to take the maximum N as an input.
 
@Sieg why?
it's a timed challenge
it's how much you output in one minute that countsw
 
If that's how you wanna keep it, then sure.
 
9:00 AM
@Sieg thanks. If you wanted to verify the answers for n= 2, 3 that would be very kind too :)
i see you are a J expert :)
 
So the code doesn't have to end automatically?
 
Right.. it should run until I kill it
preferably it shouldn't crash my computer :)
 
I think n = 2 is 8
 
oh!
why?
 
If my brains don't fail me. :P
 
9:02 AM
why would it be 8?
I mean it's not so easy to do in your head
 
No, it wouldn't be 8.
 
I think you have to write code to check it
 
I've never been good at algorithms.
Not that I have ever studied them.
 
well in this case one can write a brute force piece of code for n = 2 :)
just try every permutation of columns and rows
all (n!)^2 of them
and for each one check if it is Hankel
 
Holy ..
 
9:04 AM
not a good method if n = 10 :)
but fine for n = 2 :)
 
I'lll write a small Python script
 
thanks!
although I am disappointed it is not in Joe :)
 
I named it inefficiency.py
 
perfect!
 
Joe isn't mature enough for this.
I've been working with a more reasonable language now.
Something designed for games.
 
9:07 AM
maybe you can even test n = 3 :)
I think more people should use nim
which looks awesome
 
 
I would like to give extra PPCG points to answers in nim :)
 
That's my idea.
 
interesting
 
I call them functionally reactive data objects
This would be a circle clickery game.
Uuuuuh... Where is my python interpreter?
I've done something horrible.
 
9:21 AM
@Lembik You won't annoy me. It's you who'll be disappointed if people start picking on things that could have been found in the sandbox. ;)
 
I don't know how many of you guys are trying the Code Jam, but I just managed an algorithm for the small test cases on problem B. Anyone know any particularly difficult test cases?
 
@Lembik the spec might read more nicely if you first defined the property (and gave it a made-up name like "Hankelable") and then said, "your task is to count these"
 
@MartinBüttner Don't mean to intrude, but would you mind editing my answer into the sandbox list?
 
Indeed. I'm still playing with things :)
 
9:26 AM
done
 
Thanks!
 
@Lembik is it 1 minute for each n, or 1 minute for everything from 1 to n?
 
@MartinBüttner I like the idea of Hankelable. Thank you
@MartinBüttner new version attempted
 
9:43 AM
hm you still start with the task. I meant that it might be simpler if the post is structured like "This is a Hankel matrix. This is a Hankelable matrix. This is your task."
 
10:01 AM
I wonder if the authors of this year's google code jam know this xkcd:
 
10:15 AM
@AlexA. In Spain it's 4 years undergrad, 1 year for the master's, but they want to change it again to the 3+2 and people are really angry because the master's here are like twice as expensive. I myself started before the 4+1, so mine was a 5 year degree
And this is not because of the older system; it was because we have quite inept politicians who thought they could do better than anybody else, and decided to create a plan that was different from everybody else
 
@MartinBüttner how about now?
 
@Lembik how about now?
 
10:51 AM
@MartinBüttner even better :)
although maybe the example should just have 0s and 1s in it
now can I post it? :)
@Sieg did you get a chance to write inefficiency.py ?
 
@Lembik Ah, sorry. I got more important stuff to do now.
 
@Sieg more important!? :)
 
@Lembik Important to the level of maximal importance.
 
@Lembik go for it
 
11:10 AM
anyone else code jamming? (other than Sp3000, Nathan and TheNumberOne)
 
incentive is to learn and have fun ?
 
lol, is that not enough? I guess if you're really good you can also get a job offer from Google.
and there are probably some prizes for the best participants as well... but realistically... yes, to learn and have fun.
 
have you tried ?
 
yeah, I'm doing it right now
 
@Geobits but everyone wrote several Pyth programs
 
11:16 AM
Q1 was really easy... Q2 looks really hard... Q3 looks tricky as well, but is probably not too bad, and I'm currently doing Q4
 
done all three first ?
 
no
"looks"
 
oh, you can skip and stuff ?
 
yes you can do them in any order
 
I only see 1 round: Qualification Round 2015
 
11:20 AM
yes
that round has 4 problems
 
so where you see Q1, Q2.., do you mean A,B,C,D?
 
or do you mean i, ii , iii, iv ?
 
yes, ABCD
 
 
does the language have a name yet?
 
Nope.
I'm still having huge problems in recognizing the signal trees
That was compiled by hand.
The hand compiled version looks like this i.imgur.com/9U6JHU8.png
But I think explicit types are mandatory if I'm gonna do this.
Unless I make static values behave like reactive ones too.
 
@MartinBüttner posted!
 
btw, why did you pick the skew diagonals instead of just the normal diagonals?
 
Isn't a permutation of skew diagonals also a permutation of normal diagonals?
 
11:52 AM
yeah that's why I'm asking
 
I mean, it doesn't affect the program at all.
I personally like skew diagonals more :P
 
I personally like columns more
 
Don't try.
 
12:17 PM
Funny how I would have been done yesterday if I took the Elm route of making signals explicit.
I don't want no explicity.
 
@MartinBüttner you mean going up rather than going down?
@MartinBüttner ... no reason :)
 
we should take bets on the top score :)
I bet.... 8
 
I put my money on 7.
 
great :)
 
12:27 PM
The winner gets to comment my ~600 lines of Joe interpreter.
Which is totally uncommented.
 
okay, done problem D as well... I have no clue if it's correct, because the problem changes qualitatively for input numbers greater than the small test set :/
 
Huh... I just figured that GC is extremely hard to get to work when the values are "active".
 
can we choose any language for google codejam ?
 
@Optimizer yeah I think so
 
CJam too ?
 
12:41 PM
Wasn't CJam made for Google Codejamming?
 
Revelation
 
12:57 PM
hmmm... this looks interesting; maybe I'll try codejam as well
 
do it!
I just slept over Problem B, and I think I have the answer
 
If I do it, I'm doing it in Rust. :D
 
@Doorknob last year, Rust was used by 7 submissions
 
added "The winner will be decided 7 days after the first answer is posted."
hi @Optimizer
I have a new challenge :)
1
Q: Count the number of Hankelable matrices

LembikBackground A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1s. E.g. a 5x5 binary Hankel matrix looks like a b c d e b c d e f c d e f g d e f g h e f g h i where a, b, c, d, e, f, g, h, i are either 0 or 1. Let's define a ma...

 
uhh... what am I supposed to put for "field of study"?
 
1:02 PM
"Other"?
 
But then it asks me to "please specify"
 
@NathanMerrill huh, not a single Ruby participant?
@Doorknob "Stuff"
 
@MartinBüttner no, there were, uhh, 449 of them I think
It's near the top
 
ninja
 
1:03 PM
ohhh right
 
"Stuff" it is. :P
 
okay if I can solve the small test set of either B or C I'm through qualification
(likewise, if either my large test set for A or D is correct)
 
if you want to do B, we have some good test cases for you to try
 
I don't even have an approach yet
 
@MartinBüttner what is the qualification requirement? couldn't find at first look
 
1:08 PM
20 points
 
@NathanMerrill have you done D?
 
1:31 PM
hooray! proudly claims 7 points in 24 lines of Rust
Here's hoping my answer to the large dataset is correct.
Does it tell you whether you got it right after the 7-minute period?
apparently no
 
@MartinBüttner I just went through a long chat with a friend of mine. Apparently my idea is completely impossible in Javascript because of the lack of weak references. I have to compromise and use pull-based systems (events are read when they're needed)
There would be no problem if the signal tree would be static, but the data objects break that requirement.
The system would still be just fine for games, but that's it.
I want a virtual drawing board.
 
1:57 PM
@NathanMerrill Could I have some of those test cases?
I think I got it, but I just want to make sure
 
redesign -> rewrite -> remindbend -> deskface
Today's plan
 
2:12 PM
@Doorknob nope
that's particularly evil for D
 
I think I have a solution for B--it passes the small inputs. Anyone have good tests for large input?
 
@Nathan does, I think
 
I do
try 10 15
should be 8
 
I'm not even really sure how to confirm the correctness. Let me try that. Anything higher?
 
try 500 250 times
 
2:17 PM
I do indeed get 8. Do you mean input of 250\n500 500 500 500 500 ... ?
 
yes
you should get 500
if you do it 249 times, you should get 499
27 27 27 should give 15
 
Hmm... I seem to pass everything but the 249 500s.
How do you split up that case?
 
take 249 turns to halve all stacks. then wait 250 turns to empty them all.
 
Ah, right!
 
2:36 PM
has one of you tried BFS on this? is it feasible?
 
2:53 PM
So, why is the site's CAPTCHA just a checkbox rather than the traditional 'enter these words'?
 
because its better
 
@NathanMerrill Why?
 
59
Q: How does this checkbox recaptcha work and how can I use it?

pnmcostaI've recently signed up to the oneplusone website https://account.oneplus.net/sign-up, and noticied this checkbox recaptcha How does it work, and how can I use it on my sites? Much better than those criptic words/digits :) The recaptcha site does not mention any new recaptcha method... https...

 
@MartinBüttner what question?
 
2:56 PM
@Doorknob Neat.
 
@Doorknob cool
 

« first day (1533 days earlier)      last day (3310 days later) »