[Rust] Incrementally build possible truth states
Intuition\nSuppose that we were told the good/bad status of the people [0, 1, ...i-1] and we are then considering person i to determine if they\'re good or bad.
# Intuition\nSuppose that we were told the good/bad status of the people [0, 1, ...i-1] and we are then considering person i to determine if they\'re good or bad.\n\nFirst then we can do is ask all of our known-good people about i.\n\nIf some of our trusted memebers say "i is good" and some of them say "i is bad", then we\'re in a contradiction, because i can\'t be good and bad at the same time. That means this can\'t be a possible arrangement, and we throw out this case entirely.\n\nIf at least some of our trusted members say "i is bad" and none of them say "i is good", then i must be bad. So we can extend our known good/bad status with the fact that i is bad.\n\nIf some of our trusted members say "i is good", we then need to check what i has to say. If i disagrees with our current good/bad status (saying a known good j is actually bad, or a known bad j is actually good) then we\'re in a contradiction, and throw out the test case. Otherwise, if all known good js agree i is good, and i agrees with our current good/bad state, we can extend out good/bad status with the fact that i is definitely good.\n\nIf none of our trusted members make any definite statements on i (including if we have no members at all so far), then it\'s possible i is a liar. So we have to consider that.\n\ni might also be good, but only if they agree with our current state. If they do, then we have to consider both possibilities. If they don\'t.\n\nTaken together, this means that a known-good list of [0..i-1] will either be thrown out as a contradiction, will be extended with a single fact about i, or will be split into two new cases where i is good and i is bad.\n\nThis gives us a way to pathfind from no known good/bads, up until we have all n good/bad states defined. \n\n# Complexity\n- Time complexity: O(n^2) average case, O(2^n) in the worst case. Adding each new i requires doing an O(n) scan across the previous truth statements, so it\'s at least O(n^2). And if our grid is entirely 2s (i.e no one makes any statements) we end up considering the entire power set of the set of n people.\n\n- Space complexity: O(n * 2^n), we have to hold an O(n) vector of booleans for up to O(2^n) possible truth states.\n\n# Code\n```\nuse std::collections::VecDeque;\nimpl Solution {\n    pub fn maximum_good(statements: Vec<Vec<i32>>) -> i32 {\n        let n = statements.len();\n\n        let mut queue = VecDeque::<Vec<bool>>::new();\n        queue.push_back(Vec::new());\n        \n        let mut best = 0;\n        while let Some(mut known) = queue.pop_front() {\n            let i = known.len();\n            if i == n {\n                best = best.max(known.into_iter().filter(|&good| good).count());\n                continue;\n            }\n\n            let i_called_bad = known\n            .iter()\n            .enumerate()\n            .any(|(j, &j_good)| j_good && statements[j][i] == 0);\n\n            let i_called_good = known\n            .iter()\n            .enumerate()\n            .any(|(j, &j_good)| j_good && statements[j][i] == 1);\n\n            if i_called_bad && i_called_good {\n                // Contradiction: previous "goods" are in conflict about i\n                // This arrangement is impossible\n                continue;\n            } \n            \n            if i_called_bad {\n                // Previous goods agree i is untrustworthy\n                // We don\'t care what i says\n                known.push(false);\n                queue.push_back(known);\n                continue;\n            }\n\n            // Check consistency against known good js\n            let i_agrees_with_known = known\n            .iter()\n            .enumerate()\n            .all(|(j, &j_good)| {\n                (j_good && statements[i][j] != 0)\n                || (!j_good && statements[i][j] != 1)\n            });\n\n            if i_called_good && !i_agrees_with_known {\n                // Contradiction: i is in conflict with existing goods\n                continue;\n            }\n\n            if i_called_good {\n                // Existing goods like i\n                // i likes all existing goods\n                // i must be good\n                known.push(true);\n                queue.push_back(known);\n                continue;\n            }\n\n            // No previous good j has made a statement on i\n            if i_agrees_with_known {\n                // Possible i tells the truth\n                let mut case_i_good = known.clone();\n                case_i_good.push(true);\n                queue.push_back(case_i_good);\n            }\n\n            // Possible that i is a liar\n            let mut case_i_lies = known;\n            case_i_lies.push(false);\n            queue.push_back(case_i_lies);\n        }\n\n        best as i32\n    }\n}\n```
['Rust']