The Nineteenth Byte

Mars Ultor

8:00 AM

It's D you probably need to sleep on

Lembik

@TonHospel ok.. mine is quite ancient too :)

but not a laptop

Mars Ultor

Or else I'm missing something else really obvious for D

Ton Hospel

@lembik: I do have a serious 8 core broadwell xeon, but it's usually turned off

Lembik

@TonHospel that can wait for the multi-core version :)

@TonHospel hmm.. the sum gets really close to 1 when n gets large

is that expected?

Ton Hospel

@lembik: It's due to the way you generate your matrices. It's not true in general (the current code takes floating pioint matrices too, so you can try it for any positive definite matrix)

Lembik

8:03 AM

@TonHospel ok but even being due to the way I generate the matrices I find this very interesting. I think that if the eigenvectors of P align with the grid then the sum shouldn't be so small

does that make sense?

zyabin101

  1st 1035 xsot             70  5:44:20
  2nd 1518 MarsUltor        65  7:11:26
  3rd 1962 Maltysen         55  7:31:02
  4th 1982 TheOnlyMego      55  8:05:12
  5th 8041 cky              15    37:05

^ The code jam leaderboard for PPCG.

Mars Ultor

wait, there's a time penalty?

Lembik

I didn't even know xsot's name before today...shame

Ton Hospel

@lembik: I suspect not. If R gets bigger the orientation of the eifgenvectors should matter less and less

Mars Ultor

Pretty sure xsot is more active in anagol

zyabin101

8:05 AM

@MarsUltor Yes. It breaks most (if not all) ties in main scores.

Lembik

anagol?

Chris Jester-Young

@Lembik Anarchy golf.

k

golf.shinh.org

thanks!

8:06 AM

Mego was too late for the bronze by only a few (34) mins.

Also:

> Please do not discuss the problems during the round.

wai did u discuss 'em ;_;

Lembik

@TonHospel n = 22 !! :)

zyabin101

@MarsUltor code.google.com/codejam/faq.html#5-1

Sherlock9

How does pypy work again? pypy your_script.py #command line arguments?

Lembik

@Sherlock9 I think so

Sherlock9

Excellent

Now if I could remember where I put my installation...

Lembik

8:10 AM

@TonHospel the point being that the eigenvalues should all be around m. So if the eigenvectors are aligned with the grid you get those terms appearing

@TonHospel I mean the eigenvalues which are > 1 are all around m

Mars Ultor

@xsot can you give any more hints?

Ton Hospel

@lembik: I think the size of the eigenvalue is much more important than the alignment of the eigenvector

Lembik

@TonHospel interesting

Mars Ultor

How did people get D in ~10 minutes?

Lembik

@TonHospel well I look forward to testing it out with bigger and bigger matrices :)

xsot

8:14 AM

@MarsUltor Base k

Lembik

by the way all.. more people should upvote codegolf.stackexchange.com/a/77212/9206 . It's an awesome answer that is just getting more awesome!

Ton Hospel

@lembik: Big eigenvalues lead to quickly decreasing exponentials. You can write P as H^T D H where D is the diagonal eigenvectors, so x^T P x = (H x)^T D (H x), so H x are the axes of the ellipsoid and big eigenvalues lead to low exponents

Lembik

@TonHospel of course if it just had a little documentation ... :)

Ton Hospel

@lembik: The paper is the documentation :-)

Lembik

@TonHospel true re: big eigenvalues lead to low exponents

zyabin101

8:15 AM

@MarsUltor Related: xsot is the only one that got D_small in our group, in 4:31:49.

Lembik

@TonHospel hmmm :) It doesn't point to the paper currently!

Ton Hospel

@lembik: Ah, I should at least add that

zyabin101

IDK if he got D_large, btw.

Mars Ultor

@zyabin101 He said no

@xsot ???

Lembik

@TonHospel m = 5, n = 18 is interestingly slow. I think you mentioned this might happen before.

Mars Ultor

8:21 AM

@xsot what can be represented in base h?

Ton Hospel

@Lembik The lower m, the higer the result and the needed relative error gets big -> many points needed -> slow

Lembik

do you mean the relative error gets small? We want an additive error of 0.0001. If the result is large this is a tiny multiplicative error

Chris Jester-Young

@MarsUltor Got B now.

xsot

@MarsUltor To clarify, that's the k in the problem

Chris Jester-Young

I'll think on C and D while I do dishes.

Lembik

8:25 AM

I clearly misunderstood something .. sorry about that

Chris Jester-Young

@xsot Thank you!!!!!

Mars Ultor

@ChrisJester-Young The easiest way to do C is brute force + primality test - the naïve method

xsot

@ChrisJester-Young You are fast :)

Mars Ultor

Oh

Sp3000

@MarsUltor I beg to differ :P

xsot

8:27 AM

btw don't waste the judge for the small input

Mars Ultor

@Sp3000 ?

Sherlock9

Does anyone here use Ruby on Rails?

xsot

You can use it to test your large program

Mars Ultor

@xsot Can't you just use the same program for the large one?

Chris Jester-Young

@xsot Indeed.

xsot

8:27 AM

I couldn't test the correctness of my initial program and lost the 25 points

Chris Jester-Young

@MarsUltor Only if your small program isn't brute-force.

Mars Ultor

@ChrisJester-Young I've used the same program for both

Not D, but A and C i've brute-forced

Chris Jester-Young

@xsot OMG :'(

zyabin101

Okay, now that is awkward.

Sherlock9

My friends and I have a class on databases, and we're allowed to use the following languages: PHP, Ruby on Rails, Java, C#. Which do you think would be best for databases?

Chris Jester-Young

8:29 AM

@Sherlock9 Clojure.

Mars Ultor

@xsot If I understand correctly, that means minimum needed spots = max(0, K-C)+1?

Lembik

@TonHospel If I want to increase the precision, how do I specify this on the command line? Also I see there are constant in the code, e.g. double factor = 1e9/min; Do these need adjusting too?

xsot

@MarsUltor No!! I made that mistake

Sp3000

Oh, you're talking about D. runs away from room cos spoilers

zyabin101

  1st  791 xsot             80  9:33:14
  2nd 1586 MarsUltor        65  7:11:26
  3rd 2061 Maltysen         55  7:31:02
  4th 2081 TheOnlyMego      55  8:05:12
  5th 7428 cky              35  9:26:30

The leaderboard was amended!

Ton Hospel

8:31 AM

@lembik: Just run as: program 1e-6 < input

Sherlock9

@ChrisJester-Young These guys don't even know what Lisp is, unfortunately

Lembik

thx

Mars Ultor

@zyabin101 Maybe add totally not Dennis and definitely add Sp3000

Ton Hospel

@lembik: The constants don't need updating

Chris Jester-Young

@Sherlock9 That's a huge bummer.

zyabin101

8:31 AM

Congrats everyone, you are qualified!

Lembik

thanks again

xsot

@MarsUltor Wait, no. It's wrong, but not the way I imagined

Sherlock9

And I'm not prepared to teach them, since I barely know functional programming myself

Mars Ultor

I know, what lisp is, it's the brackety language

5

Sherlock9

@ChrisJester-Young It really is

zyabin101

8:31 AM

@MarsUltor Ok.

Chris Jester-Young

@MarsUltor readable.sourceforge.net

zyabin101

@Sp3000 what is your code jam username?

Mars Ultor

@ChrisJester-Young I know, I linked to that a while ago

Ton Hospel

@lembik: Ps, just uploaded a new version, should be twice as fast (uses the symmetry of the ellipsoids to only calculate half the points)

Mars Ultor

@zyabin101 Sp3000

Sherlock9

8:32 AM

My code jam username is also Sherlock9, if anyone wants to look for it

Lembik

@TonHospel wow.. here goes :)

Mars Ultor

@xsot D: how is it wrong

zyabin101

@Sp3000 Welcome to the leaderboard! @Maltysen is shifted to the fourth place.

Please wait until I reveal the full results.

Mars Ultor

@zyabin101 Add Sherlock9

Lembik

@TonHospel and no compilation errors! Thank you

zyabin101

8:33 AM

@Sherlock9 Welcome to the leaderboard! @cky is shifted to the seventh place.

Please wait until I reveal the full results.

Ton Hospel

@lembik: It also suggests an equivalent matrix that gives exactly the same result (and is an ellipsoid that is better aligned with the grid) Not very useful but interesting nontheless

Lembik

@TonHospel that does sound very interesting

xsot

@MarsUltor You can test it on the small judge

zyabin101

  1st  800 xsot             80  9:33:14
  2nd 1601 MarsUltor        65  7:11:26
  3rd 1710 Sp3000           65  8:10:03 *
  4th 2086 Maltysen         55  7:31:02
  5th 2106 TheOnlyMego      55  8:05:12
  6th 3179 Sherlock9        45  9:23:09 *
  7th 7438 cky              35  9:26:30

The leaderboard was amended!

Lembik

what is the challenge you are solving?

gcj people

Chris Jester-Young

8:36 AM

@Lembik I've solved A and B, just C and D left.

Lembik

but what are A and B?

zyabin101

@Lembik Four.

Lembik

can you see the challenge without registering?

Chris Jester-Young

code.google.com/codejam/contest/6254486/dashboard

zyabin101

@Lembik Yup.

Lembik

8:37 AM

thanks!

Mars Ultor

@ChrisJester-Young But C should just be primality test, plus some base conversion

xnor

for code jam, what determines your score?

Mars Ultor

And you've probably already gotten D

Optimizer

gotten em buoy

Mars Ultor

@xnor Total score of everything you get right

Lembik

8:39 AM

any python coders in? How do you change a simple loop into something parallel? bpaste.net/show/f68fdd3fc6e4 I would like to do 8 at a time in parallel

they are completely independent of each other

xnor

@MarsUltor Are the tasks hard enough that most contestants don't get all of them? or is it hard to do them in a day or so?

Mars Ultor

@xnor No

This is the qualifier

Almost everyone in PPCG should be able to do them

Chris Jester-Young

@MarsUltor I know, but I'm doing the dishes at the moment.

xnor

@MarsUltor oh, i see

Sherlock9

@Lembik A, B and C small are solved, but not D. A and B large are solved, but not C and D

xnor

8:40 AM

and in the real competition?

Chris Jester-Young

It's part of this life process called adulting. :-P

Lembik

@Sherlock9 thanks

Sherlock9

I'm actually having trouble finding enough composite numbers for C-large

Mars Ultor

@ChrisJester-Young Wait how are you chatting while doing the dishes

Sp3000

@xnor In the real contest, yes - it ramps up pretty quickly

Also real contest is 2.5 hours

Lembik

8:41 AM

@TonHospel m = 13, n = 24 takes 30 seconds for 5 iterations. m = 12, n = 24 takes 210 seconds !

xnor

@Sp3000 so is it mostly how fast you can write working code?

Sp3000

Working and efficient code, yes. Good intuition about algorithms/edge cases helps.

Or rather, efficient enough.

xnor

@Sp3000 Is your code's run-time measured?

Sp3000

No, but small inputs give you 4 minutes to solve after downloading, 8 min for large

Downloading the input, that is

xnor

so you write the code, then download the inputs, then make sure it works on them?

Ton Hospel

8:43 AM

@lembik: I could by the way completely eleminate the armadillo library since gsl has all I need, but this old style C library is SOO ugly, verbose and inconvenient in it's matrix notation

Mars Ultor

@xnor Then upload output and code

Sp3000

Hopefully you've made sure your code works well enough before you download the input, or you'll be frantically debugging for a good few min :P

xnor

i see

so i guess they want to avoid overfitting?

Sp3000

Also, small is infinite number of tries, but large input is only 1 try

Mars Ultor

@Sp3000 No

Chris Jester-Young

8:45 AM

@TonHospel I feel like I should port your solution to Boost. :-P

Mars Ultor

large has infinite tries, but only within 8 mins of start

xnor

so in this qualification round, what stops coders from getting a perfect score?

Chris Jester-Young

@xnor Nothing.

Sp3000

@MarsUltor I meant download attempts, but within the time limit after download, sure

Chris Jester-Young

@MarsUltor Because I can load a few dishes and type. Wouldn't try to code this way though.

Lembik

8:46 AM

@TonHospel :(

Sp3000

@xnor Nothing, but it doesn't matter since it's the qualifier. In the actual rounds it's sorted by score, then time + penalties, and the top X number go through

xnor

@Sp3000 ok, that makes sense, but I'm confused about the scores that people are comparing in chat

Ton Hospel

@ChrisJester-Young: Shouldn't be too hard, though you'd need to add back the parts I skipped because I assume z=0 everywhere so I could drop a lot of extra factors. But they shouldn't change the core of the code

Sp3000

@xnor Feel free to ignore them for now :P Qualifier just needs 30 to pass (note that scores during a round may drop once the round's over if people fail large inputs, which only get judged after the round)

Ton Hospel

@ChrisJester-Young: The main change needed is probably adding the uniform error approximation

xsot

8:48 AM

@xnor The scores aren't important in this round since any number of contestants can advance to the next round provided that they pass the point requirement

xnor

ok, thanks for satisfying my idle curiosity

carry on

Kenny Lau

Three Word Chat

Only Three Words

Join us :D

zyabin101

@Mego you still there? If so, output "RULES" (5 letters).

Sherlock9

9:14 AM

I am having real trouble with D

And I need to optimize C-large somehow

And I did it

Now onto D

Ton Hospel

@lembik: Does your ubuntu get libfplll-dev ?

Lembik

@TonHospel let me see

@TonHospel libfplll-dev - Library for LLL-reduction of Euclidean lattices, development
libfplll0 - Library for LLL-reduction of Euclidean lattices, runtime

yep

Ton Hospel

@lembik: Ok. Reading the docs now, I might switch to that one, it uses much more modern algorithms than NTL

Lembik

@TonHospel cool

Ton Hospel

@lembik: Don't know if it will matter though. The quality of the NTL solutions might already be good enough

Lembik

9:28 AM

@TonHospel I like the idea of your solution being ported to a mainstream library!

Sherlock9

@zyabin101 You may want to update the leaderboard. Or not, it's up to you

Ton Hospel

@lembik: What is mainstream. I basically need choleski decomposition, incomplete gamma function, a root finder and lattice reduction. Except for lattice reduction you find these everywhere. So the trick is to choose a good lib for lattice reduction

zyabin101

@Sherlock9 Okay, amending the leaderboard.

Sherlock9

@zyabin101 And DennisMitchell isn't on there

And you aren't on there

Lembik

@TonHospel oh sorry I was just referring to Boost here. All those things you describe exist in python and scipy too :)

which would be a good way to slow down your solution

Sherlock9

9:33 AM

@zyabin101 Sorry to nitpick :D

Lembik

hmm.. not so sure about lattice reduction actually

zyabin101

  1st  776 xsot            100 10:20:40
  2nd 1768 MarsUltor        65  7:11:26
  3rd 1864 Sp3000           65  8:10:03
  4th 2217 Sherlock9        65 10:37:05
  5th 2373 Maltysen         55  7:31:02
  6th 2392 TheOnlyMego      55  8:05:12
  7th 7576 cky              35  9:26:30

Kenny Lau

What fun thing do we have, except cops-and-robbers?

zyabin101

The leaderboard was amended!

Kenny Lau

We haven't had other things except code-golf for such a long time

Ton Hospel

9:34 AM

@lembik: Also pretty much all lattice reduction research is on integer bases, but we have a real basis. I "solve" that by apprimating it by an integer basis by blowing up the reals, so it needs lattice reduction that can wortk with big integers

Lembik

well there is github.com/malb/fpylll

@TonHospel very interesting!

zyabin101

@Sherlock9 I'm not participating in the code jam. O_O

Sherlock9

Ohhhh

orlp

I feel that we are missing a tag

zyabin101

@Dennis What is your code jam username?

orlp

9:35 AM

like, grid or 2d

Sherlock9

@zyabin101 It's DennisMitchell

zyabin101

@Dennis Welcome to the leaderboard!

Sherlock9

2 hours ago, by Mars Ultor

TheOnlyMego, Maltysen, xsot, MarsUltor, DennisMitchell

zyabin101

Umm, is Dennis in Paraguay?

orlp

what leader board?

zyabin101

9:37 AM

3 mins ago, by zyabin101

  1st  776 xsot            100 10:20:40
  2nd 1768 MarsUltor        65  7:11:26
  3rd 1864 Sp3000           65  8:10:03
  4th 2217 Sherlock9        65 10:37:05
  5th 2373 Maltysen         55  7:31:02
  6th 2392 TheOnlyMego      55  8:05:12
  7th 7576 cky              35  9:26:30

Sherlock9

zyabin is making a "Friends of PPCG" Google Code Jam leaderboard

orlp

@zyabin101 well yes

but what does that leaderboard refer to

zyabin101

@orlp are you participating? If so, which username?

orlp

no

I don't like speed coding

it's just stressful

I like optimal/fast solutions, not quickly hacked together ones

Sherlock9

It's not really speed coding

Not for me

I just like solving the puzzles

Chris Jester-Young

9:39 AM

@orlp Qualification round is not speed coding. Further rounds, yes.

And I dislike speed coding as much as you.

Kenny Lau

i'm in lol

zyabin101

@KennyLau Username?

Sherlock9

What's your username, Kenny?

Kenny Lau

kennylau

zyabin101

ninja'd

Sherlock9

9:41 AM

ninja'd :P

zyabin101

@KennyLau Welcome to the leaderboard!

I can't keep up with the rapidly changing results, so the leaderboard is discontinued. Don't worry, there will be a final leaderboard at the end of qualifications.

Martin Büttner

@KennyLau Would you mind clarifying the questions I posted on the cops challenge?

Kenny Lau

10:02 AM

@MartinBüttner Sorry, what are you referring to?

Martin Büttner

codegolf.stackexchange.com/questions/77419/… and the next comment

Kenny Lau

@MartinBüttner I don't really get the point of disallowing no-ops.

Can you explain it to me?

Martin Büttner

you disallowed no-ops in the rules.

but it's not clear to me what counts as a no-op.

Kenny Lau

@MartinBüttner Well I sort of typed it there.

@MartinBüttner Doesn't mean I came up with the rule.

Lembik

@MartinBüttner looks like Ton Hospel's solution beats the mathematica code hands down :)

Martin Büttner

10:09 AM

@KennyLau I'm not seeing a comment suggesting it. Was that discussed in chat?

Kenny Lau

@MartinBüttner Yes.

By @NathanMerrill

if my memory serves me well.

Adnan

@KennyLau Can I use non-ASCII characters for the cops challenge?

Kenny Lau

@Adnan I really want to respond "use common sense" to every question...

@Adnan Yes as long as it is part of the codes, not in string literals...

orlp

http://i.imgur.com/jfEmGpf.gif

8

Optimizer

oh c'mon. its so unfair to lure in stars like that :P

orlp

10:21 AM

:D

Optimizer

nooo

keep it in

Martin Büttner

@KennyLau I'm only finding a message of his asking whether they are allowed. Anyway, I think it's not clear what a no-op really is, so either that should be specified or the rule should go.

What about my other comment?

Kenny Lau

@MartinBüttner Could you explain to me why no-ops are disallowed?

Modified in response to your other comment.

Martin Büttner

I can't tell you why no-ops are disallowed, I didn't disallow them :D

@KennyLau ah sorry, didn't see that

Sp3000

Hmm yeah I'm a bit confused about the no-ops rule... does that mean " and ' aren't allowed even if they're necessary to achieve the right code layout?

Kenny Lau

10:25 AM

@MartinBüttner @Sp3000

Sp3000

Ah k

Martin Büttner

awesome

have an upvote :)

\o/

thx!

finished, finally

10:27 AM

@MartinBüttner are you planning on posting a Hexagony submission? :)

Martin Büttner

not sure, maybe

Sp3000

@KennyLau btw did you see codegolf.stackexchange.com/questions/77419/…

Kenny Lau

it's answered below :)

I'd say the values have to actually be searchable on OEIS, so that it can easily be verified that the values are correct for the chosen sequence.

Sp3000

It's hard to tell if you agree with the answer or not unless you actually leave a comment :P

Kenny Lau

sure

Sp3000

10:29 AM

(it'd be good to comment/edit in to make it more "official")

Sherlock9

@MartinBüttner Are you joining Google Code Jam?

Martin Büttner

I've done A and B

Sherlock9

Username?

D is hammering my brain in. I have a brute-force solution, it's just too unwieldy to actually be useful

Martin Büttner

mbue

Sherlock9

Thank you

I'm Sherlock9 on GCJ, if you want to add me as a friend on there

Martin Büttner

10:33 AM

Is there a requirement for a minimal solution for D?

Sherlock9

No, just that my algorithm is apparently knocking out MemoryError

Martin Büttner

small set seems trivial then

but I'm not sure yet whether I'll do C and D

Sherlock9

@MartinBüttner Perhaps. But from looking at the list of PPCG people I've added on GCJ, only xsot, Sp3000 and MarsUltor have answered D

... Now that you say it ...

I have an idea :D

Martin Büttner

well the algorithm I have for the simple set isn't applicable to the large one

Sherlock9

Thanks anyway, it might still save my bacon :D

... Maybe

Mars Ultor

10:39 AM

xsot says base K

Martin Büttner

how many points are needed for qualification?

Mars Ultor

very important hint

@MartinBüttner 30

zyabin101

@MartinBüttner 30

ninja'd

Martin Büttner

oh okay

Sherlock9

Well, I believe that my A-large, B-large and C-large solutions are correct, but I want to get D-small at least, to be sure

Mars Ultor

10:40 AM

@MartinBüttner D is the hardest IMO, if you're confident you've gotten 30 points you don't need to do it

Sherlock9

@MarsUltor Thanks :D

Kenny Lau

do you guys codeforce?

Mars Ultor

@Sherlock9 Why the time gap between Coin Jam small and large?

@KennyLau Not me

Pretty sure people are just doing GCK because its run by google, and it's a limited-time event

zyabin101

@KennyLau Erm, nope. No one... No.

Sherlock9

@MarsUltor I'll explain the stupidity in my first C-large algorithm tomorrow. I did one stupid thing that I'm still kicking myself over >_<

Basically, what was not too inefficient for C-small, blew up in my face during C-large

Mars Ultor

10:43 AM

@Sherlock9 Make sure to ping me before you start so I can find it

@Sherlock9 Primality checking?

Sherlock9

Well, I guess I can explain it

Mars Ultor

@Dennis would you mind setting up a TIO section for code jam giving output from whatever the user inputs?

@Sherlock9 D: one wrong try for D

Sherlock9

There are quite a few numbers that can be represented in 32 digits of binary. I opted at first to use trial division completely to the square root for each eligible 32-bit number. It took 15 minutes to output 16 numbers. I drastically reduced the limit to which I used trial division, and it got everything I needed in 5 seconds <_> >_<