The Ducci Sequence

Question

I wrote the following Rust code to solve this task on /r/DailyProgrammer.

Given an n-tuple of numbers as input, the Ducci Sequence is formed by taking the absolute difference of the difference between neighboring elements. (The last result is the difference between the first and last elements.)

Example input

[0; 653; 1854; 4063]

Example output

Emit the number of steps taken to get to either an all 0 tuple or when it enters a stable repeating pattern.

[0; 653; 1854; 4063]
[653; 1201; 2209; 4063]
[548; 1008; 1854; 3410]
[460; 846; 1556; 2862]
[386; 710; 1306; 2402]
[324; 596; 1096; 2016]
[272; 500; 920; 1692]
[228; 420; 772; 1420]
[192; 352; 648; 1192]
[160; 296; 544; 1000]
[136; 248; 456; 840]
[112; 208; 384; 704]
[96; 176; 320; 592]
[80; 144; 272; 496]
[64; 128; 224; 416]
[64; 96; 192; 352]
[32; 96; 160; 288]
[64; 64; 128; 256]
[0; 64; 128; 192]
[64; 64; 64; 192]
[0; 0; 128; 128]
[0; 128; 0; 128]
[128; 128; 128; 128]
[0; 0; 0; 0]
24 steps

I'm aware all the extra functions and error handling are a bit exaggerated for a task this easy, but I'm learning rust at the moment so I tried to get things right.

extern crate regex;

use std::io::Write;
use std::fmt::Display;
use std::fmt;
use regex::Regex;
use std::io;
use std::error;


fn main() {
    match read_input() {
        Ok(tuple) => {
            run(tuple);
        }   
        Err(e) => {
            eprintln!("An error occured: {}", e);
        }
    }
}

/// Tries to read input from standard input
fn read_input() -> Result<Tuple, Error> {
    print!("input: ");
    io::stdout().flush().unwrap();

    let mut input = String::new();
    io::stdin().read_line(&mut input)?;

    Tuple::new(input)
}

/// runs Ducci sequence calculation and prints every step
fn run(tuple: Tuple) {
    let mut i = tuple;

    let mut history: Vec<Tuple> = Vec::new();
    let mut steps = 1;

    while !&i.zeros() && !history.contains(&i) {
        let next = i.next();
        history.push(i);
        i = next;
        println!("{}", i);
        steps += 1;
    }

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

struct Tuple {
    data: Vec<i32>,
}

impl Tuple {
    fn new(line: String) -> Result<Tuple, Error> {
        // Regex for allowed inputs: (a, b, c, ..., d)
        let re = Regex::new(r"\(((\d)+, )*(\d)+\)").unwrap();

        if!re.is_match(line.as_str()) {
            Err(Error::ParsingError) 
        }
        else {
            // seperate single numbers, parse to integer and push into tuple instance
            let sep = Regex::new(r"(, |\(|\))").unwrap();
            let mut data: Vec<i32> =  Vec::new();
            for numbers in sep.split(line.as_str()) {
                match numbers.parse::<i32>() {
                    Ok(number) => {
                        data.push(number);
                    },
                    // ignore newline and empty captures
                    Err(_) => {},
                }   
            }
            Ok(Tuple {
                data: data,
            })
        }   
    }

    /// Calculates and returns next tuple in ducci sequence
    fn next(&self) -> Tuple {
        let mut data: Vec<i32> = Vec::new();

        // calculate first n - 1 new values
        for i in 0..self.dimension() - 1 {
            data.push((self.data[i] - self.data[i + 1]).abs());
        }
        // calculate last value
        data.push((self.data[self.dimension() - 1] - self.data[0]).abs());

        Tuple {
            data: data,
        }
    }

    /// Returns tuples dimension
    fn dimension(&self) -> usize {
        self.data.len()
    }

    /// Determines whether tuple only contains zeros
    fn zeros(&self) -> bool {
        self.data.iter().fold(true, |acc, x| {acc && *x == 0})
    }
}

impl PartialEq for Tuple {
    fn eq(&self, other: &Tuple) -> bool {
        if self.dimension() != other.dimension() { 
            false 
        }
        else {
            let mut e = true;
            for i in 0..self.dimension() {
                e = e && self.data[i] == other.data[i];
            }
            e
        } 
    }
}

impl Display for Tuple {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut s = String::new();

        s.push_str("[");

        for i in 0..self.dimension() - 1 {
            s.push_str(self.data[i].to_string().as_str());
            s.push_str("; ");
        }
        s.push_str(self.data[self.dimension() - 1].to_string().as_str());
        s.push_str("]");

        write!(f, "{}", s)
    }
}






#[derive(Debug)]
enum Error {
    ReadingError,
    ParsingError,
}

impl Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        match self {
            Error::ReadingError => {
                f.write_str("Error while reading input line from standard input.")

            }
            Error::ParsingError => {
                f.write_str("Input line does not meet format requirements: (a, b, c, ..., d)")
            }
        }
    }
}

impl error::Error for Error {}

impl std::convert::From<std::io::Error> for Error {
    fn from(_e: std::io::Error) -> Self {
        Error::ReadingError
    }
}

What are youre thoughts? What can I do better or in a more elegant way?

Answer 1

This is only a summary of some remarks that came to mind when I read your code. It looks good, but I would run it through rustfmt. Also, your delimiters are parentheses and commas ((…,…)) instead of brackets and semicolons ([…;…]), that seems off.

Use return to short-circuit were appropriate

While you can use expressions instead of explicit returns, an explicit return can make a function simpler in some circumstances. For example, your eq implementation can get simplified:

impl PartialEq for Tuple {
    fn eq(&self, other: &Tuple) -> bool {
        if self.dimension() != other.dimension() {
            false
        } else {
            for i in 0..self.dimension() {
                if self.data[i] != other.data[i] {
                    return false;
                }
            }
            true
        }
    }
}

We don't have any mutable state e. Furthermore, if the first element differs, we don't need to check all elements.

Use derive where appropriate

However, your PartialEq implementation acts the same as the Vec<i32> one. It's therefore appropriate to use

#[derive(PartialEq, Debug)]
struct Tuple {
    …
}

instead. No need to reinvent the wheel here.

Follow existing interfaces

Your fn new(input: String) -> Result<…,…> looks almost like from_str. We should use from_str from FromStr instead:

impl FromStr for Tuple {
    type Err = Error;

    fn from_str(line: &str) -> Result<Self, Self::Err> {
        // Regex for allowed inputs: (a, b, c, ..., d)
        let re = Regex::new(r"\(((\d)+, )*(\d)+\)").unwrap();

        if!re.is_match(line) {
            Err(Error::ParsingError) 
        }
        else {
            // seperate single numbers, parse to integer and push into tuple instance
            let sep = Regex::new(r"(, |\(|\))").unwrap();
            let mut data: Vec<i32> =  Vec::new();
            for numbers in sep.split(line) {
                match numbers.parse::<i32>() {
                    Ok(number) => {
                        data.push(number);
                    },
                    // ignore newline and empty captures
                    Err(_) => {},
                }   
            }
            Ok(Tuple {
                data: data,
            })
        }   
    }
}

Prefer non-owning types when possible

As you can see, from_str uses &str instead of String. from_str doesn't need to take ownership of the string, and neither did your original new. Indeed, all your uses of line in new needed as_str().

Use specialized functions where appropriate

zeroes uses fold with a boolean state. This has the same problem as your eq implementation: if the first number differs from zero, we will still check all numbers.

Instead, use all:

fn zeros(&self) -> bool {
    self.data.iter().all(|x| *x == 0)
}

Answer 2

Not a review, but an extended comment.

The loop detection by means of history drives the time complexity quadratic to the number of steps. There are two ways out: either

• use a Floyd loop detection (with slow and fast tuples), or

• exploit the property of Ducci sequence: it becomes periodic once it reaches the "binary" form, that is all non-zero elements are equal.

This way you don't need history at all. Space complexity is \$O(1)\$, and time complexity is linear to the number of steps.