Building a training set of tags for rust

[iHiD]

Hello lovely maintainers :wave:

We've recently added "tags" to student's solutions. These express the constructs, paradigms and techniques that a solution uses. We are going to be using these tags for lots of things including filtering, pointing a student to alternative approaches, and much more.

In order to do this, we've built out a full AST-based tagger in C#, which has allowed us to do things like detect recursion or bit shifting. We've set things up so other tracks can do the same for their languages, but its a lot of work, and we've determined that actually it may be unnecessary. Instead we think that we can use machine learning to achieve tagging with good enough results. We've fine-tuned a model that can determine the correct tags for C# from the examples with a high success rate. It's also doing reasonably well in an untrained state for other languages. We think that with only a few examples per language, we can potentially get some quite good results, and that we can then refine things further as we go.

I released a new video on the Insiders page that talks through this in more detail.

We're going to be adding a fully-fledged UI in the coming weeks that allow maintainers and mentors to tag solutions and create training sets for the neural networks, but to start with, we're hoping you would be willing to manually tag 20 solutions for this track. In this post we'll add 20 comments, each with a student's solution, and the tags our model has generated. Your mission (should you choose to accept it) is to edit the tags on each issue, removing any incorrect ones, and add any that are missing. In order to build one model that performs well across languages, it's best if you stick as closely as possible to the C# tags as you can. Those are listed here. If you want to add extra tags, that's totally fine, but please don't arbitrarily reword existing tags, even if you don't like what Erik's chosen, as it'll just make it less likely that your language gets the correct tags assigned by the neural network.

---

To summarise - there are two paths forward for this issue:

1. You're up for helping: Add a comment saying you're up for helping. Update the tags some time in the next few days. Add a comment when you're done. We'll then add them to our training set and move forward.
2. You not up for helping: No problem! Just please add a comment letting us know :)

If you tell us you're not able/wanting to help or there's no comment added, we'll automatically crowd-source this in a week or so.

Finally, if you have questions or want to discuss things, it would be best done on the forum, so the knowledge can be shared across all maintainers in all tracks.

Thanks for your help! :blue_heart:

---

Note: Meta discussion on the forum

[iHiD]

Exercise: raindrops

Code

pub fn raindrops(n: usize) -> String {
    let mut output = String::new();
    if n % 3 == 0 {
        output.push_str("Pling");
    }

    if n % 5 == 0 {
        output.push_str("Plang");
    }

    if n % 7 == 0 {
        output.push_str("Plong");
    }

    // If our output has no characters, return the int as a string
    if output == "" {
        output.push_str(&n.to_string());
    }

    output
}

Tags:

construct:assignment
construct:if
construct:if-else
construct:impl
construct:invocation
construct:method
construct:parameter
construct:comment
construct:string
construct:assignment
construct:usize
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
paradigm:procedural

[iHiD]

Exercise: sum-of-multiples

Code

pub fn sum_of_multiples(n: u64, m: &[u64]) -> u64 {
    (0..n).filter(|&i| {
        m.iter().any(|&x| x != 0 && i % x == 0)
    }).sum()
}

Tags:

construct:&&
construct:0
construct:boolean
construct:closure
construct:filter
construct:fn
construct:impl
construct:invocation
construct:iterator
construct:logical-and
construct:method
construct:number
construct:parameter
construct:range
construct:u64
construct:visibility
paradigm:functional
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
uses:Iterator::any

[iHiD]

Exercise: series

Code

pub fn series(digits: &str, len: usize) -> Vec<String> {
    digits
        .chars()
        .collect::<Vec<char>>()
        .windows(len)
        .map(|w| w.iter().collect::<String>())
        .collect()
}

Tags:

construct:char
construct:collect
construct:generic-type
construct:impl
construct:iterator
construct:lambda
construct:method
construct:parameter
construct:pub
construct:str
construct:string
construct:trait
construct:usize
construct:vector
construct:windows
paradigm:functional
paradigm:object-oriented
technique:higher-order-functions
uses:Vec<T>

[iHiD]

Exercise: diffie-hellman

Code

extern crate rand;

use rand::prelude::*;

pub fn private_key(p: u64) -> u64 {
    thread_rng().gen_range(2, p)
}

pub fn public_key(p: u64, g: u64, a: u64) -> u64 {
    modular_pow(g, a, p)
}

pub fn secret(p: u64, b_pub: u64, a: u64) -> u64 {
    modular_pow(b_pub, a, p)
}

//Based on wikipedia's explanation
fn modular_pow(a: u64, b: u64, m: u64) -> u64 {
    if m == 1 { return 0; }
    let mut c = 1;
    for _x in 0..b {
        c = (c * a) % m;
    }
    c
}

Tags:

construct:assignment
construct:comment
construct:extern crate
construct:for loop
construct:if expression
construct:invocation
construct:let binding
construct:method
construct:multiply
construct:number
construct:parameter
construct:return
construct:u64
construct:use directive
construct:variable
construct:visibility modifier
paradigm:imperative
paradigm:functional
paradigm:object-oriented
technique:looping

[iHiD]

Exercise: clock

Code

#![feature(euclidean_division)]
use std::fmt;

#[derive(Debug, PartialEq)]
pub struct Clock {
    minutes: i32,
}

const MINS_PER_DAY: i32 = 60 * 24;

impl Clock {
    pub fn new(hours: i32, minutes: i32) -> Self {
        Clock {
            minutes: (hours * 60 + minutes).mod_euc(MINS_PER_DAY),
        }
    }

    pub fn add_minutes(self, minutes: i32) -> Self {
        Clock::new(0, self.minutes + minutes)
    }
}

impl fmt::Display for Clock {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:02}:{:02}", self.minutes / 60, self.minutes % 60)
    }
}

Tags:

construct:add
construct:const
construct:divide
construct:field
construct:fn
construct:impl
construct:integral-number
construct:invocation
construct:method
construct:multiply
construct:number
construct:parameter
construct:struct
construct:use
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented

[iHiD]

Exercise: pascals-triangle

Code

#![feature(iter_unfold)]

use std::iter::successors;

pub struct PascalsTriangle {
    row_count: u32,
}

impl PascalsTriangle {
    pub fn new(row_count: u32) -> Self {
        Self { row_count }
    }

    pub fn rows(&self) -> Vec<Vec<u32>> {
        successors(Some(vec![1]), |row| {
            let mut next = row.to_owned();
            next.push(0);
            for (a, b) in next.iter_mut().skip(1).zip(row).rev() {
                *a += b;
            }
            Some(next)
        })
        .take(self.row_count as usize)
        .collect()
    }
}

Tags:

construct:as-cast
construct:assignment
construct:attribute
construct:for-loop
construct:impl
construct:invocation
construct:lambda
construct:method
construct:number
construct:parameter
construct:struct
construct:tuple
construct:u32
construct:use-directive
construct:vector
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions
technique:looping
technique:type-conversion
uses:Vec

[iHiD]

Exercise: all-your-base

Code

#[derive(Debug, PartialEq)]
pub enum Error {
    InvalidInputBase,
    InvalidOutputBase,
    InvalidDigit(u32),
}

///
/// Convert a number between two bases.
///
/// A number is any slice of digits.
/// A digit is any unsigned integer (e.g. u8, u16, u32, u64, or usize).
/// Bases are specified as unsigned integers.
///
/// Return an `Err(.)` if the conversion is impossible.
/// The tests do not test for specific values inside the `Err(.)`.
///
///
/// You are allowed to change the function signature as long as all test still pass.
///
///
/// Example:
/// Input
///   number: &[4, 2]
///   from_base: 10
///   to_base: 2
/// Result
///   Ok(vec![1, 0, 1, 0, 1, 0])
///
/// The example corresponds to converting the number 42 from decimal
/// which is equivalent to 101010 in binary.
///
///
/// Notes:
///  * The empty slice ( "[]" ) is equal to the number 0.
///  * Never output leading 0 digits. However, your function must be able to
///     process input with leading 0 digits.
///
pub fn convert(number: &[u32], from_base: u32, to_base: u32) -> Result<Vec<u32>, Error> {
    if from_base < 2 { return Err(Error::InvalidInputBase) }
    if to_base < 2 { return Err(Error::InvalidOutputBase) }

    let base10_value = convert_to_base10(number, from_base)?;
    Ok(convert_int_to_base(base10_value, to_base))
}

fn convert_to_base10(number: &[u32], from_base: u32) -> Result<u32, Error> {
    let mut result = 0;

    for (i, &digit) in number.iter().rev().enumerate() {
        if digit >= from_base { return Err(Error::InvalidDigit(digit))}

        result += from_base.pow(i as u32) * digit;
    }

    Ok(result)
}

fn convert_int_to_base(mut value: u32, to_base: u32) -> Vec<u32> {
    let mut result = vec![];

    while value != 0 {
        result.push(value % to_base);
        value /= to_base;
    }

    result.into_iter().rev().collect()
}

Tags:

construct:as-cast
construct:assignment
construct:attribute
construct:binary
construct:bitwise-and
construct:bitwise-or
construct:bitwise-xor
construct:enum
construct:for-loop
construct:function
construct:if-expression
construct:impl
construct:invocation
construct:iterator
construct:loop
construct:method
construct:multiply
construct:number
construct:parameter
construct:pattern-matching
construct:return
construct:shorthand-assignment
construct:struct
construct:u32
construct:usize
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:bit-manipulation
technique:bit-shifting
technique:looping

[iHiD]

Exercise: robot-simulator

Code

#[derive(PartialEq, Debug)]
pub enum Direction {
    North,
    East,
    South,
    West,
}

pub struct Robot {
    x: isize,
    y: isize,
    d: Direction,
}

impl Robot {
    pub fn new(x: isize, y: isize, d: Direction) -> Self {
        Robot { x, y, d }
    }

    pub fn turn_right(self) -> Self {
        Robot {
            x: self.x,
            y: self.y,
            d: match self.d {
                Direction::North => Direction::East,
                Direction::East => Direction::South,
                Direction::South => Direction::West,
                Direction::West => Direction::North,
            },
        }
    }

    pub fn turn_left(self) -> Self {
        Robot {
            x: self.x,
            y: self.y,
            d: match self.d {
                Direction::North => Direction::West,
                Direction::West => Direction::South,
                Direction::South => Direction::East,
                Direction::East => Direction::North,
            },
        }
    }

    pub fn advance(self) -> Self {
        Robot {
            x: match self.d {
                Direction::East => self.x + 1,
                Direction::West => self.x - 1,
                _ => self.x,
            },
            y: match self.d {
                Direction::North => self.y + 1,
                Direction::South => self.y - 1,
                _ => self.y,
            },
            d: self.d,
        }
    }

    pub fn instructions(self, instructions: &str) -> Self {
        let mut robot = self;

        for command in instructions.chars() {
            match command {
                'L' => robot = robot.turn_left(),
                'R' => robot = robot.turn_right(),
                'A' => robot = robot.advance(),
                _ => panic!("Illegal command"),
            }
        }
        robot
    }

    pub fn position(&self) -> (isize, isize) {
        (self.x, self.y)
    }

    pub fn direction(&self) -> &Direction {
        &self.d
    }
}

Tags:

construct:add
construct:assignment
construct:char
construct:debug-attribute
construct:enum
construct:field-init
construct:for-loop
construct:impl
construct:isize
construct:let
construct:match
construct:method
construct:number
construct:panic
construct:parameter
construct:pattern
construct:struct
construct:tuple
construct:underscore
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:looping

[iHiD]

Exercise: matching-brackets

Code

use std::vec::Vec;

pub fn brackets_are_balanced(string: &str) -> bool {
    let mut stack: Vec<char> = Vec::new();
    for (single_char) in string.chars() {
        match single_char {
            '(' => {
                stack.push(single_char);
                continue;
            }
            '[' => {
                stack.push(single_char);
                continue;
            }
            '{' => {
                stack.push(single_char);
                continue;
            }
            '}' if stack.last() == Some(&'{') => {
                stack.pop();
                continue;
            }
            ']' if stack.last() == Some(&'[') => {
                stack.pop();
                continue;
            }
            ')' if stack.last() == Some(&'(') => {
                stack.pop();
                continue;
            }
            '}' if stack.last() != Some(&'{') => {
                return false;
            }
            ']' if stack.last() != Some(&'[') => {
                return false;
            }
            ')' if stack.last() != Some(&'(') => {
                return false;
            }

            _ => {}
        }
    }

    if stack.is_empty() {
        true
    } else {
        false
    }
}

Tags:

construct:boolean
construct:char
construct:continue
construct:for_loop
construct:if_expression
construct:impl
construct:invocation
construct:loop
construct:match_expression
construct:method
construct:mutable_variable
construct:parameter
construct:pattern_matching
construct:return
construct:std::char
construct:std::vec
construct:use_directive
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:looping
uses:Vec<T>

[iHiD]

Exercise: bowling

Code

#[derive(Debug, PartialEq)]
pub enum Error {
    NotEnoughPinsLeft,
    GameComplete,
}

pub struct BowlingGame {
    pub frames: Vec<Frame>,
    pub current_frame: Frame,
}
#[derive(Copy, Clone)]
pub struct Frame {
    pub is_spare: bool,
    pub is_strike: bool,
    pub shots_done: u16,
    pub first: u16,
    pub second:u16,
    pub third:u16
}
impl BowlingGame {
    pub fn new() -> Self {
        BowlingGame{frames:Vec::new(),
            current_frame:Frame{
                is_strike:false, is_spare: false,
                first:0, second:0, third:0, shots_done:0}}
    }

    pub fn roll(&mut self, pins: u16) -> Result<(), Error> {
        if self.frames.len() == 10 {
            return  Err(Error::GameComplete);
        }
        //X frame
        if self.frames.len() == 9 {
            if self.current_frame.shots_done == 0 {
                if pins > 10 {
                    return Err(Error::NotEnoughPinsLeft);
                }
                if pins == 10 {
                    self.current_frame.is_strike = true;
                }
                self.current_frame.first = pins;
                self.current_frame.shots_done = 1;
                return Ok(());
            }
            if self.current_frame.shots_done == 1 {
                if pins > 10 {
                    return Err(Error::NotEnoughPinsLeft);
                }
                if !self.current_frame.is_strike && (self.current_frame.first + pins) > 10 {
                    return Err(Error::NotEnoughPinsLeft);
                }
                if pins == 10 {
                    self.current_frame.is_strike = true;
                }
                if pins + self.current_frame.first == 10 {
                    self.current_frame.is_spare = true;
                }
                self.current_frame.second = pins;
                self.current_frame.shots_done = 2;
                if !self.current_frame.is_spare && !self.current_frame.is_strike {
                    self.finish_frame();
                }
                return Ok(());
            }
            if self.current_frame.shots_done == 2 &&
                (self.current_frame.is_spare || self.current_frame.is_strike) {
                if pins > 10 {
                    return Err(Error::NotEnoughPinsLeft);
                }
                if self.current_frame.second!=10 && !self.current_frame.is_spare {
                    if pins == 10 || self.current_frame.second + pins > 10{
                        return Err(Error::NotEnoughPinsLeft);
                    }

                }
                self.current_frame.third = pins;
                self.finish_frame();
                return Ok(());
            }

        }

        if self.current_frame.shots_done == 0 {
            if pins > 10 {
                return Err(Error::NotEnoughPinsLeft);
            }
            //Strike
            if pins == 10 {
                self.current_frame.is_strike = true;
                self.current_frame.first = 10;
                self.finish_frame();
            } else {
                //normal
                self.current_frame.shots_done = 1;
                self.current_frame.first = pins;
            }

            return Ok(());
        }

        if self.current_frame.shots_done == 1 {
            if pins + self.current_frame.first > 10 {
                return Err(Error::NotEnoughPinsLeft);
            }
            //Spare
            if  pins + self.current_frame.first == 10 {
                self.current_frame.is_spare = true;
            }
            self.current_frame.shots_done = 2;
            self.current_frame.second = pins;
            self.finish_frame();
        }
        Ok(())
    }
    fn finish_frame(&mut self) {
        self.frames.push(self.current_frame);
        self.current_frame = Frame{
            is_strike:false, is_spare: false,
            first:0, second:0, third:0, shots_done:0};
    }
    pub fn score(&self) -> Option<u16> {
        if self.frames.len() == 10 {
            let mut total = 0;
            for i in 0..10 {
                let frame = self.frames[i];
                if i < 9 {
                   total += frame.first + frame.second;
                   if frame.is_spare {
                       total += self.frames[i+1].first;
                   }
                   if frame.is_strike {
                       if self.frames[i+1].is_strike && i < 8 {
                           total += self.frames[i+1].first + self.frames[i+2].first;
                       } else {
                           total += self.frames[i+1].first + self.frames[i+1].second;
                       }

                   }
                }
                else {
                    total += frame.first + frame.second + frame.third;
                }
            }
            Some(total)
        }
        else {
            None
        }
    }
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:comment
construct:enum
construct:for_loop
construct:if
construct:impl
construct:indexing
construct:initializer
construct:method
construct:number
construct:parameter
construct:return
construct:struct
construct:u16
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:looping

[iHiD]

Exercise: phone-number

Code

pub fn number(input: &str) -> Option<String> {
    input
        .chars()
        .filter(|c| c.is_ascii_digit())
        .enumerate()
        .filter(|&(i, c)| !(i == 0 && c == '1'))
        .enumerate()
        .map(|(i, (_, c))| match c {
            '0'...'1' if [0, 3].contains(&i) => None,
            _ => Some(c),
        })
        .collect::<Option<String>>()
        .filter(|s| s.len() == 10)
}

Tags:

construct:&&
construct:if
construct:impl
construct:input-parameter
construct:invocation
construct:iterator
construct:lambda
construct:match
construct:method
construct:number
construct:parameter
construct:range
construct:reference
construct:return
construct:string
construct:tuple
construct:underscore
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions

[iHiD]

Exercise: tournament

Code

use std::cmp::Ordering;
use std::collections::HashMap;
use std::fmt;
use std::iter::FromIterator;

#[derive(Debug)]
enum MatchResult {
    Win,
    Loose,
    Draw,
}

#[derive(Debug)]
struct Stats {
    win: u32,
    loose: u32,
    draw: u32,
}

struct Match {
    team_a: String,
    team_b: String,
    result: MatchResult,
}

impl Stats {
    fn points(&self) -> u32 {
        3 * self.win + self.draw
    }
    fn played(&self) -> u32 {
        self.win + self.loose + self.draw
    }
    fn new() -> Self {
        Stats {
            win: 0,
            loose: 0,
            draw: 0,
        }
    }
}

impl fmt::Display for Stats {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{} |  {} |  {} |  {} |  {}",
            self.played(),
            self.win,
            self.draw,
            self.loose,
            self.points()
        )
    }
}

impl<'a> FromIterator<&'a str> for Match {
    fn from_iter<I: IntoIterator<Item = &'a str>>(iter: I) -> Self {
        let mut iter = iter.into_iter();
        let team_a = iter.next().unwrap().to_owned();
        let team_b = iter.next().unwrap().to_owned();

        let result = match iter.next().unwrap() {
            "draw" => MatchResult::Draw,
            "win" => MatchResult::Win,
            _ => MatchResult::Loose,
        };

        Match {
            team_a,
            team_b,
            result,
        }
    }
}

pub fn tally(match_results: &str) -> String {
    let mut teams = HashMap::new();

    for line in match_results.lines() {
        let match_result = line.split(";").collect::<Match>();

        match match_result.result {
            MatchResult::Win => {
                teams.entry(match_result.team_a).or_insert(Stats::new()).win += 1;
                teams
                    .entry(match_result.team_b)
                    .or_insert(Stats::new())
                    .loose += 1;
            }
            MatchResult::Loose => {
                teams
                    .entry(match_result.team_a)
                    .or_insert(Stats::new())
                    .loose += 1;
                teams.entry(match_result.team_b).or_insert(Stats::new()).win += 1;
            }
            MatchResult::Draw => {
                teams
                    .entry(match_result.team_a)
                    .or_insert(Stats::new())
                    .draw += 1;
                teams
                    .entry(match_result.team_b)
                    .or_insert(Stats::new())
                    .draw += 1;
            }
        };
    }

    let mut teams_vec = teams.iter().collect::<Vec<_>>();

    println!("{:?}", teams_vec);

    teams_vec.sort_by(|(team_a, stats_a), (team_b, stats_b)| {
        match (team_a.cmp(team_b), stats_b.points().cmp(&stats_a.points())) {
            (a, Ordering::Equal) => a,
            (_, a) => a,
        }
    });

    println!("{:?}", teams_vec);

    teams_vec.iter().fold(
        "Team                           | MP |  W |  D |  L |  P".to_string(),
        |accum, (team_name, stats)| format!("{}\n{:30} |  {}", accum, team_name, stats),
    )
}

Tags:

construct:add
construct:assignment
construct:attribute
construct:enum
construct:for-loop
construct:generic-function
construct:hashmap
construct:impl
construct:invocation
construct:lambda
construct:let
construct:lifetime
construct:loop
construct:match
construct:method
construct:multiply
construct:number
construct:parameter
construct:struct
construct:string
construct:tuple
construct:underscore
construct:use-directive
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions
uses:HashMap
uses:String
uses:Vec

[iHiD]

Exercise: alphametics

Code

use std::collections::{HashMap, HashSet};

struct AlphaNumMap(Vec<char>);

impl AlphaNumMap {
    pub fn new() -> Self {
        Self(Vec::with_capacity(10))
    }

    pub fn push(&mut self, c: char) {
        self.0.push(c);
    }

    pub fn pop(&mut self) {
        self.0.pop();
    }

    pub fn value(&self, c: char) -> u64 {
        self.0.iter().position(|&e| e == c).map(|n| n as u64).expect(&format!("Unmmapped {:?}", c))
    }

    pub fn to_hashmap(&self) -> Option<HashMap<char, u8>> {
        if self.0.len() > 0 {
            Some(self.0.iter()
                       .enumerate()
                       .filter(|(_,&c)| c != ' ')
                       .map(|(i,&c)| (c, i as u8))
                       .collect())
        } else {
            None
        }
    }
}

struct AlphaNum<'a>(&'a str);

impl<'a> AlphaNum<'a> {
    pub fn from_equality(input: &'a str) -> (Vec<Self>,Self) {
        let equality = input.split(" == ").collect::<Vec<_>>();
        let (left, right) = match equality.len() {
            0 | 1 => panic!("Missing ' == '"),
            2     => (equality[0], equality[1]),
            _     => panic!("Too much ' == '"),
        };

        (AlphaNum::from_sum(left), AlphaNum::new(right))
    }

    pub fn from_sum(input: &'a str) -> Vec<Self> {
        input.split(" + ")
             .map(AlphaNum::new)
             .collect()
    }

    pub fn new(input: &'a str) -> Self {
        if input.len() == 0 || input.chars().any(|c| c < 'A' || c > 'Z') {
            panic!("Invalid term {:?}", input);
        }
        AlphaNum(input)
    }

    pub fn to_u64(&self, map: &AlphaNumMap) -> u64 {
        self.0.chars()
              .fold(0u64, |acc, c|  acc * 10 + map.value(c))
    }

    pub fn leading(&self) -> char {
        self.0.chars().nth(0).expect("Empty term")
    }

    pub fn len(&self) -> usize {
        self.0.len()
    }
}

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    let letters = input.chars()
                       .filter(|&c| c >= 'A' && c <= 'Z')
                       .collect::<HashSet<_>>();
    if letters.len() > 10 {
        return None
    }

    let (terms, result) = AlphaNum::from_equality(input);

    let leadings = terms.iter().chain([&result].into_iter().cloned())
                        .filter(|n| n.len() > 1)
                        .map(AlphaNum::leading)
                        .collect::<HashSet<_>>();

    let mut candidates = letters.difference(&leadings).cloned().collect::<Vec<_>>();
    candidates.extend(" ".repeat(10 - candidates.len() - leadings.len()).chars());

    let mut arrangement = AlphaNumMap::new();

    let check = |map: &AlphaNumMap| {
        let sum = terms.iter()
                       .map(|term| term.to_u64(map))
                       .sum::<u64>();
        let result = result.to_u64(map);
        sum == result
    };

    find_arrrangement(candidates, leadings, &mut arrangement, check);

    arrangement.to_hashmap()
}

fn find_arrrangement<F: Copy + Fn(&AlphaNumMap) -> bool>(candidates: Vec<char>, leadings: HashSet<char>, arrangement: &mut AlphaNumMap, f: F) -> bool {
    if candidates.is_empty() {
        f(arrangement)
    } else {
        for (i,&e) in candidates.iter().enumerate() {
            let mut subcandidates: Vec<char> = Vec::with_capacity(candidates.len());
            subcandidates.extend(&candidates[..i]);
            subcandidates.extend(&candidates[i+1..]);
            subcandidates.extend(&leadings);
            arrangement.push(e);
            if find_arrrangement(subcandidates, HashSet::new(), arrangement, f) {
                return true
            }
            arrangement.pop();
        }
        false
    }
}

Tags:

construct:add
construct:as-cast
construct:assignment
construct:boolean
construct:char
construct:constructor
construct:for-loop
construct:generic-function
construct:if-expression
construct:impl
construct:impl-method
construct:indexing
construct:invocation
construct:lambda
construct:logical-and
construct:logical-or
construct:match-expression
construct:method
construct:method-overloading
construct:number
construct:parameter
construct:pattern-matching
construct:recursion
construct:return
construct:string
construct:struct
construct:subtract
construct:tuple
construct:u64
construct:usize
construct:use-directive
construct:variable-shadowing
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
technique:looping
technique:recursion
technique:type-conversion
uses:HashSet
uses:HashMap

[iHiD]

Exercise: anagram

Code

struct Anagram{
    lower:    String,
    sorted:   Vec<char>
}

impl Anagram {
    fn new(word: &str) -> Anagram {
        let lower                 = word.to_lowercase();
        let mut sorted: Vec<char> = lower.chars().collect::<Vec<_>>();

        sorted.sort();

        Anagram { lower: lower, sorted: sorted }
    }
}

impl std::cmp::PartialEq for Anagram {
    fn eq(&self, other: &Self) -> bool {
        (self.lower != other.lower) && (self.sorted == other.sorted)
    }
}

pub fn anagrams_for<'a>(word: &'a str, candidates: &[&'a str]) -> Vec<&'a str> {
    let word_anagram = Anagram::new(word);

    candidates.iter().filter_map(|&c|
        if Anagram::new(c) == word_anagram { Some(c) } else { None }
    ).collect()
}

Tags:

construct:&&
construct:&&:bool
construct:&
construct:impl
construct:if
construct:invocation
construct:lambda
construct:let
construct:logical-and
construct:method
construct:named-argument
construct:parameter
construct:struct
construct:struct:field
construct:template
construct:tuple
construct:underscore
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions

[iHiD]

Exercise: robot-name

Code

extern crate rand;

use rand::distributions::Uniform;
use rand::{thread_rng, Rng};

pub struct Robot {
    name: String,
}

impl Robot {
    pub fn new() -> Self {
        Robot {
            name: Self::generate_name(),
        }
    }

    fn generate_name() -> String {
        let letter_part = thread_rng()
            .sample_iter(&Uniform::new(b'A', b'Z'))
            .take(2)
            .map(|c| c as char)
            .collect::<String>();
        letter_part + "100"
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn reset_name(&mut self) {
        self.name = Self::generate_name();
    }
}

Tags:

construct:as-cast
construct:assignment
construct:char
construct:field
construct:impl
construct:invocation
construct:method
construct:parameter
construct:struct
construct:struct-initializer
construct:string
construct:trait
construct:use
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions
technique:randomness
technique:type-conversion

[iHiD]

Exercise: parallel-letter-frequency

Code

use std::collections::HashMap;
use rayon::prelude::*;

fn combine(left: HashMap<char,usize>,right: HashMap<char,usize>) -> HashMap<char,usize> {
    let mut m = HashMap::new();
    for (k,v) in left {
        m.insert(k,v);
    }
    for (k,v) in right {
        m.entry(k)
            .and_modify(|v2| *v2 += v)
            .or_insert(v);
    }
    return m
}

pub fn frequency(input: &[&str], worker_count: usize) -> HashMap<char, usize> {
    match worker_count {
        1 => seq_frequency(input),
        _ => par_frequency(input)
    }
}

fn process_str(s: &str) -> HashMap<char,usize> {
    let mut m = HashMap::new();
    for c in (*s).chars() {
        normalize(c).map(|c| *m.entry(c).or_insert(0) += 1);
    }
    m
}

fn par_frequency(input: &[&str]) -> HashMap<char,usize> {
    return input.par_iter()
        .map(|s| process_str(s))
        .reduce(|| HashMap::new(),|acc,x| combine(acc, x));
}

fn seq_frequency (input: &[&str]) -> HashMap<char, usize> {
    let mut m = HashMap::new();
    for s in input {
        for c in (*s).chars() {
            normalize(c).map(|c| *m.entry(c).or_insert(0) += 1);
        }
    }
    return m
}

pub fn normalize(c: char) -> Option<char> {
    if c.is_alphabetic() {
        Some(c.to_ascii_lowercase())
    } else {
        None
    }
} 

Tags:

construct:assignment
construct:char
construct:for-loop
construct:function
construct:if-expression
construct:impl
construct:invocation
construct:iterator
construct:lambda
construct:match-expression
construct:method
construct:number
construct:parameter
construct:pub
construct:return
construct:tuple
construct:underscore
construct:use-directive
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions
technique:looping
uses:HashMap

[iHiD]

Exercise: forth

Code

use std::collections::HashMap;

pub type Value = i32;
pub type ForthResult = Result<(), Error>;
pub type StackOperation = fn(&mut Vec<Value>) -> ForthResult;

pub enum Token {
    Integer(Value),
    Command(StackOperation),
}

impl Token {
    pub fn apply(&self, to: &mut Vec<Value>) -> ForthResult {
        match *self {
            Token::Integer(n) => {
                to.push(n);
                Ok(())
            },
            Token::Command(f) => f(to),
        }
    }
}

impl Clone for Token {
    fn clone(&self) -> Self {
        match *self {
            Token::Integer(ref n) => Token::Integer(*n),
            Token::Command(ref f) => Token::Command(*f),
        }
    }
}

pub struct Forth(Vec<Value>, HashMap<String, Vec<Token>>);

#[derive(Debug, PartialEq)]
pub enum Error {
    DivisionByZero,
    StackUnderflow,
    UnknownWord,
    InvalidWord,
}

fn op_dup(stack: &mut Vec<Value>) -> ForthResult {
    let n = stack.len();
    if n==0 {
        Err(Error::StackUnderflow)
    } else {
        let i = stack[n-1].clone();
        stack.push(i);
        Ok(())
    }
}

fn op_drop(stack: &mut Vec<Value>) -> ForthResult {
    match stack.pop() {
        Some(_) => Ok(()),
        None => Err(Error::StackUnderflow),
    }
}

fn op_swap(stack: &mut Vec<Value>) -> ForthResult {
    let n = stack.len();
    if n<2 {
        Err(Error::StackUnderflow)
    } else {
        let temp = stack.remove(n-2);
        stack.push(temp);
        Ok(())
    }
}

fn op_over(stack: &mut Vec<Value>) -> ForthResult {
    let n = stack.len();
    if n<2 {
        Err(Error::StackUnderflow)
    } else {
        let temp = stack[n-2].clone();
        stack.push(temp);
        Ok(())
    }
}

fn op_plus(stack: &mut Vec<Value>) -> ForthResult {
    if stack.len()<2 {
        Err(Error::StackUnderflow)
    } else {
        let temp = stack.pop().unwrap() + stack.pop().unwrap();
        stack.push(temp);
        Ok(())
    }
}

fn op_minus(stack: &mut Vec<Value>) -> ForthResult {
    if stack.len()<2 {
        Err(Error::StackUnderflow)
    } else {
        let temp = -stack.pop().unwrap() + stack.pop().unwrap();
        stack.push(temp);
        Ok(())
    }
}

fn op_times(stack: &mut Vec<Value>) -> ForthResult {
    if stack.len()<2 {
        Err(Error::StackUnderflow)
    } else {
        let temp = stack.pop().unwrap() * stack.pop().unwrap();
        stack.push(temp);
        Ok(())
    }
}

fn op_div(stack: &mut Vec<Value>) -> ForthResult {
    if stack.len()<2 {
        Err(Error::StackUnderflow)
    } else {
        match stack.pop().unwrap() {
            0 => Err(Error::DivisionByZero),
            ref n => {
                let temp = stack.pop().unwrap() / *n;
                stack.push(temp);
                Ok(())
            },
        }
    }
}

impl Forth {
    pub fn new() -> Forth {
        let mut ops: HashMap<String, Vec<Token>> = HashMap::new();
        ops.insert("DUP".to_string(), vec![Token::Command(op_dup)]);
        ops.insert("DROP".to_string(), vec![Token::Command(op_drop)]);
        ops.insert("SWAP".to_string(), vec![Token::Command(op_swap)]);
        ops.insert("OVER".to_string(), vec![Token::Command(op_over)]);
        ops.insert("+".to_string(), vec![Token::Command(op_plus)]);
        ops.insert("-".to_string(), vec![Token::Command(op_minus)]);
        ops.insert("*".to_string(), vec![Token::Command(op_times)]);
        ops.insert("/".to_string(), vec![Token::Command(op_div)]);
        Forth(Vec::new(), ops)
    }

    pub fn format_stack(&self) -> String {
        match self.0.len() {
            0 => "".to_string(),
            _ => {
                let init = self.0[0].to_string();
                self.0[1..].into_iter().fold(init, |b,v| b+" "+&v.to_string())
            },
        }
    }

    pub fn eval(&mut self, input: &str) -> ForthResult {
        let terms: Vec<String> = input.split(|c: char| c.is_whitespace() || c.is_control()).map(|s| s.to_uppercase()).collect();
        let mut i: usize = 0;
        while i<terms.len() {
            if terms[i].len()==0 {
                i+=1;
            } else if terms[i]==":".to_string() {
                i+=1;
                match self.eval_defn(&mut i, &terms) {
                    Ok(_) => (),
                    Err(res) => return Err(res),
                };
            } else {
                match self.eval_term(&terms[i]) {
                    Ok(_) => i+=1,
                    Err(res) => return Err(res),
                };
            }
        }
        Ok(())
    }

    fn eval_defn(&mut self, i: &mut usize, terms: &Vec<String>) -> ForthResult {
        if terms.len()<*i+3 || terms[*i].parse::<Value>().is_ok() {
            Err(Error::InvalidWord)
        } else {
            let new_term = terms[*i].to_string();
            let mut ops: Vec<Token> = Vec::new();
            *i+=1;
            while *i < terms.len() {
                if terms[*i]==";" {
                    self.1.insert(new_term, ops);
                    *i+=1;
                    return Ok(());
                }
                match terms[*i].parse::<Value>() {
                    Ok(n) => ops.push(Token::Integer(n)),
                    Err(_) => match self.1.get(&terms[*i]) {
                            None => return Err(Error::UnknownWord),
                            Some(v) => ops.extend_from_slice(v),
                    },
                };
                *i+=1;
            }
            Err(Error::InvalidWord)
        }
    }

    fn eval_term(&mut self, term: &String) -> ForthResult {
        match term.parse::<Value>() {
            Ok(n) => {
                self.0.push(n);
                Ok(())
            },
            Err(_) => match self.1.get(term) {
                Some(v) => {
                    for t in v {
                        match t.apply(&mut self.0) {
                            Ok(_) => (),
                            Err(res) => return Err(res),
                        };
                    }
                    Ok(())
                },
                None => Err(Error::UnknownWord),
            },
        }
    }
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:char
construct:divide
construct:enum
construct:field
construct:for_loop
construct:if
construct:impl
construct:indexing
construct:invocation
construct:iterator
construct:lambda
construct:logical_or
construct:match
construct:method
construct:method-overloading
construct:number
construct:parameter
construct:return
construct:string
construct:struct
construct:subtract
construct:type-alias
construct:type-conversion
construct:usize
construct:variable
construct:vector
construct:visibility-modifiers
construct:while-loop
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
technique:looping
uses:HashMap
uses:Vec

[iHiD]

Exercise: forth

Code

use std::collections::HashMap;

pub type ValueType = i64;
pub type ForthResult = Result<(), Error>;
type ApplyResult = Result<Vec<ValueType>, Error>;

#[derive(Clone)]
enum Token {
  Value(ValueType),
  Call(String),
  Def(Vec<Token>),
  EndDef,
}

pub struct Forth {
  stack: Vec<ValueType>,
  custom_ops: HashMap<String, Vec<Token>>,
}

#[derive(Debug, PartialEq)]
pub enum Error {
  DivisionByZero,
  StackUnderflow,
  UnknownWord,
  InvalidWord,
}

impl Forth {
  pub fn new() -> Self {
    Forth{ stack: vec![], custom_ops: HashMap::new() }
  }

  pub fn format_stack(&self) -> String {
    self.stack.iter().map(|e| e.to_string()).collect::<Vec<_>>().join(" ")
  }

  pub fn eval(&mut self, input: &str) -> ForthResult {
    let input = input.to_lowercase();
    let mut words = input.split(|c: char| c.is_whitespace() || c.is_control())
                         .filter(|&word| word.len() > 0);
    let tokens = self.parse(&mut words, vec![]);

    self.execute_all(tokens)
  }

  fn parse(&self, words: &mut Iterator<Item=&str>, mut tokens: Vec<Token>) -> Vec<Token> {
    match words.next() {
      Some(":") => {
        tokens.push(Token::Def(self.parse(words, vec![])));
        self.parse(words, tokens)
      },
      Some(";") => {
        tokens.push(Token::EndDef);
        tokens
      },
      Some(x) => {
        tokens.push(self.atom(x));
        self.parse(words, tokens)
      },
      None => tokens
    }
  }

  fn atom(&self, word: &str) -> Token {
    match word.parse() {
      Ok(v) => Token::Value(v),
      Err(_) => Token::Call(word.to_string())
    }
  }

  fn execute_all(&mut self, tokens: Vec<Token>) -> ForthResult {
    for token in tokens {
      try!(self.execute(token));
    }
    Ok(())
  }

  fn execute(&mut self, token: Token) -> ForthResult {
    match token {
      Token::EndDef => Err(Error::InvalidWord),
      Token::Value(v) => self.push(v),
      Token::Call(op) => self.call(op),
      Token::Def(def) => self.add_definition(&def[..])
    }
  }

  fn call(&mut self, name: String) -> ForthResult {
    if self.custom_ops.contains_key(&name) {
      let tokens = self.custom_ops.get(&name).unwrap().clone();
      self.execute_all(tokens)
    } else {
      self.primitive(name)
    }
  }

  fn primitive(&mut self, input: String) -> ForthResult {
    match &input[..] {
      "+" => self.apply_2(|x, y| Ok(vec![x + y])),
      "-" => self.apply_2(|x, y| Ok(vec![x - y])),
      "*" => self.apply_2(|x, y| Ok(vec![x * y])),
      "/" => self.apply_2(|x, y| if y == 0 { Err(Error::DivisionByZero) } else { Ok(vec![x / y]) }),
      "dup" => self.apply_1(|x| Ok(vec![x, x])),
      "drop" => self.apply_1(|_| Ok(vec![])),
      "swap" => self.apply_2(|x, y| Ok(vec![y, x])),
      "over" => self.apply_2(|x, y| Ok(vec![x, y, x])),
      _  => Err(Error::UnknownWord)
    }
  }

  fn add_definition(&mut self, def: &[Token]) -> ForthResult {
    match (def.first(), def.last()) {
      // A definition must start with the name to define, and end with an EndDef token
      (Some(&Token::Call(ref name)), Some(&Token::EndDef)) => {
        self.custom_ops.insert(name.to_string(), def[1 .. def.len() - 1].to_vec());
        Ok(())
      },
      _ => Err(Error::InvalidWord)
    }
  }

  // Some shorthands
  fn push(&mut self, v: ValueType) -> ForthResult {
    self.stack.push(v);
    Ok(())
  }
  fn pop(&mut self) -> ValueType {
    self.stack.pop().unwrap()
  }

  // Some helper functions to make evaluating operators easier
  fn apply_1<F> (&mut self, f: F) -> ForthResult where F: Fn (ValueType) -> ApplyResult {
    if self.stack.len() < 1 { return Err(Error::StackUnderflow) }
    let x = self.pop();
    self.process_apply_result(f(x))
  }
  fn apply_2<F> (&mut self, f: F) -> ForthResult where F: Fn (ValueType, ValueType) -> ApplyResult {
    if self.stack.len() < 2 { return Err(Error::StackUnderflow) }
    let (y, x) = (self.pop(), self.pop());
    self.process_apply_result(f(x, y))
  }
  fn process_apply_result (&mut self, res: ApplyResult) -> ForthResult {
    res.map(|mut results| self.stack.append(&mut results))
  }
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:char
construct:comment
construct:enum
construct:field
construct:for_loop
construct:generic_type
construct:if_expression
construct:impl
construct:indexing
construct:invocation
construct:lambda
construct:logical_or
construct:match
construct:method
construct:number
construct:parameter
construct:return
construct:string
construct:struct
construct:subtract
construct:tuple
construct:type_alias
construct:type_annotation
construct:use_directive
construct:variable
construct:visibility_modifier
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
technique:looping
uses:HashMap
uses:String
uses:Vec

[iHiD]

Exercise: nucleotide-codons

Code

pub fn parse<'a>(pairs: Vec<(&'a str, &'a str)>) -> Codons<'a> {
    Codons { pairs: pairs.iter().map(|x| Codon::new(x)).collect() }
}

pub struct Codons<'a> {
    pairs: Vec<Codon<'a>>,
}

impl<'a> Codons<'a> {
    pub fn name_for(&self, shorthand: &str) -> Result<&str, ()> {
        if shorthand.is_empty() {
            return Err(());
        }

        self.pairs
            .iter()
            .find(|ref x| x.matches(shorthand))
            .map(|ref x| x.name)
            .ok_or(())
    }
}

struct Codon<'a> {
    codon: &'a str,
    name: &'a str,
}

impl<'a> Codon<'a> {
    fn new(raw: &(&'a str, &'a str)) -> Codon<'a> {
        Codon {
            codon: raw.0,
            name: raw.1,
        }
    }

    fn matches(&self, shorthand: &str) -> bool {
        shorthand.chars().zip(self.codon.chars()).all(|(a, b)| {
            match a {
                'H' => vec!['A', 'C', 'T'],
                'M' => vec!['A', 'C'],
                'N' => vec!['A', 'C', 'G', 'T'],
                'R' => vec!['A', 'G'],
                'Y' => vec!['C', 'T'],
                _ => vec![a],
            }
            .contains(&b)
        })
    }
}

Tags:

construct:char
construct:if
construct:impl
construct:invocation
construct:lambda
construct:map
construct:match
construct:named-argument
construct:parameter
construct:return
construct:struct
construct:tuple
construct:underscore
construct:vector
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:higher-order-functions

[iHiD]

Exercise: doubly-linked-list

Code

// this module adds some functionality based on the required implementations
// here like: `LinkedList::pop_back` or `Clone for LinkedList<T>`
// You are free to use anything in it, but it's mainly for the test framework.
mod pre_implemented;

pub struct LinkedList<T> {
    root : Option<Box<Link<T>>>,
}

pub struct Cursor<'a, T> {
    current : *mut Link<T>,
    list : &'a mut LinkedList<T>,
}

pub struct Iter<'a, T> {
    current : Option<&'a Link<T>>,
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            root : None,
        }
    }

    pub fn len(&self) -> usize {
        if let Some(root) = &self.root {
            Self::count_until_end(root, 1)
        } else {
            0
        }
    }

    /// Return a cursor positioned on the front element
    pub fn cursor_front(&mut self) -> Cursor<'_, T> {
        if let Some(root) = &mut self.root {
            Cursor {
                current : &mut **root as *mut Link<T>,
                list : self,
            }
        } else {
            self.create_empty_cursor()
        }
    }

    /// Return a cursor positioned on the back element
    pub fn cursor_back(&mut self) -> Cursor<'_, T> {
        if let Some(root) = &mut self.root {
            let last = Self::navigate_until_end(root);
            Cursor {
                current : last as *mut Link<T>,
                list : self,
            }
        } else {
            self.create_empty_cursor()
        }
    }

    /// Return an iterator that moves from front to back
    pub fn iter(&self) -> Iter<'_, T> {
        let mut current = None;
        if let Some(root) = &self.root {
            current = Some(&**root);
        }
        Iter {
            current,
        }
    }

    fn create_empty_cursor(&mut self) -> Cursor<'_, T> {
        Cursor {
            current : std::ptr::null_mut(),
            list : self,
        }
    }

    fn navigate_until_end(current : &mut Link<T>) -> &mut Link<T>
    {
        if current.next.is_none() {
            return current;
        }
        let next = &mut *current.next.as_mut().unwrap();
        Self::navigate_until_end(next)
    }

    fn count_until_end(current : &Link<T>, count : usize) -> usize
    {
        if current.next.is_none() {
            return count;
        }
        let next = &*current.next.as_ref().unwrap();
        Self::count_until_end(next, count+1)
    }
}

// the cursor is expected to act as if it is at the position of an element
// and it also has to work with and be able to insert into an empty list.
impl<T> Cursor<'_, T> {
    /// Take a mutable reference to the current element
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        if let Some(link) = self.peek() {
            return Some(&mut link.value)
        }
        None
    }

    /// Move one position forward (towards the back) and
    /// return a reference to the new position
    pub fn next(&mut self) -> Option<&mut T> {
        if let Some(link) = self.peek() {
            if let Some(next) = &mut link.next {
                self.current = &mut **next;
            }
        }
        self.peek_mut()
    }

    /// Move one position backward (towards the front) and
    /// return a reference to the new position
    pub fn prev(&mut self) -> Option<&mut T> {
        if let Some(link) = self.peek() {
            let prev; unsafe { prev = link.prev.as_mut(); }
            if let Some(prev) = prev {
                self.current = prev; 
            }
        }
        self.peek_mut()
    }

    /// Remove and return the element at the current position and move the cursor
    /// to the neighboring element that's closest to the back. This can be
    /// either the next or previous position.
    pub fn take(&mut self) -> Option<T> {
        if let Some(link) = self.peek() {
            let prev; unsafe { prev = link.prev.as_mut(); }
            let mut next = link.next.take();
            let current;
            if let Some(prev) = prev {
                //this is not the root of the list
                current = prev.next.take();
                if let Some(next) = next.as_mut() {
                    next.prev = prev;
                    self.current = &mut **next;
                } else {
                    self.current = prev;
                }
                prev.next = next;
            } else {
                //this is the root of the list
                current = self.list.root.take();
                if let Some(next) = next.as_mut() {
                    next.prev = std::ptr::null_mut();
                    self.current = &mut **next;
                } else {
                    self.current = std::ptr::null_mut();
                }
                self.list.root = next;
            }
            return Some(current.unwrap().value);
        } 
        None
    }

    pub fn insert_after(&mut self, element: T) {
        if let Some(link) = self.peek() {
            let mut next = link.next.take();
            let mut new = Box::new(Link::<T> {
                value : element,
                next : None,
                prev : link, 
            });
            if let Some(next) = &mut next {
                next.prev = &mut *new;
            }
            new.next = next;
            link.next = Some(new);
        } else {
            self.insert_first(element);
        }
    }

    pub fn insert_before(&mut self, element: T) {
        if let Some(link) = self.peek() {
            let mut new = Box::new(Link::<T> {
                value : element,
                next : None,
                prev : link.prev, 
            });
            let prev; unsafe { prev = link.prev.as_mut(); }
            link.prev = &mut *new;
            if let Some(prev) = prev {
                new.next = prev.next.take();
                prev.next = Some(new);
            } else {
                new.next = self.list.root.take();
                self.list.root = Some(new);
            }
        } else {
            self.insert_first(element);
        }
    }

    fn peek(&mut self) -> Option<&mut Link<T>> {
        let current; unsafe { current = self.current.as_mut(); }
        if let Some(link) = current {
            return Some(link)
        } 
        None
    }

    fn insert_first(&mut self, element: T) {
        let mut root = Box::new(Link::<T> {
            value : element,
            next : None,
            prev : std::ptr::null_mut(),
        });
        self.current = &mut *root;
        self.list.root = Some(root);
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        let mut ret = None;
        let mut new = None;
        if let Some(link) = &self.current {
            ret = Some(&link.value);
            if let Some(next) = &link.next {
                new = Some(&**next);
            }
        }
        self.current = new;
        ret
    }
}

struct Link<T> {
    value : T,
    next : Option<Box<Link::<T>>>,//last has no next
    prev : *mut Link::<T>,//first has no prev
}

Tags:

construct:as-cast
construct:assignment
construct:attribute
construct:box
construct:comment
construct:enum
construct:expression
construct:field-init
construct:generic-type
construct:if-expression
construct:impl
construct:invocation
construct:let
construct:method
construct:mod
construct:module
construct:named-argument
construct:number
construct:pattern
construct:return
construct:struct
construct:type-alias
construct:unsafe-block
construct:use
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:bit-manipulation
technique:bit-shifting
technique:bitwise-operations
technique:higher-order-functions
technique:recursion
technique:type-conversion
uses:LinkedList

[senekor]

Challenge accepted :)

[senekor]

@iHiD I'm very sorry, but I vastly underestimated the time this is going to take. I changed a couple of tags, then scrolled through the list of possible tags and solutions to tag, and realized I have no chance of completing this anytime soon.

[ErikSchierboom]

This is an automated comment

Hello :wave: Next week we're going to start using the tagging work people are doing on these. If you've already completed the work, thank you! If you've not, but intend to this week, that's great! If you're not going to get round to doing it, and you've not yet posted a comment letting us know, could you please do so, so that we can find other people to do it. Thanks!

[senekor]

I don't intend to work on this anytime soon, feel free to find someone else / open this for community contributions.

[ErikSchierboom]

Thanks for the help! We've updated the tags.