use block_map::BlockMap;
use std::fmt;
use std::fmt::Display;
pub use block_map::Position;
mod block_map;
pub struct Mauer {
    rows: usize,
    blocks: BlockMap,
}
impl Mauer {
    pub fn new(rows: usize) -> Self {
        Self {
            rows,
            blocks: BlockMap::new(rows),
        }
    }
    pub fn set(&mut self, pos: Position, value: isize) {
        self.blocks.set(pos, value);
    }
    pub fn solve(&mut self) {
        self.calc_possible();
        // if not all values are known here, we have to try and use some maths.
        if !self.blocks.solved() {
            // first check bottom line if it has only one missing value
            let bottom_lane = self.blocks.bottom_lane();
            if self.blocks.bottom_lane_value_count() == 1 {
                // only one value missing
                let missing_pos =
                    bottom_lane
                        .iter()
                        .fold(
                            Position::new(0, 0),
                            |ret, (pos, val)| {
                                if val.is_none() {
                                    **pos
                                } else {
                                    ret
                                }
                            },
                        );
                // now we look for a existing value above it and use it as top of a (possible smaller) block_map so we can use an equation
                if let (result_pos, Some(result)) = self.blocks.bottom_equation(missing_pos) {
                    self.blocks.set(result_pos, result);
                }
            }
            self.calc_possible();
            //        let left_lane = self.blocks.iter().filter(|(pos, _)| pos.1 == 1);
            //        let right_lane = self.blocks.iter().filter(|(pos, _)| pos.0 == pos.1);
        }
        // TODO do integrity check afterwards
    }
    fn calc_possible(&mut self) {
        let mut changes = true;
        while changes {
            let value_count = self.blocks.value_count();
            self.blocks.calc_all();
            let new_value_count = self.blocks.value_count();
            if value_count == new_value_count {
                changes = false;
            }
        }
    }
}
impl Display for Mauer {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut format = String::from("");
        for row in 1..=self.rows {
            let identation = self.rows - row;
            let mut top_line = " ".chars().cycle().take(4 * identation).collect::<String>();
            let mut line = " ".chars().cycle().take(4 * identation).collect::<String>();
            for pos in 1..=row {
                let block = self.blocks.get(&Position::new(row, pos));
                top_line = format!("{}+-------", top_line);
                if let Some(block) = block {
                    if let Some(value) = block {
                        line = format!("{}| {:^5} ", line, value);
                    } else {
                        line = format!("{}|       ", line);
                    }
                } else {
                    line = format!("{}|       ", line);
                }
                if pos == row {
                    top_line = format!("{}+\n", top_line);
                    line = format!("{}|\n", line);
                }
            }
            format = format!("{}{}{}", format, top_line, line);
        }
        format = format!(
            "{}{}+\n",
            format,
            "+-------"
                .chars()
                .cycle()
                .take(8 * self.rows)
                .collect::<String>()
        );
        write!(f, "{}", format)
    }
}

use std::cmp::{Eq, Ord, PartialEq, PartialOrd};
use std::collections::BTreeMap;
use std::iter::Iterator;
#[derive(Debug, Copy, Clone, PartialOrd, Ord, PartialEq, Eq)]
pub struct Position(pub usize, pub usize);
impl Position {
    pub fn new(row: usize, col: usize) -> Self {
        Self(row, col)
    }
    fn spire() -> Self {
        Self(1, 1)
    }
    pub fn top_left(&self) -> Self {
        Self(self.0.saturating_sub(1), self.1.saturating_sub(1))
    }
    pub fn top_right(&self) -> Self {
        Self(self.0.saturating_sub(1), self.1)
    }
    pub fn left(&self) -> Self {
        Self(self.0, self.1.saturating_sub(1))
    }
    pub fn right(&self) -> Self {
        Self(self.0, self.1.saturating_add(1))
    }
    pub fn bottom_left(&self) -> Self {
        Self(self.0.saturating_add(1), self.1)
    }
    pub fn bottom_right(&self) -> Self {
        Self(self.0.saturating_add(1), self.1.saturating_add(1))
    }
}
#[derive(Clone)]
pub struct BlockMap {
    rows: usize,
    size: usize,
    positions: Vec<Position>,
    inner: BTreeMap<Position, Option<isize>>,
}
impl BlockMap {
    pub fn new(rows: usize) -> Self {
        let mut size = 1;
        let mut positions = Vec::new();
        let mut inner = BTreeMap::new();
        for i in 1..=rows {
            for j in 1..=i {
                size += 1;
                let pos = Position::new(i, j);
                inner.insert(pos, None);
                positions.push(pos);
            }
        }
        Self {
            rows,
            size,
            positions,
            inner,
        }
    }
    pub fn get(&self, pos: &Position) -> Option<&Option<isize>> {
        self.inner.get(pos)
    }
    pub fn set(&mut self, pos: Position, value: isize) {
        self.inner.insert(pos, Some(value));
    }
    pub fn solved(&self) -> bool {
        self.value_count() == self.size
    }
    pub fn value_count(&self) -> usize {
        self.inner.iter().filter(|(_, val)| val.is_some()).count()
    }
    pub fn bottom_lane(&self) -> BTreeMap<&Position, &Option<isize>> {
        self.inner
            .iter()
            .filter(|(pos, _)| pos.0 == self.rows)
            .collect()
    }
    pub fn bottom_lane_value_count(&self) -> usize {
        self.bottom_lane()
            .iter()
            .filter(|(_, value)| value.is_none())
            .count()
    }
    pub fn left_lane(&self) -> BTreeMap<&Position, &Option<isize>> {
        self.inner.iter().filter(|(pos, _)| pos.1 == 1).collect()
    }
    pub fn right_lane(&self) -> BTreeMap<&Position, &Option<isize>> {
        self.inner
            .iter()
            .filter(|(pos, _)| pos.0 == pos.1)
            .collect()
    }
    pub fn is_top(&self, pos: &Position) -> bool {
        self.inner.get(&pos.top_left()).is_none()
            && self.inner.get(&pos.top_right()).is_none()
            && self.inner.get(&pos.left()).is_none()
            && self.inner.get(&pos.right()).is_none()
    }
    pub fn is_left(&self, pos: &Position) -> bool {
        self.inner.get(&pos.top_left()).is_none() && self.inner.get(&pos.left()).is_none()
    }
    pub fn is_right(&self, pos: &Position) -> bool {
        self.inner.get(&pos.top_right()).is_none() && self.inner.get(&pos.right()).is_none()
    }
    pub fn is_bottom(&self, pos: &Position) -> bool {
        self.inner.get(&pos.bottom_left()).is_none()
            && self.inner.get(&pos.bottom_right()).is_none()
    }
    pub fn bottom_equation(&self, missing_pos: Position) -> (Position, Option<isize>) {
        if let Some((spire_pos, spire_val)) = self.bottom_lane_spire(missing_pos) {
            let spire_mauer = self.inner.iter().filter(|(pos, _)| {
                let lower = spire_pos.1;
                let upper = spire_pos.1 + (pos.0 - spire_pos.0);
                pos.1 >= lower && pos.1 <= upper
            });
            let mut equation = spire_mauer
                .fold(BTreeMap::new(), |mut equation, (pos, val)| {
                    if pos.0 != self.rows {
                        let multiplier = if let Some((count_pos, _)) = equation.get(pos) {
                            let ret =  *count_pos;
                            equation.remove_entry(pos);
                            ret
                        } else {
                            1
                        };
                        if let Some((bl, _)) = equation.get_mut(&pos.bottom_left()) {
                            *bl = *bl + multiplier;
                        } else {
                            let bl_val = self.inner.get(&pos.bottom_left()).unwrap();
                            equation.insert(pos.bottom_left(), (multiplier, bl_val));
                        }
                        if let Some((br, _)) = equation.get_mut(&pos.bottom_right()) {
                            *br = *br + multiplier;
                        } else {
                            let br_val = self.inner.get(&pos.bottom_right()).unwrap();
                            equation.insert(pos.bottom_right(), (multiplier, br_val));
                        }
                    }
                    
                    equation
                });
            let (divisor, _) = equation.remove(&missing_pos).unwrap();
            let equation_val = spire_val.unwrap() - equation.iter().fold(0, |mut eq_val, (_, (val_mul, val))| {
                if let Some(val) = **val {
                    eq_val = eq_val + val_mul * val;
                }
                eq_val
            });
            if equation_val % divisor != 0 {
                return (missing_pos, None);
            }
            return (missing_pos, Some(equation_val / divisor));
        }
        (Position::new(0,0), None)
    }
    pub fn bottom_lane_spire(&self, missing_pos: Position) -> Option<(&Position, &Option<isize>)> {
        self.inner
            .iter()
            .rev()
            .filter(|(pos, _)| {
                if pos.0 == missing_pos.0 {
                    return false;
                }
                let lower = missing_pos.1.saturating_sub(missing_pos.0 - pos.0);
                let lower = if lower < 1 { 1 } else { lower };
                let upper = if missing_pos.1 <= pos.0 {
                    missing_pos.1
                } else {
                    pos.0
                };
                if lower <= pos.1 && pos.1 <= upper {
                    true
                } else {
                    false
                }
            })
            .find(|(_, val)| val.is_some())
    }
    pub fn calc_all(&mut self) {
        for pos in self.positions.clone().iter() {
            let value = self.calc(pos);
            self.inner.insert(*pos, value);
        }
    }
    fn calc(&mut self, pos: &Position) -> Option<isize> {
        // skip calculating because we already have a value
        if let Some(value) = self.inner.get(pos) {
            if value.is_some() {
                return value.as_ref().copied();
            }
            self.calc_from_bottom(pos).or(self
                .calc_from_left(pos)
                .or(self.calc_from_right(pos).or(None)))
        } else {
            None
        }
    }
    fn calc_from_bottom(&self, pos: &Position) -> Option<isize> {
        if self.is_bottom(pos) {
            // TODO get rid of unwrap, works for now, because this function is only called via calc
            return self.inner.get(pos).unwrap().as_ref().copied();
        }
        // safe to unwrap because we check with is_bottom before
        let bottom_left = self.get(&pos.bottom_left()).unwrap();
        let bottom_right = self.get(&pos.bottom_right()).unwrap();
        if let Some(bl_value) = bottom_left.as_ref() {
            if let Some(br_value) = bottom_right.as_ref() {
                return Some(*bl_value + *br_value);
            }
        }
        None
    }
    fn calc_from_left(&self, pos: &Position) -> Option<isize> {
        if self.is_left(pos) {
            // TODO get rid of unwrap, works for now, because this function is only called via calc
            return self.inner.get(pos).unwrap().as_ref().copied();
        }
        // safe to unwrap because we check with is_left before
        let top_left = self.get(&pos.top_left()).unwrap();
        let left = self.get(&pos.left()).unwrap();
        if let Some(tl_left) = top_left.as_ref() {
            if let Some(l_value) = left.as_ref() {
                return Some(*tl_left - *l_value);
            }
        }
        None
    }
    fn calc_from_right(&self, pos: &Position) -> Option<isize> {
        if self.is_right(pos) {
            // TODO get rid of unwrap, works for now, because this function is only called via calc
            return self.inner.get(pos).unwrap().as_ref().copied();
        }
        // safe to unwrap because we check with is_right before
        let top_right = self.get(&pos.top_right()).unwrap();
        let right = self.get(&pos.right()).unwrap();
        if let Some(tr_value) = top_right.as_ref() {
            if let Some(r_value) = right.as_ref() {
                return Some(*tr_value - *r_value);
            }
        }
        None
    }
}

use std::collections::BTreeMap;
use std::fmt::{Debug, Display};
use std::ops::{Add, Sub};
use super::Position;
// this is a newtrait way to alias the trait bounds.
//pub trait Integer: Debug + Display + Copy +  Eq + Add + Sub {}
//impl<T: Debug + Display + Copy +  Eq + Add<Output = T> + Sub<Output = T>> Integer for T {}
#[derive(Debug, Clone)]
pub struct Block<'a, T: Debug + Display + Copy + Eq + Add<Output = T> + Sub<Output = T>> {
    value: Option<&'a T>,
    top_left: Option<Option<&'a T>>,
    top_right: Option<Option<&'a T>>,
    left: Option<Option<&'a T>>,
    right: Option<Option<&'a T>>,
    bottom_left: Option<Option<&'a T>>,
    bottom_right: Option<Option<&'a T>>,
}
impl<'a, T: Debug + Display + Copy + Eq + Add<Output = T> + Sub<Output = T>> Block<'a, T> {
    pub fn new(position: &Position, blocks: &'a BTreeMap<Position, Option<T>>) -> Self {
        let value = blocks.get(position);
        if let Some(value) = value {
            let top_left = blocks
                .get(&(position.0 - 1, position.1 - 1))
                .map(|val| val.as_ref());
            let top_right = blocks
                .get(&(position.0 - 1, position.1))
                .map(|val| val.as_ref());
            let left = blocks
                .get(&(position.0, position.1 - 1))
                .map(|val| val.as_ref());
            let right = blocks
                .get(&(position.0, position.1 + 1))
                .map(|val| val.as_ref());
            let bottom_left = blocks
                .get(&(position.0 + 1, position.1))
                .map(|val| val.as_ref());
            let bottom_right = blocks
                .get(&(position.0 + 1, position.1 + 1))
                .map(|val| val.as_ref());
            return Self {
                value: value.as_ref(),
                top_left,
                top_right,
                left,
                right,
                bottom_left,
                bottom_right,
            };
        }
        Self {
            value: None,
            top_left: None,
            top_right: None,
            left: None,
            right: None,
            bottom_left: None,
            bottom_right: None,
        }
    }
    pub fn get(&self) -> Option<&'a T> {
        self.value
    }
    pub fn is_top(&self) -> bool {
        self.top_left.is_none()
            && self.top_right.is_none()
            && self.left.is_none()
            && self.right.is_none()
    }
    pub fn is_left(&self) -> bool {
        self.top_left.is_none() && self.left.is_none()
    }
    pub fn is_right(&self) -> bool {
        self.top_right.is_none() && self.right.is_none()
    }
    pub fn is_bottom(&self) -> bool {
        self.bottom_left.is_none() && self.bottom_right.is_none()
    }
    pub fn calc(&self) -> Option<T> {
        // skip calculating because we already have a value
        if self.value.is_some() {
            return self.value.copied();
        }
        self.calc_from_bottom()
            .or(self.calc_from_left().or(self.calc_from_right().or(None)))
    }
    fn calc_from_bottom(&self) -> Option<T> {
        if self.is_bottom() {
            return self.get().copied();
        }
        // safe to unwrap because we check with is_bottom before
        let bottom_left = self.bottom_left.unwrap();
        let bottom_right = self.bottom_right.unwrap();
        if let Some(bl_value) = bottom_left {
            if let Some(br_value) = bottom_right {
                return Some(*bl_value + *br_value);
            }
        }
        None
    }
    fn calc_from_left(&self) -> Option<T> {
        if self.is_left() {
            return self.get().copied();
        }
        // safe to unwrap because we check with is_left before
        let top_left = self.top_left.unwrap();
        let left = self.left.unwrap();
        if let Some(tl_left) = top_left {
            if let Some(l_value) = left {
                return Some(*tl_left - *l_value);
            }
        }
        None
    }
    fn calc_from_right(&self) -> Option<T> {
        if self.is_right() {
            return self.get().copied();
        }
        // safe to unwrap because we check with is_right before
        let top_right = self.top_right.unwrap();
        let right = self.right.unwrap();
        if let Some(tr_value) = top_right {
            if let Some(r_value) = right {
                return Some(*tr_value - *r_value);
            }
        }
        None
    }
}

mod mauer;
use mauer::Mauer;
use mauer::Position;
fn main() {
    let mut mauer: Mauer = Mauer::new(4);
    mauer.set(Position::new(1, 1), 92);
    mauer.set(Position::new(4, 1), 12);
    mauer.set(Position::new(4, 3), 17);
    mauer.set(Position::new(4, 4), 8);
    println!("{}", mauer);
    mauer.solve();
    println!("{}", mauer);
}

# Rechenmauer
This attempts to solve so called Rechenmauern, it probably never will be a sophisticated implementation.
Because it does act as a learning project for Rust.

[package]
name = "rechenmauer"
version = "0.1.0"
authors = ["Christoph Schmidler <c.schmidler@gmail.com>"]
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]

# This file is automatically @generated by Cargo.
# It is not intended for manual editing.
[[package]]
name = "rechenmauer"
version = "0.1.0"