1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
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())
}
|
