by Arne Sommer

# Sorted Expenditure with Raku

[239] Published 31. May 2023.

This is my response to The Weekly Challenge #219.

## Challenge #219.1: Sorted Squares

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

## Challenge #219.2: Travel Expenditure

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)

```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>

#### Deferred Errors

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.

[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.