simulation/
lib.rs

1//! # Rust :: Simulation
2
3/// 498m Diagonal Traverse
4struct Sol498 {}
5
6impl Sol498 {
7    /// 1 <= R, C <= 10^4
8    pub fn find_diagonal_order(mat: Vec<Vec<i32>>) -> Vec<i32> {
9        let (rows, cols) = (mat.len(), mat[0].len());
10
11        let mut dwalk = vec![];
12        let mut forward = true;
13
14        for r in 0..rows {
15            let mut diag = vec![];
16            for (d, row) in mat
17                .iter()
18                .rev()
19                .skip(rows - r - 1)
20                .take(rows.min(cols))
21                .enumerate()
22            {
23                diag.push(row[d]);
24            }
25
26            if !forward {
27                diag.reverse();
28            }
29            forward = !forward;
30
31            dwalk.extend(diag);
32        }
33
34        for c in 1..cols {
35            let mut diag = vec![];
36            for (d, row) in mat.iter().rev().take(rows.min(cols - c)).enumerate() {
37                diag.push(row[c + d]);
38            }
39
40            if !forward {
41                diag.reverse();
42            }
43            forward = !forward;
44
45            dwalk.extend(diag);
46        }
47
48        dwalk
49    }
50}
51
52/// 2154 Keep Multiplying Found Values by Two
53struct Sol2154 {}
54
55impl Sol2154 {
56    pub fn find_final_value(nums: Vec<i32>, original: i32) -> i32 {
57        use std::collections::HashSet;
58        use std::iter::successors;
59
60        let mut hs = HashSet::new();
61        for n in nums {
62            hs.insert(n);
63        }
64
65        successors(Some(original), |o| {
66            if hs.contains(o) { Some(o << 1) } else { None }
67        })
68        .last()
69        .unwrap()
70    }
71}
72
73/// 2161m Partition Array According to Given Pivot
74struct Sol2161;
75
76impl Sol2161 {
77    pub fn pivot_array(nums: Vec<i32>, pivot: i32) -> Vec<i32> {
78        let mut rst = vec![pivot; nums.len()];
79
80        let (mut left, mut right) = (0, nums.len() - 1);
81        for (l, r) in (0..nums.len()).zip((0..nums.len()).rev()) {
82            if nums[l] < pivot {
83                rst[left] = nums[l];
84                left += 1;
85            }
86            if nums[r] > pivot {
87                rst[right] = nums[r];
88                right -= 1;
89            }
90        }
91
92        println!(":: {:?}", rst);
93
94        rst
95    }
96}
97
98/// 2243 Calculate Digit Sum of a String
99struct Sol2243 {}
100
101impl Sol2243 {
102    pub fn digit_sum(s: String, k: i32) -> String {
103        let k = k as usize;
104
105        println!(":? {:?}", {
106            let mut s = s.clone();
107            while s.len() > k {
108                s = s
109                    .as_bytes()
110                    .chunks(k)
111                    .map(|chars| {
112                        chars
113                            .iter()
114                            .map(|chr| (chr - b'0') as u32)
115                            .sum::<u32>()
116                            .to_string()
117                    })
118                    .collect::<Vec<String>>()
119                    .join("");
120            }
121            s
122        });
123
124        let mut source: Vec<_> = s.as_bytes().iter().map(|n| (n - b'0') as u16).collect();
125
126        while source.len() > k {
127            let mut target = vec![];
128            for chunk in source.chunks(k) {
129                let mut dsum: u16 = chunk.iter().sum();
130                if dsum == 0 {
131                    target.push(0);
132                } else {
133                    let mut digits = vec![];
134                    while dsum > 0 {
135                        digits.push(dsum % 10);
136                        dsum /= 10;
137                    }
138                    digits.reverse();
139                    target.extend_from_slice(&digits);
140                }
141            }
142
143            source = target;
144        }
145
146        String::from_utf8(source.iter().map(|&n| n as u8 + b'0').collect()).unwrap()
147    }
148}
149
150/// 2303 Calculate Amount Paid in Taxes
151struct Sol2303 {}
152
153impl Sol2303 {
154    pub fn calculate_tax(brackets: Vec<Vec<i32>>, mut income: i32) -> f64 {
155        let mut rates = vec![vec![0, 0]];
156        rates.extend_from_slice(&brackets);
157
158        rates
159            .windows(2)
160            .map(|w| {
161                let diff = w[1][0] - w[0][0];
162                let tax = diff.min(income) as f64 * w[1][1] as f64 / 100.0;
163                income -= diff.min(income);
164
165                tax
166            })
167            .sum()
168    }
169}
170
171/// 2402h Meeting Room III
172struct Sol2402 {}
173
174impl Sol2402 {
175    pub fn most_booked(n: i32, mut meetings: Vec<Vec<i32>>) -> i32 {
176        use std::cmp::Reverse;
177        use std::collections::BinaryHeap;
178
179        let mut frees = BinaryHeap::new();
180        for room in 0..n {
181            frees.push((Reverse(room), 0));
182        }
183        println!("-> {frees:?}");
184
185        let mut ongoings = BinaryHeap::new();
186
187        meetings.sort_unstable();
188        for meeting in meetings {
189            while let Some(&(Reverse(end), Reverse(room), count)) = ongoings.peek() {
190                if end <= meeting[0] as i64 {
191                    ongoings.pop();
192                    frees.push((Reverse(room), count));
193                } else {
194                    break;
195                }
196            }
197
198            if let Some((Reverse(room), count)) = frees.pop() {
199                ongoings.push((Reverse(meeting[1] as i64), Reverse(room), count + 1));
200            } else if let Some((Reverse(end), Reverse(room), count)) = ongoings.pop() {
201                ongoings.push((
202                    Reverse(end + (meeting[1] - meeting[0]) as i64),
203                    Reverse(room),
204                    count + 1,
205                ));
206            }
207        }
208
209        println!("-> O:   {ongoings:?}");
210        println!("-> F:   {frees:?}");
211
212        let mut x = vec![];
213        for (Reverse(room), count) in frees.drain() {
214            x.push((Reverse(count), room));
215        }
216        for (_, Reverse(room), count) in ongoings.drain() {
217            x.push((Reverse(count), room));
218        }
219        x.sort();
220
221        println!("-> {x:?}");
222
223        x[0].1
224    }
225}
226
227/// 2460 Apply Operations to an Array
228struct Sol2460;
229
230impl Sol2460 {
231    pub fn apply_operations(nums: Vec<i32>) -> Vec<i32> {
232        let mut nums = nums;
233        for i in 0..nums.len() - 1 {
234            if nums[i] == nums[i + 1] {
235                nums[i] *= 2;
236                nums[i + 1] = 0;
237            }
238        }
239
240        let mut vcopy = nums.to_vec();
241        vcopy.sort_by_key(|&v| if v > 0 { 0 } else { 1 });
242
243        println!("-> {:?}", vcopy);
244
245        for z in 0..nums.len() {
246            if nums[z] == 0 {
247                let mut swap = z;
248                while nums[swap] == 0 {
249                    swap += 1;
250                    if swap >= nums.len() {
251                        return nums;
252                    }
253                }
254                (nums[z], nums[swap]) = (nums[swap], nums[z]);
255            }
256        }
257
258        nums
259    }
260}
261
262/// 2739 Total Distance Traveled
263struct Sol2739 {}
264
265impl Sol2739 {
266    pub fn distance_traveled(main_tank: i32, additional_tank: i32) -> i32 {
267        let mut distance = 0;
268
269        let (mut fuel, mut reserve) = (main_tank, additional_tank);
270        loop {
271            if fuel >= 5 {
272                distance += 50;
273                fuel -= 5;
274                if reserve > 0 {
275                    reserve -= 1;
276                    fuel += 1;
277                }
278            } else {
279                break distance + fuel * 10;
280            }
281        }
282    }
283}
284
285/// 3446m Sort Matrix by Diagonals
286struct Sol3446 {}
287
288impl Sol3446 {
289    /// 1 <= N <= 10
290    pub fn sort_matrix(mut grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
291        let n = grid.len();
292
293        for diag in 0..n {
294            let mut rdiag: Vec<_> = (0..n - diag).map(|d| grid[diag + d][d]).collect();
295            rdiag.sort_by(|a, b| b.cmp(a));
296            for d in 0..n - diag {
297                grid[diag + d][d] = rdiag[d];
298            }
299        }
300
301        for diag in 1..n {
302            let mut rdiag: Vec<_> = (0..n - diag).map(|d| grid[d][diag + d]).collect();
303            rdiag.sort();
304            for d in 0..n - diag {
305                grid[d][diag + d] = rdiag[d];
306            }
307        }
308
309        grid
310    }
311}
312
313#[cfg(test)]
314mod tests;
simulation/lib.rs

simulation/
lib.rs
