Last active
October 23, 2021 14:10
-
-
Save audreyt/372559f5b58d188adab0 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use std::collections::Bitv; | |
| use std::num; | |
| fn main() { | |
| let mut solved = Bitv::with_capacity(9999999999u, false); | |
| let mut todo = vec![ | |
| 1123456789u, | |
| 2123456789u, | |
| 3123456789u, | |
| 4123456789u, | |
| 5123456789u, | |
| 6123456789u, | |
| 7123456789u, | |
| 8123456789u, | |
| 9123456789u | |
| ]; | |
| let mut n = 0u; | |
| while !todo.is_empty() { | |
| let mut todo_next = vec![]; | |
| for t in todo.iter() { | |
| if solved.get(*t) { continue; } | |
| let pm = t % num::pow(10u, 9); | |
| n = n + 1; | |
| solved.set(*t, true); | |
| let prev = t - pm; | |
| // println!("Solving: {} prev {}", pm, prev); | |
| for i in range(1u, 9) { | |
| for j in range(i+1, 10) { | |
| let di = pm % num::pow(10u, i) | |
| / num::pow(10u, (i-1)); | |
| let dj = pm % num::pow(10u, j) | |
| / num::pow(10u, (j-1)); | |
| // println!("Testing {} (that is {} with {}({})<->{}({}) resolving to {} vs {})", pm_prev, pm, i, di, j, dj, (di+dj)%9, prev%9); | |
| if (prev % 9) == (di + dj) % 9 { | |
| let pm_prev = pm | |
| - (di * num::pow(10u, (i-1))) | |
| - (dj * num::pow(10u, (j-1))) | |
| + (di * num::pow(10u, (j-1))) | |
| + (dj * num::pow(10u, (i-1))); | |
| let wip_i = di * num::pow(10u, 9) + pm_prev; | |
| let wip_j = dj * num::pow(10u, 9) + pm_prev; | |
| todo_next.push(wip_i); | |
| todo_next.push(wip_j); | |
| } | |
| } | |
| } | |
| } | |
| todo = todo_next; | |
| println!("Solved: {}\nTo solve: {}", n, todo.len()); | |
| } | |
| println!("Total bits set to true (should be 3265920 = 9!*9): {}", n); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
These are the openings that, if one of the numbers in the second column is involved, will end up taking 13 steps (the final step is the ending step, so 12 moves). If the player can freely choose another opening then they each take at most 11 moves (12 steps).
Obtained by adding a
roundcounter and an extra line after theprintlnin line 50.