News for hackers. Stuff that matters.
Re:Can you solve it? The Greplin programming challenge by shiven on Friday October 08, 2010 @08:30PM (#1773978)
Seems like I may be the only person to have used a bioinformatics approach to the first problem! bl2seq to the rescue!! I'll explain my approach if anyone seems interested... as I am not sure if posting solutions is acceptable here.

Edit: As others seem to be posting gist/snips etc. so I guess it is OK.

Step 0 - Copied parent string to file: p1.txt

Step 1 - Used python to reverse the entire string and copy to second file: cat p1.txt | python -c "print raw_input()[::-1]" > p2.txt

Step 2 - Formatted the two files, so as to be parsed as FASTA, by adding sequence name headers.

Step 3 - Use bl2seq (blastp) locally or online to align the two "sequences". Final alignment shows only one major chunk of identity, i.e. the answer.

So, in essence, a dynamic programming algo would work.

Re:Can you solve it? The Greplin programming challenge by stygianguest on Saturday October 09, 2010 @10:01AM (#1775024)
If bl2seq gets the longest common subsequence I did exactly the same thing. In haskell it just seems the right thing to do. Actually it would be damn interesting to see if there are patterns in the solutions for every programming language.
Re:Can you solve it? The Greplin programming challenge by bd on Friday October 08, 2010 @04:04PM (#1773135)
"Even if you're not looking for a job, we'd love to hear what you thought about the challenge."

I would be curious how many people did you lose because of phonecall requirement (before you changed it).

Also CSV for just a list of 22 numbers wasn't really necessary.

If you do web puzzle, the best is to keep everything self-contained, no downloads, no using external channels, just copy and paste.

FYI another Python cheater here (+Wolfram Alpha & Wikipedia, I'm lazy :).

Re:Can you solve it? The Greplin programming challenge by Tichy on Friday October 08, 2010 @08:23PM (#1773962)
I just copied the CSV into the text editor. But I just realized how stupid I was. I wrote

var nums = "3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99".split(", ");

for(var i = 0;i< nums.length;i++) { nums[i] = parseInt(nums[i],10); }

Instead of just editing the numbers so that it was an array right away. Happens if you code before you think :-)

Re:Can you solve it? The Greplin programming challenge by dschoon on Friday October 08, 2010 @04:11PM (#1773164)
I don't think trivializing the combinations with Python's builtins, looking up the fib primes with OEIS, or computing factors with Alpha is cheating. I hope, in fact, it's the whole point of the exercise: choose the right tools for the job. If you're writing code to test primeness or generate Fibonacci numbers, I sure as hell don't want to hire you.
Re:Can you solve it? The Greplin programming challenge by dkarl on Friday October 08, 2010 @04:55PM (#1773349)
If you're writing code to test primeness or generate Fibonacci numbers, I sure as hell don't want to hire you.

Maybe you should have called it the "Greplin Challenge," then, instead of the "Greplin Programming Challenge." It's not a real task, after all; the reward comes from accepting a completely artificial challenge. I'm going to do the challenge before dinner tonight, and before I leave work I could get source code for the solutions from the guy down the hall from me who did the challenge as soon as it was posted -- and you certainly don't want to hire a guy who recodes other people's work for no reason, right?

Re:Can you solve it? The Greplin programming challenge by rwalker on Friday October 08, 2010 @05:35PM (#1773496)
Maybe we have a different hiring mindset than dschoon - we're equally happy with people who find the answers or create the answers. In a production system, we certainly wouldn't want hand-rolled primeness checking. But in a programming challenge, we think it's fun to write it for yourself.
Re:Can you solve it? The Greplin programming challenge by dkarl on Friday October 08, 2010 @06:09PM (#1773621)
Oops; I wrote my comment under the assumption that dschoon was with greplin, and in retrospect I'm not sure why. Sorry about that.
Re:Can you solve it? The Greplin programming challenge by zmitri on Friday October 08, 2010 @04:18PM (#1773186)
Code to generate fibs is literally one line. Remember eigenvalues :)?
Re:Can you solve it? The Greplin programming challenge by shiven on Friday October 08, 2010 @08:54PM (#1774017)
Sorry, couldn't help myself!! That approach is just so damn elegant.

int((1/math.sqrt(5))*(math.pow(((1+math.sqrt(5))/2),fibonacci)-math.pow(((1-math.sqrt(5))/2),fibonacci)))

Reference here: http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...

Re:Can you solve it? The Greplin programming challenge by btilly on Friday October 08, 2010 @09:30PM (#1774080)
Elegant, but inefficient if you want to get exact values for large n. You're much better off using doubling operations. If you forget those, you can remember them from the matrix version. If fib(0) = 0. fib(1) = 1. etc. Then

       n
  [0 1]  = [fib(n)   fib(n+1)]
  [1 1]    [fib(n+1) fib(n+2)]
With repeated squarings, you can efficiently generate any Fibonacci number you want.
Re:Can you solve it? The Greplin programming challenge by kasterma on Sunday October 10, 2010 @10:08AM (#1777102)
Here (where you have to search through Fibonacci numbers) I suspect memoization is rather the way to go:

  # memoized fibonacci function
  fibtable = {1:1, 0:1}

  def fib (n):
      global fibtable
      if n in fibtable.keys():
          return fibtable [n]
      val = fib (n-1) + fib (n-2)
      fibtable [n] = val
      return val
Re:Can you solve it? The Greplin programming challenge by btilly on Sunday October 10, 2010 @11:54AM (#1777237)
There is no need to keep track of all previous values.

  last_fib = 0
  fib = 1
  while fib < 225000 or not is_prime(fib):
    last_fib, fib = fib, last_fib + fib
Re:Can you solve it? The Greplin programming challenge by d0m on Friday October 08, 2010 @07:20PM (#1773826)
I tend to agree with dkarl here because if it was for real, I would just have looked here to find all the answers and maybe the passwords.

It was way more fun to do it from scratch :D

Thanks grepplin

p.s. the csv was copied in my [] python list :)

Re:Can you solve it? The Greplin programming challenge by extension on Sunday October 10, 2010 @03:58AM (#1776768)
I wrote extremely naive Ruby algos from scratch that solved the problems in a couple seconds, or in the case of the last problem, a couple of minutes. I'm sure the whole challenge would have taken longer if I tried to use any dependencies.
Re:Can you solve it? The Greplin programming challenge by csmajorfive on Friday October 08, 2010 @05:15PM (#1773414)
I think this would've been a better filter for hiring if the magnitude were larger (e.g. huge string, more numbers for the combination, etc) or if there was a strict time limit. As it is right now, I don't think the hardcore hackers you're looking for will be that enticed.
Re:Can you solve it? The Greplin programming challenge by cakeface on Tuesday October 12, 2010 @06:43PM (#1785281)
I think that you'd be surprised at the sheer number of applicants a very basic programming challenge can weed out. The company that I work at has a simple test to parse a csv file and a surprising amount of people who appear to be good candidates bomb it.
Re:Can you solve it? The Greplin programming challenge by cperciva on Friday October 08, 2010 @04:28PM (#1773229)
Do I get bonus marks for solving this without writing any code?
Re:Can you solve it? The Greplin programming challenge by cosgroveb on Friday October 08, 2010 @05:29PM (#1773475)
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...

Re:Can you solve it? The Greplin programming challenge by staunch on Friday October 08, 2010 @08:19PM (#1773955)
Easy job for a regex:

    while ($string =~ /((\w+)\w?(??{reverse $2}))/g) { print "$1\n"; }
Re:Can you solve it? The Greplin programming challenge by dantle on Saturday October 09, 2010 @12:33AM (#1774345)
fuckin nice. now I feel like a doofus for using ruby, when I thought it was straightforward.
Re:Can you solve it? The Greplin programming challenge by manveru on Saturday October 09, 2010 @06:36AM (#1774809)
I've done it ruby this way:

    text.scan(/(.)(.)(.)(.)(\3)(\2)(\1)/)
Re:Can you solve it? The Greplin programming challenge by Natsu on Monday October 11, 2010 @05:38AM (#1779249)
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.

Re:Can you solve it? The Greplin programming challenge by cperciva on Friday October 08, 2010 @05:32PM (#1773483)
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).
Re:Can you solve it? The Greplin programming challenge by Timothee on Friday October 08, 2010 @07:38PM (#1773863)
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.

Re:Can you solve it? The Greplin programming challenge by baddox on Friday October 08, 2010 @10:10PM (#1774139)
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). ;)
Re:Can you solve it? The Greplin programming challenge by Timothee on Friday October 08, 2010 @11:10PM (#1774226)
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.

Re:Can you solve it? The Greplin programming challenge by btilly on Friday October 08, 2010 @11:53PM (#1774306)
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.

Re:Can you solve it? The Greplin programming challenge by Timothee on Saturday October 09, 2010 @12:48AM (#1774358)
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 :))

Re:Can you solve it? The Greplin programming challenge by btilly on Friday October 08, 2010 @05:55PM (#1773581)
I would think that pencil and paper would be slower than writing the programs. But you're right that they are ridiculously easy.
Re:Can you solve it? The Greplin programming challenge by cperciva on Friday October 08, 2010 @06:02PM (#1773603)
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.
Re:Can you solve it? The Greplin programming challenge by Natsu on Sunday October 10, 2010 @04:25PM (#1777865)
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.

Re:Can you solve it? The Greplin programming challenge by btilly on Monday October 11, 2010 @02:01AM (#1778954)
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.

Re:Can you solve it? The Greplin programming challenge by cosgroveb on Friday October 08, 2010 @05:35PM (#1773495)
Ah. Well I'm an even worse hacker than I thought!
Re:Can you solve it? The Greplin programming challenge by bd on Friday October 08, 2010 @06:12PM (#1773633)
Don't feel bad, it's just how cperciva rolls :)

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

Re:Can you solve it? The Greplin programming challenge by jackowayed on Friday October 08, 2010 @07:39PM (#1773866)
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.

Re:Can you solve it? The Greplin programming challenge by staktrace on Friday October 08, 2010 @11:46PM (#1774294)
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.
Re:Can you solve it? The Greplin programming challenge by mfukar on Saturday October 09, 2010 @01:32AM (#1774428)
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.

Re:Can you solve it? The Greplin programming challenge by ynniv on Friday October 08, 2010 @11:56PM (#1774307)
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.
Re:Can you solve it? The Greplin programming challenge by rpbertp13 on Friday October 08, 2010 @04:48PM (#1773320)
I didn't know that was within the extent of your powers cperciva
Re:Can you solve it? The Greplin programming challenge by sz on Friday October 08, 2010 @07:45PM (#1773883)
Now I have to try this.
Re:Can you solve it? The Greplin programming challenge by aufreak3 on Saturday October 09, 2010 @08:22AM (#1774896)
Were you actually satisfied after doing that? You probably just wasted your time.
Re:Can you solve it? The Greplin programming challenge by gmaster1440 on Friday October 08, 2010 @06:30PM (#1773687)
Nice and short Haskell solution to #3: http://gist.github.com/617675

Ruby solutions to #1 and #2: http://gist.github.com/617676 http://gist.github.com/617678

Re:Can you solve it? The Greplin programming challenge by thomie on Sunday October 10, 2010 @05:31AM (#1776846)
Nice, but don't compute the length of a list if you don't have to.

(not . null) instead of (\x -> length x > 1) is shorter, and works on infinite lists also.

Edit: well, in case you would test for x>0.

Re:Can you solve it? The Greplin programming challenge by grogers on Friday October 08, 2010 @05:05PM (#1773387)
That was fun, good waste of time while my code was compiling. I just used C++ and hacked up a prime seive for #2 and for #3 used a combination generator I had previously used before - http://photon.poly.edu/~hbr/boost/combinations.html
Re:Can you solve it? The Greplin programming challenge by cperciva on Friday October 08, 2010 @05:36PM (#1773504)
for #3 used a combination generator

Congratulations, you just used an exponential-time algorithm for a polynomial-time problem.

Re:Can you solve it? The Greplin programming challenge by Deestan on Friday October 08, 2010 @06:37PM (#1773712)
Congratulations are in order, he sacrificed 400ms CPU time to save at least a few minutes of coding time.
Re:Can you solve it? The Greplin programming challenge by cperciva on Friday October 08, 2010 @07:22PM (#1773832)
I wasn't being entirely sarcastic. It never occurred to me that you could use a non-polynomial-time algorithm.
Re:Can you solve it? The Greplin programming challenge by util on Monday October 11, 2010 @03:19AM (#1779046)
All the solutions posted here seem to involve generating all subsequences. Could you say more about your approach?
Re:Can you solve it? The Greplin programming challenge by dsc on Friday October 08, 2010 @11:37PM (#1774276)
Not always is "exponential" a bad thing. For small sets, the expo algorithm is actually faster than the polynomial one. Although yeah, generally speaking, it's a bad idea.
Re:Can you solve it? The Greplin programming challenge by ay on Sunday October 10, 2010 @08:45AM (#1777017)
I tried on #3 the most inefficient algorithm I could come up with - blindly going through all possible combinations and checking if their biggest member is equal to the sum of the rest. Time of the execution: 0.6s

I am not sure if this step of allowing the "shortcuts" was part of the game or not. All that would had to be done is to give 128 elements of the array to exclude at least the most blatant brute-forcing.

Re:Can you solve it? The Greplin programming challenge by nene on Friday October 08, 2010 @04:14PM (#1773174)
I'm usually pretty bad at these kind of challenges (lately I tried registering at one mind-challenges site, but I couldn't even get past the five entry-level questions, which would have allowed me to even register), but this was surprisingly easy. Simple brute-force methods worked for each of the three tasks. I was totally surprised that the first time I entered the answer for each of the tasks, it was indeed the correct one.

But then again... these are all pretty standard computer science problems, nothing that I hadn't in some way done before.

On a side-note: Interestingly I used recursion for each of the three problems. Well... actually for the primes-problem I got stack overflow and rewrote it to not use recursion, but still, at least in principle :=)

Re:Can you solve it? The Greplin programming challenge by danielsoneg on Friday October 08, 2010 @05:33PM (#1773487)
Agreed - I was laughing as I was writing some of my code because it was so bad. These sort of questions are designed around algorithm design, but a one-off problem with these small of sample sets doesn't need an elegant solution - a hatchet job does just fine. I'm not a CS grad and my math skills are a bit iffy, but I was able to solve all three challenges in a pretty reasonable amount of time.
Re:Can you solve it? The Greplin programming challenge by jah on Friday October 08, 2010 @02:31PM (#1772744)
Uh ... call a phone number? No thanks.

Edit: Excellent! Back to hacking.

Re:Can you solve it? The Greplin programming challenge by rwalker on Friday October 08, 2010 @02:47PM (#1772828)
Phone call no longer required.

For what it's worth - it's just a Twilio app - we thought it would add to the fun.

Re:Can you solve it? The Greplin programming challenge by seanstickle on Friday October 08, 2010 @04:28PM (#1773230)
I'm curious to know why calling a phone number was a deal-breaker.

It seemed eminently likely (to me) that it would be an automated system, but, even if it wasn't, talking to someone isn't that big a deal to me. I certainly wasn't concerned about long-distance charges, but I suppose that might be a problem for some.

I thought it was a nice little twist in the problem set.

Re:Can you solve it? The Greplin programming challenge by petercooper on Friday October 08, 2010 @04:34PM (#1773256)
but, even if it wasn't, talking to someone isn't that big a deal to me.

A lot of people struggle with the phone. I certainly have, though I'm getting better at it. I've noticed many people become spookily compliant on the phone, endlessly listening to and being polite to even the most annoying callers instead of just hanging up.

Re:Can you solve it? The Greplin programming challenge by Deestan on Friday October 08, 2010 @06:42PM (#1773726)
I live in Norway, so the phone bill is a significant factor. Also, the wife and kids are sleeping in the next room, which would require me to step outside on the porch in the middle of the night with my cellphone.

Yet also, I'm so tired I couldn't have englished very well in my phone anyway. :-)

Re:Can you solve it? The Greplin programming challenge by jlees on Friday October 08, 2010 @06:44PM (#1773734)
Maybe you don't want them knowing your phone number to call you back with job calls or whatever. (Of course, there are ways around that too.)
Re:Can you solve it? The Greplin programming challenge by kbob on Friday October 08, 2010 @05:58PM (#1773590)
I'm hearing-impaired.
Re:Can you solve it? The Greplin programming challenge by brandon on Friday October 08, 2010 @02:37PM (#1772783)
Yep, decided not to continue when I got to that point.

It looks like the number is a landline in the Bay Area. I wonder if some poor soul at Greplin will be taking calls all day.

Re:Can you solve it? The Greplin programming challenge by whimsy on Friday October 08, 2010 @02:44PM (#1772810)
Perhaps this is one of those "secret recruitment processes."
Re:Can you solve it? The Greplin programming challenge by jewbacca on Friday October 08, 2010 @07:04PM (#1773781)
Oh my god, Haskell is so pretty. This is the first time I've used it to solve math problems. Is it kosher to share solutions?
Re:Can you solve it? The Greplin programming challenge by brandon on Friday October 08, 2010 @08:40PM (#1773996)
I gist'd one because I saw others sharing. I'd be curious to see how you did things in Haskell.
Re:Can you solve it? The Greplin programming challenge by Natsu on Friday October 08, 2010 @04:15PM (#1773179)
Damn, I have to go in to work early today or I could continue this. The first one only took a minute or two of coding to solve in Perl. The search string was several times longer than my code, even with use warnings & use strict in there.

I'd write a bit of code to memoize the function before I'd do the Fibonacci numbers, though, and I just don't have time to continue right now, even though it's pretty easy. Are the rest of the tests like that? Do they force you to use more efficient code, rather than simpler brute force tests so that your code has a decent runtime?

Re:Can you solve it? The Greplin programming challenge by Tichy on Friday October 08, 2010 @08:27PM (#1773972)
brute force seems to be sufficient
Re:Can you solve it? The Greplin programming challenge by leif on Friday October 08, 2010 @11:45PM (#1774293)
you also probably don't want to memoize, you aren't going to re-use, so why waste the memory?
Re:Can you solve it? The Greplin programming challenge by Natsu on Saturday October 09, 2010 @01:31AM (#1774425)
I wrote that right before leaving for work, so I hadn't spent any time thinking about the problem.

Coming back, I see that I really don't need to be very efficient for any of these problems, which I honestly find a little disappointing.

Re:Can you solve it? The Greplin programming challenge by 1amzave on Friday October 08, 2010 @04:02PM (#1773127)
So what languages did everyone use?

I decided to try a different one on each level, so I used Python, bash (letting GNU coreutils 'factor' do the hard work), and Haskell, respectively.

Re:Can you solve it? The Greplin programming challenge by sisk on Friday October 08, 2010 @05:37PM (#1773507)
JavaScript. I had my browser open ... it seemed like the logical place. :)
Re:Can you solve it? The Greplin programming challenge by lisper on Friday October 08, 2010 @08:09PM (#1773936)
Common Lisp of course :-)
Re:Can you solve it? The Greplin programming challenge by ismarc on Friday October 08, 2010 @07:33PM (#1773855)
I used Haskell for the first one (was my first actual Haskell program, everything before was just xmonad config), C for the second one (already had the needed code for generating fibonacci sequences and a prime number sieve from when I went through the euler problems using only ANSI C) and Perl for the last one. I initially used Data::PowerSet for the Perl code, but decided to write my own after it took several minutes to build the combinations and I discovered that I had the wrong answer because I improperly read the problem.

I should note that I used the existing C code I had because I had no idea where they would intersect and didn't feel like writing Yet Another Arbitrarily Large Integer Handler.

Re:Can you solve it? The Greplin programming challenge by nene on Friday October 08, 2010 @04:28PM (#1773228)
Ruby was my main choice + some command line tools to do bits of extra work, like 'sort' to find the largest palindrome and 'wc' to count the results in last exercise, and even Python command line to just manually sum the primes in second exercise.
Re:Can you solve it? The Greplin programming challenge by djacobs on Friday October 08, 2010 @06:13PM (#1773641)
Ruby has Array#sort, no command line required.
Re:Can you solve it? The Greplin programming challenge by Twisol on Friday October 08, 2010 @05:02PM (#1773375)
I used Lua, myself. I briefly considered using a more featureful language like Ruby, but I'm happy to say that Lua did the job just fine. I made good use of coroutines for the second and third problems.
Re:Can you solve it? The Greplin programming challenge by callahad on Friday October 08, 2010 @04:55PM (#1773348)
Python, Scheme, Python. Mainly because I had nice functions in Scheme for level 2 sitting around from when I was trying to work through SICP...
Re:Can you solve it? The Greplin programming challenge by cygwin98 on Thursday October 14, 2010 @03:32PM (#1792256)
I know I'm late to the party, :) I used Ruby 1.9.2. It's funny that it's the first time I used the combination generation method built in Ruby Array. The whole three questions took me about a bit more than 20 minutes, a bit longer than I thought tho.
Re:Can you solve it? The Greplin programming challenge by sendos on Saturday October 09, 2010 @04:04AM (#1774640)
Matlab for all three parts.

Quick and dirty solutions here: http://gist.github.com/618006

Re:Can you solve it? The Greplin programming challenge by leif on Friday October 08, 2010 @11:41PM (#1774284)
I'm wonderfully amazed that coreutils has factor.
Re:Can you solve it? The Greplin programming challenge by tef_ on Saturday October 09, 2010 @01:25PM (#1775364)
Python for 1,2 with a little bit of manual pasting into wolfram alpha

And for part 3 I used prolog. About ~6 lines or so.

Re:Can you solve it? The Greplin programming challenge by nomurrcy on Friday October 08, 2010 @04:54PM (#1773344)
Clojure here.
Re:Can you solve it? The Greplin programming challenge by djacobs on Friday October 08, 2010 @06:20PM (#1773657)
Mind posting your solution as a Gist? I want to see how to do level 1 without explicit loops or variables.
Re:Can you solve it? The Greplin programming challenge by nomurrcy on Monday October 11, 2010 @04:15PM (#1781063)
Sure, sorry about the delay.

http://gist.github.com/621130

I can't take credit for the solution I posted though.

I originally wrote a naive O(N^2) complexity solution (which was much shorter and was fine for the length of the input) I had this palindrome code in my 'toolbox' of code I've come across though, I'm afraid I don't know the orig author.

I just tweaked it as this is more in line with the type of example you're looking for.

Re:Can you solve it? The Greplin programming challenge by djacobs on Tuesday October 19, 2010 @11:01PM (#1809777)
Interesting, I'll have to go over your code fairly carefully, as I'm not familiar with every technique you're using here for performance.

I've since learned a good deal about Clojure and implemented an idiomatic (but probably less performant) version, for anyone interested in how short this can be:

http://gist.github.com/635674

Re:Can you solve it? The Greplin programming challenge by Natsu on Saturday October 09, 2010 @01:29AM (#1774418)
Perl. From the look of this thread, I guess everyone else has moved on?
Re:Can you solve it? The Greplin programming challenge by colomon on Saturday October 09, 2010 @04:14PM (#1775747)
I solved all three in Perl 6... ;)
Re:Can you solve it? The Greplin programming challenge by grigory on Friday October 08, 2010 @08:20PM (#1773958)
Python here - very quick to code in if you have terminal handy.
Re:Can you solve it? The Greplin programming challenge by aristidb on Saturday October 09, 2010 @08:42AM (#1774916)
Haskell for all. Perfect fit.
Re:Can you solve it? The Greplin programming challenge by afshin on Saturday October 09, 2010 @11:45AM (#1775170)
k, javascript, javascript

None of my solutions were particularly elegant :-)

Re:Can you solve it? The Greplin programming challenge by whimsy on Sunday October 10, 2010 @04:02PM (#1777808)
No Erlang?!
Re:Can you solve it? The Greplin programming challenge by p01nd3xt3r on Friday October 08, 2010 @05:55PM (#1773580)
c / python
Re:Can you solve it? The Greplin programming challenge by triangleman83 on Friday October 08, 2010 @03:31PM (#1773016)
Wow the G. Address was horribly mutilated.

Four score and seven years ago our faathers brought forth on this containent a new nation conceived inz Liberty and dedicated to the proposition that all men are created equal Now we are engaged in a greaht civil war testing whether that naption or any nartion so conceived and so dedicated can long endure We are qmet on a great battlefiemld of tzhat war

Re:Can you solve it? The Greplin programming challenge by rwalker on Friday October 08, 2010 @03:36PM (#1773038)
This was intentional - we had to tie break the longest palindrome and we didn't want a quick diff to be able to see what we changed.
Re:Can you solve it? The Greplin programming challenge by Cushman on Friday October 08, 2010 @08:13PM (#1773943)
Never mind that finding the actual text, removing the spaces and caps, and running diff would probably take longer than coding and executing a brute force algorithm :P
Re:Can you solve it? The Greplin programming challenge by Natsu on Saturday October 09, 2010 @01:39AM (#1774447)
Why not ask for the rightmost palindrome, then? Just to make it a tiny bit more complex (not that it's very hard to iterate backwards)?
Re:Can you solve it? The Greplin programming challenge by zmitri on Friday October 08, 2010 @04:03PM (#1773133)
The last question isn't that difficult if you brute force it and have loads of memory. I tried to do it in python using itertools on my work thinclient and got a memoryerror. If you however break up your combinations.. you're good to go!

Fun, made my day. Good idea greplin dudes!

Re:Can you solve it? The Greplin programming challenge by tbrownaw on Friday October 08, 2010 @09:19PM (#1774062)
Not sure what you'd need the loads of memory for?

    int[] nums = {...}
    for i = 1 to (2^length(nums) - 1)
        int[] possibility = { nums[x] where (2^x bitand i) > 0 }
        test possibility and perhaps increment hit counter
Re:Can you solve it? The Greplin programming challenge by zmitri on Saturday October 09, 2010 @04:52AM (#1774713)
I was at work on a crappy thin client and first tried to run list(itertools.combinations(sequence)), which was crapping out. After I switched it to itertools.combinations(sequence,i) and put that right into my for loop it was fine.
Re:Can you solve it? The Greplin programming challenge by joe_the_user on Friday October 08, 2010 @05:03PM (#1773380)
I've generally done well on job-interview programming challenges and gotten interviews afterwards. But looking on these quiz things, I'm still frustrated by them.

You see, all the "ordinary" question involved in job-fitting still have to be asked and answered so sometimes I've done great in ability part only to have really basic "culture" or requirements issue hit later when they could have been caught immediate.

And so, even though I've enjoyed and learned something on these quizzes, the employer who begins a relationship with a quiz seems to be saying they can demand some piece of my time without any investment on their part and this isn't setting a tone reciprocity, something I'd look for in a future employer.

Re:Can you solve it? The Greplin programming challenge by lisper on Friday October 08, 2010 @07:05PM (#1773782)
Too easy to solve by brute force. I'd suggest looking at Project Euler for inspiration.
Re:Can you solve it? The Greplin programming challenge by dkarl on Friday October 08, 2010 @08:46PM (#1774004)
I'm a little bored with Project Euler after solving the first 40+ problems with brute force or near-brute force algorithms. If I wasn't using it to learn a new language, I would have quit already. As it is, after solving one problem I usually quit for the day instead of moving on to the next. When do the problems pick up?
Re:Can you solve it? The Greplin programming challenge by lisper on Saturday October 09, 2010 @03:10AM (#1774566)
Well that depends on your level of expertise :-) I start to have unsolved problems around #60, but found I had to start getting pretty clever long before that. The highest number I've solved is 112, and the one before that is 102. YMMV.
Re:Can you solve it? The Greplin programming challenge by Tichy on Saturday October 09, 2010 @03:49AM (#1774620)
Or better, Google Code Jam problems.
Re:Can you solve it? The Greplin programming challenge by tedc on Friday October 08, 2010 @02:25PM (#1772722)
1-2 hours! Great...now my productivity will be shot for the day.
Re:Can you solve it? The Greplin programming challenge by stelfer on Saturday October 09, 2010 @02:28PM (#1775498)
Here's mine: http://gist.github.com/618459

I didn't see the point in doing this in anything but C. I tried it without cheating, and to make it as interesting to myself as possible. Also did it after a week of writing briefs, so that was a nice way to unwind from that! Pretty Fun.

Anyway, if I'm applying for a job (which I wasn't), the last thing I'm going to do is send in a bunch of one-liners.

Re:Can you solve it? The Greplin programming challenge by tylrdotorg on Friday October 08, 2010 @05:57PM (#1773586)
This really doesn't reflect a programmers skills in anyway. I managed to write ruby to solve the problems, but I approached it to do for fun. Brain teasers aren't going to weed out the good from bad.

Also, considering the instructions explicitly say "write code to..." I would say using tools that give you the answers is in fact cheating. It's like math test where you have to show your work.

Re:Can you solve it? The Greplin programming challenge by mace on Saturday October 09, 2010 @03:47PM (#1775672)
IMHO, these contrived puzzles, while fun, are really unrealistic and don't map well to problems you'll encounter on the job which requires knowledge, experience and creativity and do not have just one answer.

Of all of the jobs-page challenges, thesixyone's is probably the most practical and I've seen:

http://www.thesixtyone.com/static/jobs

Re:Can you solve it? The Greplin programming challenge by koblas on Friday October 08, 2010 @05:42PM (#1773529)
What about a puzzle system system -- Companies can post/host questions and then review the answers. I've drafted a quick blog post if anybody wants to comment more directly... Maybe I'll make it this weekends projects (since my frid.ge clone was killed by Facebooks new groups).

http://bit.ly/b6GC6F

Re:Can you solve it? The Greplin programming challenge by temugen on Friday October 08, 2010 @05:54PM (#1773576)
Python powerset() with max(), list.remove(), and sum() builtins made the last problem's solution ~5 lines long :)
Re:Can you solve it? The Greplin programming challenge by brandon on Friday October 08, 2010 @06:19PM (#1773652)
I don't know about powerset(), but challenge 3 was pretty trivial using Python's itertools module: http://gist.github.com/617663 (warning: spoilers)
Re:Can you solve it? The Greplin programming challenge by olalonde on Friday October 08, 2010 @10:01PM (#1774123)
I thought the challenge was to solve everything with "grep" because of the "Greplin" title.
Re:Can you solve it? The Greplin programming challenge by dasil003 on Friday October 08, 2010 @07:14PM (#1773810)
Here's better-than-brute-force solution to Q1 http://gist.github.com/617715

Is there a better algorithm? Dynamic programming of some sort? I guess we'd need a longer string to tell the difference.

Re:Can you solve it? The Greplin programming challenge by leif on Friday October 08, 2010 @11:44PM (#1774290)
I can't read ruby, but here's something a little smarter than brute force in C (on its way to DP, but I couldn't be arsed to work out the recurrence so I just iterated until it stabilized): http://gist.github.com/617854
Re:Can you solve it? The Greplin programming challenge by dasil003 on Saturday October 09, 2010 @12:58AM (#1774370)
It looks similar to mine, but you got lucky (or unlucky depending on how you look at it) that the longest palindrome had an odd character count.

The confusing bits in the Ruby are actually just the definition of an even and odd palindrome finder, which are the same except for two seed values for where the first comparison is conducted and it's length.

Re:Can you solve it? The Greplin programming challenge by leif on Saturday October 09, 2010 @01:43AM (#1774449)
oh whoops nice catch thx
Re:Can you solve it? The Greplin programming challenge by btilly on Friday October 08, 2010 @05:53PM (#1773573)
Took < 10 minutes. The problems were very, very easy. If they expect people to take 1-2 hours and have trouble with this, then the message that I would take away from this is that their hiring bar is quite low.
Re:Can you solve it? The Greplin programming challenge by JesseAldridge on Friday October 08, 2010 @08:12PM (#1773940)
Re:Can you solve it? The Greplin programming challenge by g0 on Sunday October 10, 2010 @01:54PM (#1777521)
http://codepad.org/rdSirAkD -- Solution to third problem in 26 lines of ruby _without_ using combinations. It's pretty fast too, gives the answer in 0.020s.
Re:Can you solve it? The Greplin programming challenge by sahillavingia on Friday October 08, 2010 @05:47PM (#1773550)
Any points for solving part 1 just scanning the text for something that stood out?

Seriously though, this is awesome. I'd love to know how you guys do in terms of # of applicants and the end-result (any hires?).

Re:Can you solve it? The Greplin programming challenge by jiaaro on Friday October 08, 2010 @06:40PM (#1773719)
solutions in python http://gist.github.com/617686

about 30 lines of code in the tersest style, 40ish in the readability-obsesssive style I prefer

Re:Can you solve it? The Greplin programming challenge by Natsu on Monday October 11, 2010 @05:47AM (#1779257)
I see that you did brute force primality testing, too. Am I the only one who at least only divided by odd numbers (and two) in their brute-force is_prime function? Technically, you only need to test divide by all primes less than or equal to sqrt(n), after all.

I guess I could have used a faster primality test, but I didn't feel like writing anything that complex. I know there's a website out there that has a test that works for anything under about 10 billion, if memory serves, by using the probabalistic tests and doing a special check for the only exception. Heck, it even gives you the factors for the largest number in its range...

Re:Can you solve it? The Greplin programming challenge by jiaaro on Sunday October 17, 2010 @11:09PM (#1802228)
this code solved the problem in under 1 second.

I would say for code that is executed one time ever, even including the sqrt(n) part is premature optimization (though I did include it)

Re:Can you solve it? The Greplin programming challenge by cube on Saturday October 09, 2010 @06:19AM (#1774800)
Thanks for sharing! Love the style and it's readability. My newbie python code did the trick, but is way harder to read - your code really showed me room for improvement!
Re:Can you solve it? The Greplin programming challenge by _prototype_ on Friday October 08, 2010 @08:26PM (#1773971)
I did the naive implementation for problem 1. (double loop, O(n2)), in Javascript. Took chrome about 1 minute to compute the comparisons of all strings. I'm so lazy.
Re:Can you solve it? The Greplin programming challenge by lamnk on Friday October 08, 2010 @07:12PM (#1773805)
Difficult level is about the same as Project Euler's problems 1x
Re:Can you solve it? The Greplin programming challenge by siglesias on Friday October 08, 2010 @02:51PM (#1772849)
Anybody else browsing by mobile try to do Level 1 by inspection?
Re:Can you solve it? The Greplin programming challenge by eqdw on Friday October 08, 2010 @02:52PM (#1772862)
After doing the obvious brute force algorithm, the correct answer is not a real word. So you'll have a tough time getting it on your own
Re:Can you solve it? The Greplin programming challenge by siglesias on Friday October 08, 2010 @03:01PM (#1772896)
Well, I was suggesting looking for symmetrical triads (or repeating characters) and then working outward. I'd say the eye is pretty good at picking out symmetries.
Re:Can you solve it? The Greplin programming challenge by 9ec4c12949a4f3 on Friday October 08, 2010 @03:08PM (#1772932)
Why aren't you guys just searching for the palindromes?

There's more efficient ways than doing every character, or groups of them... What constitutes a palindrome? What does that mean to simplify what we're doing?

http://www.w3schools.com/jsref/jsref_obj_string.asp

Re:Can you solve it? The Greplin programming challenge by davidjhall on Friday October 08, 2010 @04:26PM (#1773220)
I was in the middle of thinking through the algorithm when I looked at it and saw the password in the text --- the password worked but I still want to code the algorithm later to confirm.
Re:Can you solve it? The Greplin programming challenge by siglesias on Friday October 08, 2010 @05:39PM (#1773514)
That's sort of what I mean here. It's like solving a wordsearch puzzle. There can't be more than a couple dozen strings with structure xyx, or xyyx. Find them by eye and work outward and see if it's zxyxz, and so on. Decided to make this process into my algorithm.
Re:Can you solve it? The Greplin programming challenge by l0nwlf on Friday October 08, 2010 @03:25PM (#1772996)
Brute works here because of bad test case. Author could have generated a smart test case and then optimal algorithm could be using suffix array which takes O(n), brute would take O(n!). However a bit smart brute gave the answer in approx 3-4 minutes ( computation + coding time). And yes, Python FTW.
Re:Can you solve it? The Greplin programming challenge by orangecat on Friday October 08, 2010 @04:38PM (#1773279)
Isn't brute force just O(n^3)? Loop over each character to start potential palindrome, loop from start character to end, reverse substring and compare. But yeah, the test input should be longer and/or smarter. Ditto on the third problem.
Re:Can you solve it? The Greplin programming challenge by brown9-2 on Friday October 08, 2010 @04:49PM (#1773323)
reverse substring and compare

D'oh! My is_palindrome(word) just got a lot shorter, thanks :)

Re:Can you solve it? The Greplin programming challenge by johnfn on Friday October 08, 2010 @07:44PM (#1773880)
3-4 minutes!

Try this:

    for i in range(len(str)):
         for j in range(i, len(str)):
              if str[i:j] == str[i:j][::-1]:
                  #...
Choose the start and end indices. Then take a slice to see if it's a palindrome. Nice and speedy! :)
Re:Can you solve it? The Greplin programming challenge by preek on Friday October 08, 2010 @06:25PM (#1773672)
3-4min? Since it was only like 5 lines of code I did it in brute force. Python and Mac Mini here - the answer came almost instantaneously.
Re:Can you solve it? The Greplin programming challenge by l0nwlf on Friday October 08, 2010 @11:18PM (#1774240)
By 3-4 minutes I mean both computation as well as coding time. Solution of mine came in < 1s.
Re:Can you solve it? The Greplin programming challenge by eqdw on Friday October 08, 2010 @02:48PM (#1772835)
Um, no answer on the phone. I let it ring for over a minute.
Re:Can you solve it? The Greplin programming challenge by Twisol on Friday October 08, 2010 @05:04PM (#1773383)
Did you forget the 1 before the area code? I did.
Re:Can you solve it? The Greplin programming challenge by riffraff on Friday October 08, 2010 @04:45PM (#1773305)
damn it had a typo in the fib generation for the second number and lost a lot of time trying to factor a _massive_ number that was obviously the wrong one :)
Re:Can you solve it? The Greplin programming challenge by badsquare on Saturday October 09, 2010 @11:11AM (#1775113)
numbers ="3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97].split() numbers = [int(i) for i in numbers]

def sum_eq(lst,k): total = sum(lst) if total == k or k==0:return 1 elif total < k or len(lst)==1:return 0 else: n1,nr = lst[0],lst[1:] return sum_eq(nr,k-n1) + sum_eq(nr,k)

def sum_all_eq(lst): total = 0 for k in range(1,len(lst)): total += sum_eq(lst[0:k],lst[k]) return total

Re:Can you solve it? The Greplin programming challenge by LordLandon on Saturday October 09, 2010 @04:53PM (#1775848)
My C is terribly rusty, so I decided to not cheat with python: http://sprunge.us/GiDD

How terrible is it?

Re:Can you solve it? The Greplin programming challenge by bradly on Friday October 08, 2010 @05:13PM (#1773411)
Spoiler alert.

Here is my Part 1 implemented in Ruby. http://gist.github.com/617566

Re:Can you solve it? The Greplin programming challenge by tta on Tuesday October 12, 2010 @01:41PM (#1784193)
Anyone know other 'challenges' like this one?
Re:Can you solve it? The Greplin programming challenge by zaius on Friday October 08, 2010 @06:26PM (#1773680)
My solutions, in ruby:

http://gist.github.com/617672

Any improvements welcome!

(warning - contains the answers!)

Re:Can you solve it? The Greplin programming challenge by hammerdr on Saturday October 09, 2010 @12:28PM (#1775243)
Anyone else read Q2 as (sum of the prime factors of X) + 1? Confused me for a good 10 minutes :(
Re:Can you solve it? The Greplin programming challenge by orangecat on Friday October 08, 2010 @03:04PM (#1772906)
Done, as usual with these things using Python feels like cheating.
Re:Can you solve it? The Greplin programming challenge by jasondavies on Friday October 08, 2010 @03:08PM (#1772931)
The last problem was really simple in Python. I was all psyched up for a big bad end-level boss! Still, it was fun to play.
Re:Can you solve it? The Greplin programming challenge by rpbertp13 on Friday October 08, 2010 @04:52PM (#1773336)
35 mins, but in less than 40 lines of ruby
Re:Can you solve it? The Greplin programming challenge by djacobs on Friday October 08, 2010 @06:02PM (#1773601)
I used Ruby, too. Nothing else required.

I think Clojure might've made things a tad easier (given all its sequence functions), but I'm just learning it, so Ruby all the way.

That said, finding the palindromes in Ruby took me about 12 lines of code (less if I didn't structure it using methods).

Re:Can you solve it? The Greplin programming challenge by ajstiles on Friday October 08, 2010 @03:08PM (#1772926)
30 minutes. Would have been less but the IVR response was a little confusing. Took about 40 lines Ruby code to solve.
Re:Can you solve it? The Greplin programming challenge by dann on Friday October 08, 2010 @06:13PM (#1773636)
what did you put as answer for the first level?
Re:Can you solve it? The Greplin programming challenge by droz on Friday October 08, 2010 @03:30PM (#1773011)
too easy. about 30mins and 100 lines of C#.
Re:Can you solve it? The Greplin programming challenge by Muzza on Friday October 08, 2010 @03:10PM (#1772939)
There are only 31 known Fibonacci primes (plus a handful probable primes)...
Re:Can you solve it? The Greplin programming challenge by hackermom on Saturday October 09, 2010 @06:29PM (#1776061)
Problem 1: 2 minutes for 5 lines of PHP code. Problem 2: 1 minute of Google and Google (why reinvent the wheel?). Problem 3: half a minute of brainwork, 15 minutes worth of tedious PHP snippet.

I got the impression that this particular test was not a good one for finding apt programmers. The questions and the solutions were just so very "off".

Re:Can you solve it? The Greplin programming challenge by ody on Friday October 08, 2010 @07:37PM (#1773862)
suckers ... no really, you are.