Project Euler 18

https://projecteuler.net/problem=18

To simplify finding the maximum path in the triangle, the first step is to translate the problem into a directed acyclic graph structure.

So

1
2 3
4 5 6

is represented as a graph.

graph[4] = [2]
graph[5] = [2, 3]
graph[6] = [3]
graph[2] = [1]
graph[3] = [1]
graph[1] = []

However, since each number in the triangle could be non unique, the position is used instead to identity the node in the graph. So the graph becomes an adjacency list of tuple positions x and y.

graph[(2, 0)] = [(1, 0)]
graph[(2, 1)] = [(1, 0), (1, 1)]

Since we want to find the previous max value from the node’s neighbors, we reverse the edges in the graph, so the inner edges become outer edges.

Each node has at most only two possible edges, so traversing from the bottom to the top only requires checking O(# of edges) plus the cost of traversing the adjacency list to determine the maximum path.

The max sum of all neighbors and the current node value is stored in a maximum-values table, which is initialized with the original positional value. The table is populated by traversing from bottom to top, along each row of the triangle. From there, the maximum path sum is found at the origin (0, 0).

/*
maximum path
*/
type AdjListPos = HashMap<(usize, usize), Vec<(usize, usize)>>;

pub fn reverse_edges_tuples(edges: &mut AdjListPos) -> AdjListPos {
    let mut in_edges: AdjListPos = HashMap::new();
    for (key, value) in edges.iter() {
        for i in value.iter() {
            in_edges.entry(*i).or_insert(Vec::new()).push(*key);
        }
    }
    in_edges
}

pub fn find_max_path(graph: &str) -> i128 {
    let line_strings: Vec<&str> = graph.split("\n").map(|s| s.trim()).collect();
    let mut list = vec!();
    // parse into vector
    for line in line_strings.iter() {
        let arrayline: Vec<i128> = line.split_whitespace().filter_map(|s| s.parse::<i128>().ok()).collect();
        if arrayline.len() > 0 {
            list.push(arrayline);
        }
    }
    // generate adjacency list of graph
    let mut adjlist: AdjListPos = HashMap::new();
    let mut maxvalues: HashMap<(usize, usize), i128> = HashMap::new();
    for (i, row) in list.iter().enumerate().rev() {
        for (j, value) in row.iter().enumerate() {
            let pos = (i, j);
            if i == 0 {
                adjlist.insert(pos, Vec::new());
            }
            else {
                if j == 0 {
                    adjlist.entry(pos).or_insert(Vec::new()).push((i-1, j));
                } else if j < i {
                    adjlist.entry(pos).or_insert(Vec::new()).push((i-1, j-1));
                    adjlist.entry(pos).or_insert(Vec::new()).push((i-1, j));
                } else {
                    adjlist.entry(pos).or_insert(Vec::new()).push((i-1, j-1));
                }
            }
             maxvalues.entry(pos).or_insert(*value);
        }
    }
    let reversed_edges = reverse_edges_tuples(&mut adjlist);
    // find max path bottom up to top
    for (i, row) in list.iter().enumerate().rev() {
        for (j, item) in row.iter().enumerate() {
            let node = (i, j);
            match reversed_edges.get(&node) {
                Some(positions) => {
                    let mut max_value = 0;
                    for pos in positions {
                        let val = *maxvalues.get(pos).unwrap();
                        if val > max_value {
                            max_value = val;
                        }
                    }
                    let node_val = list[i][j];
                    maxvalues.insert(node, max_value + node_val);
                },
                None => ()
            }
        }
    }
    // maximum path sum is accumulated at the origin
    *maxvalues.get(&(0, 0)).unwrap()
}


pub fn problem_18() -> i128 {
    let triangle_str = "
    75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
    ";
    find_max_path(triangle_str)
}

Project Euler 17

https://projecteuler.net/problem=17


/*
one, two, three, four, five, six, seven, eight, nine,
ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen. nineteen,
ten, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety,
one hundred and one,
two hundred,
one thousand
*/
pub fn problem_17() -> i128 {
    let t_1_9 = [3, 3, 5, 4, 4, 3, 5, 5, 4];
    let t_10_19 = [3, 6, 6, 8, 8, 7, 7, 9, 8, 8];
    let sum_t_1_9 = t_1_9.iter().fold(0, |a, &b| a + b);
    let sum_t_10_19 = t_10_19.iter().fold(0, |a, &b| a + b);

    // tens, twenty, ..., ninety
    let tens = [0, 6, 6, 5, 5, 5, 7, 6, 6];
    // t_1_20 = sum(1-20)
    // t_20_100 = [6, 6, 5, 5, 5, 7, 6, 6] * 10 + sum(1-9) * 8
    let mut t_1_99 = 0;
    for i in tens.iter() {
        t_1_99 += i * 10 as i128;
    }
    t_1_99 += sum_t_1_9 * 9 + sum_t_10_19;
    /*
    100-199
    t_100_199 = [3+7] * 100 + t_1_99
    */
    let mut t_100_999 = 0;
    for i in t_1_9.iter() {
        t_100_999 += (*i as i128 + 7 + 3) * 100 + t_1_99 - 3;
    }
    let t = t_1_99 + t_100_999 + 11;
    t
}

Project Euler 16

https://projecteuler.net/problem=16

How do you factor a large exponential number when rust only supports integers up to 128 bits?

The solution was to write a big integer struct, to support multiplication and addition. The input integer could be arbitrarily large, so I used a string argument to initialize the bigint struct.

  • After which its split into chunks of 8 digits, stored in reverse order in a vector.
  • First I handled addition, checking the overflow of chunk size limit and carrying it over to the n+1 place, and storing the reminder modulus of the chunk limit at n.
  • The multiplication method, loops over each chunk and creates a vector of BigInts for intermediate products, and then sums the total.
  • Finally, the exponential function was composed of a loop of the multiply method accumulated into a sum in a BigInt struct.
use std::cmp;
/*
big integer class
- stores large ints in chunk sizes in a stack
- supports add and multiply
*/

// split string into chunk size integers
fn split_chunks(val: &str) -> Vec<i64> {
    let c_size = 8;
    let mut parts = vec!();
    let mut j = val.len();
    let mut i = if j > c_size { j - c_size } else { 0 };
    while j > 0 {
        let part = &val[i..j];
        parts.push(part.parse::<i64>().unwrap());
        j = i;
        i = if i > c_size { i - c_size } else { 0 };
    }
    parts
}

pub struct BigInt {
    // stored in reverse order
    chunks: Vec<i64>
}

impl BigInt {
    fn new(val: &str) -> BigInt {
        // split into chunks
        let chunks = split_chunks(val);
        // println!("BitInteger::new {:?}", chunks);
        BigInt { chunks: chunks }
    }
    fn add(&self, b: &BigInt) -> BigInt {
        let mut sum = vec!();
        let max_len = cmp::max(self.chunks.len(), b.chunks.len());
        let mut carry = 0;
        for i in 0..max_len {
            let x = if i < self.chunks.len() { self.chunks[i] } else { 0 };
            let y = if i < b.chunks.len() { b.chunks[i] } else { 0 };
            let s = x + y + carry;
            // check overflow
            carry = s / (100_000_000);
            let rem = s % 100_000_000;
            sum.push(rem);
        }
        if carry > 0 { sum.push(carry) };
        BigInt{ chunks: sum }
    }
    fn multiply(&self, b: &BigInt) -> BigInt {
        let max_len = cmp::max(self.chunks.len(), b.chunks.len());
        let mut middle_sums = vec!();
        for j in 0..b.chunks.len() {
            let mut sum = vec!();
            // add zeros place
            for k in 0..j {
                sum.push(0);
            }
            let mut carry = 0;
            for i in 0..max_len {
                let x = if i < self.chunks.len() { self.chunks[i] } else { 1 };
                let y = b.chunks[j];
                let s = x * y + carry;
                carry = s / (100_000_000);
                let rem = s % 100_000_000;
                sum.push(rem);
            }
            if carry > 0 { sum.push(carry) };
            middle_sums.push(BigInt{ chunks: sum });
        }
        let mut total = BigInt::new("0");
        for i in middle_sums.iter() {
            total = total.add(i);
        }
        total
    }
    pub fn value(&self) -> String {
        let mut digits = vec!();
        for (i, chunk) in self.chunks.iter().enumerate().rev() {
            let valstr = if i == self.chunks.len() - 1 { chunk.to_string() } else { format!("{:08}", chunk) };
            digits.push(valstr);
        }
        digits.join("")
    }
}


pub fn big_exponential(a: i64, x: i64) -> BigInt {
    let base = BigInt::new(&a.to_string());
    let mut total = BigInt::new("1");
    for _ in 0..x {
        total = total.multiply(&base);
    }
    total
}

I also wrote unit tests for the bigint struct. You run tests with this command

cargo test
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bigint_add() {
        let a = BigInt::new("99999999923456789");
        let b = BigInt::new("99950999");
        let x = a.add(&b);
        let y: i128 = 99999999923456789 + 99950999;
        assert_eq!(x.value(), y.to_string());
    }

    #[test]
    fn test_bigint_multiply() {
        let a = BigInt::new("99999999923456789");
        let b = BigInt::new("1299950999");
        let x = a.multiply(&b);
        let y: i128 = 99999999923456789 * 1299950999;
        assert_eq!(x.value(), y.to_string());
    }

    #[test]
    fn test_bigint_exponential() {
        let x = big_exponential(2, 10);
        assert_eq!(x.value(), "1024");
    }
}

The solution was easy once the bigint struct support was written.

use euler::bigint;

pub fn problem_16() -> i128 {
    let x = bigint::big_exponential(2, 1000);
    let y = x.value();
    let mut accum = 0;
    for i in 0..y.len() {
        let ch = y.chars().nth(i).unwrap();
        accum += ch.to_digit(10).unwrap();
    }
    println!("total: {}", accum);
    println!("y: {:?}", y);
    accum as i128
}