diff options
| -rw-r--r-- | challenge-285/ppentchev/rust/Cargo.lock | 512 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/Cargo.toml | 25 | ||||
| -rwxr-xr-x | challenge-285/ppentchev/rust/run-clippy.sh | 70 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/src/change.rs | 188 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/src/defs.rs | 24 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/src/lib.rs | 15 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/src/routes.rs | 49 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/src/tests/change.rs | 52 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/src/tests/mod.rs | 9 | ||||
| -rw-r--r-- | challenge-285/ppentchev/rust/src/tests/routes.rs | 60 |
10 files changed, 1004 insertions, 0 deletions
diff --git a/challenge-285/ppentchev/rust/Cargo.lock b/challenge-285/ppentchev/rust/Cargo.lock new file mode 100644 index 0000000000..9f27053341 --- /dev/null +++ b/challenge-285/ppentchev/rust/Cargo.lock @@ -0,0 +1,512 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "aho-corasick" +version = "1.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8e60d3430d3a69478ad0993f19238d2df97c507009a52b3c10addcd7f6bcb916" +dependencies = [ + "memchr", +] + +[[package]] +name = "anyhow" +version = "1.0.87" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "10f00e1f6e58a40e807377c75c6a7f97bf9044fab57816f2414e6f5f4499d7b8" + +[[package]] +name = "autocfg" +version = "1.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0c4b4d0bd25bd0b74681c0ad21497610ce1b7c91b1022cd21c80c6fbdd9476b0" + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "either" +version = "1.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "60b1af1c220855b6ceac025d3f6ecdd2b7c4894bfe9cd9bda4fbb4bc7c0d4cf0" + +[[package]] +name = "futures" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "645c6916888f6cb6350d2550b80fb63e734897a8498abe35cfb732b6487804b0" +dependencies = [ + "futures-channel", + "futures-core", + "futures-executor", + "futures-io", + "futures-sink", + "futures-task", + "futures-util", +] + +[[package]] +name = "futures-channel" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eac8f7d7865dcb88bd4373ab671c8cf4508703796caa2b1985a9ca867b3fcb78" +dependencies = [ + "futures-core", + "futures-sink", +] + +[[package]] +name = "futures-core" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dfc6580bb841c5a68e9ef15c77ccc837b40a7504914d52e47b8b0e9bbda25a1d" + +[[package]] +name = "futures-executor" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a576fc72ae164fca6b9db127eaa9a9dda0d61316034f33a0a0d4eda41f02b01d" +dependencies = [ + "futures-core", + "futures-task", + "futures-util", +] + +[[package]] +name = "futures-io" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a44623e20b9681a318efdd71c299b6b222ed6f231972bfe2f224ebad6311f0c1" + +[[package]] +name = "futures-macro" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "87750cf4b7a4c0625b1529e4c543c2182106e4dedc60a2a6455e00d212c489ac" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "futures-sink" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9fb8e00e87438d937621c1c6269e53f536c14d3fbd6a042bb24879e57d474fb5" + +[[package]] +name = "futures-task" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38d84fa142264698cdce1a9f9172cf383a0c82de1bddcf3092901442c4097004" + +[[package]] +name = "futures-timer" +version = "3.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f288b0a4f20f9a56b5d1da57e2227c661b7b16168e2f72365f57b63326e29b24" + +[[package]] +name = "futures-util" +version = "0.3.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3d6401deb83407ab3da39eba7e33987a73c3df0c82b4bb5813ee871c19c41d48" +dependencies = [ + "futures-channel", + "futures-core", + "futures-io", + "futures-macro", + "futures-sink", + "futures-task", + "memchr", + "pin-project-lite", + "pin-utils", + "slab", +] + +[[package]] +name = "glob" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d2fabcfbdc87f4758337ca535fb41a6d701b65693ce38287d856d1674551ec9b" + +[[package]] +name = "itertools" +version = "0.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "413ee7dfc52ee1a4949ceeb7dbc8a33f2d6c088194d9f922fb8318faf1f01186" +dependencies = [ + "either", +] + +[[package]] +name = "lazy_static" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bbd2bcb4c963f2ddae06a2efc7e9f3591312473c50c6685e1f298068316e66fe" + +[[package]] +name = "log" +version = "0.4.22" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a7a70ba024b9dc04c27ea2f0c0548feb474ec5c54bba33a7f72f873a39d07b24" + +[[package]] +name = "matchers" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8263075bb86c5a1b1427b5ae862e8889656f126e9f77c484496e8b47cf5c5558" +dependencies = [ + "regex-automata 0.1.10", +] + +[[package]] +name = "memchr" +version = "2.7.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "78ca9ab1a0babb1e7d5695e3530886289c18cf2f87ec19a575a0abdce112e3a3" + +[[package]] +name = "nu-ansi-term" +version = "0.46.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "77a8165726e8236064dbb45459242600304b42a5ea24ee2948e18e023bf7ba84" +dependencies = [ + "overload", + "winapi", +] + +[[package]] +name = "once_cell" +version = "1.19.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3fdb12b2476b595f9358c5161aa467c2438859caa136dec86c26fdd2efe17b92" + +[[package]] +name = "overload" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b15813163c1d831bf4a13c3610c05c0d03b39feb07f7e09fa234dac9b15aaf39" + +[[package]] +name = "perl-weekly-challenge-285" +version = "0.1.0" +dependencies = [ + "anyhow", + "itertools", + "rstest", + "thiserror", + "tracing", + "tracing-test", +] + +[[package]] +name = "pin-project-lite" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bda66fc9667c18cb2758a2ac84d1167245054bcf85d5d1aaa6923f45801bdd02" + +[[package]] +name = "pin-utils" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8b870d8c151b6f2fb93e84a13146138f05d02ed11c7e7c54f8826aaaf7c9f184" + +[[package]] +name = "proc-macro2" +version = "1.0.86" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5e719e8df665df0d1c8fbfd238015744736151d4445ec0836b8e628aae103b77" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "quote" +version = "1.0.37" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b5b9d34b8991d19d98081b46eacdd8eb58c6f2b201139f7c5f643cc155a633af" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "regex" +version = "1.10.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4219d74c6b67a3654a9fbebc4b419e22126d13d2f3c4a07ee0cb61ff79a79619" +dependencies = [ + "aho-corasick", + "memchr", + "regex-automata 0.4.7", + "regex-syntax 0.8.4", +] + +[[package]] +name = "regex-automata" +version = "0.1.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6c230d73fb8d8c1b9c0b3135c5142a8acee3a0558fb8db5cf1cb65f8d7862132" +dependencies = [ + "regex-syntax 0.6.29", +] + +[[package]] +name = "regex-automata" +version = "0.4.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38caf58cc5ef2fed281f89292ef23f6365465ed9a41b7a7754eb4e26496c92df" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax 0.8.4", +] + +[[package]] +name = "regex-syntax" +version = "0.6.29" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f162c6dd7b008981e4d40210aca20b4bd0f9b60ca9271061b07f78537722f2e1" + +[[package]] +name = "regex-syntax" +version = "0.8.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7a66a03ae7c801facd77a29370b4faec201768915ac14a721ba36f20bc9c209b" + +[[package]] +name = "relative-path" +version = "1.9.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ba39f3699c378cd8970968dcbff9c43159ea4cfbd88d43c00b22f2ef10a435d2" + +[[package]] +name = "rstest" +version = "0.18.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "97eeab2f3c0a199bc4be135c36c924b6590b88c377d416494288c14f2db30199" +dependencies = [ + "futures", + "futures-timer", + "rstest_macros", + "rustc_version", +] + +[[package]] +name = "rstest_macros" +version = "0.18.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d428f8247852f894ee1be110b375111b586d4fa431f6c46e64ba5a0dcccbe605" +dependencies = [ + "cfg-if", + "glob", + "proc-macro2", + "quote", + "regex", + "relative-path", + "rustc_version", + "syn", + "unicode-ident", +] + +[[package]] +name = "rustc_version" +version = "0.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cfcb3a22ef46e85b45de6ee7e79d063319ebb6594faafcf1c225ea92ab6e9b92" +dependencies = [ + "semver", +] + +[[package]] +name = "semver" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "61697e0a1c7e512e84a621326239844a24d8207b4669b41bc18b32ea5cbf988b" + +[[package]] +name = "sharded-slab" +version = "0.1.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f40ca3c46823713e0d4209592e8d6e826aa57e928f09752619fc696c499637f6" +dependencies = [ + "lazy_static", +] + +[[package]] +name = "slab" +version = "0.4.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8f92a496fb766b417c996b9c5e57daf2f7ad3b0bebe1ccfca4856390e3d3bb67" +dependencies = [ + "autocfg", +] + +[[package]] +name = "smallvec" +version = "1.13.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3c5e1a9a646d36c3599cd173a41282daf47c44583ad367b8e6837255952e5c67" + +[[package]] +name = "syn" +version = "2.0.77" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9f35bcdf61fd8e7be6caf75f429fdca8beb3ed76584befb503b1569faee373ed" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "thiserror" +version = "1.0.63" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c0342370b38b6a11b6cc11d6a805569958d54cfa061a29969c3b5ce2ea405724" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "1.0.63" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a4558b58466b9ad7ca0f102865eccc95938dca1a74a856f2b57b6629050da261" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "thread_local" +version = "1.1.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8b9ef9bad013ada3808854ceac7b46812a6465ba368859a37e2100283d2d719c" +dependencies = [ + "cfg-if", + "once_cell", +] + +[[package]] +name = "tracing" +version = "0.1.40" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c3523ab5a71916ccf420eebdf5521fcef02141234bbc0b8a49f2fdc4544364ef" +dependencies = [ + "pin-project-lite", + "tracing-attributes", + "tracing-core", +] + +[[package]] +name = "tracing-attributes" +version = "0.1.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34704c8d6ebcbc939824180af020566b01a7c01f80641264eba0999f6c2b6be7" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "tracing-core" +version = "0.1.32" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c06d3da6113f116aaee68e4d601191614c9053067f9ab7f6edbcb161237daa54" +dependencies = [ + "once_cell", + "valuable", +] + +[[package]] +name = "tracing-log" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ee855f1f400bd0e5c02d150ae5de3840039a3f54b025156404e34c23c03f47c3" +dependencies = [ + "log", + "once_cell", + "tracing-core", +] + +[[package]] +name = "tracing-subscriber" +version = "0.3.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ad0f048c97dbd9faa9b7df56362b8ebcaa52adb06b498c050d2f4e32f90a7a8b" +dependencies = [ + "matchers", + "nu-ansi-term", + "once_cell", + "regex", + "sharded-slab", + "smallvec", + "thread_local", + "tracing", + "tracing-core", + "tracing-log", +] + +[[package]] +name = "tracing-test" +version = "0.2.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "557b891436fe0d5e0e363427fc7f217abf9ccd510d5136549847bdcbcd011d68" +dependencies = [ + "tracing-core", + "tracing-subscriber", + "tracing-test-macro", +] + +[[package]] +name = "tracing-test-macro" +version = "0.2.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "04659ddb06c87d233c566112c1c9c5b9e98256d9af50ec3bc9c8327f873a7568" +dependencies = [ + "quote", + "syn", +] + +[[package]] +name = "unicode-ident" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" + +[[package]] +name = "valuable" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "830b7e5d4d90034032940e4ace0d9a9a057e7a45cd94e6c007832e39edb82f6d" + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" diff --git a/challenge-285/ppentchev/rust/Cargo.toml b/challenge-285/ppentchev/rust/Cargo.toml new file mode 100644 index 0000000000..90342c1a4e --- /dev/null +++ b/challenge-285/ppentchev/rust/Cargo.toml @@ -0,0 +1,25 @@ +# SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> +# SPDX-License-Identifier: BSD-2-Clause + +[package] +name = "perl-weekly-challenge-285" +version = "0.1.0" +rust-version = "1.62" +authors = ["Peter Pentchev <roam@ringlet.net>"] +edition = "2021" +description = "Solve the challenge 285 problems" +readme = "README.md" +repository = "https://github.com/ppentchev/perlweeklychallenge-club" +license = "BSD-2-Clause" +categories = ["algorithms"] +keywords = ["perl-weekly-challenge"] + +[dependencies] +anyhow = "1" +itertools = "0.13" +thiserror = "1" +tracing = "0.1.40" + +[dev-dependencies] +rstest = "0.18" +tracing-test = "0.2.5" diff --git a/challenge-285/ppentchev/rust/run-clippy.sh b/challenge-285/ppentchev/rust/run-clippy.sh new file mode 100755 index 0000000000..746742f2e4 --- /dev/null +++ b/challenge-285/ppentchev/rust/run-clippy.sh @@ -0,0 +1,70 @@ +#!/bin/sh +# +# SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> +# SPDX-License-Identifier: BSD-2-Clause + + +set -e + +def_cargo='cargo' + +usage() +{ + cat <<EOUSAGE +Usage: run-clippy.sh [-c cargo] [-n] + -c specify the Cargo command to use (default: $def_cargo) + -n also warn about lints in the Clippy "nursery" category +EOUSAGE +} + +unset run_nursery +cargo="$def_cargo" + +while getopts 'c:n' o; do + case "$o" in + c) + cargo="$OPTARG" + ;; + + n) + run_nursery=1 + ;; + + *) + usage 1>&2 + exit 1 + ;; + esac +done +shift "$((OPTIND - 1))" + +# The list of allowed and ignored checks is synced with Rust 1.76. +set -x +"$cargo" clippy \ + --tests \ + -- \ + -W warnings \ + -W future-incompatible \ + -W nonstandard-style \ + -W rust-2018-compatibility \ + -W rust-2018-idioms \ + -W rust-2021-compatibility \ + -W unused \ + -W clippy::restriction \ + -A clippy::blanket_clippy_restriction_lints \ + -A clippy::std_instead_of_alloc \ + -A clippy::std_instead_of_core \ + -A clippy::implicit_return \ + -A clippy::missing_trait_methods \ + -A clippy::mod_module_files \ + -A clippy::question_mark_used \ + -A clippy::ref_patterns \ + -A clippy::semicolon_outside_block \ + -A clippy::separated_literal_suffix \ + -A clippy::single_call_fn \ + -A clippy::self_named_module_files \ + -W clippy::pedantic \ + -A clippy::module_name_repetitions \ + -W clippy::cargo \ + ${run_nursery+-W clippy::nursery} \ + "$@" 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"), + } +} |