with Raku

This is my response to The Weekly Challenge #219.

You are given a list of numbers.

Write a script to square each number in the list and return the sorted list, increasing order.

Example 1:

Write a script to square each number in the list and return the sorted list, increasing order.

Example 1:

Input: @list = (-2, -1, 0, 3, 4)
Output: (0, 1, 4, 9, 16)

Example 2:
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(", ") ~ ')';

You are given two list, @costs and @days.

The list @costs contains the cost of three different types of travel cards you can buy.

For example @costs = (5, 30, 90)

For example: @days = (1, 3, 4, 5, 6)

The above example means you want to travel on day 1, day 3, day 4, day 5 and day 6 of the year.

Write a script to find the minimum travel cost.

Example 1:

The list @costs contains the cost of three different types of travel cards you can buy.

For example @costs = (5, 30, 90)

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.

The list @days contains the day number you want to travel in the year.
For example: @days = (1, 3, 4, 5, 6)

The above example means you want to travel on day 1, day 3, day 4, day 5 and day 6 of the year.

Write a script to find the minimum travel cost.

Example 1:

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.

Example 2:
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.