From 8f0fd6660f94577761bccdc707281d0b2a88f157 Mon Sep 17 00:00:00 2001 From: rir Date: Wed, 31 May 2023 14:49:05 -0400 Subject: 219 --- challenge-219/0rir/raku/algorithm-2.txt | 28 ++++++ challenge-219/0rir/raku/ch-1.raku | 38 ++++++++ challenge-219/0rir/raku/ch-2.raku | 149 ++++++++++++++++++++++++++++++++ 3 files changed, 215 insertions(+) create mode 100644 challenge-219/0rir/raku/algorithm-2.txt create mode 100644 challenge-219/0rir/raku/ch-1.raku create mode 100644 challenge-219/0rir/raku/ch-2.raku diff --git a/challenge-219/0rir/raku/algorithm-2.txt b/challenge-219/0rir/raku/algorithm-2.txt new file mode 100644 index 0000000000..7365b4aba0 --- /dev/null +++ b/challenge-219/0rir/raku/algorithm-2.txt @@ -0,0 +1,28 @@ +https://cs.stackexchange.com/questions/59797/minimizing-cost-of-bus-travel +gnasher729, Jun 21, 2016 at 20:23 +retrieved May 30, 2023 07:44:03 EDT +:::: +int n = 6; +int dates [n+1] = { 1, 3, 5, 8, 9, 10, infinity }; +int ticket [n]; +int cost [n+1]; + +cost [n] = 0; + +for i = n-1 downto 0 + cost for 1 day = 2 + cost [i+1] + let k7 = smallest k where dates [k] ≥ dates [i] + 7 + cost for 7 day = 7 + cost [k7] + let k30 = smallest k where dates [k] ≥ dates [i] + 30 + cost for 30 days = 25 + cost [k30] + + if cost for 1 day is smallest + ticket [i] = 1 + cost [i] = cost for 1 day + else if cost for 7 day is smallest + ticket [i] = 7 + cost [i] = cost for 7 days + else + ticket [i] = 30 + cost [i] = cost for 30 days + endif diff --git a/challenge-219/0rir/raku/ch-1.raku b/challenge-219/0rir/raku/ch-1.raku new file mode 100644 index 0000000000..121e1887fc --- /dev/null +++ b/challenge-219/0rir/raku/ch-1.raku @@ -0,0 +1,38 @@ +#!/usr/bin/env raku +# :vim ft=raku sw=4 expandtab # 🦋 ∅∪∩∋∈∉ ≡ ≢ «␤ » ∴ +use v6.d; +use lib $?FILE.IO.parent(2).add("lib"); +use Test; + +=begin comment +219-1: Sorted Squares Submitted by: Mohammad S Anwar +Given a list of numbers, 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) + +=end comment + +my @Test = + (-2, -1, 0, 3, 4), (0, 1, 4, 9, 16), + (5, -4, -1, 3, 6), (1, 9, 16, 25, 36), +; + +plan +@Test ÷ 2; + +sub square-sort( @l -->Seq) { @l.map(*²).sort; } + +for @Test -> @in, @exp { + is square-sort(@in), @exp, "@exp[]\t<- @in[]"; +} +done-testing; + +my @list = (5, -5, -100, 101, 3, 6); +say "\nInput: @list = @list[]\nOutput: &square-sort( @list)"; +exit; + diff --git a/challenge-219/0rir/raku/ch-2.raku b/challenge-219/0rir/raku/ch-2.raku new file mode 100644 index 0000000000..a1cae289fb --- /dev/null +++ b/challenge-219/0rir/raku/ch-2.raku @@ -0,0 +1,149 @@ +#!/usr/bin/env raku +# :vim ft=raku sw=4 expandtab # 🦋 ∅∪∩∋∈∉ ≡ ≢ «␤ » ∴ +use v6.d; +use Test; + +=begin comment +219-2: Travel Expenditure Submitted by: Mohammad S Anwar +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. +=end comment + +# For an array of travel dates (here day-numbers), a set of 3 prices and +# durations for travel passes, determine the lowest cost for all scheduled +# travel. +# +# TODO for usefulness: +# 1) use real Date dates +# 2) eliminate three-duration constraint, # Args for 2,3 or 3,2 +# 3) consolidate @price & @span into a Pass type, +# 4) fancies like passes for a set period or set periods, +# + +sub thrifty-pass( @travel-date, @price, @span -->Real) { + # The three sisters. + my @date = @travel-date; # value is date + my @cost; # value is date's expenditure + my @ticket; # value is date's type of ticket + + @date.push: ∞; # A sink-hole in which to bury long look-a-heads. + enum span < Day Week Mo >; + my @cur-cost; # candidate costs [day,week,month] for a @date element + + @cost[@date.end] = 0; # starting cost (in sink-hole) + + for (@date.end-1)…0 -> $i { + @cur-cost[Day] = @price[Day] + @cost[$i+1]; + + my $idx-wk-later = @date.first( * ≥ @date[$i] + @span[Week], :k); + @cur-cost[Week] = @price[Week] + @cost[$idx-wk-later]; + + my $idx-mo-later = @date.first( * ≥ @date[$i] + @span[Mo], :k); + @cur-cost[Mo] = @price[Mo] + @cost[$idx-mo-later]; + + given @cur-cost.min { + when @cur-cost[Day] { + @ticket[$i] = @span[Day]; + @cost[$i] = @cur-cost[Day]; + } + when @cur-cost[Week] { + @ticket[$i] = @span[Week]; + @cost[$i] = @cur-cost[Week]; + } + when @cur-cost[Mo] { + @ticket[$i] = @span[Mo]; + @cost[$i] = @cur-cost[Mo]; + } + default { die "bad programmer" } + } + } + return @cost[0]; +} + + +my @Test = +# spans prices ydays cost + + # varied prices + [[1,7,30], [2,5,20], [39,53,174,202,208,240,244,278,340,342], 20,], + [[1,7,30], [2,6,19], [1,2,3,5,7,10,11,12,14,20,30], 16,], + [[1,7,30], [2,7,19], [1,2,3,5,7,10,11,12,14,20,30], 18,], + [[1,7,30], [2,7,13], [1..14], 13,], + [[1,7,30], [2,7,13], [1..31], 15,], + [[1,7,30], [2,7,20], [1..14], 14,], + [[1,7,30], [3,7,19], [1,2,3,5,7,10,11,12,14,20,30], 19,], + [[1,7,30], [3,5,20], [39,53,174,202,208,240,244,278,340,342], 27,], + + # 2 7 25 + [[1,7,30], [2,7,25], [1,], 2,], + [[1,7,30], [2,7,25], [1,2], 4,], + [[1,7,30], [2,7,25], [1..3], 6,], + [[1,7,30], [2,7,25], [1..4], 7,], + [[1,7,30], [2,7,25], [1..7], 7,], + [[1,7,30], [2,7,25], [1..8], 9,], + [[1,7,30], [2,7,25], [1,2,3,5,7,10,11,12,14,20,30,31], 20,], + [[1,7,30], [2,7,25], [1,2,3,5,7,10,11,12,14,20,30,31], 20,], + [[1,7,30], [2,7,25], [39,53,174,202,208,240,244,278,340,342], 20,], + + [[1,7,30], [2,7,25], [ |(1..7), |(10..14), |(30..59), 71, + 194,195,196,197,198,199,200, + 201,202,203,204,205, + 208, 210, 213,214, + 215,216, 219,220,221, + 222, 227,228, + 229,230, + 238], 75,], +; + +plan +@Test; + +for @Test -> ( @span, @price, @travel-day, $cost ) { + is thrifty-pass( @travel-day, @price, @span), $cost, + "$cost <- @travel-day.raku()"; +} + +done-testing; +my @pass = 1,7,30; +my @cost = 2, 7, 25; +my @day = 1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31; + +say "\nInput:\t@pass = @pass.raku()\n\t@cost = @cost.raku()\n\t" + ~ "@day = @day.raku()\nOutput:\t", thrifty-pass( @day, @cost, @pass); +exit; -- cgit From c998666a0a036b559a9886381a5fe9c2809f6582 Mon Sep 17 00:00:00 2001 From: rir Date: Wed, 31 May 2023 23:27:56 -0400 Subject: generalize --- challenge-219/0rir/raku/ch-2.raku | 49 ++++++++++++++------------------------- 1 file changed, 18 insertions(+), 31 deletions(-) diff --git a/challenge-219/0rir/raku/ch-2.raku b/challenge-219/0rir/raku/ch-2.raku index a1cae289fb..1489a8f096 100644 --- a/challenge-219/0rir/raku/ch-2.raku +++ b/challenge-219/0rir/raku/ch-2.raku @@ -50,18 +50,16 @@ So the total cost is 7 + 7 + 2 + 2 + 2 => 20. # durations for travel passes, determine the lowest cost for all scheduled # travel. # -# TODO for usefulness: -# 1) use real Date dates -# 2) eliminate three-duration constraint, # Args for 2,3 or 3,2 -# 3) consolidate @price & @span into a Pass type, -# 4) fancies like passes for a set period or set periods, -# +# TODO toward usefulness: +# 1) Use real Date dates. +# 2) Consolidate @price & @span into a Pass type. +# 3) Fancies like passes for a set period or set periods. sub thrifty-pass( @travel-date, @price, @span -->Real) { - # The three sisters. + # Three sisters. my @date = @travel-date; # value is date my @cost; # value is date's expenditure - my @ticket; # value is date's type of ticket + my @ticket; # value is date's type of ticket, i.e its duration @date.push: ∞; # A sink-hole in which to bury long look-a-heads. enum span < Day Week Mo >; @@ -69,30 +67,19 @@ sub thrifty-pass( @travel-date, @price, @span -->Real) { @cost[@date.end] = 0; # starting cost (in sink-hole) + for (@date.end-1)…0 -> $i { - @cur-cost[Day] = @price[Day] + @cost[$i+1]; - - my $idx-wk-later = @date.first( * ≥ @date[$i] + @span[Week], :k); - @cur-cost[Week] = @price[Week] + @cost[$idx-wk-later]; - - my $idx-mo-later = @date.first( * ≥ @date[$i] + @span[Mo], :k); - @cur-cost[Mo] = @price[Mo] + @cost[$idx-mo-later]; - - given @cur-cost.min { - when @cur-cost[Day] { - @ticket[$i] = @span[Day]; - @cost[$i] = @cur-cost[Day]; - } - when @cur-cost[Week] { - @ticket[$i] = @span[Week]; - @cost[$i] = @cur-cost[Week]; - } - when @cur-cost[Mo] { - @ticket[$i] = @span[Mo]; - @cost[$i] = @cur-cost[Mo]; - } - default { die "bad programmer" } - } + + for ^@span -> $dur-idx { + @cur-cost[$dur-idx] = @price[$dur-idx] + @cost[ + @date.first( * ≥ @date[$i] + @span[$dur-idx], :k) + ]; + } + + my $best = @cur-cost.min; + my $min-k = @cur-cost.first( * == $best, :k); + @ticket[$i] = @span[$min-k]; + @cost[$i] = @cur-cost[$min-k]; } return @cost[0]; } -- cgit