aboutsummaryrefslogtreecommitdiff
path: root/challenge-285/ppentchev/rust/src
diff options
context:
space:
mode:
Diffstat (limited to 'challenge-285/ppentchev/rust/src')
-rw-r--r--challenge-285/ppentchev/rust/src/change.rs188
-rw-r--r--challenge-285/ppentchev/rust/src/defs.rs24
-rw-r--r--challenge-285/ppentchev/rust/src/lib.rs15
-rw-r--r--challenge-285/ppentchev/rust/src/routes.rs49
-rw-r--r--challenge-285/ppentchev/rust/src/tests/change.rs52
-rw-r--r--challenge-285/ppentchev/rust/src/tests/mod.rs9
-rw-r--r--challenge-285/ppentchev/rust/src/tests/routes.rs60
7 files changed, 397 insertions, 0 deletions
diff --git a/challenge-285/ppentchev/rust/src/change.rs b/challenge-285/ppentchev/rust/src/change.rs
new file mode 100644
index 0000000000..0f44915c39
--- /dev/null
+++ b/challenge-285/ppentchev/rust/src/change.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/challenge-285/ppentchev/rust/src/defs.rs b/challenge-285/ppentchev/rust/src/defs.rs
new file mode 100644
index 0000000000..974d9fd653
--- /dev/null
+++ b/challenge-285/ppentchev/rust/src/defs.rs
@@ -0,0 +1,24 @@
+// SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net>
+// SPDX-License-Identifier: BSD-2-Clause
+//! Common definitions for the `perl-weekly` crate.
+
+use anyhow::Error as AnyError;
+use thiserror::Error;
+
+/// An error that occurred during the doing of things.
+#[derive(Debug, Error)]
+#[non_exhaustive]
+#[allow(clippy::error_impl_error)]
+pub enum Error {
+ /// Something went really, really wrong.
+ #[error("fnmatch-regex internal error")]
+ InternalError(#[source] AnyError),
+
+ /// Either no solution or too many solutions or something else.
+ #[error("No solution found: {0}")]
+ NoSolution(String),
+
+ /// Some known missing functionality.
+ #[error("Not implemented yet: {0}")]
+ NotImplemented(String),
+}
diff --git a/challenge-285/ppentchev/rust/src/lib.rs b/challenge-285/ppentchev/rust/src/lib.rs
new file mode 100644
index 0000000000..5b5e0768b0
--- /dev/null
+++ b/challenge-285/ppentchev/rust/src/lib.rs
@@ -0,0 +1,15 @@
+// SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net>
+// SPDX-License-Identifier: BSD-2-Clause
+
+#![deny(missing_docs)]
+#![deny(clippy::missing_docs_in_private_items)]
+//! Solve the tasks in Perl weekly challenge 285.
+
+#![allow(clippy::needless_borrowed_reference)]
+
+pub mod change;
+pub mod defs;
+pub mod routes;
+
+#[cfg(test)]
+mod tests;
diff --git a/challenge-285/ppentchev/rust/src/routes.rs b/challenge-285/ppentchev/rust/src/routes.rs
new file mode 100644
index 0000000000..18ba2b98f9
--- /dev/null
+++ b/challenge-285/ppentchev/rust/src/routes.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/tests/change.rs b/challenge-285/ppentchev/rust/src/tests/change.rs
new file mode 100644
index 0000000000..98927ef23e
--- /dev/null
+++ b/challenge-285/ppentchev/rust/src/tests/change.rs
@@ -0,0 +1,52 @@
+// SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net>
+// SPDX-License-Identifier: BSD-2-Clause
+//! Test the second for week 285, "Making Change".
+
+use anyhow::Result;
+use rstest::rstest;
+use tracing_test::traced_test;
+
+use crate::change::{self, Coin};
+
+/// Check whether we know how to recurse into breaking amounts of money down.
+#[traced_test]
+#[rstest]
+#[case(1, Coin::HalfDollar, &[])]
+#[case(2, Coin::HalfDollar, &[])]
+#[case(6, Coin::HalfDollar, &[(1_u32, Coin::Penny)])]
+#[case(6, Coin::Nickel, &[(1_u32, Coin::Penny)])]
+#[case(6, Coin::Penny, &[])]
+#[case(7, Coin::HalfDollar, &[(2_u32, Coin::Penny)])]
+#[case(7, Coin::Nickel, &[(2_u32, Coin::Penny)])]
+#[case(7, Coin::Penny, &[])]
+#[case(10, Coin::HalfDollar, &[(0_u32, Coin::Nickel), (5_u32, Coin::Penny), (0_u32, Coin::Penny)])]
+#[case(10, Coin::Dime, &[(0_u32, Coin::Nickel), (5_u32, Coin::Penny), (0_u32, Coin::Penny)])]
+#[case(10, Coin::Nickel, &[(5_u32, Coin::Penny), (0_u32, Coin::Penny)])]
+#[case(10, Coin::Penny, &[])]
+#[case(12, Coin::HalfDollar, &[(2_u32, Coin::Nickel), (7_u32, Coin::Penny), (2_u32, Coin::Penny)])]
+#[case(12, Coin::Dime, &[(2_u32, Coin::Nickel), (7_u32, Coin::Penny), (2_u32, Coin::Penny)])]
+#[case(12, Coin::Nickel, &[(7_u32, Coin::Penny), (2_u32, Coin::Penny)])]
+#[case(12, Coin::Penny, &[])]
+#[case(15, Coin::HalfDollar, &[(5_u32, Coin::Nickel), (10_u32, Coin::Penny), (5_u32, Coin::Penny), (0_u32, Coin::Penny)])]
+#[case(15, Coin::Dime, &[(5_u32, Coin::Nickel), (10_u32, Coin::Penny), (5_u32, Coin::Penny), (0_u32, Coin::Penny)])]
+#[case(15, Coin::Nickel, &[(10_u32, Coin::Penny), (5_u32, Coin::Penny), (0_u32, Coin::Penny)])]
+#[case(15, Coin::Penny, &[])]
+fn test_break_down_ways(
+ #[case] amount: u32,
+ #[case] highest: Coin,
+ #[case] expected: &[(u32, Coin)],
+) -> Result<()> {
+ assert_eq!(change::break_down_ways(amount, highest)?, expected);
+ Ok(())
+}
+
+/// Check whether we can calculate the number of ways money can be broken down.
+#[traced_test]
+#[rstest]
+#[case(9, 2)]
+#[case(15, 6)]
+#[case(100, 292)]
+fn test_making_change(#[case] amount: u32, #[case] expected: u32) -> Result<()> {
+ assert_eq!(change::solve_making_change(amount)?, expected);
+ Ok(())
+}
diff --git a/challenge-285/ppentchev/rust/src/tests/mod.rs b/challenge-285/ppentchev/rust/src/tests/mod.rs
new file mode 100644
index 0000000000..a9b7d657c0
--- /dev/null
+++ b/challenge-285/ppentchev/rust/src/tests/mod.rs
@@ -0,0 +1,9 @@
+// SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net>
+// SPDX-License-Identifier: BSD-2-Clause
+//! Test the Perl Weekly Challenge tasks.
+
+#![allow(clippy::print_stdout)]
+#![allow(clippy::panic_in_result_fn)]
+
+mod change;
+mod routes;
diff --git a/challenge-285/ppentchev/rust/src/tests/routes.rs b/challenge-285/ppentchev/rust/src/tests/routes.rs
new file mode 100644
index 0000000000..5f5b98c46c
--- /dev/null
+++ b/challenge-285/ppentchev/rust/src/tests/routes.rs
@@ -0,0 +1,60 @@
+// SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net>
+// SPDX-License-Identifier: BSD-2-Clause
+//! Test the first task for week 285, "No Connection".
+
+use anyhow::{bail, Context, Result};
+use rstest::rstest;
+use tracing_test::traced_test;
+
+use crate::defs::Error;
+use crate::routes;
+
+/// Check whether the first task solver works.
+#[traced_test]
+#[rstest]
+#[case(
+ &[
+ ("me".to_owned(), "you".to_owned()),
+ ],
+ "you",
+)]
+#[case(
+ &[
+ ("here".to_owned(), "there".to_owned()),
+ ("here".to_owned(), "everywhere".to_owned()),
+ ("there".to_owned(), "everywhere".to_owned()),
+ ],
+ "everywhere",
+)]
+#[case(
+ &[("B".to_owned(), "C".to_owned()), ("D".to_owned(), "B".to_owned()), ("C".to_owned(), "A".to_owned())],
+ "A",
+)]
+#[case(&[("A".to_owned(), "Z".to_owned())], "Z")]
+fn test_connection(#[case] routes: &[(String, String)], #[case] expected: &str) -> Result<()> {
+ println!();
+ let found = routes::solve_no_connection(routes).context("Could not solve 285/1")?;
+ assert_eq!(found, expected);
+ Ok(())
+}
+
+/// Check whether the first task solver reports errors as expected.
+#[traced_test]
+#[rstest]
+#[case(&[])]
+#[case(&[
+ ("here".to_owned(), "there".to_owned()),
+ ("here".to_owned(), "everywhere".to_owned()),
+])]
+#[case(&[
+ ("me".to_owned(), "you".to_owned()),
+ ("you".to_owned(), "me".to_owned()),
+])]
+fn test_no_connection(#[case] routes: &[(String, String)]) -> Result<()> {
+ println!();
+ match routes::solve_no_connection(routes) {
+ Ok(res) => bail!("Unexpected success: {res:?}"),
+ Err(Error::NoSolution(_)) => Ok(()),
+ Err(err) => Err(err).context("Unexpected error"),
+ }
+}
generated by cgit (git 2.34.1) at 2026-07-12 18:01:41 +0000