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

On Tuesday 11 August 2009 17:55:06 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.
>
> ---------------
>
> 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 a preceding and following space.
>
> As an example:
>
> {{{{{{{{{{{{{
> $ ./plusified-equation 12341234 1010
> 1+23+41+2+34 = 101+0
> 1+2+3+4+1+2+3+4 = 10+10
> }}}}}}}}}}}}}
>

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()
        );
        $self->last_digits("");
       
        return $self->terminator_cb()->(
            $self
        );
    }

    my $next_digit = substr($self->next_digits(), 0, 1);
    # Handle the not plus
    blessed($self)->new(
        last_sum => $self->last_sum(),
        last_digits => 
            ($self->last_digits() . $next_digit),
        next_digits => substr($self->next_digits(), 1),
        terminator_cb => $self->terminator_cb(),
        formula => $self->formula() . $next_digit,
    )->recurse();

    # Handle the with plus.

    # No leading plus.
    if ($self->last_digits() ne "")
    {
        blessed($self)->new(
            last_sum => $self->last_sum()+$self->last_digits(),
            last_digits => $next_digit,
            next_digits => substr($self->next_digits(), 1),
            terminator_cb => $self->terminator_cb(),
            formula => $self->formula() . "+" . $next_digit,
        )->recurse();
    }

    return;
}

package main;

sub solve_for_right
{
    my ($left_state, $right) = @_;

    State::Side->new(
        last_sum => 0,
        last_digits => "",
        next_digits => $right,
        terminator_cb => sub { 

            my ($right_state) = @_;

            if ($left_state->last_sum() == $right_state->last_sum())
            {
                print $left_state->formula(), " = ", 
                      $right_state->formula(), "\n"
                      ;
            }

            return;
        },
        formula => "",
    )->recurse();

    return;
}

sub solve_for
{
    my ($left, $right) = @_;

    State::Side->new(
        last_sum => 0,
        last_digits => "",
        next_digits => $left,
        terminator_cb => sub { 
            my ($left_state) = @_;

            solve_for_right($left_state, $right);
            return;
        },
        formula => "",
    )->recurse();

    return;
}

my ($l, $r) = @ARGV;
solve_for($l, $r);


]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

C++ version:
------------

[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[

#include <list>
#include <iostream>
#include <cstdlib>


namespace PlusEquation
{
    using namespace std;

    class StateSide;

    typedef list<char> Str;
    typedef void (*terminator_cb_t)(StateSide * self, void * context);

    int int_val(Str & s)
    {
        Str::iterator i = s.begin();
        int ret = 0;
        while (i != s.end())
        {
            ret = ret*10 + (*i-'0');
            i++;
        }
        return ret;
    }

    Str Str_val(int val)
    {
        Str ret;

        while (val)
        {
            ret.push_front('0'+val%10);
            val /= 10;
        }

        return ret;
    }

    ostream& operator<<(ostream& cout, Str & s)
    {
        Str::iterator i = s.begin();

        while (i != s.end())
        {
            cout << (*i);
            i++;
        }

        return cout;
    }

    class StateSide
    {
        protected:
        Str last_digits;
        int last_sum;
        Str next_digits;
        Str formula;
        terminator_cb_t terminator_cb;
        void * context;
        
        public:
        
        StateSide(
                int new_last_sum,
                Str & new_last_digits,
                Str & new_next_digits,
                terminator_cb_t new_terminator_cb,
                void * new_context,
                Str & new_formula
                )
            : last_sum(new_last_sum), context(new_context), 
              terminator_cb(new_terminator_cb)
        {
            last_digits = new_last_digits;
            next_digits = new_next_digits;
            formula = new_formula;
        };
        void recurse(void);
        Str & get_formula(void) { return formula; }
        int get_last_sum(void) { return last_sum; }
    };

    void StateSide::recurse(void)
    {
        int num_left = next_digits.size();

        if (num_left == 0)
        {
            last_sum += int_val(last_digits);
            last_digits = Str();
            terminator_cb(
                this,
                context
            );
            return;
        }
        char next_digit = next_digits.front();

        {
            // Handle the not plus
            Str new_last_digits(last_digits);
            new_last_digits.push_back(next_digit);

            Str new_next_digits(next_digits);
            new_next_digits.pop_front();

            Str new_formula(formula);
            new_formula.push_back(next_digit);

            
            StateSide(
                    last_sum,
                    new_last_digits,
                    new_next_digits,
                    terminator_cb,
                    context,
                    new_formula
            ).recurse();
        }

        // Handle the with plus
        
        // No leading plus.
        if (! last_digits.empty())
        {
            Str new_last_digits;
            new_last_digits.push_back(next_digit);

            Str new_next_digits(next_digits);
            new_next_digits.pop_front();

            Str new_formula(formula);
            new_formula.push_back('+');
            new_formula.push_back(next_digit);

            StateSide(
                    last_sum + int_val(last_digits),
                    new_last_digits,
                    new_next_digits,
                    terminator_cb,
                    context,
                    new_formula
            ).recurse();
        }

        return;
    }

   

    void solve_final_callback (StateSide * right_state, void * context)
    {
        StateSide * left_state = (StateSide *)context;

        if (left_state->get_last_sum() == right_state->get_last_sum())
        {
            cout << left_state->get_formula()  << " = "
                 << right_state->get_formula() << endl
                 ;
        }
    }

    void solve_for_right (StateSide * left_state, void * context)
    {
        int right = *(int *)context;

        Str last_digits;
        Str formula;
        Str right_str = Str_val(right);

        StateSide(
            0,
            last_digits,
            right_str,
            solve_final_callback,
            ((void *)left_state),
            formula
        ).recurse();
    }

    void solve_for(int left, int right)
    {
        Str last_digits;
        Str formula;
        Str left_str = Str_val(left);

        StateSide(
            0,
            last_digits,
            left_str,
            solve_for_right,
            ((void *)&right),
            formula
        ).recurse();
    }
};

int main(int argc, char * argv[])
{
    if (argc != 3)
    {
        std::cerr << "Usage: ./fondi-plus [num1] [num2]" << std::endl;
        return -1;
    }
    
    PlusEquation::solve_for(atoi(argv[1]), atoi(argv[2]));

#if 0
    PlusEquation::Str s;

    s.push_back('1');
    s.push_back('0');
    s.push_back('5');

    std::cout << PlusEquation::int_val(s) << std::endl;
#endif

    return 0;
}

]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

Perl version using eval:

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

use strict;
use warnings;

my @n = @ARGV;
die "Wrong" if grep { !/\A\d+\z/ } @n;

r("", [map{ [split//, $_] } @n], []);

sub myeval
{
    my $s = shift;
    $s =~ s{(\d+)}{int($1)}eg;
    return eval $s;
}

sub r
{
    my ($expr, $list_of_rests, $list_of_exprs) = @_;
    
    if (!@$list_of_rests)
    {
        print join(" = ", @$list_of_exprs), "\n";
    }
    else
    {
        my $rest = shift(@$list_of_rests);
        if (!@$rest)
        {
            if ((!@$list_of_exprs) || 
                (myeval($expr) == myeval($list_of_exprs->[0])))
            {
                r("", 
                    [map { [@$_] } @$list_of_rests], 
                    [@$list_of_exprs, $expr]
                );
            }
            return;
        }
        else
        {
            my $first = shift(@$rest);
            for my $suffix ("", (length($expr)?"+":()))
            {
                r(
                    $expr.$suffix.$first, 
                    [map { [@$_] } $rest,@$list_of_rests],
                    [@$list_of_exprs]
                );
            }
        }
    }
    return;
}


]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

Regards,

	Shlomi Fish

> Enjoy!
>
> Regards,
>
> 	Shlomi Fish

-- 
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
"The Human Hacking Field Guide" - http://xrl.us/bjn8q

God gave us two eyes and ten fingers so we will type five times as much as we
read.