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"(, 
 

 /// 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, 


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?

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 ))").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 x

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.