- Added solutions by Peter Meszaros.

- Added solutions by Matthew Neleigh.
- Added solutions by Jorg Sommrey.
- Added solutions by Robbie Hatley.
- Added solutions by Robert Ransbottom.
- Added solutions by Torgny Lyon.
- Added solutions by Peter Pentchev.
- Added solutions by Laurent Rosenfeld.

2 files changed, 237 insertions, 0 deletions

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())
+}