recursion/
lib.rs

1//! # Rust :: Recursion, Backtracking
2
3#![feature(test)]
4extern crate test;
5
6/// 37h Sudoku Solver
7struct Sol37;
8
9impl Sol37 {
10    pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
11        fn valid(board: &[Vec<char>], r: usize, c: usize, digit: char) -> bool {
12            for i in 0..9 {
13                if board[i][c] == digit || board[r][i] == digit {
14                    return false;
15                }
16            }
17
18            for row in board.iter().skip(r / 3 * 3).take(3) {
19                for &v in row.iter().skip(c / 3 * 3).take(3) {
20                    if v == digit {
21                        return false;
22                    }
23                }
24            }
25
26            true
27        }
28
29        fn solve(board: &mut Vec<Vec<char>>, r: usize, c: usize) -> bool {
30            if r == 9 {
31                return true;
32            }
33
34            let (mut x, mut y) = (r, c + 1);
35            if y == 9 {
36                (x, y) = (r + 1, 0);
37            }
38
39            if board[r][c] != '.' {
40                return solve(board, x, y);
41            }
42
43            for digit in ['1', '2', '3', '4', '5', '6', '7', '8', '9'] {
44                if valid(board, r, c, digit) {
45                    board[r][c] = digit;
46                    if solve(board, x, y) {
47                        return true;
48                    }
49                    board[r][c] = '.';
50                }
51            }
52            false
53        }
54
55        solve(board, 0, 0);
56        for r in board.iter() {
57            println!(" -> {:?}", r);
58        }
59    }
60}
61
62/// 50m Power(x, n)
63struct Sol50;
64
65impl Sol50 {
66    /// -100 <= x <= 100
67    /// -2^31 <= n <= 2^31-1
68    pub fn my_pow(x: f64, n: i32) -> f64 {
69        let mut p = 1.;
70
71        let mut x = x;
72        let mut e = if n < 0 { -(n as i64) } else { n as i64 };
73        while e > 0 {
74            if e & 1 == 1 {
75                p *= x;
76            }
77            x *= x;
78            e >>= 1;
79        }
80
81        use std::cmp::Ordering::*;
82        match n.cmp(&0) {
83            Less => 1. / p,
84            _ => p,
85        }
86    }
87}
88
89/// 60h Permutation Sequence
90struct Sol60;
91
92impl Sol60 {
93    pub fn get_permutation(n: i32, k: i32) -> String {
94        // 1 <= n <= 9
95        let mut seq = vec![];
96        for chr in ('1'..='9').take(n as usize) {
97            seq.push(chr);
98        }
99
100        fn perms(n: i32, p: usize, seq: &mut Vec<char>) {
101            if p == n as usize {
102                println!("-> {:?}", seq);
103                return;
104            }
105
106            perms(n, p + 1, seq);
107            for i in p + 1..n as usize {
108                (seq[i], seq[p]) = (seq[p], seq[i]);
109                perms(n, p + 1, seq);
110                (seq[i], seq[p]) = (seq[p], seq[i]);
111            }
112        }
113
114        perms(n, 0, &mut seq);
115
116        let mut rst = vec![];
117        let mut vis = vec![false; n as usize];
118
119        fn perms_sql(n: usize, k: i32, vis: &mut Vec<bool>, rst: &mut Vec<char>) -> i32 {
120            let mut k = k;
121            if rst.len() == n {
122                k -= 1;
123                if k == 0 {
124                    println!(":: {:?}", rst);
125                }
126                return k;
127            }
128
129            for (i, chr) in ('1'..='9').enumerate().take(n) {
130                if !vis[i] {
131                    vis[i] = true;
132                    rst.push(chr);
133
134                    k = perms_sql(n, k, vis, rst);
135                    if k == 0 {
136                        return 0;
137                    }
138
139                    rst.pop();
140                    vis[i] = false;
141                }
142            }
143
144            k
145        }
146
147        perms_sql(n as usize, k, &mut vis, &mut rst);
148        rst.iter().collect()
149    }
150}
151
152/// 282h Expression Add Operators
153struct Sol282;
154
155impl Sol282 {
156    pub fn add_operators(num: String, target: i32) -> Vec<String> {
157        println!("** {:?}", num);
158
159        let mut rst = vec![];
160
161        fn search(
162            num: &str,
163            target: i32,
164            rst: &mut Vec<String>,
165            start: usize,
166            prv_opr: i64,
167            cur_val: i64,
168            expr: &str,
169        ) -> Result<(), std::num::ParseIntError> {
170            if start == num.len() {
171                if cur_val == target as i64 {
172                    rst.push(expr.to_string());
173                }
174                return Ok(());
175            }
176
177            for i in start..num.len() {
178                if num.as_bytes()[start] == b'0' && i > start {
179                    break;
180                }
181
182                let v = num[start..i + 1].parse()?;
183                if start == 0 {
184                    search(
185                        num,
186                        target,
187                        rst,
188                        i + 1,
189                        v,
190                        cur_val + v,
191                        &(expr.to_string() + &num[start..i + 1]),
192                    )?;
193                } else {
194                    search(
195                        num,
196                        target,
197                        rst,
198                        i + 1,
199                        v,
200                        cur_val + v,
201                        &(expr.to_string() + "+" + &num[start..i + 1]),
202                    )?;
203                    search(
204                        num,
205                        target,
206                        rst,
207                        i + 1,
208                        -v,
209                        cur_val - v,
210                        &(expr.to_string() + "-" + &num[start..i + 1]),
211                    )?;
212                    search(
213                        num,
214                        target,
215                        rst,
216                        i + 1,
217                        prv_opr * v,
218                        cur_val - prv_opr + prv_opr * v,
219                        &(expr.to_string() + "*" + &num[start..i + 1]),
220                    )?;
221                }
222            }
223
224            Ok(())
225        }
226
227        let _ = search(&num, target, &mut rst, 0, 0, 0, "");
228        println!(":: {:?}", rst);
229
230        rst
231    }
232}
233
234/// 301h Remove Invalid Parentheses
235struct Sol301 {}
236
237impl Sol301 {
238    /// 1 <= N <= 25
239    pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
240        use std::collections::{HashMap, HashSet};
241
242        let chrs: Vec<char> = s.chars().collect();
243        println!("* {chrs:?}");
244
245        fn search(
246            start: usize,
247            opens: usize,
248            closes: usize,
249            chrs: &[char],
250            picks: &mut [bool],
251            lengths: &mut HashMap<usize, HashSet<String>>,
252        ) {
253            if start == picks.len() {
254                let s: String = chrs
255                    .iter()
256                    .zip(picks.iter())
257                    .filter(|(_, pick)| **pick)
258                    .map(|(&chr, _)| chr)
259                    .collect();
260
261                let valid = || -> bool {
262                    let mut stack = 0;
263                    for chr in s.chars() {
264                        match chr {
265                            '(' => stack += 1,
266                            ')' => {
267                                if stack == 0 {
268                                    return false;
269                                } else {
270                                    stack -= 1;
271                                }
272                            }
273                            _ => (),
274                        }
275                    }
276                    stack == 0
277                };
278
279                if opens == closes && valid() {
280                    let entry = lengths.entry(s.len()).or_default();
281                    entry.insert(s);
282                }
283
284                return;
285            }
286
287            match chrs[start] {
288                '(' => {
289                    if opens > 0 {
290                        search(start + 1, opens - 1, closes, chrs, picks, lengths);
291                    }
292
293                    picks[start] = true;
294                    search(start + 1, opens, closes, chrs, picks, lengths);
295                    picks[start] = false;
296                }
297                ')' => {
298                    if closes > 0 {
299                        search(start + 1, opens, closes - 1, chrs, picks, lengths);
300                    }
301
302                    picks[start] = true;
303                    search(start + 1, opens, closes, chrs, picks, lengths);
304                    picks[start] = false;
305                }
306                _ => {
307                    picks[start] = true;
308                    search(start + 1, opens, closes, chrs, picks, lengths);
309                }
310            }
311        }
312
313        let mut picks = vec![false; chrs.len()];
314        let mut lengths: HashMap<usize, HashSet<String>> = HashMap::new();
315
316        let (mut opens, mut closes) = (0, 0);
317        for chr in chrs.iter() {
318            match chr {
319                '(' => opens += 1,
320                ')' => {
321                    if opens > 0 {
322                        opens -= 1;
323                    } else {
324                        closes += 1;
325                    }
326                }
327                _ => (),
328            }
329        }
330        println!("-> Extra# (Must Remove): {opens} (   {closes} )");
331
332        search(0, opens, closes, &chrs, &mut picks, &mut lengths);
333
334        println!("-> {lengths:?}");
335
336        match lengths.keys().max() {
337            Some(lmax) => lengths[lmax].clone().into_iter().collect(),
338            _ => vec![],
339        }
340    }
341}
342
343/// 386m Lexicographical Numbers
344struct Sol386 {}
345
346impl Sol386 {
347    pub fn lexical_order(n: i32) -> Vec<i32> {
348        let mut lorder = vec![];
349
350        fn dfs(v: i32, n: i32, lorder: &mut Vec<i32>) {
351            lorder.push(v);
352            (0..=9)
353                .take_while(|d| 10 * v + d <= n)
354                .for_each(|d| dfs(10 * v + d, n, lorder));
355        }
356
357        for v in 1..=9.min(n) {
358            dfs(v, n, &mut lorder);
359        }
360
361        lorder
362    }
363}
364
365/// 679h 24 Game
366struct Sol679 {}
367
368impl Sol679 {
369    /// L_cards = 4, 1 <= Cards_i <= 9
370    pub fn judge_point24(cards: Vec<i32>) -> bool {
371        fn possible_results(a: f64, b: f64) -> Vec<f64> {
372            let mut rs = vec![a + b, a - b, b - a, a * b];
373            if b != 0.0 {
374                rs.push(a / b);
375            }
376            if a != 0.0 {
377                rs.push(b / a);
378            }
379
380            println!("-> ({a}, {b}) :: {rs:?}");
381            rs
382        }
383
384        fn search(cards: &[f64]) -> bool {
385            println!("-> {cards:?}");
386
387            if cards.len() == 1 {
388                return (cards[0] - 24.0).abs() <= 1e-5;
389            }
390
391            for a in 0..cards.len() {
392                for b in a + 1..cards.len() {
393                    let mut n_cards: Vec<_> = cards
394                        .iter()
395                        .enumerate()
396                        .filter(|&(i, _)| i != a && i != b)
397                        .map(|(_, &v)| v)
398                        .collect();
399
400                    for v in possible_results(cards[a], cards[b]) {
401                        n_cards.push(v);
402                        if search(&n_cards) {
403                            return true;
404                        }
405                        n_cards.pop();
406                    }
407                }
408            }
409
410            false
411        }
412
413        search(&cards.iter().map(|&n| n as f64).collect::<Vec<_>>())
414    }
415}
416
417/// 1079m Letter Tile Possibilities
418struct Sol1079;
419
420impl Sol1079 {
421    pub fn num_tile_possibilities(tiles: String) -> i32 {
422        use std::collections::HashSet;
423
424        println!("|| {:?}", tiles);
425
426        fn gen_combinations(
427            hset: &mut HashSet<String>,
428            used: &mut Vec<bool>,
429            tiles: &mut Vec<char>,
430            tile: &mut String,
431        ) {
432            hset.insert(tile.clone());
433
434            for i in 0..tiles.len() {
435                if !used[i] {
436                    used[i] = true;
437                    tile.push(tiles[i]);
438
439                    gen_combinations(hset, used, tiles, tile);
440
441                    used[i] = false;
442                    tile.pop();
443                }
444            }
445        }
446
447        let mut hset = HashSet::new();
448        let mut used = vec![false; tiles.len()];
449
450        gen_combinations(
451            &mut hset,
452            &mut used,
453            &mut tiles.chars().collect(),
454            &mut "".to_string(),
455        );
456
457        println!("-> {:?}", hset);
458
459        hset.len() as i32 - 1
460    }
461}
462
463/// 1718m Construct the Lexicographically Largest Valid Sequence
464struct Sol1718;
465
466impl Sol1718 {
467    pub fn construct_distanced_sequence(n: i32) -> Vec<i32> {
468        let mut rst = vec![0; 2 * n as usize - 1];
469        let mut numbers = vec![false; 1 + n as usize];
470
471        fn search(rst: &mut Vec<i32>, numbers: &mut Vec<bool>, start: usize) -> bool {
472            if start == rst.len() {
473                return true;
474            }
475
476            if rst[start] != 0 {
477                return search(rst, numbers, start + 1);
478            }
479
480            for n in (1..numbers.len()).rev() {
481                if numbers[n] {
482                    continue;
483                }
484
485                rst[start] = n as i32;
486                numbers[n] = true;
487
488                if n == 1 && search(rst, numbers, start + 1) {
489                    return true;
490                }
491
492                if n > 1 && start + n < rst.len() && rst[start + n] == 0 {
493                    rst[start + n] = n as i32;
494                    if search(rst, numbers, start + 1) {
495                        return true;
496                    }
497
498                    rst[start + n] = 0; // backtrack
499                }
500
501                rst[start] = 0; // backtrack
502                numbers[n] = false; // backtrack
503            }
504
505            false
506        }
507
508        search(&mut rst, &mut numbers, 0);
509
510        println!(":: {:?}", rst);
511
512        rst
513    }
514}
515
516/// 1922m Count Good Numbers
517struct Sol1922;
518
519impl Sol1922 {
520    /// 1 <= N <= 10^15
521    pub fn count_good_numbers(n: i64) -> i32 {
522        const M: i64 = 1e9 as i64 + 7;
523
524        fn mpower(mut b: i64, mut e: i64) -> i64 {
525            let mut mpower = 1;
526            while e > 0 {
527                if e & 1 == 1 {
528                    mpower = (b * mpower) % M;
529                }
530                b = (b * b) % M;
531                e >>= 1;
532            }
533            mpower
534        }
535
536        (mpower(5, (n + 1) / 2) * mpower(4, n / 2) % M) as i32
537    }
538}
539
540/// 2044m Count Number of Maximum Bitwise-OR Subsets
541struct Sol2044 {}
542
543impl Sol2044 {
544    pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
545        let x_or = nums.iter().fold(0, |x_or, &n| x_or | n);
546
547        fn search(start: usize, or: i32, x_or: i32, nums: &[i32]) -> i32 {
548            if start == nums.len() {
549                return 0;
550            }
551
552            (if or | nums[start] == x_or { 1 } else { 0 })
553                + search(start + 1, or, x_or, nums)
554                + search(start + 1, or | nums[start], x_or, nums)
555        }
556
557        search(0, 0, x_or, &nums)
558    }
559}
560
561/// 2375m Construct Smallest Number From DI String
562struct Sol2375;
563
564impl Sol2375 {
565    pub fn smallest_number(pattern: String) -> String {
566        println!("|| {}", pattern);
567
568        fn search(rst: &mut String, last: usize, used: &mut [bool], pattern: &Vec<char>) -> bool {
569            println!("-> {:?}", rst);
570
571            if rst.len() == pattern.len() + 1 {
572                return true;
573            }
574
575            for d in 1..=9 {
576                if !used[d] {
577                    match (pattern[rst.len() - 1], d < last) {
578                        ('D', true) | ('I', false) => {
579                            used[d] = true;
580                            rst.push((b'0' + d as u8) as char);
581
582                            if search(rst, d, used, pattern) {
583                                return true;
584                            }
585
586                            used[d] = false;
587                            rst.pop();
588                        }
589                        _ => (),
590                    }
591                }
592            }
593
594            false
595        }
596
597        let mut used = [false; 10];
598        let pattern = pattern.chars().collect();
599
600        let mut rst = String::new();
601        for d in 1..=9 {
602            rst.push((b'0' + d as u8) as char);
603            used[d] = true;
604
605            if search(&mut rst, d, &mut used, &pattern) {
606                return rst;
607            }
608
609            rst.pop();
610            used[d] = false;
611        }
612
613        "".to_string()
614    }
615}
616
617/// 2698m Find the Punishment Number of an Integer
618struct Sol2698;
619
620impl Sol2698 {
621    pub fn punishment_number(n: i32) -> i32 {
622        fn partition(digits: &Vec<i32>, n: i32, parts: &mut [bool], start: usize) -> bool {
623            println!("-> {:?}", (n, start, &parts));
624
625            for p in start..digits.len() {
626                parts[p] = true;
627
628                let (mut dsum, mut csum) = (0, 0);
629                for p in 0..digits.len() {
630                    match parts[p] {
631                        true => {
632                            dsum += 10 * csum + digits[p];
633                            csum = 0;
634                        }
635                        _ => csum = 10 * csum + digits[p],
636                    }
637                }
638
639                dsum += csum;
640                if n == dsum {
641                    return true;
642                }
643
644                if partition(digits, n, parts, p + 1) {
645                    return true;
646                }
647
648                parts[p] = false;
649            }
650
651            false
652        }
653
654        (1..=n)
655            .filter(|&n| {
656                let mut digits = vec![];
657                let mut sqr = n * n;
658                while sqr > 0 {
659                    digits.push(sqr % 10);
660                    sqr /= 10;
661                }
662                digits.reverse();
663
664                partition(&digits, n, &mut vec![false; digits.len()], 0)
665            })
666            .map(|n| n * n)
667            .sum::<i32>()
668    }
669}
670
671#[cfg(test)]
672mod tests;
recursion/lib.rs

recursion/
lib.rs
