Perl Quiz, Perl Solution: Plusified Equations

Posted: September 11th, 2009 | Author: Eduard Lohmann | Filed under: Perl, Perl Quiz of the Week | No Comments »

For problem definition see: The Haskell solution.

Because this was a test for an applicant, I felt I should solve it too in order to get a good idea of how difficult it is.

My approach was so generate the plussified expressions from smallest to largest sum. That way I can discard any expressions from one list that have a smaller sum then the least sum of the other list.

The Algorithm

  1. Generate a list of plussified expressions for each of the integers, sorted smallest to largest sum.
  2. Compare the sums of the first elements of both lists. If one is less then the other remove it and repeat.

  3. If the sums are equal you have found an answer.

    You could now drop the first expression of each list and continue,
    but you would miss the answers where you link the current first element of one list with
    expressions in the other list that are not first, but have the same sum.
    Therefore I also explicitly look for those answers with a recursive call.

Questions welcome at eduard@tty.nl .

#!/usr/bin/env perl
use strict;
use warnings;

main( @ARGV );

sub main {
    /^\d+$/ or die("'$_' is not a valid string of digits.") for @_;
    2 == @_ or die("Supply exactly 2 strings of digits seperated by a space");

    my @answers = find_answers( [ plusify(shift) ], [ plusify(shift) ] );
    print join("\n", @answers ), "\nFound " . scalar(@answers) . " answers.\n";

    return;
}

sub plusify  {
    my ($num) = @_;
    my ($first_digit, $rest) = $num =~ m/(\d)(\d+)?/;
    return ($first_digit) if not defined $rest;
    my @ways = map {  $first_digit . $_ , $first_digit . '+' . $_ } plusify($rest);

    return sort { sum_expression($a) <=> sum_expression($b) } @ways;
}


sub sum_expression  {
    my ($expression) = @_;
    my $sum = 0;
    $sum += $_ for split(qr{\+}, $expression);

    return $sum;
}

sub find_answers  {
    my ( $expressions_1, $expressions_2 ) = @_;
    my @expressions_1 = @{ $expressions_1 };
    my @expressions_2 = @{ $expressions_2 };
    my @answers = ();
    while ( @expressions_1 and @expressions_2 ) {
        my $head_1 = shift(@expressions_1);
        my $head_2 = shift(@expressions_2);
        my $sum_1 = sum_expression($head_1);
        my $sum_2 = sum_expression($head_2);
        if ( $sum_1 == $sum_2 ) {
            push(@answers,"$head_1 = $sum_1 = $head_2" ) ;
            push(@answers, find_answers( [ $head_1 ],  [ @expressions_2 ] ) );
            push(@answers, find_answers( [ @expressions_1 ], [ $head_2 ] ) );
        };

        # Effectively only shift the lowest of the heads
        unshift(@expressions_2, $head_2) if $sum_1 < $sum_2;
        unshift(@expressions_1, $head_1) if $sum_2 < $sum_1;
    };

    return @answers;
}

1;

Perl Quiz, Haskell Solution: Plusified Equations

Posted: August 19th, 2009 | Author: Michel Rijnders | Filed under: Haskell, Perl Quiz of the Week | 1 Comment »

The Quiz

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.

A Haskell Solution

Listing of the complete solution:

module Main where

import Data.List (iterate)
import System (getArgs)

split :: Char -> String -> [String]
split delim s =
  let (s', s'') = break (== delim) s
  in s' : case s'' of
        delim : _ -> split delim (tail s'')
            otherwise -> []

plusify :: String -> [String]
plusify ""       = [""]
plusify (c : "") = [c : ""]
plusify (c : cs) = concatMap (\cs' -> [c : cs', c : '+' : cs']) (plusify cs)

combis :: String -> String -> [(String, String)]
combis x y =
  [(l, r) | l <- plusify x, r <- plusify y, sum' l == sum' r]
    where sum' = sum . map (\s -> read s :: Int) . split '+'

main :: IO ()
main = do
  args <- getArgs
  mapM_ (putStrLn . \(l, r) -> l ++ " = " ++ r) (combis (args!!0) (args!!1))
  return ()