Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: a couple of rounds of golf for the weekend

by barrachois (Pilgrim)
on Aug 26, 2005 at 23:02 UTC ( #487058=note: print w/ replies, xml ) Need Help??


in reply to a couple of rounds of golf for the weekend

I played around with part 1. An interesting problem, but it didn't feel like a a good one for golf.

"the intention is that entries should calculate the terms rather than simply embed them", you say, but when I looked at your part 1 code, I found plenty of embedded data. Disappointing.

Below is 14 lines of code that generates the desired 288 lines, starting only with the constraint definitions and "my $N=4;". It would, I believe, work as well for N=9 - if you were willing to wait. :)

The algorithm uses regular expressions and recursion both to generate the permutations and recognize the sudoku solutions. I put together a different, iterative version as well; that one didn't squash quite as small. If there's any interest I could post more readable versions of each.

#!/usr/bin/perl use warnings; use strict; my $N=4;my $sqN=sqrt($N);my @d=1..$N;my @nsq=0..$N**2-1;my $o2n=join(' +',@d); my (@perm,@sud,$p_regex,$s_regex,%cnstrnts,@extra,$i,$j,$p); sub ro {int(shift()/$N)} sub col {shift()%$N} sub yy {int(int(shift()/$N)/$sqN)} sub xx {int((shift()%$N)/$sqN)} for $i (0..$N-1){$p_regex.='(?!'.join('|',map {'\\'.$_} 1..$i).')' if +$i>0; $p_regex.='(\\d)'} $p_regex = qr($p_regex)o; for $i (@nsq){ my @cnflct +s; for $j (@nsq){next unless $i!=$j && (ro($i)==ro($j)||col($i)==col($j)| +| xx($i)==xx($j)&&yy($i)==yy($j)); push(@cnflcts, 1+$j)} $cnstrnts{$i}=\ +@cnflcts} for $i (@nsq){$s_regex.='(?!'.join('|',map{'\\'.$_}@{$cnstrnts{$i}}).' +)(\\d)'} $s_regex=qr($s_regex)x; our ($br,$max,$regex,@ans)=(\@d,$N,$p_regex); sub recur {my $st = shift; if (length($st)>=$max) {push(@ans,$st) if $st=~$regex} else {recur($st.$_) for @$br}} recur(''); @perm=@ans; ($br,$max,$regex,@ans)=(\@perm,$N**2,$s_regex); recur($o2n); @sud=@ans +; my @as; for $p (@perm){eval("tr/$o2n/$p/"),push(@as,$_) for @sud} print "$_\n" + for @as; # Generate strings representing sudoku puzzle solutions. # This could certainly be made shorter, but at about 1000 characters # it's already illegible enough for me. # N=4 : iterations = (N!)**(N-1) = 24**3 = 13824 ; runs in < 1 second +. # N=9 : (9!)**8 = 362880**8 = 3e44, so a million/sec would take 1e31 +years... print "\n Number of sudokus found is " . scalar(@as) . ".\n\n"; # N=4 +gives 288


Comment on Re: a couple of rounds of golf for the weekend
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://487058]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (7)
As of 2015-07-28 08:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (254 votes), past polls