Problem 239

[hisoka-san]

Is it any 22 of prime-number disks are not on their place, and others are on place,
or 22 specific ones?

[ed_r]

Any 22.

[hisoka-san]

The problem was a bit tricky, but I've solved it, Thanks!

[DNS]

Is it correct to read the problem in such way
that disk with number "2" is on place if it is found exactly on 2nd place?
Or on 2nd place could be any prime, because 2nd place is a place for prime?

[gonzolino]

The good way to understand the problem is : "that disk with number "2" is on place if it is found exactly on 2nd place"

[estanford]

I'm having trouble understanding why it matters that the 22 disks in question are labeled with prime numbers. If I'm reading the problem statement correctly, the specific labels of the 22 chosen disks is an irrelevant concern. Am I missing something here?

EDIT

I read the problem like this:

Given that there are 100 disks, calculate the number of ways to permute the disks' positions such that exactly 22 of them are deranged.

I just realized how that way of thinking about the problem is incorrect. I'd wondered why such a high-numbered problem should turn out to be a one-liner (answer: it didn't). Fixing my algorithm now...

[stijn263]

I'd wondered why such a high-numbered problem should turn out to be a one-liner (answer: it didn't)

There are definitely "high-numbered" problems that allow one-liners in certain high level languages. Which ones, you'll have to find out for yourself

[zwuupeape]

It would certainly cause me serious mental issues if it turns out problem 212 is solvable in one line

[quilan]

It would certainly cause me serious mental issues if it turns out problem 212 is solvable in one line

Nah, that's one that takes a little bit of work, but it's completely straight up algorithmic in nature -- no hidden math or crazy stuff involved. Actually, come to think of it, both of your unsolved are completely straight-forward; I'd have thought they were some of the first to go. Good luck!

Edit: For further challenge, my 212 Python code runs in 5.1s on my home computer -- that'd probably be about 3s on a work PC.

[daniel.is.fischer]

It would certainly cause me serious mental issues if it turns out problem 212 is solvable in one line

Well, I don't know if it's possible in Python, but in C or Java or Haskell, you can put the entire programme on one line.
I would revoke your coding licence if you did, but you could

[quilan]

It would certainly cause me serious mental issues if it turns out problem 212 is solvable in one line

Well, I don't know if it's possible in Python, but in C or Java or Haskell, you can put the entire programme on one line.
I would revoke your coding licence if you did, but you could

Unless you managed to figure out a way to write a program without any nested while/for loops, if statements, try blocks or function definitions, then it can't be done in one line in Python. You can append many statements together with ';', but any time there's a second ':' it's gotta be on a new line. Kind of a shame, I'd love to be able to write:

for i in xrange(10), j in xrange(i): print i,j;

for brevity. I think I saw that once in a rejected future codebase suggestion somewhere.

Edit: I thought Haskell had some restrictions on whitespace too? I seemed to end up running into those a few times while writing some Haskell code once. Ideas?

[zwuupeape]

You can write:

Code: Select all

for i,j in (((i,j) for i in range(10) for j in range(i))): print(i,j)

... I don't think 212 is straightforward. To be honest, I also thought the one with the segments was incredibly hard because I tried to use something less than O(n^2) for some time but it turns out its reasonable. So it could be easier than I think. But I programmed something that I have no idea how you could even theoretically improve upon and it should take, I suppose, about 3 days to finish (not till the end of time).

I think in Haskell it's solvable in one line. I don't know this language well, but in languages like it, and LISP, everything is technically a one liner, since there are no statements, just expressions.

[daniel.is.fischer]

I thought Haskell had some restrictions on whitespace too? I seemed to end up running into those a few times while writing some Haskell code once. Ideas?

Well, in Haskell you can use layout to structure your code, and that's what's normally done, because the code is far more readable. But you can also use explicit {braces; and semicolons;}. You can even mix both styles (but usually people who try that run into a lot of fiendish parse errors). Using explicit braces and semicolons, you can cram your whole module on one line, but it's even worse than doing that in C.

[quilan]

I thought Haskell had some restrictions on whitespace too? I seemed to end up running into those a few times while writing some Haskell code once. Ideas?

Well, in Haskell you can use layout to structure your code, and that's what's normally done, because the code is far more readable. But you can also use explicit {braces; and semicolons;}. You can even mix both styles (but usually people who try that run into a lot of fiendish parse errors). Using explicit braces and semicolons, you can cram your whole module on one line, but it's even worse than doing that in C.

Cool beans. At my workplace, they're showing a series of lectures on Haskell, so I've been re-catching up on my own time (sadly the interpreter still isn't working for me in Eclipse == no Haskell writing for me). The only difficulty is that the language is being presented in The. Most. Boring. Manner. Ever. Hardly no mentions of why Haskell is fun (corecursion, lazy-evaluation, beautiful language, etc). I'm glad I've written some small stuff for it in the past or else I wouldn't approach it with a 20-foot stick as it's presented.

[daniel.is.fischer]

I thought Haskell had some restrictions on whitespace too? I seemed to end up running into those a few times while writing some Haskell code once. Ideas?

Well, in Haskell you can use layout to structure your code, and that's what's normally done, because the code is far more readable. But you can also use explicit {braces; and semicolons;}. You can even mix both styles (but usually people who try that run into a lot of fiendish parse errors). Using explicit braces and semicolons, you can cram your whole module on one line, but it's even worse than doing that in C.

Cool beans. At my workplace, they're showing a series of lectures on Haskell, so I've been re-catching up on my own time (sadly the interpreter still isn't working for me in Eclipse == no Haskell writing for me).

a) Why would you need an IDE?
b) Try leksah, if you care to install ghc and some dependencies (if you're on Windows or Mac, you get almost everything you need by installing the Haskell Platform, if you're on Linux, install a ghc binary and get yourself cabal-install [included in the Platform installer for Windows and Mac]. Then you need to install gtk2hs, which unfortunately is not yet cabalized . With that in place, "$ cabal update && cabal install leksah").

The only difficulty is that the language is being presented in The. Most. Boring. Manner. Ever.

Ugh. What a waste.

Hardly no mentions of why Haskell is fun (corecursion, lazy-evaluation, beautiful language, etc). I'm glad I've written some small stuff for it in the past or else I wouldn't approach it with a 20-foot stick as it's presented.

Read some papers by Simon Peyton Jones, Philip Wadler, John Hughes, Oleg Kiselyov, Jerzy Karczmarczuk, …. Fascinating stuff. And [many are] astonishingly accessible, even if one has no formal CS education. And of course the wikibook and RWH.

[zwuupeape]

Hey daniel. what do you think about Learn You a Haskell for Great Good? I don't know how high quality it is from a 'professional' perspective but it was certainly fun to read. I don't really remember at what part I stopped reading it, or why, though =\

[daniel.is.fischer]

Hey daniel. what do you think about Learn You a Haskell for Great Good? I don't know how high quality it is from a 'professional' perspective but it was certainly fun to read. I don't really remember at what part I stopped reading it, or why, though =\

Just spent too much time reading it
It's not bad, a little too longwinded and untheoretical for my taste. But it's a fun read much of the time, definitely worth dropping by and looking whether it suits your taste.

[szymczak]

I'm having trouble understanding why it matters that the 22 disks in question are labeled with prime numbers.

I don't think it does. The problem should be the same for any 25-element subset of {1, ... 100}.

I'm getting the wrong answer though

If the problem was 'partial derangement such that exactly 21 prime number discs are away from their natural positions' I get 0.000105014085. Can anyone tell me if this is correct?

[thundre]

If the problem was 'partial derangement such that exactly 21 prime number discs are away from their natural positions' I get 0.000105014085. Can anyone tell me if this is correct?

The first 2 significant digits are correct: 0.00010. After that you're wrong.

I agree that there's nothing special about the prime subset.

[szymczak]

The first 2 significant digits are correct: 0.00010. After that you're wrong.

I agree that there's nothing special about the prime subset.

Thanks for the reply. I'm confused as to why I'm getting the wrong answer. I'm almost certain my solution is correct. I've even torn my code apart, and I don't think it is a precision error. If I make a nice write up of my solution (formula and explanation) will you, or anyone else who has solved the problem take a PM and look at it? At least to tell me where (and not how) my reasoning went wrong.

I am in the middle of studying for finals and applying to grad school, so I haven't had the time to work on the problem. This write-up will probably not happen for another week or so. Once break starts I'll be able to get back into Project Euler mode.