headers
Shlomi Fish | 22 Feb 2010 16:31
Picon
Gravatar

Perl QOTW #2010-02-22 - Freecell Scans with Short Solutions

IMPORTANT: Please do not post solutions, hints, or other spoilers
until at least 60 hours after the date of this message.  Thanks.

Requests for clarifications and other discussion would be OK.

---------------

Today I'm borrowing the collective wisdom of the Perl Quiz-of-the-Whatever
forum for an algorithmic task I need to accomplish for my own project.
The project in question is Freecell Solver ( http://fc-solve.berlios.de/ ),
which is an automated solver for http://en.wikipedia.org/wiki/FreeCell and 
several other types of card solitaire. 

fc-solve starts from the initial layout of the solitaire game and recurses
into more and more positions, which are counted by the solver's iterations,
until it reaches the final, solved state where all cards were moved to the
foundations.

After a certain number of iterations (which are roughly indicative of 
how long it took it to run), it yields a solution of a certain length ,which 
is desired to be as short as possible. Note that it may also report that it
is unable to solve the board (after going over all the derived positions) or 
that it could not find a solution within the quota of iterations that have
been allocated for it. 

Now, fc-solve has many different atomic scans, that when run alone, each
yields different solutions with different iteration counts and lengths.

In this Subversion directory, I have collected the iterations counts and the
solutions lengths of a sample of boards - the first 32,000 games in Microsoft
(Continue reading)

Permalink | Reply | 0 comments |
headers
Peter Scott | 12 Oct 2009 21:54

Re: Perl 'Medium' Quiz-of-the-Whatever for 2009-08-11 : Plusified Equations

Here's my solution, which also uses binary number counting to decide 
where to put the + signs.  I have been unable to remove the duplicated 
code without making it much less clear and no shorter.

use strict;
use warnings;

my ($left, $right) =  <at> ARGV;

my ($count_left, $count_right) = map { length() - 1 } ($left, $right);

for my $left_num ( 0 .. 2**$count_left - 1)
{
   my $left = $left;
   my $i = $count_left;
   $left =~ s/(.)(?=.)/$1 . ($left_num & 1 << --$i ? '+' : '')/ge;

   for my $right_num ( 0 .. 2**$count_right - 1 )
   {
     my $right = $right;
     my $i = $count_right;
     $right =~ s/(.)(?=.)/$1 . ($right_num & 1 << --$i ? '+' : '')/ge;
     print "$left == $right\n" if eval $left == eval $right;
   }
}
--

-- 
Peter Scott
Pacific Systems Design Technologies
http://www.perldebugged.com/
http://www.perlmedic.com/
(Continue reading)

Permalink | Reply | 0 comments |
headers
Shlomi Fish | 11 Aug 2009 16:55
Picon
Gravatar

Perl 'Medium' Quiz-of-the-Whatever for 2009-08-11 : Plusified Equations

IMPORTANT: Please do not post solutions, hints, or other spoilers
until at least 60 hours after the date of this message.  Thanks.

---------------

We are given two positive integers $L and $R we need to find Plusified 
expressions of both for which Eval($E_L) == Eval($E_R). So what is a plusified 
expression? It is an expression where we can choose whether to add a single 
"+" between any consecutive digit. So for example the number 123 has the 
following plusified expression:

* 123
* 12+3
* 1+23
* 1+2+3

So if we are given 123 and 96 we can form the following plusified equation:

* 12+3 == 9+6

Your mission is to write a Perl program (or an equivalent program in any 
programming language) that will find all solutions to the plusified equation 
of two numbers given as input. To normalise the output we'll rule that:

1. The equations should be given one at each line.

2. They will be sorted so consecutive digits will take precedence over "+"'s.

3. A "+" has no surrounding spaces.
(Continue reading)

Permalink | Reply | 8 comments |
headers
Shlomi Fish | 27 Mar 2008 23:38
Picon
Gravatar

[QUIZ] Perl 'Hard' Quiz of the Whatever #2008-03-28 - Solving Kakuro

IMPORTANT: Please do not post solutions, hints, or other spoilers
until at least 60 hours after the date of this message.  Thanks.

Kakuro (a.k.a Cross-sums) is a kind of puzzle game:

http://en.wikipedia.org/wiki/Kakuro

In it, one fills in squares in a crossword-like grid that sum to their sums. 
One can fill in the digits from 1 to 9, and no digit can be repeated twice.

Your object is that given a Kakuro board in a text format described below, 
then output the final solution.

You can find some sample layouts from kakuro.com here: 
http://www.shlomifish.org/Files/files/text/kakuro.com-layouts/ 

and there's a new daily puzzle everyday there. (Requires Flash) There are also 
some more layouts googleable or on the wikipedia page.

The layout has the following format:

1. It consists of $Height lines.

2. Each line has $Width squares. Whitespace inside each line is ignored.

3. Each square starts with [ and ends with ]. 

4. A square that contains a \ is a blocked square (i.e: a square that cannot 
have any digit). If a number appears to the left of the \ it is the sum of 
the digits below the square. If a number appears to the right of the \ it is
(Continue reading)

Permalink | Reply | 7 comments |
headers
Greg Bacon | 6 Mar 2008 15:44
X-Face

Re: [QUIZ] Perl 'Medium' Quiz of the Whatever #2008-02-28 - Kakuro Digit Sums

In Haskell, FWIW:

    get_digits_sum _ 0 = []
    get_digits_sum 0 _ = []
    get_digits_sum goal n = find goal n [1..9]
      where find _ _ [] = []
            find goal n (d:ds)
              | n == 1 && d == goal = [[d]]
              | otherwise = with ++ find goal n ds
                  where with = map (d:) $ find (goal - d) (n - 1) ds

Greg
Permalink | Reply | 0 comments |
headers
Greg Bacon | 25 Mar 2005 17:19
X-Face

[SPOILER] Perl 'Hard' Quiz of the Week #2005-03-22

I don't know whether Pr. Fish intended his state labels (i.e., their
ret values) to be a hint, but they suggested each state encoding the
remainder of the input so far divided by $N.  That worked!  At first,
I was computing the transition function with a depth-first search,
so to improve performance, I went back and changed the code to use
breadth-first search.

Then I went back and read the spec and saw that the input arrived
LSB-first.  I tried the same approach on paper but got stuck when
I realized all powers of two would land in the same state, for
instance.  I even tried to think of a way to use the pumping lemma
to show that the reversed language isn't regular.

Somehow I noticed that reversing the directions of the transitions
seemed to accept the reversed language but lost the property of
tracking remainders.

Testing seems to show this to be a valid approach, and I wish I knew
why.  I need to look through the Linz book to see if this is a property
of regular languages.

For kicks, I wrote a class, in ModMachine.pm below, that converts the
transition function to a regular expression.  It's really fast for
small $N but starts to bog down when $N reaches thirty or forty.

Fun quiz!  (Then again, I'm a graph theory nerd.)

Enjoy,
Greg
(Continue reading)

Permalink | Reply | 2 comments |
headers
Greg Bacon | 23 Mar 2005 23:28
X-Face

Re: [QUIZ] Perl 'Hard' Quiz of the Week #2005-03-22

In message <200503221754.23325.shlomif@...>,
    Shlomi Fish writes:

: [...]
: Your mission is to write a function - gen_is_divisable_fsm($N) - that
: when given a non-even number $N will generate a state machine to
: determine if a number represented by a sequence of binary digits
: (starting from the least significant bit) is evenly divisable by $N.

Should "least significant" be "most significant," or will the input
bits really arrive in reverse order?  I didn't notice this sentence
until after I'd already completed an MSB-first implementation.

It's interesting that the resulting automata are isomorphic to one
another.  That they do makes sense after you've seen it, but it wasn't
an initial expectation.

Greg
Permalink | Reply | 3 comments |
headers
michael | 6 Mar 2008 11:05
Picon

Re: [QUIZ] Perl 'Medium' Quiz of the Whatever #2008-02-28 - Kakuro Digit Sums

Shlomi Fish writes:
>IMPORTANT: Please do not post solutions, hints, or other spoilers
>until at least 60 hours after the date of this message.  Thanks.
>
>Kakuro (a.k.a Cross-sums) is a kind of puzzle game:

Here's my solution.  It, too, is recursive, but unlike M. Fish's, I've
used a secondary accumulator parameter.

    -- michael.

--
#!perl
use strict;
sub get_digits_sum {
    my ($sum, $left, $soln,  <at> ns) =  <at> _;
    return 
	if $sum == 0;
    return [get_digits_sum($sum, $left, [], 1..9)] 
	if !defined $soln;
    return (grep {$sum==$_}  <at> ns) ? [ <at> $soln, $sum] : () 
	if $left == 1;
    my  <at> rv;
    for my $n ( <at> ns) {
	return  <at> rv 
	    if $n > $sum; # rest won't work either
	push  <at> rv, get_digits_sum($sum-$n, $left-1, [ <at> $soln, $n], ($n+1)..9);
    }
    return  <at> rv;
}
(Continue reading)

Permalink | Reply | 0 comments |
headers
Premysl Anydot Hruby | 3 Mar 2008 18:25
Picon
Gravatar

Re: [QUIZ] Perl 'Medium' Quiz of the Whatever #2008-02-28 - Kakuro Digit Sums

On (28/02/08 21:40), Shlomi Fish wrote:
> To: perl-qotw-discuss@...
> From: Shlomi Fish <shlomif@...>
> Subject: [QUIZ] Perl 'Medium' Quiz of the Whatever #2008-02-28 - Kakuro Digit
> 	Sums
> 
> IMPORTANT: Please do not post solutions, hints, or other spoilers
> until at least 60 hours after the date of this message.  Thanks.
> 
> Kakuro (a.k.a Cross-sums) is a kind of puzzle game:
> 
> http://en.wikipedia.org/wiki/Kakuro
> 
> In it, one fills in squares in a crossword-like grid that sum to their sums. 
> One can fill in the digits from 1 to 9, and no digit can be repeated twice.
> 
> Your object is to find all posssible combinations for a given sum and a given 
> number of squares. You'll write a function get_digits_sum($sum, $num_places), 
> that will return an array reference of array references, each one containing 
> an possible solution (in ascending order). The solutions themselves should be 
> in ascending order too, starting from the lowest numbers. Here are some 
> examples:
> 
> get_digits_sum(7, 3) => returns [[1,2,4]].
> 
> get_digits_sum(7, 2) => returns [[1,6],[2,5],[3,4]];
> 
> The daily puzzle in http://www.kakuro.com/index.php#daily (requires Flash) has 
> a feature to display the permutations in a similar manner.
>
(Continue reading)

Permalink | Reply | 1 comment |
headers
Shlomi Fish | 3 Mar 2008 16:04
Picon
Gravatar

Re: [QUIZ] Perl 'Medium' Quiz of the Whatever #2008-02-28 - Kakuro Digit Sums

On Thursday 28 February 2008, Shlomi Fish wrote:
> IMPORTANT: Please do not post solutions, hints, or other spoilers
> until at least 60 hours after the date of this message.  Thanks.
>
> Kakuro (a.k.a Cross-sums) is a kind of puzzle game:
>
> http://en.wikipedia.org/wiki/Kakuro
>
> In it, one fills in squares in a crossword-like grid that sum to their
> sums. One can fill in the digits from 1 to 9, and no digit can be repeated
> twice.
>
> Your object is to find all posssible combinations for a given sum and a
> given number of squares. You'll write a function get_digits_sum($sum,
> $num_places), that will return an array reference of array references, each
> one containing an possible solution (in ascending order). The solutions
> themselves should be in ascending order too, starting from the lowest
> numbers. Here are some examples:
>
> get_digits_sum(7, 3) => returns [[1,2,4]].
>
> get_digits_sum(7, 2) => returns [[1,6],[2,5],[3,4]];
>
> The daily puzzle in http://www.kakuro.com/index.php#daily (requires Flash)
> has a feature to display the permutations in a similar manner.
>
> Regards,
>
> 	Shlomi Fish
>
(Continue reading)

Permalink | Reply | 0 comments |
headers
Shlomi Fish | 28 Dec 2007 12:31
Picon
Gravatar

[QUIZ] Perl 'Hard' Quiz of the Whatever #2008-12-28 - Symmetric Sokoban

IMPORTANT: Please do not post solutions, hints, or other spoilers
until at least 60 hours after the date of this message.  Thanks.

I was told the "What does this code do?" quizzes were not as good as a new 
programming task, so here's a more traditional QOTW that I came up with. In 
this quiz you'll try to solve the following Sokoban ( 
http://en.wikipedia.org/wiki/Sokoban ) puzzle using Perl:

{{{{{{{{{{{{{{
  ####
  #  #
  #  ####
###$.$  #
#  . <at> .  #
#  $.$###
####  #
   #  #
   ####
}}}}}}}}}}}}}}

If you're not familiar with the notation, then "#" are walls, "$" are the 
initial positions of the boxes to be moved, "." are the destinations and " <at> " 
is the initial position of the player.

This level is the Microban level No. 142 in the levels collection of KSokoban. 
You may want to solve it yourself before using Perl to do so. You can load it 
into a Sokoban clone by saving it into a file and then using the "load" 
command.

Good luck and happy new year!
(Continue reading)

Permalink | Reply | 1 comment |

Gmane