Ok, here's a naive attempt at a classic problem, which is to read a graph and perform a DFS. The problem is Where is my Internet; here's my naive attempt at it:
// Solution to https://open.kattis.com/problems/wheresmyinternet
// @author godmar
//
// In naive Java (using java.util.Scanner, ArrayDeque<Integer>, and System.out.println()),
// this problem times out with the 1sec limit.
//
// How will it perform in naive Rust?
//
use std::io::{self, BufRead};
// would love to generalize into n ints
fn read2ints<R: BufRead>(stdin: &mut R) -> (usize, usize)
{
let mut line = String::new();
stdin.read_line(&mut line).unwrap();
let line = line.trim(); // trim trailing newline
// how do I destructure the iterator returned by split?
let lv : Vec<usize> = line.split(" ").map(|x| x.parse().unwrap()).collect();
match lv[..] {
[n, m] => return (n, m),
_ => panic!("wrong input")
};
}
fn main() {
let stdin = io::stdin();
let mut stdin = stdin.lock(); // only the locked version implements BufRead
let (n, m) = read2ints(&mut stdin);
// allocate n vectors
let mut adj : Vec<Vec<usize>> = vec![vec![]; n];
// read adjacency lists
for _i in 0..m {
let (a, b) = read2ints(&mut stdin);
adj[a-1].push(b-1);
adj[b-1].push(a-1);
}
// DFS
let mut marked = vec![false; n];
let mut dfs = vec![0];
marked[0] = true;
let mut left = n - 1;
while !dfs.is_empty() {
let u = dfs.pop().unwrap();
for v in &adj[u] {
if !marked[*v] {
left -= 1;
marked[*v] = true;
dfs.push(*v);
}
}
}
// naive, repeated calls to println!
if left == 0 {
println!("Connected");
} else {
for i in 0..n {
if !marked[i] {
println!("{}", i+1);
}
}
}
}
I couldn't figure out how to destructure the iterator returned by the split into a tuple or array, hence the awkward read2ints
function. I also couldn't find a token-based reader (a la scanf
or cin
or java.util.Scanner
or java.util.StringTokenizer
) in the std
library.
The good news is that this naive implementation passes in 0.28s (the limit is 1s). By contrast, an equally naive Java implementation (via java.util.Scanner and System.out.println(), which similarly to Rust fails to buffer) times out due to I/O overhead.
So this is tentative good news, though I'm curious how to write the I/O code more elegantly.