This is my response to The Weekly Challenge #219.
Input: @list = (-2, -1, 0, 3, 4)
Output: (0, 1, 4, 9, 16)
Input: @list = (5, -4, -1, 3, 6)
Output: (1, 9, 16, 25, 36)
File: sorted-squares
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems >= 1 && all(@list) ~~ Int); # [1]
say '(' ~ @list.map( * ** 2 ).sort.join(", ") ~ ')'; # [2]
[1] Ensure at least one value. I have chosen to restrict them to
integers, as that is used in the examples. Replace Int
with Numeric if you want to adhere to the challenge text
instead.
[2] Use map to square the values
(** 2), then sort to sort them in ascending order,
and join to print the commas between the values. The first
* is a placeholder for the current value. (You cannot use the
more impressive looking ( * * * ), as the last *
will be taken as a second placeholder. We have only one input value for
each iteration of map.)
See
docs.raku.org/routine/map
for more information about map.
Running it:
$ ./sorted-squares -- -2 -1 0 3 4
(0, 1, 4, 9, 16)
$ ./sorted-squares 5 -4 -1 3 6
(1, 9, 16, 25, 36)
Looking good.
As a oneliner, without the input guard rails:
say '(' ~ @*ARGS.map( * ** 2 ).sort.join(", ") ~ ')';
Index 0 element represent the cost of 1 day travel card.
Index 1 element represent the cost of 7 days travel card.
Index 2 element represent the cost of 30 days travel card.
Input: @costs = (2, 7, 25)
@days = (1, 5, 6, 7, 9, 15)
Output: 11
On day 1, we buy a one day pass for 2 which would cover the day 1.
On day 5, we buy seven days pass for 7 which would cover days 5 - 9.
On day 15, we buy a one day pass for 2 which would cover the day 15.
So the total cost is 2 + 7 + 2 => 11.
Input: @costs = (2, 7, 25)
@days = (1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31)
Output: 20
On day 1, we buy a seven days pass for 7 which would cover days 1 - 7.
On day 10, we buy a seven days pass for 7 which would cover days 10 - 14.
On day 20, we buy a one day pass for 2 which would cover day 20.
On day 30, we buy a one day pass for 2 which would cover day 30.
On day 31, we buy a one day pass for 2 which would cover day 31.
So the total cost is 7 + 7 + 2 + 2 + 2 => 20.
I am going to use recursion, because I am going to use recursion. And that is because I am... (You get the point, surely.)
File: travel-expenditure (partial)
#! /usr/bin/env raku
unit sub MAIN ($costs, $days, :v(:$verbose)); # [1]
my @costs = $costs.words>>.Numeric; # [2]
die "Specify three costs" unless @costs.elems == 3; # [3]
die "Costs must be numeric" unless all(@costs) ~~ Numeric; # [4]
my %costs = ( 1 => @costs[0], 7 => @costs[1], 30 => @costs[2] ); # [5]
my @days = $days.words>>.UInt; # [6]
die "The days must be positive integers (1..366)" # [7]
unless all(@days) ~~ UInt && 1 <= all(@days) <= 366;
my @res = gather # [8]
{
recurse(log => (), total-cost => 0, todo => @days.sort); # [9]
}
my $lowest = Inf; # [10]
for @res -> $row # [11]
{
print ": Cost: $row{'cost'}" if $verbose;
if $row{'cost'} < $lowest # [12]
{
$lowest = $row{'cost'}; # [12a]
say " - new lowest" if $verbose;
}
elsif $verbose
{
say "";
}
if $verbose
{
for @($row{'log'}) -> $log
{
say ": - $log";
}
say "";
}
}
say $lowest; # [13]
[1] The costs and days as separate space separated strings.
[2] Split the costs into seperate values (with words)
and coerce those values to numbers (from the default string we get
by words). This will cause a run time error if the
coersion fails, but that does not matter. Yet./p>
Coercing the input to Numeric (or UInt in [6])
will fail when passed an un-coercable value. But the failure will only happen
when we use the value, as we do in the error checking ([4] and [7]).
Note that REPL mode tricks you up here, as it prints the last value, thus usually triggering an exception up front - what you would expect if you are not familiar with Raku Deferriment.
See e.g. my Dynamic Zero with Raku article for more details.
[3] The cost array must have exactly three elements.
[4] All the values must be numeric. This will trigger a deferred error from the coersion in [2] if they are not.
[5] Set up the costs as a hash, with the number of days as keys.
[6] Get the days, coerced to integers.
[7] This will also potentially trigger a deferred error (from [6]). Also note the chained comparison to ensure that the day numbers are reasonable (1..366; in case of a leap year).
[8] Using gather/take to set
up the sequence (of possible combinations) is ideal here, as we return values
(with take) are returned (so to speak) inside a recursive procedure
- one at a time. Be aware that this is a brute force approach, which potenially
will do a lot of computations (as shown when using verbose mode on the second
example).
See my Raku Gather,
I Take article or
docs.raku.org/syntax/gather take for more information about
gather/take.
[9] Off we go, recursively. The procedure uses named arguments; «log» is an array of verbose explanation, «total-cost» is the total cost so far, and «todo» is a (sorted) list of days yet to parse.
The result of the block in [8] and [9] is an array of values, returned one at a
time by take somewhere in the recursive procedure. We will get back
to that later.
[10] We are looking for the (or a) solution with the lowest total cost. So we start off with the highest possible value.
[11] Iterate over the results.
[12] Each result is a hash. Look up the cost, and save that as the current lowest cost if it is lower than the previously lowest value.
[13] Print the total cost.
File: travel-expenditure (the rest)
sub recurse (:@log, :$total-cost, :@todo is copy) # [14]
{
my $today = @todo.shift; # [15]
for 1,7,30 -> $days # [16]
{
my $paid = $total-cost + %costs{$days}; # [17]
my $paid-to = $today + $days; # [18]
my @covered = ($today,); # [19]
my @new-todo = @todo.clone; # [20]
my @new-log = @log.clone; # [21]
while @todo.elems && @todo[0] < $paid-to # [22]
{
@covered.push: @todo.shift;
}
@new-log.push: "At day $today pay for $days day(s) ({ @covered.join(",") })";
if @todo.elems # [23]
{
recurse(log => @new-log, total-cost => $paid, todo => @new-todo)
}
else # [24]
{
take { cost => $paid, log => @new-log };
}
}
}
[14] The signature of the procedure. Note the : prefixes,
indicating named arguments.
[15] Start with the first non-parsed day.
[16] Iterate over the different ticket period types.
[17] The cost so far, including this ticket.
[18] The last day of the current ticket period.
[19] The days (given by the user) that are covered by the current ticket will end up here (for verbose output usage).
[20] Get a copy of this one, as we are removing values from it (in [22]) that should only apply inside the scope of the current iteration of the for loop.
[21] Ditto, but we are adding to this one.
[22] As long as the first unparsed day is covered by the current ticket, move the day from the todo list to the list of covered dates.
[23] Have we covered all the dates? If not, go on recursively (until we do so).
[24] If we have, return the cost and log lines (with take).
Running it:
$ ./travel-expenditure "5 30 90" "1 3 4 5 6"
25
$ ./travel-expenditure "2 7 25" "1 5 6 7 9 15"
12
$ ./travel-expenditure "2 7 25" "1 2 3 5 7 10 11 12 14 20 30 31"
20
Looking good. (The first one is the unnumbered example in the challenge text, perhaps a candidate for the «example 0» moniker.)
With verbose mode:
$ ./travel-expenditure -v "5 30 90" "1 3 4 5 6"
: Cost: 25 - new lowest
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 1 day(s) (3)
: - At day 4 pay for 1 day(s) (4)
: - At day 5 pay for 1 day(s) (5)
: - At day 6 pay for 1 day(s) (6)
: Cost: 50
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 1 day(s) (3)
: - At day 4 pay for 1 day(s) (4)
: - At day 5 pay for 1 day(s) (5)
: - At day 6 pay for 7 day(s) (6)
: Cost: 110
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 1 day(s) (3)
: - At day 4 pay for 1 day(s) (4)
: - At day 5 pay for 1 day(s) (5)
: - At day 6 pay for 30 day(s) (6)
: Cost: 45
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 1 day(s) (3)
: - At day 4 pay for 1 day(s) (4)
: - At day 5 pay for 7 day(s) (5,6)
: Cost: 105
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 1 day(s) (3)
: - At day 4 pay for 1 day(s) (4)
: - At day 5 pay for 30 day(s) (5,6)
: Cost: 40
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 1 day(s) (3)
: - At day 4 pay for 7 day(s) (4,5,6)
: Cost: 100
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 1 day(s) (3)
: - At day 4 pay for 30 day(s) (4,5,6)
: Cost: 35
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 7 day(s) (3,4,5,6)
: Cost: 95
: - At day 1 pay for 1 day(s) (1)
: - At day 3 pay for 30 day(s) (3,4,5,6)
: Cost: 30
: - At day 1 pay for 7 day(s) (1,3,4,5,6)
: Cost: 90
: - At day 1 pay for 30 day(s) (1,3,4,5,6)
25
The first example produces 132 lines of verbose output, so I have removed most of them:
$ ./travel-expenditure -v "2 7 25" "1 5 6 7 9 15"
...
: Cost: 11 - new lowest
: - At day 1 pay for 1 day(s) (1)
: - At day 5 pay for 7 day(s) (5,6,7,9)
: - At day 15 pay for 1 day(s) (15)
...
11
The second example produces a staggering 2517 lines of verbose output, so here is the relevant part:
$ ./travel-expenditure -v "2 7 25" "1 2 3 5 7 10 11 12 14 20 30 31"
...
: Cost: 20 - new lowest
: - At day 1 pay for 7 day(s) (1,2,3,5,7)
: - At day 10 pay for 7 day(s) (10,11,12,14)
: - At day 20 pay for 1 day(s) (20)
: - At day 30 pay for 1 day(s) (30)
: - At day 31 pay for 1 day(s) (31)
...
20
And that's it.