diff options
30 files changed, 3711 insertions, 3301 deletions
diff --git a/challenge-285/laurent-rosenfeld/blog1.txt b/challenge-285/laurent-rosenfeld/blog1.txt new file mode 100644 index 0000000000..5c4f2fc8f5 --- /dev/null +++ b/challenge-285/laurent-rosenfeld/blog1.txt @@ -0,0 +1 @@ +https://blogs.perl.org/users/laurent_r/2024/09/perl-weekly-challenge-285-making-change.html diff --git a/challenge-285/laurent-rosenfeld/perl/ch-2.pl b/challenge-285/laurent-rosenfeld/perl/ch-2.pl new file mode 100644 index 0000000000..b3274f4d81 --- /dev/null +++ b/challenge-285/laurent-rosenfeld/perl/ch-2.pl @@ -0,0 +1,30 @@ +use strict; +use warnings; +no warnings 'recursion'; +use feature 'say'; + +my @coins = (50, 25, 10, 5, 1); +my $count; + +sub make_change { + my ($amount, $limit) = @_; + for my $coin (@coins) { + next if $coin > $amount; + # Prevent duplicate combinations in different orders + next if $coin > $limit; + my $rest = $amount - $coin; + if ($rest == 0) { + $count++; + } else { + make_change($rest, $coin); + } + } + return $count; +} + +my @tests = (9, 15, 50, 100); +for my $test (@tests) { + $count = 0; + printf "%-5d => ", $test; + say make_change $test, 50; +} diff --git a/challenge-285/laurent-rosenfeld/raku/ch-2.raku b/challenge-285/laurent-rosenfeld/raku/ch-2.raku new file mode 100644 index 0000000000..ccc486d834 --- /dev/null +++ b/challenge-285/laurent-rosenfeld/raku/ch-2.raku @@ -0,0 +1,24 @@ +my @coins = 50, 25, 10, 5, 1; +my $count; + +sub make-change ($amount, $limit) { + for @coins -> $coin { + next if $coin > $amount; + # Prevent duplicate combinations in different orders + next if $coin > $limit; + my $rest = $amount - $coin; + if $rest == 0 { + $count++; + } else { + make-change($rest, $coin); + } + } + return $count; +} + +my @tests = 9, 15, 100; +for @tests -> $test { + $count = 0; + printf "%-5d => ", $test; + say make-change $test, 50; +} diff --git a/challenge-285/ppentchev/rust/src/ch-1.rs b/challenge-285/ppentchev/rust/src/ch-1.rs new file mode 100644 index 0000000000..18ba2b98f9 --- /dev/null +++ b/challenge-285/ppentchev/rust/src/ch-1.rs @@ -0,0 +1,49 @@ +// SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> +// SPDX-License-Identifier: BSD-2-Clause +//! Solve the first task for week 285, "No Connection". + +use std::collections::HashSet; + +use tracing::{debug, trace}; + +use crate::defs::Error; + +/// Week 285 task 1: No Connection. +/// +/// # Errors +/// +/// [`Error::NotImplemented`] so far. +#[tracing::instrument(skip(routes))] +#[inline] +pub fn solve_no_connection(routes: &[(String, String)]) -> Result<String, Error> { + debug!( + "About to look for a leaf destination in {count} routes", + count = routes.len() + ); + let (set_from, set_to) = routes.iter().fold( + (HashSet::new(), HashSet::new()), + |(mut set_from, mut set_to): (HashSet<&str>, HashSet<&str>), + &(ref route_from, ref route_to)| { + set_from.insert(route_from.as_ref()); + set_to.insert(route_to.as_ref()); + (set_from, set_to) + }, + ); + trace!("from: {count}", count = set_from.len()); + trace!("to: {count}", count = set_to.len()); + + let mut diff = set_to.difference(&set_from); + let first = diff + .next() + .ok_or_else(|| Error::NoSolution("Not even a single leaf destination".to_owned()))?; + trace!(first); + diff.next().map_or_else( + || Ok((*first).to_owned()), + |second| { + trace!(second); + Err(Error::NoSolution( + "More than one leaf destination".to_owned(), + )) + }, + ) +} diff --git a/challenge-285/ppentchev/rust/src/ch-2.rs b/challenge-285/ppentchev/rust/src/ch-2.rs new file mode 100644 index 0000000000..0f44915c39 --- /dev/null +++ b/challenge-285/ppentchev/rust/src/ch-2.rs @@ -0,0 +1,188 @@ +// SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> +// SPDX-License-Identifier: BSD-2-Clause +//! Solve the second for week 285, "Making Change". + +use std::collections::HashMap; +use std::fmt::{Display, Formatter, Result as FmtResult}; + +use anyhow::{anyhow, Context}; +use itertools::Itertools; +use tracing::{debug, trace}; + +use crate::defs::Error; + +/// The coin denominations. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +#[allow(clippy::exhaustive_enums)] +pub enum Coin { + /// A penny (1c). + Penny, + + /// A nickel (5c). + Nickel, + + /// A dime (10c). + Dime, + + /// A quarter (25c). + Quarter, + + /// A half-dollar (50c). + HalfDollar, +} + +impl Coin { + /// The coin denominations from highest to lowest, except for the penny. + /// + /// The penny is excluded because we don't want to return it in the recursive + /// breakdown processing. + const ORDER_ABP: [Self; 4] = [Self::HalfDollar, Self::Quarter, Self::Dime, Self::Nickel]; + + /// The name of a penny. + pub const PENNY: &'static str = "penny"; + + /// The name of a nickel. + pub const NICKEL: &'static str = "nickel"; + + /// The name of a dime. + pub const DIME: &'static str = "dime"; + + /// The name of a quarter. + pub const QUARTER: &'static str = "quarter"; + + /// The name of a half dollar. + pub const HALF_DOLLAR: &'static str = "half dollar"; + + /// The numeric value of a coin. + #[inline] + #[must_use] + pub const fn value(&self) -> u32 { + match *self { + Self::Penny => 1, + Self::Nickel => 5, + Self::Dime => 10, + Self::Quarter => 25, + Self::HalfDollar => 50, + } + } + + /// The next step down. + /// + /// # Errors + /// + /// [`Error::InternalError`] if this is invoked for [`Coin::Penny`]. + #[inline] + pub fn lower(&self) -> Result<Self, Error> { + match *self { + Self::Penny => Err(Error::InternalError(anyhow!( + "Coin::lower() should never be asked about a penny" + ))), + Self::Nickel => Ok(Self::Penny), + Self::Dime => Ok(Self::Nickel), + Self::Quarter => Ok(Self::Dime), + Self::HalfDollar => Ok(Self::Quarter), + } + } +} + +impl AsRef<str> for Coin { + #[inline] + fn as_ref(&self) -> &str { + match *self { + Self::Penny => Self::PENNY, + Self::Nickel => Self::NICKEL, + Self::Dime => Self::DIME, + Self::Quarter => Self::QUARTER, + Self::HalfDollar => Self::HALF_DOLLAR, + } + } +} + +impl Display for Coin { + #[inline] + #[allow(clippy::min_ident_chars)] + fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult { + write!(f, "{value}", value = self.as_ref()) + } +} + +/// Prepare to recurse into breaking an amount of money down into parts. +/// +/// Return the different ways of breaking down into smaller coins except for pennies-only. +#[tracing::instrument] +pub fn break_down_ways(amount: u32, highest: Coin) -> Result<Vec<(u32, Coin)>, Error> { + Coin::ORDER_ABP + .iter() + .filter(|coin| **coin <= highest) + .map(|coin| -> Result<Vec<(u32, Coin)>, Error> { + trace!(?coin); + let value = coin.value(); + trace!(value); + let lower = coin.lower()?; + trace!(?lower); + let step = usize::try_from(value) + .with_context(|| format!("Could not convert {value} to usize")) + .map_err(Error::InternalError)?; + Ok((value..) + .step_by(step) + .map_while(|used| amount.checked_sub(used).map(|rem| (rem, lower))) + .collect()) + }) + .flatten_ok() + .collect::<Result<_, _>>() +} + +/// Figure out whether the set of parameters trivially resolves to a single solution. +fn trivial(amount: u32, highest: Coin) -> bool { + highest == Coin::Penny || amount == 0 +} + +/// Recurse into breaking an amount of money down into parts. +/// +/// Count the different ways of breaking down into smaller coins, pennies-only included. +#[tracing::instrument] +pub fn make_change_rec( + amount: u32, + highest: Coin, + cache: &mut HashMap<(u32, Coin), u32>, +) -> Result<u32, Error> { + if trivial(amount, highest) { + return Ok(1); + } + if let Some(seen) = cache.get(&(amount, highest)) { + return Ok(*seen); + } + + let ways = break_down_ways(amount, highest)?; + trace!(?ways); + let (sum, upd_cache) = ways.into_iter().try_fold( + (1_u32, cache), + |(sum, current_cache), (b_amount, b_highest)| { + let current = if trivial(b_amount, b_highest) { + 1_u32 + } else { + make_change_rec(b_amount, b_highest, current_cache)? + }; + + let upd_sum = sum + .checked_add(current) + .ok_or_else(|| Error::InternalError(anyhow!("Could not add {current} to {sum}")))?; + Ok((upd_sum, current_cache)) + }, + )?; + trace!(sum); + upd_cache.insert((amount, highest), sum); + Ok(sum) +} + +/// Week 285 task 2: Making Change. +/// +/// # Errors +/// +/// [`Error::NotImplemented`] so far. +#[tracing::instrument] +#[inline] +pub fn solve_making_change(amount: u32) -> Result<u32, Error> { + debug!("About to break {amount} cents down"); + make_change_rec(amount, Coin::HalfDollar, &mut HashMap::new()) +} diff --git a/guests.json b/guests.json index 5887d2baaf..987caa137a 100644 --- a/guests.json +++ b/guests.json @@ -17,6 +17,7 @@ "mfoda" : "Mohammad Foda", "michael-dicicco" : "Michael DiCicco", "orestis-zekai" : "Orestis Zekai", + "ppentchev" : "Peter Pentchev", "pieviero" : "Tymoteusz Moryto", "probablyfine" : "Alex Wilson", "geekruthie" : "Ruth Holloway", diff --git a/stats/pwc-challenge-203.json b/stats/pwc-challenge-203.json index a951eb0993..a611ed83d9 100644 --- a/stats/pwc-challenge-203.json +++ b/stats/pwc-challenge-203.json @@ -1,42 +1,31 @@ { "subtitle" : { - "text" : "[Champions: 36] Last updated at 2024-07-29 17:29:09 GMT" + "text" : "[Champions: 37] Last updated at 2024-09-07 14:50:53 GMT" }, - "tooltip" : { - "headerFormat" : "<span style='font-size:11px'>{series.name}</span><br/>", - "followPointer" : 1, - "pointFormat" : "<span style='color:{point.color}'>{point.name}</span>: <b>{point.y:f}</b><br/>" + "chart" : { + "type" : "column" }, "xAxis" : { "type" : "category" }, - "title" : { - "text" : "The Weekly Challenge - 203" - }, - "plotOptions" : { - "series" : { - "dataLabels" : { - "enabled" : 1, - "format" : "{point.y}" - }, - "borderWidth" : 0 + "yAxis" : { + "title" : { + "text" : "Total Solutions" } }, - "chart" : { - "type" : "column" - }, "series" : [ { + "name" : "The Weekly Challenge - 203", "data" : [ { "drilldown" : "Adam Russell", - "y" : 2, - "name" : "Adam Russell" + "name" : "Adam Russell", + "y" : 2 }, { - "name" : "Arne Sommer", "y" : 3, - "drilldown" : "Arne Sommer" + "drilldown" : "Arne Sommer", + "name" : "Arne Sommer" }, { "name" : "Athanasius", @@ -45,43 +34,43 @@ }, { "name" : "BarrOff", - "y" : 2, - "drilldown" : "BarrOff" + "drilldown" : "BarrOff", + "y" : 2 }, { - "name" : "Bob Lied", + "y" : 2, "drilldown" : "Bob Lied", - "y" : 2 + "name" : "Bob Lied" }, { "drilldown" : "Carlos Oliveira", - "y" : 2, - "name" : "Carlos Oliveira" + "name" : "Carlos Oliveira", + "y" : 2 }, { - "name" : "Cheok-Yin Fung", + "y" : 1, "drilldown" : "Cheok-Yin Fung", - "y" : 1 + "name" : "Cheok-Yin Fung" }, { + "name" : "Chicagoist", "drilldown" : "Chicagoist", - "y" : 2, - "name" : "Chicagoist" + "y" : 2 }, { - "name" : "Colin Crain", "y" : 2, + "name" : "Colin Crain", "drilldown" : "Colin Crain" }, { "y" : 3, - "drilldown" : "Dave Jacoby", - "name" : "Dave Jacoby" + "name" : "Dave Jacoby", + "drilldown" : "Dave Jacoby" }, { "y" : 2, - "drilldown" : "David Ferrone", - "name" : "David Ferrone" + "name" : "David Ferrone", + "drilldown" : "David Ferrone" }, { "y" : 2, @@ -89,33 +78,33 @@ "name" : "Duncan C. White" }, { - "drilldown" : "E. Choroba", "y" : 2, + "drilldown" : "E. Choroba", "name" : "E. Choroba" }, { + "y" : 2, "name" : "Feng Chang", - "drilldown" : "Feng Chang", - "y" : 2 + "drilldown" : "Feng Chang" }, { - "y" : 6, "drilldown" : "Flavio Poletti", - "name" : "Flavio Poletti" + "name" : "Flavio Poletti", + "y" : 6 }, { "y" : 3, - "drilldown" : "James Smith", - "name" : "James Smith" + "name" : "James Smith", + "drilldown" : "James Smith" }, { "y" : 2, - "drilldown" : "Jan Krnavek", - "name" : "Jan Krnavek" + "name" : "Jan Krnavek", + "drilldown" : "Jan Krnavek" }, { - "drilldown" : "Jorg Sommrey", "y" : 2, + "drilldown" : "Jorg Sommrey", "name" : "Jorg Sommrey" }, { @@ -124,39 +113,44 @@ "y" : 2 }, { + "name" : "Laurent Rosenfeld", "drilldown" : "Laurent Rosenfeld", - "y" : 5, - "name" : "Laurent Rosenfeld" + "y" : 5 }, { - "name" : "Lubos Kolouch", "y" : 2, - "drilldown" : "Lubos Kolouch" + "drilldown" : "Lubos Kolouch", + "name" : "Lubos Kolouch" }, { - "y" : 8, "drilldown" : "Luca Ferrari", - "name" : "Luca Ferrari" + "name" : "Luca Ferrari", + "y" : 8 }, { + "name" : "Mariano Spadaccini", "drilldown" : "Mariano Spadaccini", - "y" : 2, - "name" : "Mariano Spadaccini" + "y" : 2 }, { - "name" : "Mark Anderson", "y" : 2, + "name" : "Mark Anderson", "drilldown" : "Mark Anderson" }, { - "drilldown" : "Paulo Custodio", "y" : 2, + "drilldown" : "Paulo Custodio", "name" : "Paulo Custodio" }, { + "y" : 3, "name" : "Peter Campbell Smith", - "drilldown" : "Peter Campbell Smith", - "y" : 3 + "drilldown" : "Peter Campbell Smith" + }, + { + "drilldown" : "Peter Meszaros", + "name" : "Peter Meszaros", + "y" : 2 }, { "name" : "Pip Stuart", @@ -164,14 +158,14 @@ "y" : 4 }, { - "name" : "Robbie Hatley", "y" : 3, - "drilldown" : "Robbie Hatley" + "drilldown" : "Robbie Hatley", + "name" : "Robbie Hatley" }, { + "drilldown" : "Robert DiCicco", "name" : "Robert DiCicco", - "y" : 2, - "drilldown" : "Robert DiCicco" + "y" : 2 }, { "name" : "Robert Ransbottom", @@ -179,24 +173,24 @@ "y" : 2 }, { - "name" : "Roger Bell_West", + "y" : 5, "drilldown" : "Roger Bell_West", - "y" : 5 + "name" : "Roger Bell_West" }, { "y" : 1, - "drilldown" : "Simon Green", - "name" : "Simon Green" + "name" : "Simon Green", + "drilldown" : "Simon Green" }, { - "drilldown" : "Solathian", "y" : 2, - "name" : "Solathian" + "name" : "Solathian", + "drilldown" : "Solathian" }, { + "y" : 4, "name" : "Thomas Kohler", - "drilldown" : "Thomas Kohler", - "y" : 4 + "drilldown" : "Thomas Kohler" }, { "y" : 2, @@ -209,26 +203,35 @@ "y" : 3 } ], - "name" : "The Weekly Challenge - 203", "colorByPoint" : 1 } ], + "title" : { + "text" : "The Weekly Challenge - 203" + }, + "tooltip" : { + "pointFormat" : "<span style='color:{point.color}'>{point.name}</span>: <b>{point.y:f}</b><br/>", + "followPointer" : 1, + "headerFormat" : "<span style='font-size:11px'>{series.name}</span><br/>" + }, "legend" : { "enabled" : 0 }, "drilldown" : { "series" : [ { - "id" : "Adam Russell", - "name" : "Adam Russell", "data" : [ [ "Perl", 2 ] - ] + ], + "id" : "Adam Russell", + "name" : "Adam Russell" }, { + "name" : "Arne Sommer", + "id" : "Arne Sommer", "data" : [ [ "Raku", @@ -238,9 +241,7 @@ "Blog", 1 ] - ], - "name" : "Arne Sommer", - "id" : "Arne Sommer" + ] }, { "name" : "Athanasius", @@ -257,54 +258,54 @@ ] }, { + "name" : "BarrOff", + "id" : "BarrOff", "data" : [ [ "Raku", 2 ] - ], - "name" : "BarrOff", - "id" : "BarrOff" + ] }, { - "id" : "Bob Lied", - "name" : "Bob Lied", "data" : [ [ "Perl", 2 ] - ] + ], + "name" : "Bob Lied", + "id" : "Bob Lied" }, { - "id" : "Carlos Oliveira", - "name" : "Carlos Oliveira", "data" : [ [ "Perl", 2 ] - ] + ], + "id" : "Carlos Oliveira", + "name" : "Carlos Oliveira" }, { - "name" : "Cheok-Yin Fung", - "id" : "Cheok-Yin Fung", "data" : [ [ "Perl", 1 ] - ] + ], + "name" : "Cheok-Yin Fung", + "id" : "Cheok-Yin Fung" }, { - "id" : "Chicagoist", - "name" : "Chicagoist", "data" : [ [ "Perl", 2 ] - ] + ], + "id" : "Chicagoist", + "name" : "Chicagoist" }, { "data" : [ @@ -317,8 +318,6 @@ "name" : "Colin Crain" }, { - "name" : "Dave Jacoby", - "id" : "Dave Jacoby", "data" : [ [ "Perl", @@ -328,11 +327,13 @@ "Blog", 1 ] - ] + ], + "name" : "Dave Jacoby", + "id" : "Dave Jacoby" }, { - "id" : "David Ferrone", "name" : "David Ferrone", + "id" : "David Ferrone", "data" : [ [ "Perl", @@ -341,24 +342,24 @@ ] }, { + "id" : "Duncan C. White", + "name" : "Duncan C. White", "data" : [ [ "Perl", 2 ] - ], - "name" : "Duncan C. White", - "id" : "Duncan C. White" + ] }, { - "name" : "E. Choroba", - "id" : "E. Choroba", "data" : [ [ "Perl", 2 ] - ] + ], + "name" : "E. Choroba", + "id" : "E. Choroba" }, { "data" : [ @@ -371,6 +372,8 @@ "id" : "Feng Chang" }, { + "id" : "Flavio Poletti", + "name" : "Flavio Poletti", "data" : [ [ "Perl", @@ -384,11 +387,11 @@ "Blog", 2 ] - ], - "id" : "Flavio Poletti", - "name" : "Flavio Poletti" + ] }, { + "name" : "James Smith", + "id" : "James Smith", "data" : [ [ "Perl", @@ -398,9 +401,7 @@ "Blog", 1 ] - ], - "name" : "James Smith", - "id" : "James Smith" + ] }, { "data" : [ @@ -423,14 +424,14 @@ ] }, { + "id" : "Kjetil Skotheim", + "name" : "Kjetil Skotheim", "data" : [ [ "Perl", 2 ] - ], - "name" : "Kjetil Skotheim", - "id" : "Kjetil Skotheim" + ] }, { "data" : [ @@ -451,18 +452,16 @@ "name" : "Laurent Rosenfeld" }, { - "id" : "Lubos Kolouch", - "name" : "Lubos Kolouch", "data" : [ [ "Perl", 2 ] - ] + ], + "id" : "Lubos Kolouch", + "name" : "Lubos Kolouch" }, { - "id" : "Luca Ferrari", - "name" : "Luca Ferrari", "data" : [ [ "Raku", @@ -472,7 +471,9 @@ "Blog", 6 ] - ] + ], + "id" : "Luca Ferrari", + "name" : "Luca Ferrari" }, { "data" : [ @@ -485,28 +486,28 @@ "name" : "Mariano Spadaccini" }, { - "id" : "Mark Anderson", - "name" : "Mark Anderson", "data" : [ [ "Raku", 2 ] - ] + ], + "id" : "Mark Anderson", + "name" : "Mark Anderson" }, { + "id" : "Paulo Custodio", + "name" : "Paulo Custodio", "data" : [ [ "Perl", 2 ] - ], - "name" : "Paulo Custodio", - "id" : "Paulo Custodio" + ] }, { - "name" : "Peter Campbell Smith", "id" : "Peter Campbell Smith", + "name" : "Peter Campbell Smith", "data" : [ [ "Perl", @@ -523,6 +524,16 @@ [ "Perl", 2 + ] + ], + "id" : "Peter Meszaros", + "name" : "Peter Meszaros" + }, + { + "data" : [ + [ + "Perl", + 2 ], [ "Raku", @@ -543,10 +554,12 @@ 1 ] ], - "id" : "Robbie Hatley", - "name" : "Robbie Hatley" + "name" : "Robbie Hatley", + "id" : "Robbie Hatley" }, { + "id" : "Robert DiCicco", + |