MojoでProject Euler 86

https://projecteuler.net/problem=86

例だと、またぐ辺が5と3だから8で、6と直角になって斜辺が10となります。直方体の最も長い辺が直角三角形の一つの辺で残りの辺の和で直角を成します。
なので、直角三角形を最も長い辺になる長さが小さいほうから列挙するとよいです。その際、(3, 4, 5), (4, 3, 5)と同じ直角三角形でもどちらが直方体の最も長い辺になるかで分けると組みやすくなります。

import sys


#################### library ####################

fn gcd(n: Int, m: Int) -> Int:
    if m == 0:
        return n
    else:
        return gcd(m, n % m)


#################### HeapQueue ####################

struct HeapQueue[T: ComparableCollectionElement]:
    var a: List[T]
    
    fn __init__(inout self):
        self.a = List[T]()
    
    fn is_empty(self) -> Bool:
        return len(self.a) == 0
    
    fn pop(inout self) -> T:
        var top = self.a[0]
        self.a[0] = self.a.pop()
        var N = self.a.size
        var i = 0
        while i < N-1:
            var j1 = i*2+1
            var j2 = i*2+2
            var j: Int = 0
            if j1 >= N:
                break
            elif j2 == N:
                j = j1
            else:
                if self.a[j1] <= self.a[j2]:
                    j = j1
                else:
                    j = j2
            if self.a[j] < self.a[i]:
                self.swap(i, j)
                i = j
            else:
                break
        
        return top
    
    fn push(inout self, e: T):
        self.a.append(e)
        var i = self.a.size - 1
        while i > 0:
            var j = (i-1) // 2
            if self.a[j] <= self.a[i]:
                break
            else:
                self.swap(i, j)
                i = j
    
    fn swap(inout self, i: Int, j: Int):
        var tmp = self.a[i]
        self.a[i] = self.a[j]
        self.a[j] = tmp^


#################### RightTriangle ####################

@value
struct RightTriangle(Comparable):
    var l: Int
    var m: Int
    var n: Int
    var is_b: Bool      # 2lmnが対象か
    
    fn a(self) -> Int:
        return self.l * (self.m**2 - self.n**2)
    
    fn b(self) -> Int:
        return 2 * self.l * self.m * self.n
    
    fn value(self) -> Int:
        return self.b() if self.is_b else self.a()
    
    fn __lt__(self, other: RightTriangle) -> Bool:
        return self.value() < other.value()
    
    fn __le__(self, other: RightTriangle) -> Bool:
        return self.value() <= other.value()
    
    fn __eq__(self, other: RightTriangle) -> Bool:
        return self.value() == other.value()
    
    fn __ne__(self, other: RightTriangle) -> Bool:
        return self.value() != other.value()
    
    fn __gt__(self, other: RightTriangle) -> Bool:
        return self.value() > other.value()
    
    fn __ge__(self, other: RightTriangle) -> Bool:
        return self.value() >= other.value()


#################### process ####################

fn nexts(tri: RightTriangle) -> List[RightTriangle]:
    var tris = List[RightTriangle]()
    tris.append(RightTriangle(tri.l+1, tri.m, tri.n, tri.is_b))
    if tri.l > 1:
        pass
    elif tri.is_b:
        if tri.n <= 2:
            tris.append(RightTriangle(1, tri.m+2, tri.n, True))
        for n in range(tri.n+2, tri.m, 2):
            if gcd(tri.m, n) == 1:
                tris.append(RightTriangle(tri.l, tri.m, n, True))
                break
    else:
        if tri.n == tri.m - 1 and tri.m >= 3:
            tris.append(RightTriangle(1, tri.m+1, tri.n+1, False))
        for n in range(tri.n-2, 0, -2):
            if gcd(tri.m, n) == 1:
                tris.append(RightTriangle(tri.l, tri.m, n, False))
                break
    return tris

fn count_cuboids(tri: RightTriangle) -> Int:
    if tri.is_b:
        if tri.b() > tri.a():
            return tri.a() // 2
        else:
            return max(0, tri.a() // 2 - (tri.a() - tri.b() - 1))
    else:
        if tri.a() > tri.b():
            return tri.b() // 2
        else:
            return max(0, tri.b() // 2 - (tri.b() - tri.a() - 1))

fn f(N: Int) -> Int:
    var counter = 0
    var pq = HeapQueue[RightTriangle]()
    pq.push(RightTriangle(1, 2, 1, True))
    pq.push(RightTriangle(1, 2, 1, False))
    pq.push(RightTriangle(1, 3, 2, True))
    pq.push(RightTriangle(1, 3, 2, False))
    var M = 0
    while counter < N:
        var tri = pq.pop()
        var a = tri.a()
        var b = tri.b()
        counter += count_cuboids(tri)
        M = tri.value()
        
        var tris = nexts(tri)
        for tri1 in tris:
            pq.push(tri1[])
    return M

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    print(f(N))

MojoでProject Euler 85

https://projecteuler.net/problem=85

左上の点を共有する長方形の面積の合計と同じです。
長方形の高さをh、幅をwとすると面積の合計は

hが小さいほうから最適なwを求めていけばいいです。

import sys


#################### library ####################

fn int_sqrt(n: Int) -> Int:
    var x = 1
    x = (x + n // x) // 2
    while True:
        var x1 = (x + n // x) // 2
        if x1 >= x:
            return x
        x = x1


#################### process ####################

fn find_opt_width(h: Int, N: Int) -> Int:
    var sh = h * (h + 1) // 2
    var w = (-1 + int_sqrt(1 + 8 * N // sh)) // 2
    var sw1 = w * (w + 1) // 2
    var sw2 = (w + 1) * (w + 2) // 2
    if N - sh * sw1 < sh * sw2 - N:
        return w
    else:
        return w + 1

fn f(N: Int) -> Int:
    var nearest_area = 0
    var nearest_value = 0
    for h in range(1, N):
        var w = find_opt_width(h, N)
        if w < h:
            break
        var value = h * (h + 1) // 2 * w * (w + 1) // 2
        if abs(value - N) < abs(nearest_value - N):
            nearest_value = value
            nearest_area = h * w
    return nearest_area

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    print(f(N))

MojoでProject Euler 84

https://projecteuler.net/problem=84

ちゃんと計算しようとすると大変です。カードをシャッフルして上から取って一番下に入れるというのが難しいです。シャッフルしてからでも状態の数が10240あります。シャッフルしてから収束させて、すべてのシャッフルに対して行うというのは無理です。
しかし、単に100万回をランダムに進めるだけで答えが出ます。

import sys
import random


#################### List ####################

fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]:
    var a = List[T](capacity=N)
    for n in range(N):
        a.append(init)
    return a

trait Printable(CollectionElement, Stringable):
    pass

fn print_list[T: Printable](a: List[T]):
    if a.size > 0:
        var s = "[" + str(a[0])
        for i in range(1, a.size):
            s += ", " + str(a[i])
        s += "]"
        print(s)
    else:
        print("[]")

fn copy_list[T: CollectionElement](a: List[T]) -> List[T]:
    return sublist(a, 0, len(a))

fn sublist[T: CollectionElement](a: List[T], first: Int, last: Int) -> List[T]:
    var b = List[T]()
    for i in range(first, last):
        b.append(a[i])
    return b


#################### process ####################

var squares = List[StringLiteral](
                "GO", "A1", "CC1", "A2", "T1", "R1", "B1", "CH1", "B2", "B3",
                "JAIL", "C1", "U1", "C2", "C3", "R2", "D1", "CC2", "D2", "D3",
                "FP", "E1", "CH2", "E2", "E3", "R3", "F1", "F2", "U2", "F3",
                "G2J", "G1", "G2", "CC3", "G3", "R4", "CH3", "H1", "T2", "H2")
var CC_cards = List[StringLiteral]("GO", "JAIL")
var CH_cards = List[StringLiteral]("GO", "JAIL", "C1", "E3", "H2",
                                        "R1", "R", "R", "U", "BACK")
var dic = Dict[StringLiteral, Int]()

fn find_next(j: Int, sq: StringLiteral) -> Int:
    if sq == "R":
        if j == 8:
            return 15
        elif j == 22:
            return 25
        else:
            return 5
    else:
        if j == 22:
            return 28
        else:
            return 12

fn step_simply(state: Int, N: Int) -> Int:
    var pos = state >> 8
    for _ in range(3):
        var dice1 = int(random.random_si64(1, N))
        var dice2 = int(random.random_si64(1, N))
        if dice1 != dice2:
            pos = (pos + dice1 + dice2) % 40
            return pos
    else:
        return 10   # JAIL

fn step(state: Int, N: Int) -> Int:
    var pos = state >> 8
    var cci = state & 15
    var chi = (state >> 4) & 15
    var new_pos = step_simply(state, N)
    var square = squares[new_pos]
    if square == "G2J":
        new_pos = 10
        return cci | (chi << 4) | (new_pos << 8)
    elif "CC" in squares[new_pos]:
        if cci < 2:
            new_pos = dic.get(CC_cards[cci], -1)
        return (cci+1) | (chi << 4) | (new_pos << 8)
    elif "CH" in square:
        if chi < 6:
            new_pos = dic.get(CH_cards[chi], -1)
        elif square == "R":
            new_pos = find_next(new_pos, "R")
        elif square == "U":
            new_pos = find_next(new_pos, "U")
        elif square == "BACK":
            new_pos = (new_pos - 3) % 40
        return cci | ((chi + 1) << 4) | (new_pos << 8)
    else:
        return cci | (chi << 4) | (new_pos << 8)

@value
struct Item(Comparable):
    var s: Float64
    var i: Int
    
    fn __lt__(self, other: Item) -> Bool:
        return self.s < other.s
    
    fn __le__(self, other: Item) -> Bool:
        return self.s <= other.s
    
    fn __gt__(self, other: Item) -> Bool:
        return self.s > other.s
    
    fn __ge__(self, other: Item) -> Bool:
        return self.s >= other.s
    
    fn __eq__(self, other: Item) -> Bool:
        return self.s == other.s
    
    fn __ne__(self, other: Item) -> Bool:
        return self.s != other.s

fn f(N: Int) -> String:
    for i in range(len(squares)):
        dic[squares[i]] = i
    random.seed(2)
    var L = 10**6
    var counter = initialize_list(40, 0)
    var state = 0
    for _ in range(L):
        state = step(state, N)
        var pos = state >> 8
        counter[pos] += 1
    var v = List[Item]()
    for i in range(40):
        v.append(Item(counter[i], i))
    sort(v)
    var n1 = v[39].i
    var n2 = v[38].i
    var n3 = v[37].i
    return (String(n1//10) + String(n1%10) +
            String(n2//10) + String(n2%10) +
            String(n3//10) + String(n3%10))

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    print(f(N))

AtCoder Beginner Contest 386 E

https://atcoder.jp/contests/abc386/tasks/abc386_e

KがN/2以下のときはふつうに分割統治法を使えばよいですが、Kが大きいときは分割したときの個数が大きくなることがあります。例えば、N=100でK=99だと、100を2つで割って50個の有り無しになるので、2[sup]50[/sup]個の場合があって間に合いません。こういう場合は、K=1と考えるとよいです。全てのAのXORを取って、K=1のときの数とXORを取ればよいです。

// Diagonal Separation
#![allow(non_snake_case)]

use std::cmp::{min, max};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<u64>) {
    let v: Vec<usize> = read_vec();
    let K = v[1];
    let A: Vec<u64> = read_vec();
    (K, A)
}

fn DC(A: &[u64], K: usize) -> Vec<Vec<u64>> {
    if A.len() == 1 {
        return vec![vec![0], vec![A[0]]]
    }
    
    let mid = A.len() / 2;
    let v1 = DC(&A[..mid], K);
    let v2 = DC(&A[mid..], K);
    let L = min(A.len()+1, K+1);
    let mut v: Vec<Vec<u64>> = vec![vec![]; L];
    for (i, &ref w1) in v1.iter().enumerate() {
        if i > K {
            continue
        }
        for (j, &ref w2) in v2.iter().enumerate() {
            let k = i + j;
            if k > K {
                continue
            }
            for &n1 in w1.iter() {
                for &n2 in w2.iter() {
                    v[k].push(n1 ^ n2)
                }
            }
        }
    }
    v
}

fn F_core(K: usize, A: Vec<u64>, base: u64) -> u64 {
    let N = A.len();
    if N == 0 {
        return base
    }
    else if N == 1 {
        return A[0]
    }
    
    let mid = N / 2;
    let v1 = DC(&A[..mid], K);
    let v2 = DC(&A[mid..], K);
    let mut max_n: u64 = 0;
    for (i, &ref w1) in v1.iter().enumerate() {
        if i + v2.len() < K || i > K {
            continue
        }
        let j = K - i;
        for &n1 in w1.iter() {
            for &n2 in v2[j].iter() {
                let n = n1 ^ n2 ^ base;
                max_n = max(n, max_n)
            }
        }
    }
    max_n
}

fn F(K: usize, A: Vec<u64>) -> u64 {
    if K > A.len() / 2 {
        let total = A.iter().fold(0, |x, &y| x ^ y);
        F_core(A.len() - K, A, total)
    }
    else {
        F_core(K, A, 0)
    }
}

fn main() {
    let (N, paints) = read_input();
    println!("{}", F(N, paints))
}

AtCoder Beginner Contest 385 F

https://atcoder.jp/contests/abc385/tasks/abc385_f

原点から全てのビルを見られなければ、左から順に左隣のビルの陰にならないように高さを上げていきます。
これ、最初からf64にするとハマりますね。

// Santa Claus 2
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Point ////////////////////

type Point = (i64, i64);

fn read_point() -> Point {
    let v: Vec<i64> = read_vec();
    (v[0], v[1])
}


//////////////////// process ////////////////////

fn read_input() -> Vec<Point> {
    let N: usize = read();
    let points: Vec<Point> = (0..N).map(|_| read_point()).collect();
    points
}

fn is_all_visible_from_origin(points: &Vec<Point>) -> bool {
    for i in 0..points.len()-1 {
        let (x1, H1) = points[i];
        let (x2, H2) = points[i+1];
        if x1 * H2 <= x2 * H1 {
            return false
        }
    }
    true
}

fn F(points: Vec<Point>) -> String {
    if is_all_visible_from_origin(&points) {
        return (-1).to_string()
    }
    
    let mut h: f64 = 0.0;
    for i in 0..points.len()-1 {
        let (x1, H1) = points[i];
        let (x2, H2) = points[i+1];
        if x1 as f64 * (H2 as f64 - h) <= x2 as f64 * (H1 as f64 - h) {
            h = ((x2 * H1 - x1 * H2) as f64) / ((x2 - x1) as f64)
        }
    }
    h.to_string()
}

fn main() {
    let points = read_input();
    println!("{}", F(points))
}

AtCoder Beginner Contest 385 D

https://atcoder.jp/contests/abc385/tasks/abc385_d

同じ場所を何度も通ってそこにたくさんの点があると時間がかかるので、重複を除いてあらかじめ通る場所を計算しておきます。そのために、各固定座標に対し範囲をBTreeSetにし、そこに範囲を追加して、範囲が結合できるなら結合するようにします。

// Santa Claus 2
#![allow(non_snake_case)]

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


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Point ////////////////////

type Point = (i64, i64);

fn read_point() -> Point {
    let v: Vec<i64> = read_vec();
    (v[0], v[1])
}


//////////////////// Range ////////////////////

type Range = (i64, i64);

fn add_range(rng: Range, ranges: &mut BTreeSet<Range>) {
    let mut to_remove = Vec::new();
    let mut start = rng.0;
    let mut end = rng.1;
    
    for &range in ranges.range((rng.0, i64::MIN)..(rng.1, i64::MAX)) {
        if range.1 < rng.0 || range.0 > rng.1 {
            continue
        }
        to_remove.push(range);
        start = start.min(range.0);
        end = end.max(range.1)
    }
    
    // 影響を受ける範囲を削除
    for range in to_remove {
        ranges.remove(&range);
    }
    
    // 新しいマージされた範囲を追加
    ranges.insert((start, end));

}


//////////////////// process ////////////////////

fn read_input() -> (usize, Point, Vec<Point>) {
    let v: Vec<i64> = read_vec();
    let (N, M) = (v[0] as usize, v[1] as usize);
    let S = (v[2], v[3]);
    let houses: Vec<Point> = (0..N).map(|_| read_point()).collect();
    (M, S, houses)
}

fn classify(keys: &Vec<i64>, values: &Vec<i64>) -> HashMap<i64, BTreeSet<i64>> {
    let mut c: HashMap<i64, BTreeSet<i64>> = HashMap::new();
    for (&k, &v) in keys.iter().zip(values.iter()) {
        let e = c.entry(k).or_insert(BTreeSet::new());
        (*e).insert(v);
    }
    c
}

fn read_move() -> (char, i64) {
    let v: Vec<String> = read_vec();
    let D: char = v[0].chars().next().unwrap();
    let C: i64 = v[1].parse().unwrap();
    (D, C)
}

fn collect_moves(moves: Vec<(char, i64)>, start: Point) ->
                                    (HashMap<i64, BTreeSet<Range>>,
                                     HashMap<i64, BTreeSet<Range>>, Point) {
    let mut range_x_dir: HashMap<i64, BTreeSet<Range>> = HashMap::new();
    let mut range_y_dir: HashMap<i64, BTreeSet<Range>> = HashMap::new();
    let mut x = start.0;
    let mut y = start.1;
    for (D, C) in moves.into_iter() {
        match D {
            'U' => {
                let e = range_y_dir.entry(x).or_insert(BTreeSet::new());
                add_range((y, y+C+1), &mut *e);
                y += C
            }
            'D' => {
                let e = range_y_dir.entry(x).or_insert(BTreeSet::new());
                add_range((y-C, y+1), &mut *e);
                y -= C
            }
            'L' => {
                let e = range_x_dir.entry(y).or_insert(BTreeSet::new());
                add_range((x-C, x+1), &mut *e);
                x -= C
            }
            _   => {
                let e = range_x_dir.entry(y).or_insert(BTreeSet::new());
                add_range((x, x+C+1), &mut *e);
                x += C
            }
        }
    }
    (range_x_dir, range_y_dir, (x, y))
}

fn count(set_xs: &BTreeSet<i64>, x_ranges: &BTreeSet<Range>) -> Vec<i64> {
    let xs: Vec<i64> = set_xs.iter().map(|&x| x).collect();
    let ranges: Vec<Range> = x_ranges.iter().map(|&r| r).collect();
    let mut v: Vec<i64> = vec![];
    let mut k: usize = 0;
    let mut l: usize = 0;
    while k < xs.len() && l < ranges.len() {
        let x = xs[k];
        let (first, last) = ranges[l];
        if first <= x && x < last {
            v.push(x);
            k += 1
        }
        else if x < first {
            k += 1
        }
        else {
            l += 1
        }
    }
    v
}

fn F(M: usize, S: Point, houses: Vec<Point>) {
    let xs: Vec<i64> = houses.iter().map(|&(x, _)| x).collect();
    let ys: Vec<i64> = houses.iter().map(|&(_, y)| y).collect();
    let collection_by_xs = classify(&xs, &ys);
    let collection_by_ys = classify(&ys, &xs);
    let moves: Vec<(char, i64)> = (0..M).map(|_| read_move()).collect();
    let (range_x_dir, range_y_dir, G) = collect_moves(moves, S);
    
    let mut set: BTreeSet<Point> = BTreeSet::new();
    for (y, x_ranges) in range_x_dir.into_iter() {
        match collection_by_ys.get(&y) {
            Some(set_xs) => {
                let xs1 = count(set_xs, &x_ranges);
                for x in xs1.into_iter() {
                    set.insert((x, y));
                }
            },
            None       => ()
        }
    }
    for (x, y_ranges) in range_y_dir.into_iter() {
        match collection_by_xs.get(&x) {
            Some(set_ys) => {
                let ys1 = count(set_ys, &y_ranges);
                for y in ys1.into_iter() {
                    set.insert((x, y));
                }
            },
            None       => ()
        }
    }
    println!("{} {} {}", G.0, G.1, set.len())
}

fn main() {
    let (M, S, houses) = read_input();
    F(M, S, houses)
}

MojoでProject Euler 83

https://projecteuler.net/problem=83

ダイクストラ法ですが、実装するのはけっこう大変ですね。TupleがComparableCollectionElementとKeyElementを実装してくれれば簡単なんですけどね。

import sys


#################### List ####################

trait Printable(CollectionElement, Stringable):
    pass

fn print_list[T: Printable](a: List[T]):
    if a.size > 0:
        var s = "[" + str(a[0])
        for i in range(1, a.size):
            s += ", " + str(a[i])
        s += "]"
        print(s)
    else:
        print("[]")

fn copy_list[T: CollectionElement](a: List[T]) -> List[T]:
    return sublist(a, 0, len(a))

fn sublist[T: CollectionElement](a: List[T], first: Int, last: Int) -> List[T]:
    var b = List[T]()
    for i in range(first, last):
        b.append(a[i])
    return b


#################### HeapQueue ####################

struct HeapQueue[T: ComparableCollectionElement]:
    var a: List[T]
    
    fn __init__(inout self):
        self.a = List[T]()
    
    fn is_empty(self) -> Bool:
        return len(self.a) == 0
    
    fn pop(inout self) -> T:
        var top = self.a[0]
        self.a[0] = self.a.pop()
        var N = self.a.size
        var i = 0
        while i < N-1:
            var j1 = i*2+1
            var j2 = i*2+2
            var j: Int = 0
            if j1 >= N:
                break
            elif j2 == N:
                j = j1
            else:
                if self.a[j1] <= self.a[j2]:
                    j = j1
                else:
                    j = j2
            if self.a[j] < self.a[i]:
                self.swap(i, j)
                i = j
            else:
                break
        
        return top
    
    fn push(inout self, e: T):
        self.a.append(e)
        var i = self.a.size - 1
        while i > 0:
            var j = (i-1) // 2
            if self.a[j] <= self.a[i]:
                break
            else:
                self.swap(i, j)
                i = j
    
    fn swap(inout self, i: Int, j: Int):
        var tmp = self.a[i]
        self.a[i] = self.a[j]
        self.a[j] = tmp^


#################### Point ####################

@value
struct Point(KeyElement):
    var x: Int
    var y: Int
    
    fn __eq__(self, other: Point) -> Bool:
        return self.x == other.x and self.y == other.y
    
    fn __ne__(self, other: Point) -> Bool:
        return self.x != other.x or self.y != other.y
    
    fn __hash__(self) -> Int:
        return self.x * 10000 + self.y


#################### Item ####################

@value
struct Item(Comparable):
    var value: Int
    var pt: Node
    
    fn __lt__(self, other: Item) -> Bool:
        return self.value < other.value
    
    fn __le__(self, other: Item) -> Bool:
        return self.value <= other.value
    
    fn __eq__(self, other: Item) -> Bool:
        return self.value == other.value
    
    fn __ne__(self, other: Item) -> Bool:
        return self.value != other.value
    
    fn __gt__(self, other: Item) -> Bool:
        return self.value > other.value
    
    fn __ge__(self, other: Item) -> Bool:
        return self.value >= other.value


#################### library ####################


#################### Matrix ####################

fn read_matrix(path: String) -> List[List[Int]]:
    try:
        var matrix = List[List[Int]]()
        with open(path, "r") as f:
            var whole = f.read()
            var lines = whole.split('\n')
            for line in lines:
                if line[] == '':
                    break
                var ns = List[Int]()
                var v = line[].split(',')
                for s in v:
                    var n = atol(s[])
                    ns.append(n)
                matrix.append(ns)
        return matrix
    except:
        return List[List[Int]]()


#################### Graph ####################

alias Node = Point

struct Graph:
    var g: Dict[Node, List[Node]]
    var table: List[List[Int]]
    
    fn __init__(inout self, g: Dict[Node, List[Node]], table: List[List[Int]]):
        self.g = g
        self.table = table
    
    fn value(self, pt: Point) -> Int:
        return self.table[pt.x][pt.y]
    
    @staticmethod
    fn create(table: List[List[Int]]) raises -> Graph:
        var H = len(table)
        var W = len(table[0])
        var g = Dict[Node, List[Node]]()
        for x in range(H):
            for y in range(W):
                var pt = Point(x, y)
                g[pt] = List[Node]()
                if x != 0:
                    g[pt].append(Point(x-1, y))
                if x != H - 1:
                    g[pt].append(Point(x+1, y))
                if y != 0:
                    g[pt].append(Point(x, y-1))
                if y != W - 1:
                    g[pt].append(Point(x, y+1))
        return Graph(g, table)


#################### process ####################

fn Dijkstra(graph: Graph, start: Node, goal: Node) raises -> Int:
    var queue = HeapQueue[Item]()
    queue.push(Item(graph.value(start), start))
    var visited = Set[Node]()
    while not queue.is_empty():
        var e = queue.pop()
        visited.add(e.pt)
        if e.pt == goal:
            return e.value
        for dest in graph.g[e.pt]:
            if dest[] not in visited:
                queue.push(Item(e.value + graph.value(dest[]), dest[]))
    return -1

fn f(path: String) -> Int:
    var table = read_matrix(path)
    var H = len(table)
    var W = len(table[0])
    try:
        var graph = Graph.create(table)
        return Dijkstra(graph, Point(0, 0), Point(H-1, W-1))
    except:
        return 0

fn main():
    var path = String("0083_matrix.txt")
    print(f(path))