gmane.comp.lang.perl.qotw.discuss

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

Shlomi Fish — 2010-02-22T15:31:32

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 unab

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

Peter Scott — 2009-10-13T04:40:37

My last submission was more for clarity than efficiency.  This one is 
a bit more efficient, in generating the list for one side in advance, 
but a bit less clear:

use strict;
use warnings;

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

my < at >left;
iter( $left,  sub { push < at >left, shift                                     } );
iter( $right, sub { eval == eval $_[0] and print "$_ = $_[0]\n" for < at >left } );

sub iter
{
   my ($side, $cb) = < at >_;

   my $count = length($side) - 1;
   for my $num ( 0 .. 2**$count - 1)
   {
     my $i = $count;
     (my $side = $side) =~ s/(.)(?=.)/$1 . ($num & 1 << --$i ? '+' : '')/ge;
     $cb->( $side );
   }
}

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

Peter Scott — 2009-10-12T19:54:23

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;
   }
}

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

Josh Narins — 2009-10-08T00:04:21

http://www.flowersofpeace.com/telephone_code.html

Since I, by default, use +, - * and / I also make sure not to divide by zero :)



On Wed, Oct 7, 2009 at 1:50 PM, Jeff Yoak <jeff-orzAD85Mt8U< at >public.gmane.org> wrote:

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

Jeff Yoak — 2009-10-07T17:50:52

Somehow I missed the original statement of the problem, but these  
solutions, perhaps with a slight mod in some cases, could be used to  
solve the current problem at http://mathfactor.uark.edu/ .  As the  
poster of that particular problem, I can say that anyone who wanted to  
share code with a solution would be welcome.

Cheers,
Jeff

On Oct 7, 2009, at 9:55 AM, Ronald J Kimball wrote:

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

Ronald J Kimball — 2009-10-07T16:55:00

Yay, the list is back.  Here's my solution.  I generate the plusified
expressions iteratively by doing repeated increments, treating the
expression itself as a binary string with '+' and '' representing 1 and 0:

  s/(.*\d)(\d.*)/my $x = $2; $x =~ tr!+!!d; "$1+$x"/e

To be more efficient, I don't store both sets of results.  First, I
calculate and store the results for the second expression only.  Then, I
generate results one at a time for the first expression, print any matches
immediately, and throw away the result.  This gives the correct order of
output without any sorting.

#!perl

use strict;
use warnings;

< at >ARGV == 2
  or die usage();

foreach (< at >ARGV) {
  /^\d+\z/
    or die usage();
}

my %p2;

my ($p1, $p2) = < at >ARGV;

do {
  push < at >{ $p2{do_eval($p2)} }, $p2;
} while ($p2 = next_plusify($p2));

do {
  if (my $match = $p2{do_eval($p1)}) {
    print "$p1 = $_\n" for < at >$match;
  }
} while ($p1 = next_plusify($p1));

sub next_plusify {
  my ($exp) = < at >_;
  $exp =~ s/(.*\d)(\d.*)/my $x = $2; $x =~ tr!+!!d; "

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

Shlomi Fish — 2009-10-07T13:20:15

I have a few solutions. The first one I wrote in Perl using Moose and a lot of 
stuff that will be suitable for C++. I later translated it to C++ because the 
kid who asked me for a solution doesn't know Perl. Then I wrote a different 
Perl implementation without using Moose, but with using eval. The first Perl 
solution was kinda slow , the C++ version was very fast, and the third Perl 
implementation was somewhere in between.

Moose version:

[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[
#!/usr/bin/perl 

package State::Side;

use strict;
use warnings;

use Moose;

has 'last_digits' => (is => "rw", isa => "Str");
has 'last_sum' => (is => "rw", isa => "Int");
has 'next_digits' => (is => "rw", isa => "Str");
has 'terminator_cb' => (is => "rw", isa => "CodeRef");
has 'formula' => (is => "rw", isa => "Str");

sub recurse
{
    my $self = shift;

    my $num_left = length($self->next_digits()) ;

    if ($num_left == 0)
    {
        $self->last_sum(
            $self->last_sum() + $self->last_digits()
        );

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

Josh Narins — 2009-10-07T10:37:29

I'll put the code up online after I get home from work today at
http://www.flowersofpeace.com/telephone_code.html

On Wed, Oct 7, 2009 at 6:36 AM, Josh Narins <josh.narins-Re5JQEeQqe8AvxtiuMwx3w< at >public.gmane.org> wrote:

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

Josh Narins — 2009-10-07T10:36:37

I set up my solution about a half year before the contest was
announced, although I would prefer if no one requests any answers to
future contests at this time.

Mine started when I noticed that my telephone number was a true
equation. Someone mentioned at work that the current calendar day was
a perfect square, or something quite like that, I mentioned my
telephone number, and someone asked for a programmatic solution.

My solution allows up to eight operators, +, -, *, /, **, ^, & and I,
but as a party trick, the first four are the default. It's also a
recursive solution around the number of digits, so you can blow out
your memory if you could think of some more operators.

Like the previous answer, I use eval. I also skip all numbers that
begin with 0 but basically because this is designed as a party trick,
and some people simply don't appreciate being told 1+01=2. I also
eliminate 0.

I also didn't care where the = was, so I try it at all meaningful locations.

Since it is recursive, I currently limit it

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

Chris Charley — 2009-10-07T02:31:03

Hello Shlomi,

I have heard that 'a thousand monkeys at a thousand
typewriters will eventually type out the entire works
of Shakespeare'. So, I put my best team of monkeys
on this problem and it resulted in the program below.  :-)

This was a good exercise. My solution saw that
the '+' signs distributed between the numbers
as a power set.

For example, for the number 7637, I first
modified it to be '7 6 3 7', (with 3 spaces as placeholders).
The power set distributing '+'s for this number would be:
000
001
010
011
100
101
110
111

There are 8, (2**3), ways the plus sign could be
distributed. To generate the 8 expressions, I
tested the binary representation (above). If the bit was 1,
I replaced the space with a '+' and if not, removed
the space (placeholder). The results are:
7637
763+7
76+37
76+3+7
7+637
7+63+7
7+6+37
7+6+3+7

Then, I used string 'eval' to get the sum and placed
it and the expression in the %sums hash.

 $sums{$number}{$sum}{$expr} = ();

After calculating all the sums, I found a match If
a

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

Shlomi Fish — 2009-08-11T14:55:06

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.

4. The = sign does have