From 49cf08a0df734aa6855f6fe700bf5b40e0ed8004 Mon Sep 17 00:00:00 2001 From: Peter Pentchev Date: Sat, 7 Sep 2024 12:54:27 +0300 Subject: Add Peter Pentchev's Rust solution to 285. --- challenge-285/ppentchev/rust/Cargo.lock | 512 +++++++++++++++++++++++ challenge-285/ppentchev/rust/Cargo.toml | 25 ++ challenge-285/ppentchev/rust/run-clippy.sh | 70 ++++ challenge-285/ppentchev/rust/src/change.rs | 188 +++++++++ challenge-285/ppentchev/rust/src/defs.rs | 24 ++ challenge-285/ppentchev/rust/src/lib.rs | 15 + challenge-285/ppentchev/rust/src/routes.rs | 49 +++ challenge-285/ppentchev/rust/src/tests/change.rs | 52 +++ challenge-285/ppentchev/rust/src/tests/mod.rs | 9 + challenge-285/ppentchev/rust/src/tests/routes.rs | 60 +++ 10 files changed, 1004 insertions(+) create mode 100644 challenge-285/ppentchev/rust/Cargo.lock create mode 100644 challenge-285/ppentchev/rust/Cargo.toml create mode 100755 challenge-285/ppentchev/rust/run-clippy.sh create mode 100644 challenge-285/ppentchev/rust/src/change.rs create mode 100644 challenge-285/ppentchev/rust/src/defs.rs create mode 100644 challenge-285/ppentchev/rust/src/lib.rs create mode 100644 challenge-285/ppentchev/rust/src/routes.rs create mode 100644 challenge-285/ppentchev/rust/src/tests/change.rs create mode 100644 challenge-285/ppentchev/rust/src/tests/mod.rs create mode 100644 challenge-285/ppentchev/rust/src/tests/routes.rs (limited to 'challenge-285/ppentchev') 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 +# SPDX-License-Identifier: BSD-2-Clause + +[package] +name = "perl-weekly-challenge-285" +version = "0.1.0" +rust-version = "1.62" +authors = ["Peter Pentchev "] +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 +# SPDX-License-Identifier: BSD-2-Clause + + +set -e + +def_cargo='cargo' + +usage() +{ + cat <&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 +// 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 { + 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 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, Error> { + Coin::ORDER_ABP + .iter() + .filter(|coin| **coin <= highest) + .map(|coin| -> Result, 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::>() +} + +/// 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 { + 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 { + 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 +// 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 +// 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 +// 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 { + 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 +// 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 +// 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 +// 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"), + } +} -- cgit From 2c00c8317e49b81cb207c862c0cc03ea36f0b04b Mon Sep 17 00:00:00 2001 From: Mohammad Sajid Anwar Date: Sat, 7 Sep 2024 15:54:46 +0100 Subject: - 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. --- challenge-285/ppentchev/rust/src/ch-1.rs | 49 ++++++++ challenge-285/ppentchev/rust/src/ch-2.rs | 188 +++++++++++++++++++++++++++++++ 2 files changed, 237 insertions(+) create mode 100644 challenge-285/ppentchev/rust/src/ch-1.rs create mode 100644 challenge-285/ppentchev/rust/src/ch-2.rs (limited to 'challenge-285/ppentchev') 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 +// 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 { + 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 +// 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 { + 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 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, Error> { + Coin::ORDER_ABP + .iter() + .filter(|coin| **coin <= highest) + .map(|coin| -> Result, 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::>() +} + +/// 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 { + 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 { + debug!("About to break {amount} cents down"); + make_change_rec(amount, Coin::HalfDollar, &mut HashMap::new()) +} -- cgit From 50445dbe3f83551244d858e5d2a0a0e1a90adf75 Mon Sep 17 00:00:00 2001 From: Peter Pentchev Date: Sat, 7 Sep 2024 13:23:38 +0300 Subject: Add Peter Pentchev's Python solution to 285. --- challenge-285/ppentchev/python/.gitignore | 7 ++ .../ppentchev/python/LICENSES/BSD-2-Clause.txt | 9 ++ challenge-285/ppentchev/python/README.md | 8 ++ challenge-285/ppentchev/python/pyproject.toml | 86 +++++++++++++ .../ppentchev/python/requirements/install.txt | 2 + .../ppentchev/python/requirements/ruff.txt | 4 + .../ppentchev/python/requirements/test.txt | 6 + challenge-285/ppentchev/python/ruff-base.toml | 39 ++++++ .../python/src/perl_weekly_285/__init__.py | 3 + .../ppentchev/python/src/perl_weekly_285/change.py | 88 ++++++++++++++ .../ppentchev/python/src/perl_weekly_285/defs.py | 34 ++++++ .../ppentchev/python/src/perl_weekly_285/routes.py | 50 ++++++++ .../ppentchev/python/tests/unit/__init__.py | 3 + .../ppentchev/python/tests/unit/test_change.py | 133 +++++++++++++++++++++ .../ppentchev/python/tests/unit/test_metadata.py | 21 ++++ .../ppentchev/python/tests/unit/test_routes.py | 73 +++++++++++ challenge-285/ppentchev/python/tox.ini | 106 ++++++++++++++++ 17 files changed, 672 insertions(+) create mode 100644 challenge-285/ppentchev/python/.gitignore create mode 100644 challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt create mode 100644 challenge-285/ppentchev/python/README.md create mode 100644 challenge-285/ppentchev/python/pyproject.toml create mode 100644 challenge-285/ppentchev/python/requirements/install.txt create mode 100644 challenge-285/ppentchev/python/requirements/ruff.txt create mode 100644 challenge-285/ppentchev/python/requirements/test.txt create mode 100644 challenge-285/ppentchev/python/ruff-base.toml create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/change.py create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/defs.py create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/routes.py create mode 100644 challenge-285/ppentchev/python/tests/unit/__init__.py create mode 100644 challenge-285/ppentchev/python/tests/unit/test_change.py create mode 100644 challenge-285/ppentchev/python/tests/unit/test_metadata.py create mode 100644 challenge-285/ppentchev/python/tests/unit/test_routes.py create mode 100644 challenge-285/ppentchev/python/tox.ini (limited to 'challenge-285/ppentchev') diff --git a/challenge-285/ppentchev/python/.gitignore b/challenge-285/ppentchev/python/.gitignore new file mode 100644 index 0000000000..05f929a541 --- /dev/null +++ b/challenge-285/ppentchev/python/.gitignore @@ -0,0 +1,7 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +site/ +.tox/ + +**/__pycache__/ diff --git a/challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt b/challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt new file mode 100644 index 0000000000..5f662b354c --- /dev/null +++ b/challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt @@ -0,0 +1,9 @@ +Copyright (c) + +Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: + +1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. + +2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/challenge-285/ppentchev/python/README.md b/challenge-285/ppentchev/python/README.md new file mode 100644 index 0000000000..6ee66a9ba8 --- /dev/null +++ b/challenge-285/ppentchev/python/README.md @@ -0,0 +1,8 @@ + + +# perl-weekly-285 - task solutions + +These are Peter Pentchev's solutions to the Perl weekly challenge 285. diff --git a/challenge-285/ppentchev/python/pyproject.toml b/challenge-285/ppentchev/python/pyproject.toml new file mode 100644 index 0000000000..d09bf621ca --- /dev/null +++ b/challenge-285/ppentchev/python/pyproject.toml @@ -0,0 +1,86 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +[build-system] +requires = [ + "hatchling >= 1.8, < 2", + "hatch-requirements-txt >= 0.3, < 0.5", +] +build-backend = "hatchling.build" + +[project] +name = "perl-weekly-285" +description = "Parse an expression for selecting stages and tags" +readme = "README.md" +license = {text = "BSD-2-Clause"} +requires-python = ">= 3.11" +dynamic = ["dependencies", "version"] +classifiers = [ + "Development Status :: 5 - Production/Stable", + "Intended Audience :: Developers", + "License :: DFSG approved", + "License :: Freely Distributable", + "License :: OSI Approved :: BSD License", + "Operating System :: OS Independent", + "Programming Language :: Python", + "Programming Language :: Python :: 3", + "Programming Language :: Python :: 3 :: Only", + "Programming Language :: Python :: 3.11", + "Programming Language :: Python :: 3.12", + "Programming Language :: Python :: 3.13", + "Topic :: Software Development :: Libraries", + "Topic :: Software Development :: Libraries :: Python Modules", + "Topic :: Software Development :: Testing", + "Topic :: Software Development :: Testing :: Unit", + "Typing :: Typed", +] + +[[project.authors]] +name = "Peter Pentchev" +email = "roam@ringlet.net" + +[project.scripts] +"perl-weekly-285" = "perl_weekly_285.__main__:main" + +[project.urls] +Homepage = "https://devel.ringlet.net/misc/perl-weekly-285/" +Changes = "https://devel.ringlet.net/misc/perl-weekly-285/changes/" +"Issue Tracker" = "https://gitlab.com/ppentchev/perl-weekly-285/-/issues" +"Source Code" = "https://gitlab.com/ppentchev/perl-weekly-285" + +[tool.hatch.build.targets.wheel] +packages = ["src/perl_weekly_285"] + +[tool.hatch.metadata.hooks.requirements_txt] +files = ["requirements/install.txt"] + +[tool.hatch.version] +path = "src/perl_weekly_285/defs.py" +pattern = '(?x) ^ VERSION \s* (?: : \s* Final \s* )? = \s* " (?P [^\s"]+ ) " \s* $' + +[tool.mypy] +strict = true + +[tool.publync.format.version] +major = 0 +minor = 1 + +[tool.publync.build.tox] + +[tool.publync.sync.rsync] +remote = "marla.ludost.net:vhosts/devel.ringlet.net/public_html/misc/perl-weekly-285" + +[tool.ruff] +extend = "ruff-base.toml" +output-format = "concise" +preview = true + +[tool.ruff.lint] +select = ["ALL"] + +[tool.test-stages] +stages = [ + "(@check or @docs) and @quick and not @manual", + "(@check or @docs) and not @manual", + "@tests and not @manual", +] diff --git a/challenge-285/ppentchev/python/requirements/install.txt b/challenge-285/ppentchev/python/requirements/install.txt new file mode 100644 index 0000000000..eb4185e66d --- /dev/null +++ b/challenge-285/ppentchev/python/requirements/install.txt @@ -0,0 +1,2 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause diff --git a/challenge-285/ppentchev/python/requirements/ruff.txt b/challenge-285/ppentchev/python/requirements/ruff.txt new file mode 100644 index 0000000000..1c69e31418 --- /dev/null +++ b/challenge-285/ppentchev/python/requirements/ruff.txt @@ -0,0 +1,4 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +ruff == 0.6.4 diff --git a/challenge-285/ppentchev/python/requirements/test.txt b/challenge-285/ppentchev/python/requirements/test.txt new file mode 100644 index 0000000000..01f71935cf --- /dev/null +++ b/challenge-285/ppentchev/python/requirements/test.txt @@ -0,0 +1,6 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +packaging >= 21.3, < 24 +pygments >= 2.7, < 3 +pytest >= 7, < 9 diff --git a/challenge-285/ppentchev/python/ruff-base.toml b/challenge-285/ppentchev/python/ruff-base.toml new file mode 100644 index 0000000000..a76ef30a2e --- /dev/null +++ b/challenge-285/ppentchev/python/ruff-base.toml @@ -0,0 +1,39 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +target-version = "py311" +line-length = 100 + +[lint] +select = [] +ignore = [ + # No blank lines before the class docstring, TYVM + "D203", + + # The multi-line docstring summary starts on the same line + "D213", + + # We do not document everything in the docstring + "DOC201", + "DOC402", + "DOC501", + + # The /x regex modifier is common enough in many languages + "FURB167", +] + +[lint.flake8-copyright] +notice-rgx = "(?x) SPDX-FileCopyrightText: \\s \\S" + +[lint.isort] +force-single-line = true +known-first-party = ["perl_weekly_285"] +lines-after-imports = 2 +single-line-exclusions = ["collections.abc", "typing"] + +[lint.per-file-ignores] +# This is a command-line tool; console output is part of its job. +"src/perl_weekly_285/__main__.py" = ["T201"] + +# This is a test suite +"tests/unit/**.py" = ["S101", "T201"] diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py b/challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py new file mode 100644 index 0000000000..39cb6886dc --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py @@ -0,0 +1,3 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the tasks in Perl weekly challenge 285.""" diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/change.py b/challenge-285/ppentchev/python/src/perl_weekly_285/change.py new file mode 100644 index 0000000000..d2cc783794 --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/change.py @@ -0,0 +1,88 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the second task in Perl weekly challenge 285, "Making Change".""" + +from __future__ import annotations + +import enum +import itertools +import typing + + +if typing.TYPE_CHECKING: + from typing import Final + + +class Coin(enum.IntEnum): + """A single denomination for breaking change down.""" + + PENNY = 1 + NICKEL = 5 + DIME = 10 + QUARTER = 25 + HALF_DOLLAR = 50 + + def lower(self) -> Coin: + """Return the next lower denomination.""" + match self: + case value if value == Coin.PENNY: + raise RuntimeError(repr(self)) + + case value if value == Coin.NICKEL: + return Coin.PENNY + + case value if value == Coin.DIME: + return Coin.NICKEL + + case value if value == Coin.QUARTER: + return Coin.DIME + + case value if value == Coin.HALF_DOLLAR: + return Coin.QUARTER + + +_ORDER_ABP: Final = [Coin.HALF_DOLLAR, Coin.QUARTER, Coin.DIME, Coin.NICKEL] +"""The denominations in descending order.""" + + +def break_down_ways(amount: int, highest: Coin) -> list[tuple[int, Coin]]: + """Make sure of things and stuff.""" + + def process_single(high: Coin) -> list[tuple[int, Coin]]: + """Get the candidates if we use this coin.""" + lower: Final = high.lower() + return [(amount - mult, lower) for mult in range(high, amount + 1, high)] + + return list(itertools.chain(*(process_single(high) for high in _ORDER_ABP if high <= highest))) + + +def make_change_rec(amount: int, highest: Coin, cache: dict[tuple[int, Coin], int]) -> int: + """Let me count the ways, recursively.""" + + def trivial(amt: int, high: Coin) -> bool: + """Sometimes there is only one.""" + return amt == 0 or high == Coin.PENNY + + if trivial(amount, highest): + return 1 + + cached: Final = cache.get((amount, highest)) + if cached is not None: + return cached + + def process_single(amt: int, high: Coin) -> int: + """Recursively count fewer ways.""" + if trivial(amt, high): + return 1 + + return make_change_rec(amt, high, cache) + + ways: Final = break_down_ways(amount, highest) + total: Final = 1 + sum(itertools.starmap(process_single, ways)) + cache[amount, highest] = total + return total + + +def solve_making_change(amount: int) -> int: + """Let me count the ways.""" + return make_change_rec(amount, Coin.HALF_DOLLAR, {}) diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/defs.py b/challenge-285/ppentchev/python/src/perl_weekly_285/defs.py new file mode 100644 index 0000000000..26d7ea59c6 --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/defs.py @@ -0,0 +1,34 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Common definitions for the perl-weekly-285 library.""" + +from __future__ import annotations + +import dataclasses +import typing + + +if typing.TYPE_CHECKING: + from typing import Final + + +VERSION: Final = "0.1.0" +"""The perl-weekly-285 library version, semver-like.""" + + +@dataclasses.dataclass +class Error(Exception): + """An error that occurred during the processing.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return f"{type(self).__str__} must be overridden for {self!r}" + + +@dataclasses.dataclass +class NoSolutionError(Error): + """No solution could be found.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return f"Could not find a solution: {self!r}" diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/routes.py b/challenge-285/ppentchev/python/src/perl_weekly_285/routes.py new file mode 100644 index 0000000000..51e19e556e --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/routes.py @@ -0,0 +1,50 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the first task in Perl weekly challenge 285, "No Connection".""" + +from __future__ import annotations + +import dataclasses +import typing + +from . import defs + + +if typing.TYPE_CHECKING: + from typing import Final + + +@dataclasses.dataclass +class NoLeafError(defs.NoSolutionError): + """No leaf destinations at all.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return "No leaf destinations could be found" + + +@dataclasses.dataclass +class MultipleLeavesError(defs.NoSolutionError): + """More than one leaf destination.""" + + multiple: list[str] + """The leaf destinations found.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return f"Multiple leaf destinations found: {self.multiple!r}" + + +def solve_no_connection(routes: list[tuple[str, str]]) -> str: + """Solve the first task, "No Connection.""" + loc_from: Final = {item[0] for item in routes} + loc_to: Final = {item[1] for item in routes} + match sorted(loc_to - loc_from): + case []: + raise NoLeafError + + case [single]: + return single + + case multiple: + raise MultipleLeavesError(multiple) diff --git a/challenge-285/ppentchev/python/tests/unit/__init__.py b/challenge-285/ppentchev/python/tests/unit/__init__.py new file mode 100644 index 0000000000..2fcf8ce229 --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/__init__.py @@ -0,0 +1,3 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Unit tests for the Perl weekly challenge 285 solutions.""" diff --git a/challenge-285/ppentchev/python/tests/unit/test_change.py b/challenge-285/ppentchev/python/tests/unit/test_change.py new file mode 100644 index 0000000000..e93bbe0286 --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/test_change.py @@ -0,0 +1,133 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Test the second task in Perl weekly challenge 285, "Making Change".""" + +from __future__ import annotations + +import dataclasses + +import pytest + +from perl_weekly_285 import change + + +@dataclasses.dataclass(frozen=True) +class BreakDownWaysCase: + """A test case for the "No Connection" task.""" + + amount: int + """The amount to break down.""" + + highest: change.Coin + """The highest coin to use for this amount.""" + + expected: list[tuple[int, change.Coin]] + """The ways to break this amount down into smaller chunks.""" + + +@pytest.mark.parametrize( + "tcase", + [ + BreakDownWaysCase(amount=1, highest=change.Coin.HALF_DOLLAR, expected=[]), + BreakDownWaysCase(amount=2, highest=change.Coin.HALF_DOLLAR, expected=[]), + BreakDownWaysCase( + amount=6, + highest=change.Coin.HALF_DOLLAR, + expected=[(1, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=6, highest=change.Coin.NICKEL, expected=[(1, change.Coin.PENNY)]), + BreakDownWaysCase(amount=6, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=7, + highest=change.Coin.HALF_DOLLAR, + expected=[(2, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=7, highest=change.Coin.NICKEL, expected=[(2, change.Coin.PENNY)]), + BreakDownWaysCase(amount=7, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=10, + highest=change.Coin.HALF_DOLLAR, + expected=[(0, change.Coin.NICKEL), (5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=10, + highest=change.Coin.DIME, + expected=[(0, change.Coin.NICKEL), (5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=10, + highest=change.Coin.NICKEL, + expected=[(5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=10, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=12, + highest=change.Coin.HALF_DOLLAR, + expected=[(2, change.Coin.NICKEL), (7, change.Coin.PENNY), (2, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=12, + highest=change.Coin.DIME, + expected=[(2, change.Coin.NICKEL), (7, change.Coin.PENNY), (2, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=12, + highest=change.Coin.NICKEL, + expected=[(7, change.Coin.PENNY), (2, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=12, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=15, + highest=change.Coin.HALF_DOLLAR, + expected=[ + (5, change.Coin.NICKEL), + (10, change.Coin.PENNY), + (5, change.Coin.PENNY), + (0, change.Coin.PENNY), + ], + ), + BreakDownWaysCase( + amount=15, + highest=change.Coin.DIME, + expected=[ + (5, change.Coin.NICKEL), + (10, change.Coin.PENNY), + (5, change.Coin.PENNY), + (0, change.Coin.PENNY), + ], + ), + BreakDownWaysCase( + amount=15, + highest=change.Coin.NICKEL, + expected=[(10, change.Coin.PENNY), (5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=15, highest=change.Coin.PENNY, expected=[]), + ], +) +def test_break_down_ways(*, tcase: BreakDownWaysCase) -> None: + """Make sure we can find the leaf destination.""" + assert change.break_down_ways(tcase.amount, tcase.highest) == tcase.expected + + +@dataclasses.dataclass(frozen=True) +class MakeChangeCase: + """A test case for the actual "how many ways can we break this down" function.""" + + amount: int + """The amount to break down.""" + + expected: int + """The expected number of ways.""" + + +@pytest.mark.parametrize( + "tcase", + [ + MakeChangeCase(amount=9, expected=2), + MakeChangeCase(amount=15, expected=6), + MakeChangeCase(amount=100, expected=292), + ], +) +def test_make_change(tcase: MakeChangeCase) -> None: + """Make sure we can count the ways.""" + assert change.solve_making_change(tcase.amount) == tcase.expected diff --git a/challenge-285/ppentchev/python/tests/unit/test_metadata.py b/challenge-285/ppentchev/python/tests/unit/test_metadata.py new file mode 100644 index 0000000000..e957790fba --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/test_metadata.py @@ -0,0 +1,21 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Basic test for file importing.""" + +from __future__ import annotations + +import typing + +from packaging import version as pkg_version + +from perl_weekly_285 import defs + + +if typing.TYPE_CHECKING: + from typing import Final + + +def test_version() -> None: + """Make sure the `VERSION` variable has a sane value.""" + version: Final = pkg_version.Version(defs.VERSION) + assert version > pkg_version.Version("0") diff --git a/challenge-285/ppentchev/python/tests/unit/test_routes.py b/challenge-285/ppentchev/python/tests/unit/test_routes.py new file mode 100644 index 0000000000..743e0d20d2 --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/test_routes.py @@ -0,0 +1,73 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Test the first task in Perl weekly challenge 285, "No Connection".""" + +from __future__ import annotations + +import dataclasses + +import pytest + +from perl_weekly_285 import defs +from perl_weekly_285 import routes + + +@dataclasses.dataclass(frozen=True) +class RoutesCase: + """A test case for the "No Connection" task.""" + + routes: list[tuple[str, str]] + """The routes to examine.""" + + expected: str + """The leaf destination we expect to find.""" + + +@pytest.mark.parametrize( + "tcase", + [ + RoutesCase( + routes=[ + ("me", "you"), + ], + expected="you", + ), + RoutesCase( + routes=[ + ("here", "there"), + ("here", "everywhere"), + ("there", "everywhere"), + ], + expected="everywhere", + ), + RoutesCase( + routes=[("B", "C"), ("D", "B"), ("C", "A")], + expected="A", + ), + ], +) +def test_connection(*, tcase: RoutesCase) -> None: + """Make sure we can find the leaf destination.""" + assert routes.solve_no_connection(tcase.routes) == tcase.expected + + +@pytest.mark.parametrize( + "tcase", + [ + RoutesCase( + routes=[ + ("here", "there"), + ("here", "everywhere"), + ], + expected="not really", + ), + RoutesCase( + routes=[("me", "you"), ("you", "me")], +