This is my response to The Weekly Challenge #343.
Input: @nums = (4, 2, -1, 3, -2)
Output: 1
Values closest to 0: -1 and 2 (distance = 1 and 2)
Input: @nums = (-5, 5, -3, 3, -1, 1)
Output: 1
Values closest to 0: -1 and 1 (distance = 1)
Input: @ums = (7, -3, 0, 2, -8)
Output: 0
Values closest to 0: 0 (distance = 0)
Exact zero wins regardless of other close values.
Input: @nums = (-2, -5, -1, -8)
Output: 1
Values closest to 0: -1 and -2 (distance = 1 and 2)
Input: @nums = (-2, 2, -4, 4, -1, 1)
Output: 1
Values closest to 0: -1 and 1 (distance = 1)
classify:
my %c = $str.comb.classify({ <a d>[ ?/<digit>/ ] });
my @digits = %c.sort;
my @alphas = %c.sort;
See docs.raku.org/routine/classify for more information about classify.
#! /usr/bin/env raku
unit sub MAIN (*@nums where @nums.elems > 0 && all(@nums) ~~ Numeric); # [1]
say @nums>>.abs.min; # [2]
[1] At least 1 element, all of which must be numeric (as specified in the challenge text). The examples use integers only, but that may be a red herring.
[2] Remove the sign if any on all the values (with >>.abs), pick the
lowest value (with min) and print it.
Running it:
$ ./zero-friend 4 2 -1 3 -2
1
$ ./zero-friend -- -5 5 -3 3 -1 1
1
$ ./zero-friend -- -7 -3 0 2 -0
0
3 (master)$ ./zero-friend -- -2 -5 -1 -8
1
$ ./zero-friend -- -2 2 -4 4 -1 1
1
Looking good.
With some non-integer values:
$ ./zero-friend 1 2 3 4 0.3 10 -0.4
0.3
$ ./zero-friend 1 2 3 4 -0.3 10 -0.4
-0.3
That last one is wrong, as (-0.3).abs should have removed the sign.
Negative integer values are handled correctly, though:
$ ./zero-friend -- -1 2 3 4 5
1
Coercing the values to the Numeric type before removing the sign does
the trick. I have no idea why, so feel free to use Redit to explain.
#! /usr/bin/env raku
unit sub MAIN (*@nums where @nums.elems > 0 && all(@nums) ~~ Numeric);
say @nums>>.Numeric>>.abs.min;
$ ./zero-friend-fixed 1 2 3 4 -0.3 10 -0.4
0.3
Another «solution» could be sticking with integers only:
File: zero-friend-int
#! /usr/bin/env raku
unit sub MAIN (*@nums where @nums.elems > 0 && all(@nums) ~~ Int)
say @nums>>.abs.min;
Verbose mode did not fit in with the one-linerish concept.
grid[i][j] == 1, then team i is stronger than team j
grid[i][j] == 0, then team j is stronger than team i
Input: @grid = (
[0, 1, 1],
[0, 0, 1],
[0, 0, 0],
)
Output: Team 0
[0, 1, 1] => Team 0 beats Team 1 and Team 2
[0, 0, 1] => Team 1 beats Team 2
[0, 0, 0] => Team 2 loses to all
Input: @grid = (
[0, 1, 0, 0],
[0, 0, 0, 0],
[1, 1, 0, 0],
[1, 1, 1, 0],
)
Output: Team 3
[0, 1, 0, 0] => Team 0 beats only Team 1
[0, 0, 0, 0] => Team 1 loses to all
[1, 1, 0, 0] => Team 2 beats Team 0 and Team 1
[1, 1, 1, 0] => Team 3 beats everyone
Input: @grid = (
[0, 1, 0, 1],
[0, 0, 1, 1],
[1, 0, 0, 0],
[0, 0, 1, 0],
)
Output: Team 0
[0, 1, 0, 1] => Team 0 beats teams 1 and 3
[0, 0, 1, 1] => Team 1 beats teams 2 and 3
[1, 0, 0, 0] => Team 2 beats team 0
[0, 0, 1, 0] => Team 3 beats team 2
Of the teams with 2 wins, Team 0 beats team 1.
Input: @grid = (
[0, 1, 1],
[0, 0, 0],
[0, 1, 0],
)
Output: Team 0
[0, 1, 1] => Team 0 beats Team 1 and Team 2
[0, 0, 0] => Team 1 loses to Team 2
[0, 1, 0] => Team 2 beats Team 1 but loses to Team 0
Input: @grid = (
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[1, 1, 0, 1, 1],
[1, 1, 0, 0, 0],
[1, 1, 0, 1, 0],
)
Output: Team 2
[0, 0, 0, 0, 0] => Team 0 loses to all
[1, 0, 0, 0, 0] => Team 1 beats only Team 0
[1, 1, 0, 1, 1] => Team 2 beats everyone except self
[1, 1, 0, 0, 0] => Team 3 loses to Team 2
[1, 1, 0, 1, 0] => Team 4 loses to Team 2
The first part of the program, dealing with the situation where a single team has the most wins.
File: champion-team (partial)
#! /usr/bin/env raku
unit sub MAIN (*@rows where @rows.elems == @rows[0].chars # [1]
&& all(@rows) ~~ /^ <[01]> ** { @rows[0].chars } $/, # [2]
## && [==] @rows>>.chars, # [3]
:v(:$verbose));
my @matrix = @rows>>.comb>>.Array; # [4]
my @scores = @matrix>>.sum; # [5]
if $verbose
{
for ^@matrix.elems -> $team
{
say ": Team $team has score @scores[$team] \
(values [ @matrix[$team].join(", ") ])";
}
}
my $max = @scores.max; # [6]
my $scores-b = @scores.Bag; # [7]
if $scores-b{$max} == 1 # [8]
{
my $winner = @scores.first($max, :k); # [9]
say ": One team ($winner) has the most wins ($max)" if $verbose;
say $winner; # [10]
exit; # [11]
}
[1] We specify the values as a string for each row, separated by spaces.
E.g. "011 001 000". Ensure that the number of columns (on the first
row) and the number of rows are equal.
[2] Ensure that the rows contain binary digits only, and the same number of them as on the first row.
[3] This one is not needed, as [2] took care of that for us.
[4] Get the two dimentional matrix. The coercion of rows to Arrays makes it possible to change the values later on (in [18]).
[5] Get the scores; the sum of the values on each row.
[6] Get the maximum score.
[7] Get the scores as a Bag, which counts the frequencies.
See docs.raku.org/routine/Bag for more information about Bag.
[8] Only one team with the highest score?
[9] Get the first (and only) team. The :k adverb tells first to return
the key (the index) instead of the actual value.
[10] And the winner is...
[11] We are finished.
The second part of the program, where we have to do a second pass to get to the winner.
File: champion-team (the final part)
my @indices = (0 .. @scores.end).grep({ @scores[$_] == $max }); # [12]
say ": Teams with the highest score ($max): { @indices.join(",") }"
if $verbose;
for 0 .. @scores.end -> $i # [13]
{
for 0 .. @scores.end -> $j # [14]
{
next if $i == any(@indices) && $j == any(@indices); # [15]
@matrix[$i;$j] = 0; # [16]
say ": Clearing value for i:$i,j:$j" if $verbose;
}
}
my @scores2 = @matrix>>.sum; # [17]
if $verbose
{
for ^@matrix.elems -> $team
{
say ": Team $team has score @scores2[$team] \
(values [ @matrix[$team].join(", ") ])";
}
}
my $max2 = @scores2.max; # [18]
my $scores2-b = @scores2.Bag; # [19]
if $scores2-b{$max2} == 1 # [20]
{
my $winner = @scores2.first($max2, :k); # [21]
say ": One team ($winner) has the most wins ($max2)" if $verbose;
say $winner; # [22]
}
else # [23]
{
die "Not unique"; # [23a]
}
[12] Get the indices of the teams (or team numbers) with the highest score. This is a for loop over the indices in disguise.
[13] We could have extracted the winning teams into a new matrix, but that would have messed up the nice mapping between team and row number. So instead we iterate over all the rows
[14] and column indices
[15] Skip this iteration if any of the teams are a winner.
[16] Zero out the team otherwise.
[17] As [5].
[18] As [6].
[19] As [7].
[20] As [8].
[21] As [9].
[22] As [10].
[23] If we still have no single winner after the second iteration, report failure [23a].
Running it:
$ ./champion-team 011 001 000
0
$ ./champion-team 0100 0000 1100 1110
3
$ ./champion-team 0101 0011 1000 0010
0
$ ./champion-team 011 000 010
0
$ ./champion-team 00000 10000 11011 11000 11010
2
Looking good.
With verbose mode:
$ ./champion-team -v 011 001 000
: Team 0 has score 2 (values [ 0, 1, 1 ])
: Team 1 has score 1 (values [ 0, 0, 1 ])
: Team 2 has score 0 (values [ 0, 0, 0 ])
: One team has the most wins (2)
0
$ ./champion-team -v 0100 0000 1100 1110
: Team 0 has score 1 (values [ 0, 1, 0, 0 ])
: Team 1 has score 0 (values [ 0, 0, 0, 0 ])
: Team 2 has score 2 (values [ 1, 1, 0, 0 ])
: Team 3 has score 3 (values [ 1, 1, 1, 0 ])
: One team (3) has the most wins (3)
3
$ ./champion-team -v 0101 0011 1000 0010
: Team 0 has score 2 (values [ 0, 1, 0, 1 ])
: Team 1 has score 2 (values [ 0, 0, 1, 1 ])
: Team 2 has score 1 (values [ 1, 0, 0, 0 ])
: Team 3 has score 1 (values [ 0, 0, 1, 0 ])
: Teams with the highest score (2): 0,1
: Clearing value for i:0,j:2
: Clearing value for i:0,j:3
: Clearing value for i:1,j:2
: Clearing value for i:1,j:3
: Clearing value for i:2,j:0
: Clearing value for i:2,j:1
: Clearing value for i:2,j:2
: Clearing value for i:2,j:3
: Clearing value for i:3,j:0
: Clearing value for i:3,j:1
: Clearing value for i:3,j:2
: Clearing value for i:3,j:3
: Team 0 has score 1 (values [ 0, 1, 0, 0 ])
: Team 1 has score 0 (values [ 0, 0, 0, 0 ])
: Team 2 has score 0 (values [ 0, 0, 0, 0 ])
: Team 3 has score 0 (values [ 0, 0, 0, 0 ])
: One team (0) has the most wins (1)
0
$ ./champion-team -v 011 000 010
: Team 0 has score 2 (values [ 0, 1, 1 ])
: Team 1 has score 0 (values [ 0, 0, 0 ])
: Team 2 has score 1 (values [ 0, 1, 0 ])
: One team (0) has the most wins (2)
0
$ ./champion-team -v 00000 10000 11011 11000 11010
: Team 0 has score 0 (values [ 0, 0, 0, 0, 0 ])
: Team 1 has score 1 (values [ 1, 0, 0, 0, 0 ])
: Team 2 has score 4 (values [ 1, 1, 0, 1, 1 ])
: Team 3 has score 2 (values [ 1, 1, 0, 0, 0 ])
: Team 4 has score 3 (values [ 1, 1, 0, 1, 0 ])
: One team (2) has the most wins (4)
2
The repeated code ([17-22]) really is suited for a common procedure, called once (example 1, 2, 4, 5) or twice (example 3) - or perhaps even more - until we end up with a single winner, or cannot remove any more teams.
So here it is:
File: champion-team-loop
#! /usr/bin/env raku
unit sub MAIN (*@rows where @rows.elems == @rows[0].chars
&& all(@rows) ~~ /^ <[01]> ** { @rows[0].chars } $/,
:v(:$verbose));
my @matrix = @rows>>.comb>>.Array;
my @team-numbers = ^@matrix.elems; # [1]
my $size = @matrix.elems; # [5]
my $iteration = 1; # [2]
loop # [3]
{
my %res = winners(@matrix, @team-numbers); # [4]
@matrix = @(%res<matrix>); # [4a]
@team-numbers = @(%res<team-numbers>); # [4b]
last if @team-numbers.elems == $size || @team-numbers.elems == 1; # [5a]
$size = @team-numbers.elems; # [5b]
}
say @team-numbers.join(", "); # [6]
sub winners (@matrix, @team-numbers)
{
my @scores = @matrix>>.sum;
my $max = @scores.max;
if $verbose
{
say ": Iteration { $iteration++ } (with size { @matrix.elems })";
my $i = 0;
for ^@matrix.elems -> $team
{
say ": Team {@team-numbers[$i++]} has score @scores[$team] \
(values [ @matrix[$team].join(", ") ]) \
{ @scores[$team] == $max ?? "MAX" !! "" }";
}
}
my @maxes = (0 .. @scores.end).grep({ @scores[$_] == $max });
my @new-matrix;
my @new-team-numbers;
## return { matrix => $max, team-numbers => @team-numbers[@maxes[0]] }
## if @maxes.elems == 1; # [7]
for ^@matrix.elems -> $i
{
next unless $i == any(@maxes);
@new-team-numbers.push: @team-numbers[$i]; # [8]
my @row;
for ^@matrix.elems -> $j
{
next unless $j == any(@maxes);
@row.push: @matrix[$i;$j];
}
@new-matrix.push: @row;
}
return { matrix => @new-matrix, team-numbers => @new-team-numbers }; # [9]
}
[1] The team numbers are the same as the indices initially, but they will differ when we start removing rows of non-winners (loosers). So, yes, I have decided to remove non-winning rows and columns this time.
[2] Used by verbose mode only.
[3] An eternal loop, with an exit strategy in [4].
[4] Get the winners, and extract them and the team-numbers.
[5] The current size of the matrix. We are finished if we cannot reduce the size any further - or the size is 1 [5a]. Save the new size in preparation for the next iteration [5b].
[6] The winning team, or teams.
[7] Return the single team, if we are left with just one. I have disabled this check as the loop below works just fine in that situation as well.
[8] Save the team number.
[9] Return the two arrays, packed inside a hash fdor the heck of it.
Running it, with verbose mode:
$ ./champion-team-loop -v 011 001 000
: Iteration 1 (with size 3)
: Team 0 has score 2 (values [ 0, 1, 1 ]) MAX
: Team 1 has score 1 (values [ 0, 0, 1 ])
: Team 2 has score 0 (values [ 0, 0, 0 ])
0
$./champion-team-loop -v 0100 0000 1100 1110
: Iteration 1 (with size 4)
: Team 0 has score 1 (values [ 0, 1, 0, 0 ])
: Team 1 has score 0 (values [ 0, 0, 0, 0 ])
: Team 2 has score 2 (values [ 1, 1, 0, 0 ])
: Team 3 has score 3 (values [ 1, 1, 1, 0 ]) MAX
3
$ ./champion-team-loop -v 0101 0011 1000 0010
: Iteration 1 (with size 4)
: Team 0 has score 2 (values [ 0, 1, 0, 1 ]) MAX
: Team 1 has score 2 (values [ 0, 0, 1, 1 ]) MAX
: Team 2 has score 1 (values [ 1, 0, 0, 0 ])
: Team 3 has score 1 (values [ 0, 0, 1, 0 ])
: Iteration 2 (with size 2)
: Team 0 has score 1 (values [ 0, 1 ]) MAX
: Team 1 has score 0 (values [ 0, 0 ])
0
$ ./champion-team-loop -v 011 000 010
: Iteration 1 (with size 3)
: Team 0 has score 2 (values [ 0, 1, 1 ]) MAX
: Team 1 has score 0 (values [ 0, 0, 0 ])
: Team 2 has score 1 (values [ 0, 1, 0 ])
0
$ ./champion-team-loop -v 00000 10000 11011 11000 11010
: Iteration 1 (with size 5)
: Team 0 has score 0 (values [ 0, 0, 0, 0, 0 ])
: Team 1 has score 1 (values [ 1, 0, 0, 0, 0 ])
: Team 2 has score 4 (values [ 1, 1, 0, 1, 1 ]) MAX
: Team 3 has score 2 (values [ 1, 1, 0, 0, 0 ])
: Team 4 has score 3 (values [ 1, 1, 0, 1, 0 ])
2
Some examples where we do not end up with a single winner:
$ ./champion-team-loop -v 011 101 110
: Iteration 1 (with size 3)
: Team 0 has score 2 (values [ 0, 1, 1 ]) MAX
: Team 1 has score 2 (values [ 1, 0, 1 ]) MAX
: Team 2 has score 2 (values [ 1, 1, 0 ]) MAX
0, 1, 2
$ ./champion-team-loop -v 0110 1010 1100 0000
: Iteration 1 (with size 4)
: Team 0 has score 2 (values [ 0, 1, 1, 0 ]) MAX
: Team 1 has score 2 (values [ 1, 0, 1, 0 ]) MAX
: Team 2 has score 2 (values [ 1, 1, 0, 0 ]) MAX
: Team 3 has score 0 (values [ 0, 0, 0, 0 ])
: Iteration 2 (with size 3)
: Team 0 has score 2 (values [ 0, 1, 1 ]) MAX
: Team 1 has score 2 (values [ 1, 0, 1 ]) MAX
: Team 2 has score 2 (values [ 1, 1, 0 ]) MAX
0, 1, 2
$ ./champion-team-loop -v 0110 1010 1001 1000
: Iteration 1 (with size 4)
: Team 0 has score 2 (values [ 0, 1, 1, 0 ]) MAX
: Team 1 has score 2 (values [ 1, 0, 1, 0 ]) MAX
: Team 2 has score 2 (values [ 1, 0, 0, 1 ]) MAX
: Team 3 has score 1 (values [ 1, 0, 0, 0 ])
: Iteration 2 (with size 3)
: Team 0 has score 2 (values [ 0, 1, 1 ]) MAX
: Team 1 has score 2 (values [ 1, 0, 1 ]) MAX
: Team 2 has score 1 (values [ 1, 0, 0 ])
: Iteration 3 (with size 2)
: Team 0 has score 1 (values [ 0, 1 ]) MAX
: Team 1 has score 1 (values [ 1, 0 ]) MAX
0, 1
And finally this one where we do end up with a single winner, though with dubious input (as team 1 has won against itself).
$ ./champion-team-loop -v 0110 1100 1001 1000
: Iteration 1 (with size 4)
: Team 0 has score 2 (values [ 0, 1, 1, 0 ]) MAX
: Team 1 has score 2 (values [ 1, 1, 0, 0 ]) MAX
: Team 2 has score 2 (values [ 1, 0, 0, 1 ]) MAX
: Team 3 has score 1 (values [ 1, 0, 0, 0 ])
: Iteration 2 (with size 3)
: Team 0 has score 2 (values [ 0, 1, 1 ]) MAX
: Team 1 has score 2 (values [ 1, 1, 0 ]) MAX
: Team 2 has score 1 (values [ 1, 0, 0 ])
: Iteration 3 (with size 2)
: Team 0 has score 1 (values [ 0, 1 ])
: Team 1 has score 2 (values [ 1, 1 ]) MAX
1
And that's it.