This is my response to The Weekly Challenge #223.
$n.
Input: $n = 10
Output: 4
Since there are 4 primes (2,3,5,7) less than or equal to 10.
Input: $n = 1
Output: 0
Input: $n = 20
Output: 8
Since there are 4 primes (2,3,5,7,11,13,17,19) less than or equal to 20.
This is basically a one liner, shown here with the added crash bang line and error checking on the input.
File: count-primes
#! /usr/bin/env raku
unit sub MAIN (UInt $n where $n > 0); # [1]
say (1 .. $n).grep({ .is-prime }).elems; # [2]
[1] Ensure a positive (where $n > 0) integer (UInt
gives an usigned int, which includes zero, but the other part fixes that).
[2] Start with all the possible integers (1 .. $n),
disregarding the fact that 2 is the lowest prime (so we could have started there,
instead of at 1). Then we use grep to collect only the values that
are prime (with .is-prime). We are interested in the number of
primes, not the values themselves, so we apply .elems to do just
that, before printing the result.
See
docs.raku.org/routine/is-prime
for more information about is-prime.
Running it:
$ ./count-primes 10
4
$ ./count-primes 1
0
$ ./count-primes 20
8
Looking good.
Some more, just for fun:
$ ./count-primes 1_000_000
78498
$ ./count-primes 2_000_000
148933
$ ./count-primes 3_000_000
216816
$ ./count-primes 4_000_000
283146
$ ./count-primes 5_000_000
348513
@box.
box[i] then we collect the coins
$box[i-1] * $box[i] * $box[i+1]. If $box[i+1]
or $box[i-1] is out of bound then treat it as
1 coin.
Input: @box = (3, 1, 5, 8)
Output: 167
Step 1: pick box [i=1] and collected coins 3 * 1 * 5 => 15.
Boxes available (3, 5, 8).
Step 2: pick box [i=1] and collected coins 3 * 5 * 8 => 120.
Boxes available (3, 8).
Step 3: pick box [i=0] and collected coins 1 * 3 * 8 => 24.
Boxes available (8).
Step 4: pick box [i=0] and collected coins 1 * 8 * 1 => 8.
No more box available.
Input: @box = (1, 5)
Output: 10
Step 1: pick box [i=0] and collected coins 1 * 1 * 5 => 5.
Boxes available (5).
Step 2: pick box [i=0] and collected coins 1 * 5 * 1 => 5.
No more box available.
We are looking for the maximum. This is best achieved by eliminating the smallest numbers first, so that can multiply even larger numbers in future steps.
This approach works until we have 3 boxes left, and this step should give us the largest contribution to the grand total (as we now have the threee largest numbers in the input; just as in step 2 for the second example).
Now we pick the one in the middle (so that we can multiply all of the three remaining numbers together). Then we have two. it does not matter which one we pick for this step by itself, as we multiply them together. But we should pick the lowest one, so that the highest one can come in at the very end (when we have only one).
File: box-coins
#! /usr/bin/env raku
unit sub MAIN (*@box where @box.elems > 0 # [1]
&& all(@box) ~~ UInt && all(@box) > 0,
:v(:$verbose));
my $coins = 0; # [2]
while (@box.elems) # [3]
{
my $i = 0; # [4]
if @box.elems > 3 # [5]
{
$i = smallest-index(@box); # [5a]
}
elsif @box.elems == 3 # [6]
{
$i = 1; # [6a]
}
elsif @box.elems == 2 # [7]
{
$i = 1 if @box[1] < @box[0]; # [7a]
}
print ":Box: @box[] | I:$i" if $verbose;
my $left = $i > 0 ?? @box[$i -1] !! 1; # [8]
my $curr = @box[$i]; # [9]
my $right = $i < @box.end ?? @box[$i +1] !! 1; # [10]
my $add = $left * $curr * $right; # [11]
$coins += $add; # [12]
@box.splice($i,1); # [13]
say " -> box: @box[] | coins: $add | total: $coins" if $verbose;
}
say $coins; # [14]
sub smallest-index (@list) # [15]
{
my $index = 0; # [16]
my $val = @list[0]; # [17]
for 1 .. @list.end -> $i # [18]
{
if @list[$i] < $val # [19]
{
$index = $i; # [19a]
$val = @list[$i]; # [19b]
}
}
return $index; # [20]
}
[1] At least one value (box); and the values must be positive integers.
[2] The sum (number of coins) obtained after taking out all the boxes.
[3] As long as we have boxes left.
[4] The i (index) to use, with 0 as the default value. (This is used on the very last item, as the if block [5-7] does not apply.)
[5] More than three elements? Choose the index of the lowest number [5a].
[6] Exactly three elemets? Choose the middle one. [6a]
[7] Exactly two elements? Choose the index of the lowest number [7a].
[8] The left value, or 1 if it is out of bounds.
[9] The current value.
[10] The right value, or 1 if it is out of bounds.
[11] Multiply the three values together.
[12] Add the new value to the total number of coins.
[13] Remove the chosen value from the list (with
splice).
See
docs.raku.org/routine/splice
for more information about splice.
[14] Print the total number of coins.
[15] Get the index of the lowest value in the supplied array.
[16] Starting at index 0.
[17] And the value found at index 0.
[18] Iterate over the indices of the rest of the array (i.e. excluding the initial value).
[19] Is the new value lower than the previously lowest value? If so, save the index [19a] and value [19b]. (Note that multiple instances of the same lowest value will give us the index of the first one.)
[20] Return the index of the lowest value.
Running it:
$ ./box-coins 3 1 5 8
167
$ ./box-coins 1 5
10
Looking good.
With verbose mode:
$ ./box-coins -v 3 1 5 8
:Box: 3 1 5 8 | I:1 -> box: 3 5 8 | coins: 15 | total: 15
:Box: 3 5 8 | I:1 -> box: 3 8 | coins: 120 | total: 135
:Box: 3 8 | I:0 -> box: 8 | coins: 24 | total: 159
:Box: 8 | I:0 -> box: | coins: 8 | total: 167
167
$ ./box-coins -v 1 5
:Box: 1 5 | I:0 -> box: 5 | coins: 5 | total: 5
:Box: 5 | I:0 -> box: | coins: 5 | total: 10
10
And that's it.