t3/edgar

``````# -*- mode: cperl6; -*-

# 2011 Perl 6 Coding Contest
# Edgar Gonzàlez i Pellicer

use v6;

use Position;

# Target
my Int \$target;

# Best solution so far
my Int @best-sol;
my Int \$best-length;

# Find greedy solution
sub find-greedy() {
# Powers of two up to the target
my @powers = 1, 2, 4 ...^ * > \$target;

# Find bits
my @bits = sprintf('%b', \$target).comb(/./).reverse>>.Int;

# Find first 1
my \$i = 0;
++\$i while !@bits[\$i]; # There will be one for sure

# All powers of two will take part in the solution
my \$sol = @powers;

# Find required extra steps
my \$sum = @powers[\$i];
for \$i ^..^ +@bits -> \$j {
if @bits[\$j] {
\$sum += @powers[\$j];
\$sol.push(\$sum);
}
}

# Set as solution
@best-sol    = \$sol.list;
\$best-length = \$sol.elems;
}

# Current solution
my Int @current-sol;
my Int %current-sol;
my Int \$current-max;

# Backtrack
sub backtrack(PosPair \$pp0) {
# Pruning #1: Larger than the best?
return if @current-sol >= \$best-length - 1;

# Pruning #2: Achivable upper bound is lower than target
my \$ub = \$current-max * (2 ** (\$best-length - @current-sol));
return if \$ub < \$target;

# Try with all combinations
for \$pp0 .. end(@current-sol) -> \$pp {
# The new one
my \$new = @current-sol[\$pp.i] + @current-sol[\$pp.j];

# Larger than the target?
if \$new > \$target {
# Skip!
}

# Is it the target?
elsif \$new == \$target {
# We updated the best solution
@best-sol = @current-sol;
@best-sol.push(\$new);
\$best-length = @best-sol.elems;
}

# Is it not already there?
elsif !%current-sol.exists(\$new) {
%current-sol{\$new} = 1;
@current-sol.push(\$new);

# Update max
my \$prev-max = \$current-max;
\$current-max max= \$new;

# Backtrack from the next position on,
# to avoid already tried pairs
backtrack(\$pp.succ);

# Restore
%current-sol.delete(\$new);
@current-sol.pop();
\$current-max = \$prev-max;
}
}
}

# Solve
sub solve(Int \$n) {
# Positive?
if \$n > 0 {
# Set as target
\$target = \$n;

# Find the greedy solution, to allow pruning
find-greedy();

# Try to backtrack to improve
@current-sol = 1;
%current-sol = 1 => 1;
\$current-max = 1;
backtrack(start(@current-sol));

# Show the solution
say('(' ~ @best-sol.sort.join(', ') ~ ')');
}
else {
# Error
say('Argument must be positive.');
}
}

# Main
## Without arguments
multi sub MAIN() {
# Read and solve each line
for \$*IN.lines {
solve(.Int);
}
}

# Main
## With arguments
multi sub MAIN(*@ARGS) {
# For each one
for @ARGS {
solve(.Int);
}
}

# Call main
MAIN(|@*ARGS);
``````

Position.pm6:

``````# -*- mode: cperl6; -*-

# 2011 Perl 6 Coding Contest
# Edgar Gonzàlez i Pellicer

# Positions
module Position;

# Position pair
class PosPair is export {
has Int \$.i;
has Int \$.j;

# Next
method succ() {
if \$.j == \$.i {
return PosPair.new(i => \$.i + 1, j => 0);
}
else {
return PosPair.new(i => \$.i, j => \$.j + 1);
}
}

# Conversion to numeric
method Numeric() {
return \$.i * (\$.i + 1) / 2 + \$.j;
}
}

# Position pair at the start of a container
sub start(\$) is export {
return PosPair.new(i => 0, j => 0);
}

# Position pair at the end of a container
sub end(\$container) is export {
return PosPair.new(i => \$container.elems - 1,
j => \$container.elems - 1);
}
``````

Correctness

The code produces correct results.

Consistency

Nothing to comment on here. Looks good.

Clarity of intent

It's clear that some thought has gone into this solution.

Some of the comments only take up unnecessary space by re-stating what is already clear from the program code itself.

The attribute names `.i` and `.j` are woefully nondescript.

Algorithmic efficiency

The solution starts off from a powers-of-two chain. The later "backtracking" is still just a recursive search through a lot of solutions, making this solution of the same complexity as the other depth-first solutions.

Idiomatic use of Perl 6

There's no need to store `\$best-length`, since an array knows its length in Perl 6.

The cute `while` loop to find the first `1` would've been an excellent opportunity to use the Perl 6 built-in `&first`, which works like `&grep` but stops after the first match.

It's really nice to see a custom-defined `.succ` method so that ranges of a user-defined object type can then be employed. That is a pleasurable form of abstraction.

A happy shout-out to the use of `max=`.

Brevity

Spread out over a longish script and a module.