4 ms·

Challenging Programming Exercises Published Weekly

109 points by krat0sprakhar 14y ago

new_test 14y ago
Another similar excellent resource: http://www.reddit.com/r/dailyprogrammer/ http://www.reddit.com/r/dailyprogrammer/
- jbranchaud 14y ago
  Any idea where so many daily programming problems come from?
  - new_test 14y ago
    http://www.reddit.com/r/dailyprogrammer_ideas http://www.reddit.com/r/dailyprogrammer_ideas
gryphonic 14y ago
For more math oriented challenges (more project euler like), check out the monthly IBM 'I ponder this'. These are usually quite challenging, but the problems are interesting and solutions are posted at the end of the month. http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/pages/index.html http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/pages/in...
jschulenklopper 14y ago
Obligatory link to a nice and long-running initiative: Project Euler: http://projecteuler.net/ http://projecteuler.net/. "Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."
- chii 14y ago
  its interesting that all of these are programming "in the small" problems. Is there a site that gives you common/difficult programming "in the large" problems?
  - sillysaurus 14y ago
    Here are several "real-world" projects in order of increasing difficulty: http://shawnpresser.blogspot.com/2010/10/how-to-become-game-programmer.html http://shawnpresser.blogspot.com/2010/10/how-to-become-game-... I've thought about making this into a series.
VMG 14y ago
Looks interesting. Some suggestions: * The font needs to be larger * The color scheme could use a little more contrast * Pasting source code needs to be easier
- Surio 14y ago
  Agree with OP on all three points. Please look into this.
bduerst 14y ago
This is awesome.
eddington 14y ago
Complete solution to today's problem in one line of python def gen(univ, n=5): return univ if n == 1 else [x+y for y in gen(univ,n-1) for x in univ if all([(x+y)[start:start+upto] != (x+y)[start+upto:start+upto*2] for start in range(len(x+y)) for upto in range(1,(len(x+y)-start+2)/2)])] ... god that looks ugly. Call it with >>> gen(["1", "2", "3"], 5) ['13121', '23121', '21321', '31321', '12321', '12131', '32131', '21231', '31231', '13231', '13212', '23212', '21312', '12312', '32312', '12132', '32132', '23132', '21232', '31232', '31213', '13213', '23213', '12313', '32313', '32123', '13123', '23123', '21323', '31323']
- peteretep 14y ago
  And in some rather nicer Perl: sub solutions { my ( $target_length, $alphabet, $head ) = @_; $head //= ''; # Base Case our head is the right length return $head if (length $head) == $target_length; # General Case return map { generate( $target_length, $alphabet, $_ ) } grep { ! /(.{2})\1/ } map { $head . $_ } @$alphabet; } eg: my @solutions = solutions( 5, [1..3] );
  - JasonFruit 14y ago
    That's quite pretty Perl. You've lessened my prejudice against the language by writing code that can be read.
  - finnh 14y ago
    Is that accurate? This looks like it only checks for sequential runs of two characters apiece. The challenge calls for sequences "such that no two immediately adjacent subsequences are equal". This, to me, implies subsequences of any length > 1. For a $target_length of 5, your solution is correct as 2 is the longest repeatable subsequence. Easy fix, of course: grep { ! /(.{2})\1/ } becomes grep { ! /(.{2,})\1/ } I wonder if it would help performance to say: grep { $max = length()/2; $max < 2 || ! /(.{2,$max})\1/ } Or if the regexp engine manages to do that automatically. [UPDATE: it is slower to provide your own max length. the perl regexp engine is badass. repeating timings on my mac pro with a target_length of 12 show the plain {2,} version is 15% quicker]. (also, you've a minor typo as you recurse into "generate" instead of "solutions", I assume b/c you renamed the function at the very end to make the eg: code scan better).
jbranchaud 14y ago
Great resource, I just added this to my list of programming puzzle resources -- http://joshbranchaud.wordpress.com/2011/07/09/my-somewhat-comprehensive-list-of-programming-problems/ http://joshbranchaud.wordpress.com/2011/07/09/my-somewhat-co...
- jcl 14y ago
  You might also want to check out SPOJ, an enormous collection of problems from programming contests, with an online solution evaluator: http://www.spoj.com/problems/classical/ http://www.spoj.com/problems/classical/
  - jbranchaud 14y ago
    Thanks for the pointer, that is jam packed!
sillysaurus 14y ago
I used Mathematica to give the solution to Wirth's Problem (http://programmingpraxis.com/2012/12/07/wirth-problem-15-12/ http://programmingpraxis.com/2012/12/07/wirth-problem-15-12/). Screenshot: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.png https://dl.dropbox.com/u/315/math/problems/wirth/wirth.png Output: https://dl.dropbox.com/u/315/math/problems/wirth/wirth_output.png https://dl.dropbox.com/u/315/math/problems/wirth/wirth_outpu... Notebook: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.nb https://dl.dropbox.com/u/315/math/problems/wirth/wirth.nb Mathematica code turns out to be surprisingly readable.

109 points by krat0sprakhar 14y ago

new_test 14y ago

Another similar excellent resource: http://www.reddit.com/r/dailyprogrammer/ http://www.reddit.com/r/dailyprogrammer/

jbranchaud 14y ago
Any idea where so many daily programming problems come from?
- new_test 14y ago
  http://www.reddit.com/r/dailyprogrammer_ideas http://www.reddit.com/r/dailyprogrammer_ideas

gryphonic 14y ago

For more math oriented challenges (more project euler like), check out the monthly IBM 'I ponder this'. These are usually quite challenging, but the problems are interesting and solutions are posted at the end of the month. http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/pages/index.html http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/pages/in...

jschulenklopper 14y ago

Obligatory link to a nice and long-running initiative: Project Euler: http://projecteuler.net/ http://projecteuler.net/. "Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."

chii 14y ago
its interesting that all of these are programming "in the small" problems. Is there a site that gives you common/difficult programming "in the large" problems?
- sillysaurus 14y ago
  Here are several "real-world" projects in order of increasing difficulty: http://shawnpresser.blogspot.com/2010/10/how-to-become-game-programmer.html http://shawnpresser.blogspot.com/2010/10/how-to-become-game-... I've thought about making this into a series.

VMG 14y ago

Looks interesting. Some suggestions: * The font needs to be larger * The color scheme could use a little more contrast * Pasting source code needs to be easier

Surio 14y ago
Agree with OP on all three points. Please look into this.

bduerst 14y ago

This is awesome.

eddington 14y ago

Complete solution to today's problem in one line of python def gen(univ, n=5): return univ if n == 1 else [x+y for y in gen(univ,n-1) for x in univ if all([(x+y)[start:start+upto] != (x+y)[start+upto:start+upto*2] for start in range(len(x+y)) for upto in range(1,(len(x+y)-start+2)/2)])] ... god that looks ugly. Call it with >>> gen(["1", "2", "3"], 5) ['13121', '23121', '21321', '31321', '12321', '12131', '32131', '21231', '31231', '13231', '13212', '23212', '21312', '12312', '32312', '12132', '32132', '23132', '21232', '31232', '31213', '13213', '23213', '12313', '32313', '32123', '13123', '23123', '21323', '31323']

peteretep 14y ago
And in some rather nicer Perl: sub solutions { my ( $target_length, $alphabet, $head ) = @_; $head //= ''; # Base Case our head is the right length return $head if (length $head) == $target_length; # General Case return map { generate( $target_length, $alphabet, $_ ) } grep { ! /(.{2})\1/ } map { $head . $_ } @$alphabet; } eg: my @solutions = solutions( 5, [1..3] );
- JasonFruit 14y ago
  That's quite pretty Perl. You've lessened my prejudice against the language by writing code that can be read.
- finnh 14y ago
  Is that accurate? This looks like it only checks for sequential runs of two characters apiece. The challenge calls for sequences "such that no two immediately adjacent subsequences are equal". This, to me, implies subsequences of any length > 1. For a $target_length of 5, your solution is correct as 2 is the longest repeatable subsequence. Easy fix, of course: grep { ! /(.{2})\1/ } becomes grep { ! /(.{2,})\1/ } I wonder if it would help performance to say: grep { $max = length()/2; $max < 2 || ! /(.{2,$max})\1/ } Or if the regexp engine manages to do that automatically. [UPDATE: it is slower to provide your own max length. the perl regexp engine is badass. repeating timings on my mac pro with a target_length of 12 show the plain {2,} version is 15% quicker]. (also, you've a minor typo as you recurse into "generate" instead of "solutions", I assume b/c you renamed the function at the very end to make the eg: code scan better).

jbranchaud 14y ago

Great resource, I just added this to my list of programming puzzle resources -- http://joshbranchaud.wordpress.com/2011/07/09/my-somewhat-comprehensive-list-of-programming-problems/ http://joshbranchaud.wordpress.com/2011/07/09/my-somewhat-co...

jcl 14y ago
You might also want to check out SPOJ, an enormous collection of problems from programming contests, with an online solution evaluator: http://www.spoj.com/problems/classical/ http://www.spoj.com/problems/classical/
- jbranchaud 14y ago
  Thanks for the pointer, that is jam packed!

sillysaurus 14y ago

I used Mathematica to give the solution to Wirth's Problem (http://programmingpraxis.com/2012/12/07/wirth-problem-15-12/ http://programmingpraxis.com/2012/12/07/wirth-problem-15-12/). Screenshot: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.png https://dl.dropbox.com/u/315/math/problems/wirth/wirth.png Output: https://dl.dropbox.com/u/315/math/problems/wirth/wirth_output.png https://dl.dropbox.com/u/315/math/problems/wirth/wirth_outpu... Notebook: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.nb https://dl.dropbox.com/u/315/math/problems/wirth/wirth.nb Mathematica code turns out to be surprisingly readable.