Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://487058]
[Discipulus]: it seems a legitimate one.. grin ..

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (7)
As of 2018-05-22 12:20 GMT
Find Nodes?
    Voting Booth?