Challenging Programming Exercises Published Weekly(programmingpraxis.com)
programmingpraxis.com
Challenging Programming Exercises Published Weekly
http://programmingpraxis.com
19 comments
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?
Is there a site that gives you common/difficult programming "in the large" problems?
Here are several "real-world" projects in order of increasing difficulty: http://shawnpresser.blogspot.com/2010/10/how-to-become-game-...
I've thought about making this into a series.
I've thought about making this into a series.
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']
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']
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;
}
my @solutions = solutions( 5, [1..3] );That's quite pretty Perl. You've lessened my prejudice against the language by writing code that can be read.
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:
[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).
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/ }
grep { ! /(.{2,})\1/ }
grep { $max = length()/2; $max < 2 || ! /(.{2,$max})\1/ }
[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).
Here is an ugly iterative solution, in one lambda:
from itertools import product
f = lambda n: [
s for s in
map(''.join, product("abc", repeat=n))
if not any(a==b
for a,b in
[(s[a:b], s[b:c])
for a,b,c in
[(i,i+w,i+2*w)
for w in range(1,len(s)/2+1)
for i in range(len(s)-2*w+1)]])]
>>> f(5)
['abaca', 'abacb', 'abcab', 'abcac', 'abcba', 'acaba',
'acabc', 'acbab', 'acbac', 'acbca', 'babca', 'babcb',
'bacab', 'bacba', 'bacbc', 'bcaba', 'bcabc', 'bcacb',
'bcbab', 'bcbac', 'cabac', 'cabca', 'cabcb', 'cacba',
'cacbc', 'cbabc', 'cbaca', 'cbacb', 'cbcab', 'cbcac']Great resource, I just added this to my list of programming puzzle resources -- http://joshbranchaud.wordpress.com/2011/07/09/my-somewhat-co...
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/
Thanks for the pointer, that is jam packed!
Another similar excellent resource: http://www.reddit.com/r/dailyprogrammer/
Any idea where so many daily programming problems come from?
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/in...
I used Mathematica to give the solution to Wirth's Problem (http://programmingpraxis.com/2012/12/07/wirth-problem-15-12/).
Screenshot: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.png
Output: https://dl.dropbox.com/u/315/math/problems/wirth/wirth_outpu...
Notebook: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.nb
Mathematica code turns out to be surprisingly readable.
Screenshot: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.png
Output: https://dl.dropbox.com/u/315/math/problems/wirth/wirth_outpu...
Notebook: https://dl.dropbox.com/u/315/math/problems/wirth/wirth.nb
Mathematica code turns out to be surprisingly readable.
This is awesome.
"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."