atcoder/lib/math/
radix.rs

1//! 整数と任意基数の桁列を相互変換します。
2
3/// 非負整数 `value` を通常の `base` 進数の桁列へ変換します。
4///
5/// 桁は上位（最上位桁）から順に並び、各桁は `0..base` の値になります。
6/// `value` が `0` の場合は `[0]` を返します。
7/// 桁数を `d` とすると、時間・追加領域はともに `O(d)` です。
8///
9/// # Panics
10///
11/// `base` が `2` 未満の場合は panic します。
12///
13/// # Examples
14///
15/// ```
16/// use atcoder::math::radix::to_digits;
17///
18/// assert_eq!(to_digits(13, 2), vec![1, 1, 0, 1]);
19/// assert_eq!(to_digits(255, 16), vec![15, 15]);
20/// assert_eq!(to_digits(0, 10), vec![0]);
21/// ```
22pub fn to_digits(mut value: usize, base: usize) -> Vec<usize> {
23    assert!(base >= 2, "base must be at least 2");
24
25    if value == 0 {
26        return vec![0];
27    }
28
29    let mut digits = Vec::new();
30    while value > 0 {
31        digits.push(value % base);
32        value /= base;
33    }
34    digits.reverse();
35    digits
36}
37
38/// 正の `value` を bijective base-`base`（桁に 0 を使わない表記）の桁列へ変換します。
39///
40/// 桁は上位から順に並びます。返される各桁は文字などへの添字として扱いやすいように
41/// `0..base` で表され、数値としてはそれぞれ `1..=base` に対応します。
42///
43/// # Panics
44///
45/// `base` が `2` 未満、または `value` が `0` の場合は panic します。桁数を `d` とすると、
46/// 時間・追加領域はともに `O(d)` です。
47///
48/// # Examples
49///
50/// ```
51/// use atcoder::math::radix::to_bijective_digits;
52///
53/// assert_eq!(to_bijective_digits(1, 26), vec![0]);
54/// assert_eq!(to_bijective_digits(26, 26), vec![25]);
55/// assert_eq!(to_bijective_digits(27, 26), vec![0, 0]);
56/// ```
57pub fn to_bijective_digits(mut value: usize, base: usize) -> Vec<usize> {
58    assert!(base >= 2, "base must be at least 2");
59    assert!(value >= 1, "value must be positive");
60
61    let mut digits = Vec::new();
62    while value > 0 {
63        value -= 1;
64        digits.push(value % base);
65        value /= base;
66    }
67    digits.reverse();
68    digits
69}
70
71/// 通常の `base` 進数の桁列を `usize` へ変換します。
72///
73/// 桁は上位（最上位桁）から順に渡します。空の桁列、`base` 以上の桁、または値が
74/// `usize` の範囲を超える場合は `None` を返します。`base` が `2` 以上なら先頭の 0 桁も許可します。
75/// 桁数を `d` とすると計算量は `O(d)`、追加領域は `O(1)` です。
76///
77/// # Panics
78///
79/// `base` が `2` 未満の場合は panic します。
80///
81/// # Examples
82///
83/// ```
84/// use atcoder::math::radix::from_digits;
85///
86/// assert_eq!(from_digits(&[1, 1, 0, 1], 2), Some(13));
87/// assert_eq!(from_digits(&[15, 15], 16), Some(255));
88/// ```
89pub fn from_digits(digits: &[usize], base: usize) -> Option<usize> {
90    assert!(base >= 2, "base must be at least 2");
91
92    if digits.is_empty() {
93        return None;
94    }
95
96    digits.iter().try_fold(0_usize, |value, &digit| {
97        if digit >= base {
98            return None;
99        }
100        value.checked_mul(base)?.checked_add(digit)
101    })
102}
103
104#[cfg(test)]
105mod tests {
106    use super::{from_digits, to_bijective_digits, to_digits};
107
108    #[test]
109    fn converts_values_to_digits() {
110        assert_eq!(to_digits(0, 2), vec![0]);
111        assert_eq!(to_digits(13, 2), vec![1, 1, 0, 1]);
112        assert_eq!(to_digits(255, 16), vec![15, 15]);
113        assert_eq!(to_digits(26, 26), vec![1, 0]);
114    }
115
116    #[test]
117    fn converts_values_to_bijective_digits() {
118        assert_eq!(to_bijective_digits(1, 26), vec![0]);
119        assert_eq!(to_bijective_digits(26, 26), vec![25]);
120        assert_eq!(to_bijective_digits(27, 26), vec![0, 0]);
121        assert_eq!(to_bijective_digits(28, 26), vec![0, 1]);
122        assert_eq!(
123            to_bijective_digits(usize::MAX, usize::MAX),
124            vec![usize::MAX - 1]
125        );
126    }
127
128    #[test]
129    fn converts_digits_to_values() {
130        assert_eq!(from_digits(&[0], 2), Some(0));
131        assert_eq!(from_digits(&[1, 1, 0, 1], 2), Some(13));
132        assert_eq!(from_digits(&[15, 15], 16), Some(255));
133        assert_eq!(from_digits(&[0, 0, 1], 10), Some(1));
134    }
135
136    #[test]
137    fn round_trips_values() {
138        for base in [2, 3, 10, 16, 26, usize::MAX] {
139            for value in [0, 1, 25, 26, 255, usize::MAX] {
140                assert_eq!(from_digits(&to_digits(value, base), base), Some(value));
141            }
142        }
143    }
144
145    #[test]
146    fn rejects_empty_invalid_or_overflowing_digits() {
147        assert_eq!(from_digits(&[], 10), None);
148        assert_eq!(from_digits(&[1, 2], 2), None);
149        assert_eq!(from_digits(&[usize::MAX], usize::MAX), None);
150        assert_eq!(from_digits(&[1, 1], usize::MAX), None);
151    }
152
153    #[test]
154    #[should_panic(expected = "base must be at least 2")]
155    fn rejects_invalid_base_when_encoding() {
156        to_digits(10, 1);
157    }
158
159    #[test]
160    #[should_panic(expected = "value must be positive")]
161    fn rejects_zero_when_bijective_encoding() {
162        to_bijective_digits(0, 26);
163    }
164
165    #[test]
166    #[should_panic(expected = "base must be at least 2")]
167    fn rejects_invalid_base_when_decoding() {
168        from_digits(&[1], 1);
169    }
170}
atcoder/lib/math/radix.rs

atcoder/lib/math/
radix.rs
