This is my response to The Weekly Challenge #191.
@list.
Input: @list = (1,2,3,4)
Output: -1
The largest in the given list is 4. However 4 is not greater than twice
of every remaining elements.
1 x 2 <= 4
2 x 2 <= 4
2 x 3 > 4
Input: @list = (1,2,0,5)
Output: 1
The largest in the given list is 5. Also 5 is greater than twice of every
remaining elements.
1 x 2 <= 5
2 x 2 <= 5
0 x 2 <= 5
Input: @list = (2,6,3,1)
Output: 1
The largest in the given list is 6. Also 6 is greater than twice of every
remaining elements.
2 x 2 <= 6
3 x 2 <= 6
1 x 2 <= 6
Input: @list = (4,5,2,3)
Output: -1
The largest in the given list is 5. Also 5 is not greater than twice of
every remaining elements.
4 x 2 > 5
2 x 2 <= 5
3 x 2 > 5
Off we go...
File: twice-largest
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ Int,
:v(:$verbose));
my @sorted = @list.sort; # [1]
say ":Sorted: @sorted[]" if $verbose;
my $largest = @sorted.pop; # [2]
my $next = @sorted.pop; # [3]
say ":Largest: $largest" if $verbose;
say ":Next: $next" if $verbose;
say ($largest >= $next * 2) ?? 1 !! -1; # [4]
[1] We are looking for the largest value. Using max will certainly do that,
but we need the second largest value as well (and max cannot help us with
this). So we sort the values instead. The default order is lowest first, which is fine.
[2] Get the largest value, by removing it from the end of the sorted list
(with pop).
See
docs.raku.org/routine/pop
for more information about pop.
[3] Then we get the remaining highest value (again with pop. We do not
have to compare every value, just this one. As «at least twice as large as each of
the other items» will be satisfied if the largest of «the other items» work out.
[4] Then we simply compare the values, and print «1» if it passed the test, and «-1» otherwise.
Running it:
$ ./twice-largest 1 2 3 4
-1
$ ./twice-largest 1 2 0 5
1
$ ./twice-largest 2 6 3 1
1
$ ./twice-largest 4 5 2 3
-1
Looking good.
With verbose mode:
$ ./twice-largest -v 1 2 3 4
:Sorted: 1 2 3 4
:Largest: 4
:Next: 3
-1
$ ./twice-largest -v 1 2 0 5
:Sorted: 0 1 2 5
:Largest: 5
:Next: 2
1
$ ./twice-largest -v 2 6 3 1
:Sorted: 1 2 3 6
:Largest: 6
:Next: 3
1
$ ./twice-largest -v 4 5 2 3
:Sorted: 2 3 4 5
:Largest: 5
:Next: 4
-1
0 < $n <= 15.
1) $list[$i] is evenly divisible by $i
or
2) $i is evenly divisible by $list[$i]
Input: $n = 2
Ouput: 2
Since $n = 2, the list can be made up of two integers only i.e. 1 and 2.
Therefore we can have two list i.e. (1,2) and (2,1).
@list = (1,2) is cute since $list[1] = 1 is divisible by 1 and $list[2]
= 2 is divisible by 2.
#! /usr/bin/env raku
unit sub MAIN (UInt $n where 0 < $n <= 15, :v(:$verbose)); # [1]
my @list = (1 .. $n); # [2]
say ":List: [{ @list.join(",") }]" if $verbose;
my @permutations = @list.permutations; # [3]
say ":Permutations: ", @permutations if $verbose;
my $cute;
for @permutations -> @permutation # [4]
{
$cute++ if is-cute(@permutation); # [5]
}
say $cute; # [6]
sub is-cute (@list) # [7]
{
for 1 .. @list.elems -> $i # [8]
{
return 0 unless @list[$i -1] %% $i || $i %% @list[$i -1]; # [9]
}
return 1; # [10]
}
[1] Note the stacked comparison in the where clause. The
UInt (unsigned integer) type can be replaced with the more
known Int here without causing problems.
[2] Generate the list.
[3] Get all the permutations, with the aptly named
permutations method.
See
docs.raku.org/routine/permutations for more information about permutations.
[4] Iterate over the permutations,
[5] Add one to the counter if the current permutution is cute.
[6] Print the result.
[7] Is the list cute?
[8] Iterate over the indices (1 based).
[9] We fail (return 0) if both divisible expressions fail.
[10] If we reach the end of the loop without failing, we have succeeded.
Running it:
$ ./cute-list 2
2
We got the expected result, but this is the only example we got.
Let us try some other values, with verbose mode:
$ ./cute-list -v 1
:List: [1]
:Permutations: [(1)]
1
$ ./cute-list -v 2
:List: [1,2]
:Permutations: [(1 2) (2 1)]
2
$ ./cute-list -v 3
:List: [1,2,3]
:Permutations: [(1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)]
3
$ ./cute-list -v 4
:List: [1,2,3,4]
:Permutations: [(1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) ...]
8
$ ./cute-list -v 5
:List: [1,2,3,4,5]
:Permutations: [(1 2 3 4 5) (1 2 3 5 4) (1 2 4 3 5) (1 2 4 5 3) ...]
10
$ ./cute-list -v 6
:List: [1,2,3,4,5,6]
:Permutations: [(1 2 3 4 5 6) (1 2 3 4 6 5) (1 2 3 5 4 6) ...]
36
$ ./cute-list -v 7
:List: [1,2,3,4,5,6,7]
:Permutations: [(1 2 3 4 5 6 7) (1 2 3 4 5 7 6) (1 2 3 4 6 5 7) ...]
41
$ ./cute-list -v 8
:List: [1,2,3,4,5,6,7,8]
:Permutations: [(1 2 3 4 5 6 7 8) (1 2 3 4 5 6 8 7) (1 2 3 4 5 7 6 8) ...]
132
$ ./cute-list -v 9
:List: [1,2,3,4,5,6,7,8,9]
:Permutations: [(1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 9 8) ...]
250
$ ./cute-list -v 10
:List: [1,2,3,4,5,6,7,8,9,10]
:Permutations: [(1 2 3 4 5 6 7 8 9 10) (1 2 3 4 5 6 7 8 10 9) ...]
700
$ time ./cute-list -v 11
:List: [1,2,3,4,5,6,7,8,9,10,11]
:Permutations: [(1 2 3 4 5 6 7 8 9 10 11) (1 2 3 4 5 6 7 8 9 11 10)
750
Higher values gives longer runtime. «10» took 21 seconds on my pc, whereas «11» took 9 minutes. I stopped there...
Note that I have shortened the
permutations-lines, to make the output readable. Raku will also shorten them (courtesy
of say), but not so agressively.
And that's it.