Re: pathsearch/backtracking in Perl - how to solve a problem apparently requiring it? (comparison of Perl with Standard ML)

Whenever I hear Backtracking in the context of Perl, I think Regular Expressions. So, if you can express the problem as a string, and a matching solution as a regular expression, Perl can solve the problem:

use strict;

my $change = 16;
my @coins = reverse sort qw(2 5);

my $q='1'x$change;

my $solution = join'',map{qr(((?:.{$_})+))} @coins;

$q = ~/^()$solution$/
  or die "Error in regex construction";
{
  # This should maybe be done via @-, but I'm lazy:
  no strict;
  print(length(${$_})/$_, '*', $_) for (1..4)
};
[download]

The key to using Perl effectively is to use its strengths rather than its weaknesses.

Update: Roy Johnson pointed out that I erroneously changed names between testing out and posting - $sol was left over in one place.

Comment on Re: pathsearch/backtracking in Perl - how to solve a problem apparently requiring it? (comparison of Perl with Standard ML) Download Code

Replies are listed 'Best First'.
Re^2: pathsearch/backtracking in Perl - how to solve a problem apparently requiring it? (comparison of Perl with Standard ML) by !1 (Hermit) on Nov 11, 2004 at 20:43 UTC
Hmmm, a few fixes so you can have 0 counts for some of the coins. `use strict; my $change = 16; my @coins = sort { $b <=> $a } qw(2 5); my $q='1'x$change; my $solution = join "", map { qr[((?:.{$_}))] } @coins; $q =~ /^$solution$/ or die "Error in regex construction"; { # This should maybe be done via @-, but I'm lazy: no strict; print(length(${$_})/$coins[$_-1], '', $coins[$_-1]) for (1..@coins) +; }; __END__` [download]	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: pathsearch/backtracking in Perl - how to solve a problem apparently requiring it? (comparison of Perl with Standard ML)
by !1 (Hermit) on Nov 11, 2004 at 20:43 UTC

Hmmm, a few fixes so you can have 0 counts for some of the coins.

use strict;

my $change = 16;
my @coins = sort { $b <=> $a } qw(2 5);

my $q='1'x$change;

my $solution = join "", map { qr[((?:.{$_})*)] } @coins;

$q =~ /^$solution$/
  or die "Error in regex construction";
{
  # This should maybe be done via @-, but I'm lazy:
  no strict;
  print(length(${$_})/$coins[$_-1], '*', $coins[$_-1]) for (1..@coins)
+;
};
__END__
[download]

[reply]
[d/l]