Hacker News Reader

Comment by cperciva | Hacker News Reader

Do I get bonus marks for solving this without writing any code?

I immediately went to Wikipedia, found out what type of CS problem the first challenge was, then followed the external links at the bottom of the page to find the Perl module I needed and installed it from CPAN.

I quit because this seemed like cheating but now I'm thinking... Maybe it was the point? To see if I would try to find something off-the-shelf to solve the problem quickly. Still not sure it was, because if so the challenge certainly doesn't demonstrate that I have any CS chops. :-\

Spoiler alert: I believe this module will do the trick http://search.cpan.org/~gray/Tree-Suffix-0.21/lib/Tree/Suffi...

I didn't solve the problems using existing code either. All three are entirely solvable by pencil and paper (or just inspection in the first case).

Ah. Well I'm an even worse hacker than I thought!

Don't feel bad, it's just how cperciva rolls :)

http://news.ycombinator.com/item?id=35083

Wow, I strongly recommend reading this (or, better yet, the full back-and-forth leading up to it: http://news.ycombinator.com/item?id=35068 ).

I wish I had discovered HN back then.

I would think that pencil and paper would be slower than writing the programs. But you're right that they are ridiculously easy.

For the third problem, yes. But after solving the first two problems without writing code, I didn't feel like starting on the last problem.

I seem to recall that there were 2^22 sets in the power set of that list of numbers, so you obviously had to use some kind of technique to cull the vast majority of the sets.

Hmm... now that I think about it, did you do something like starting at the end of the list, then subtracting numbers as you went until you either found a set that added up to your top number, or found it impossible for that number to be in the set?

It seems like it would take a lot of paper to do that, but it's more efficient than the simple brute force technique I did.

I'm just curious, because I bet there are better ways to do that one and I think the challenge is probably over by now.

Here is a hint. Look at http://en.wikipedia.org/wiki/Pascal%27s_triangle and ask yourself why the 23nd row can be calculated without explicitly enumerating all possible subsets.

I'm pretty sure that cperciva used a similar trick, but in each row you're potentially adding another element of the set, and not potentially adding 1.

This gives you a mapping telling you how many ways there are to get 0, 1, 2, 3, etc as the sum of some subset of the set. Just sum this over the set, and subtract the size of the set. (Every element in the set is the sum of itself, but you don't want to count those.) And there is your answer.

How do you go about solving #2 on pen and paper? Well, calculating the Fibonacci sequence, ok. The sum of prime divisors of X+1, I guess... though it gets slightly harder for me after dividing by 2, 3 and 5. But how do you know for sure that X is prime?

Based on bd's link, I'll just assume that you have super powers. (or I'm approaching the problem the wrong way)

edit: I was starting to think about what to write for #1, but ended finding the answer by looking at it as well.

You can use the Sieve of Eratosthenes to generate primes with pen and paper very easily. Or, you could find a roll of paper and evaluate any computable function (assuming unbounded paper). ;)

It doesn't seem to make it especially easy: you still have the same problem of having to eliminate the multiples of 61, 79, 89, etc. which are not obvious. Yes, you can count, but it looks very time-consuming.

The problem still stands that one needs to go in the 500,000s for that problem (thus 700s for the square root). That's still a long way to go…

I'm really curious about how cperciva did it. You're supposed to find the first Fibonacci prime over 227,000. The first Fibonacci number over that is obviously not prime (multiple of 3), but the one after that is not obvious even if you have the list of primes obtained with that method.

You have less than 30 Fibbonacci numbers to compute.

That 317811 is divisible by 3 is obvious upon adding its digits together.

Once you've verified that 514229 isn't divisible by a handful of small primes, you don't try to prove primality. Instead factor 514230 and stick it in. After dividing by 2, 3, and 5, you've got 17141. It doesn't take that long to run through 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 and 61. At which point you have an answer you can try plugging in to discover it is correct. Which is a sequence cperciva pretty definitely has memorized. (I do.) Or alternately cperciva may have better factorization techniques memorized.

If you already have a routine around for factoring (I do), then this takes longer than coding it. But I could do it with paper and pencil pretty easily.

Fair enough. Though I'd argue on "entirely solvable by pencil and paper", since the answer is an educated guess in that case and the proof that it's correct resides in checking with the webpage. ;-)

To be honest, in the same amount of time, one could also estimate the range where the answer should be and plug it one by one in the form until it validates. (which we'll call a less educated guess :))

Easy job for a regex:

    while ($string =~ /((\w+)\w?(??{reverse $2}))/g) { print "$1\n"; }

fuckin nice. now I feel like a doofus for using ruby, when I thought it was straightforward.

I've done it ruby this way:

    text.scan(/(.)(.)(.)(.)(\3)(\2)(\1)/)

That's pretty frail. It won't catch palindromes with an even number of letters (e.g. ababbaba) and it'll only find those of at most 7 characters. Granted, you can use those matches to work outwards and search for more, but I didn't think the general solution was all that hard.

Oddly enough, it didn't even occur to me to try a regex and I like using them quite a bit.

I solved all three problems in under a half-hour by writing quick-and-dirty Java programs to do it. The standard libraries provide almost everything I needed; the only thing I used other than that was Maple to factor the number. I'm pretty sure mucking around with CPAN libs such would have taken me longer. Granted, my solutions were brute-force and not very elegant, but for simple problems like these with small inputs I can write code to solve it faster than finding the answer elsewhere.

Writing code for 2 & 3 would probably take more than solving it with pen&paper, for me at least. I wrote code for #1 because it was practically 3 lines..

If it was really meant as a programming challenge, it should feature problems which are worth writing code for.

I'm disappointed that it is possible to solve by hand, as that undercuts the reward. This is one of the great aspects of ITA's programming problems: none of them are even solvable by brute force.

I didn't know that was within the extent of your powers cperciva

Now I have to try this.

Were you actually satisfied after doing that? You probably just wasted your time.

Reply on news.ycombinator.com