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

On (28/02/08 21:40), Shlomi Fish wrote:
> To: [email protected]
> From: Shlomi Fish <shlomif-ik1l9ssToec+JF/[email protected]>
> 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.
> 
> Regards,
> 
> 	Shlomi Fish
> 

my recursive solution:
8<----8<
#!/usr/bin/perl

use warnings;
use strict;
use Data::Dumper;

sub get_digits_sum {
	my ($sum, $num, $start) = @_;
	my $max = ($sum < 10 ? $sum : 9);
	$start = 1 unless $start;

	return [] unless $num;
	return [] if $sum <= 0;
	return [] if $max < $start;
	return [[$sum]] if $num == 1;

	my @result;

	for my $current ($start..$max) {
		push @result, map [$current, @$_], @{get_digits_sum($sum - $current, $num - 1, $current + 1)};
	}
	
	return \@result;
}

die ("run with sum and number of cell's") 
	unless @ARGV == 2;
print Dumper(get_digits_sum(@ARGV));
8<----8<


-- 
Premysl "Anydot" Hruby >> http://www.redrum.cz <<