英文:
Why does changing the graph in the main function result in an error?
问题
我从网站复制了一个Rust程序，并且运行良好。但是，当我改变了图形时，却导致了一个错误。可能的原因是什么？
use std::collections::HashMap as H;
type I = i64;
type E = Vec<(I, I)>;
fn d(g: &E) -> bool {
// ...（代码太长，无法完全翻译）
}
fn main() {
let graph = vec![
(0, 1),
(0, 3),
(0, 4),
// ...（部分代码省略）
];
let result = d(&graph);
println!("Result: {}", result);
}
我将图形更改为包含12个顶点的图形，如下所示。
fn main() {
let graph = vec![
(0, 1),
(0, 2),
(0, 3),
// ...（部分代码省略）
];
let result = d(&graph);
println!("Result: {}", result);
}
显示错误信息：
线程 'main' 在 'code.tio:1:816' 处恐慌：尝试溢出乘法
注意：使用RUST_BACKTRACE=1环境变量运行以显示回溯。
我很好奇出了什么问题，以及如何使其正确输出。
英文:
I copied a Rust program from the website, and it ran well. However, when I changed the graph, it resulted in an error. What could be the reason for this?
use std::collections::HashMap as H;type I=i64;
type E=Vec<(I,I)>;fn d(g:&E)->bool{let mut s:Vec<(E,Vec<I>)>=vec![];for e in g{let(v,w)=e;
let f=(*v,*w);let z=|x|s.iter().position(|p|p.1.contains(x));
match(z(v),z(w))
{(Some(i),Some(j))=>{if i!=j{let mut p=s.remove(i);let q=s.remove(j-(i<j)as usize);p.0.extend(q.0);p.1.extend(q.1);s.push(p)}else{s[i].0.push(f)}}(Some(i),_)=>{s[i].0.push(f);s[i].1.push(*w)}(_,Some(j))=>{s[j].0.push(f);s[j].1.push(*v)}_=>{s.push((vec![f], vec![*v, *w]))}}}s.iter().map(|h|{let mut p=H::new();let mut r=H::new();let mut i=0;
for e in&h.0{let(v,w)=e;i+=2;p.insert(i-1,i);p.insert(i,i-1);r.entry(v).or_insert(vec![]).push(i-1);r.entry(w).or_insert(vec![]).push(i)}let mut r:Vec<Vec<I>>=r.values().cloned().collect();r.sort();let mut x=0;let m=r.iter().flat_map(|v|1..v.len()).fold(1,|p,n|p*n);for mut w in 0..m{let mut t=H::new();
for u in&r{let mut v=u.clone();
let s=v.pop().unwrap();let mut f=s;while v.len()>0
{let o=v.remove(w%v.len());w/=v.len()+1;t.insert(f,o);f=o}t.insert(f,s);}let mut f=vec![];let mut n=0;
for s in p.keys(){if!f.contains(s){n+=1;
let mut c=s;loop{f.push(*c);c=&t[&p[c]];if c==s{break}}}}x=x.max(n)}1-(r.len()as I-g.len()as I+x as I)/2}).sum::<I>()<2}
fn main() {
let graph = vec![
(0, 1),
(0, 3),
(0, 4),
(2, 1),
(2, 3),
(2, 5),
(4, 1),
(4, 3),
(4, 5),
(5, 6),
(5, 8),
(5, 10),
(7, 6),
(7, 8),
(7, 10),
(9, 6),
(9, 8),
(9, 10),
];
let result = d(&graph);
println!("Result: {}", result);
}
I changed the graph to one with 12 vertices as follows.
fn main() {
let graph = vec![
(0, 1),
(0, 2),
(0, 3),
(0, 4),
(0, 5),
(0, 6),
(1, 2),
(1, 3),
(1, 4),
(1, 5),
(1, 7),
(2, 3),
(2, 4),
(2, 6),
(2, 7),
(3, 5),
(3, 6),
(3, 7),
(4, 5),
(4, 6),
(4, 8),
(4, 9),
(4, 10),
(5, 7),
(5, 8),
(5, 9),
(5, 11),
(6, 7),
(6, 8),
(6, 10),
(6, 11),
(7, 9),
(7, 10),
(7, 11),
(8, 9),
(8, 10),
(8, 11),
(9, 10),
(9, 11),
(10, 11),
];
let result = d(&graph);
println!("Result: {}", result);
}
It shows:
> thread 'main' panicked at 'attempt to multiply with overflow', code.tio:1:816
> note: run with RUST_BACKTRACE=1 environment variable to display a backtrace.
I'm curious about what went wrong and how to get it to output correctly.
答案1
得分: 1
我编写了这个程序。在未压缩的代码中，旋转系统的数量表示为“num_rotations”变量，其增长速度与图的大小呈指数关系。这就是导致程序溢出并崩溃的变量。然而，即使变量没有溢出，由于每个旋转系统都需要单独评估，评估每个系统并找出给定图是否是环形的时间将变得难以实现。对于像你发布的较大图形，需要依赖更少于蛮力的算法。
英文:
I wrote this program. The number of rotation systems, as represented in the "num_rotations" variable in the ungolfed code, is exponential in the size of the graph. This is the variable that is overflowing and crashing the program. However, even if the variable didn't overflow, because each rotation system is individually evaluated it would take an infeasibly long time to evaluate each of them and find out whether the given graph is toroidal. For larger graphs, like the one you posted, an algorithm which relies less on brute-force is needed.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论