Rust实现AOC2022第7天：示例正常但正式输入结果异常求助

问题概述 #

用Rust完成Advent of Code 2022第7天任务时，代码在示例输入上运行正常，但正式输入结果不符合预期：预期输出1501149，实际得到1035695。

项目结构 #

.
├── example_input.txt
├── input.txt
├── src
    ├── bin
    │  └── part_1.rs
    └── lib.rs

示例输入 #

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

代码内容 #

lib.rs #

#![allow(unused)]
use std::borrow::{Borrow, BorrowMut};
use std::cell::RefCell;
use std::fmt;

macro_rules! get_part {
    ($line:expr, $index:expr) => {
        $line.split(" ").nth($index).unwrap()
    };
}

#[derive(Debug)]
pub struct Dir<'a> {
    pub name: &'a str,
    pub files: Vec<File<'a>>,
    pub dirs: Vec<Dir<'a>>,
}


impl<'a> Dir<'a> {
    pub fn add_content_to_subdir(
        &mut self,
        destination_dir: &str,
        new_dir: &'a str,
        new_file: Option<File<'a>>,
    ) -> () {
        let destination_dir = self.find_dir(destination_dir).unwrap();
        match new_file {
            Some(expr) => destination_dir.files.push(expr),
            None => destination_dir.dirs.push(Dir {
                name: new_dir,
                files: Vec::new(),
                dirs: Vec::new(),
            }),
        }
    }

    pub fn find_dir<'b>(&'b mut self, name: &str) -> Option<&'b mut Dir<'a>> {
        if self.name == name {
            return Some(self);
        }
        self.dirs.iter_mut().find_map(|dir| dir.find_dir(name))
    }

    pub fn find_dir_not_mut<'b>(&'b self, name: &str) -> Option<&'b Dir<'a>> {
        if self.name == name {
            return Some(self);
        }

        self.dirs.iter().find_map(|dir| dir.find_dir_not_mut(name))
    }
}

fn calculate_size_of_folder<'a>(dir: &'a RefCell<Dir<'a>>, name: &str) -> Option<i64> {
    let mut sum = 0;
    let search_in = dir.borrow();
    let search_in = search_in.find_dir_not_mut(name).unwrap();
    
    for file in &search_in.files {
        sum += file.size;
    }
    if sum > 100000 {
        return None;
    }
    for subdir in &search_in.dirs {
        if let Some(size) = calculate_size_of_folder(dir, &subdir.name) {
            sum += size;
        }
    }
    if sum > 100000 {
        return None;
    }

    Some(sum)
}



#[derive(Debug)]
pub struct File<'a> {
    pub name: &'a str,
    pub size: i64,
}

fn read_input<'a>(
    input: &'a str,
    dir: &'a RefCell<Dir<'a>>,
) -> (&'a RefCell<Dir<'a>>, Vec<String>) {
    let mut file = File { name: "", size: 13 };
    let mut all_dirs = vec![];
    let mut dir_name = "";
    let mut found_dir = "";
    for line in input.lines() {
        match line {
            line if line.starts_with("$ ls") => {}
            line if line.starts_with("$ cd ..") => {}
            line if line.starts_with("$ cd ") => {
                dir_name = get_part!(line, 2);
                all_dirs.push(dir_name.to_string());
            }
            line if line.starts_with("dir ") => {
                found_dir = get_part!(line, 1);
                dir.borrow_mut()
                    .add_content_to_subdir(dir_name, found_dir, None);
            }
            _ => {
                let size: i64 = get_part!(line, 0).parse::<i64>().unwrap();
                let size: i64 = get_part!(line, 0).parse::<i64>().unwrap();
                let name = get_part!(line, 1);
                dir.borrow_mut().add_content_to_subdir(
                    dir_name,
                    "",
                    Some(File { size, name }),
                );
            }
        }
    }
    (dir, all_dirs)
}

pub fn part_one(input: &str) {
    let mut dir = RefCell::new(Dir {
        name: "/",
        files: vec![],
        dirs: vec![],
    });

    let (file_tree, mut all_dirs) = read_input(&input, &dir);

    let mut sum = 0;

    for dir in &all_dirs {
        let dir_size = calculate_size_of_folder(file_tree, &dir);
        match dir_size {
            Some(expr) => sum += expr,
            None => (),
        }
    }

    println!("{}", sum);
}

part_1.rs #

use d7::*;
use std::fs;

fn main() {
    let input = fs::read_to_string("input.txt").unwrap();
    part_one(input);
}

问题根源分析 #

1. 目录查找逻辑缺陷：find_dir和find_dir_not_mut通过目录名称全局查找，正式输入中存在同名目录时，会错误匹配到其他层级的目录，导致内容添加位置错误，最终大小计算偏差。
2. 当前目录跟踪失效：处理$ cd ..时未更新当前目录的状态，dir_name始终停留在上一级目录，后续所有文件/目录都会被错误添加到之前的目录下，完全破坏了目录结构。
3. 目录大小计算逻辑错误：calculate_size_of_folder在计算过程中，若当前目录文件总和超过100000就直接返回None，且仅累加子目录中大小<=100000的部分。但题目要求计算目录完整总大小（包含所有子目录），再判断是否<=100000，当前逻辑完全错误地截断了大小计算。
4. 重复计算目录：all_dirs会重复收集同一名称的目录（不同层级），导致同一目录被多次求和。

修复方案 #

1. 维护当前目录层级（用栈跟踪） #

替换单个dir_name为栈结构，准确跟踪当前目录路径，避免同名目录冲突：

fn read_input<'a>(
    input: &'a str,
    root: &'a RefCell<Dir<'a>>,
) -> (&'a RefCell<Dir<'a>>, Vec<Vec<&'a str>>) {
    let mut all_dir_paths = vec![];
    let mut current_path = vec!["/"];
    all_dir_paths.push(current_path.clone());

    for line in input.lines() {
        match line {
            line if line.starts_with("$ ls") => {}
            line if line.starts_with("$ cd ..") => {
                if current_path.len() > 1 {
                    current_path.pop();
                }
            }
            line if line.starts_with("$ cd /") => {
                current_path = vec!["/"];
                all_dir_paths.push(current_path.clone());
            }
            line if line.starts_with("$ cd ") => {
                let dir_name = get_part!(line, 2);
                current_path.push(dir_name);
                all_dir_paths.push(current_path.clone());
            }
            line if line.starts_with("dir ") => {
                let dir_name = get_part!(line, 1);
                // 从根目录遍历到当前路径，找到当前目录
                let mut current_dir = root.borrow_mut();
                for &name in &current_path[1..] {
                    current_dir = current_dir.find_dir(name).unwrap();
                }
                current_dir.dirs.push(Dir {
                    name: dir_name,
                    files: Vec::new(),
                    dirs: Vec::new(),
                });
            }
            _ => {
                let size: i64 = get_part!(line, 0).parse().unwrap();
                let name = get_part!(line, 1);
                let mut current_dir = root.borrow_mut();
                for &name in &current_path[1..] {
                    current_dir = current_dir.find_dir(name).unwrap();
                }
                current_dir.files.push(File { size, name });
            }
        }
    }
    // 去重目录路径
    all_dir_paths.dedup();
    (root, all_dir_paths)
}

2. 修正目录大小计算逻辑 #

先计算目录完整总大小，再判断是否符合条件：

// 新增辅助函数：计算目录总大小
fn get_dir_size(dir: &Dir) -> i64 {
    let mut size = 0;
    // 累加当前目录文件大小
    for file in &dir.files {
        size += file.size;
    }
    // 累加子目录大小
    for subdir in &dir.dirs {
        size += get_dir_size(subdir);
    }
    size
}

// 修正后的计算函数
fn calculate_size_of_folder<'a>(dir: &'a RefCell<Dir<'a>>, path: &[&str]) -> Option<i64> {
    let root = dir.borrow();
    let mut current_dir = &root;
    // 根据路径找到目标目录
    for &name in &path[1..] {
        current_dir = current_dir.find_dir_not_mut(name).unwrap();
    }
    let total_size = get_dir_size(current_dir);
    if total_size <= 100000 {
        Some(total_size)
    } else {
        None
    }
}

3. 更新part_one函数 #

适配新的目录路径集合：

pub fn part_one(input: &str) {
    let root = RefCell::new(Dir {
        name: "/",
        files: vec![],
        dirs: vec![],
    });

    let (file_tree, all_dir_paths) = read_input(&input, &root);

    let mut sum = 0;

    for path in &all_dir_paths {
        if let Some(size) = calculate_size_of_folder(file_tree, path) {
            sum += size;
        }
    }

    println!("{}", sum);
}

额外优化 #

• 移除read_input中重复的size解析代码；
• 可以给Dir添加parent引用，避免每次从根目录遍历查找当前目录，提升效率。

内容的提问来源于stack exchange，提问作者grandkahuna