HN Explorer

19 comments

[ 4.7 ms ] story [ 47.7 ms ] thread
jschulenklopper
Obligatory link to a nice and long-running initiative: Project Euler: 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."

VMG
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
Agree with OP on all three points. Please look into this.
eddington
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
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
That's quite pretty Perl. You've lessened my prejudice against the language by writing code that can be read.
finnh
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).

notaddicted
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']