Challenging Programming Exercises Published Weekly
programmingpraxis.com
programmingpraxis.com
"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."
Is there a site that gives you common/difficult programming "in the large" problems?
I've thought about making this into a series.
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']
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] );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).
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']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.
Some suggestions:
* The font needs to be larger
* The color scheme could use a little more contrast
* Pasting source code needs to be easier