Category: algorithm

### 単純に計算していく方法

fn main() {
    
    let mut vote = [
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let n = vote.len();

    let half = n / 2;
    let mut winner = "".to_string();

    for i in 0..n {
        if vote[i] == "" {
            continue;
        }

        let mut count = 1;

        for j in i+1..n {
            if vote[j] == vote[i] {
                count += 1;
                vote[j] = "".to_string();
                if count > half {
                    winner = vote[i].clone();
                    break;
                }
            }
        }
        if winner != "".to_string() {
            break;
        }
    }

    if winner != "".to_string() {
        println!("{}が過半数を取りました", winner);
    } else {
        println!("過半数を取った人はいません");
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/basic`
鈴木花子が過半数を取りました

### ボイアーとムーアのアルゴリズム
最初に最も多い組み合わせを調べ、それが過半数に達しているか計算する。
計算量が少なくて済む。

fn main() {
    
    let vote = [
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let n = vote.len();
    let mut candidate = "".to_string();

    let mut survivor = 0;

    for i in 0..n {
        if survivor == 0 {
            candidate = vote[i].clone();
            survivor = 1;
        } else if candidate == vote[i] {
            survivor += 1;
        } else {
            survivor -= 1;
        }
    }
    let mut count = 0;
    if survivor != 0 {
        for i in 0..n {
            if candidate == vote[i] {
                count += 1;
            }
        }
    }

    if count > (n / 2) {
        println!("{}が過半数を取りました。", candidate);
    } else {
        println!("過半数を取った人はいません。");
    }
}

### ソートによるカウント
ソートして真ん中の値のカウントをする。これも美しい。

fn main() {
    
    let mut vote = vec![
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let half = vote.len() / 2;

    vote.sort();

    if vote.clone().into_iter().filter(|n| *n == vote[half]).count() > half {
        println!("{}が過半数を取りました。", vote[half]);
    } else {
        println!("過半数を取った人はいません。");
    }
}

### hashmapで計算する

use std::collections::HashMap;

fn main() {
    
    let vote = [
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let mut blackboard: HashMap<String, i32> = HashMap::new();

    for v in vote.clone() {
        if !blackboard.contains_key(&v) {
            blackboard.insert(v.clone(),1);
        } else {
            blackboard.insert(v.clone(), 1 + blackboard[&v]);
        }
        println!("{:?}", blackboard);
    }

    let key_with_max_value =blackboard.iter().max_by_key(|entry | entry.1).unwrap();
    if *key_with_max_value.1 as usize > (vote.len() / 2) {
        println!("過半数を取得しました。{:?}", key_with_max_value);
    } else {
        println!("過半数を取った人はいません。");
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/basic`
{“山田太郎”: 1}
{“山田太郎”: 1, “鈴木花子”: 1}
{“山田太郎”: 1, “鈴木花子”: 1, “佐藤三郎”: 1}
{“佐藤三郎”: 1, “山田太郎”: 1, “鈴木花子”: 2}
{“佐藤三郎”: 1, “山田太郎”: 1, “鈴木花子”: 3}
{“佐藤三郎”: 2, “山田太郎”: 1, “鈴木花子”: 3}
{“佐藤三郎”: 2, “山田太郎”: 1, “鈴木花子”: 4}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 4}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 5}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 6}
{“佐藤三郎”: 3, “山田太郎”: 2, “鈴木花子”: 6}
{“佐藤三郎”: 3, “山田太郎”: 2, “鈴木花子”: 7}
過半数を取得しました。(“鈴木花子”, 7)

これが感覚的には一番わかりやすい。でもアルゴリズム的にはボイヤーの方が優れているんだよなー

fn leap_year(year: u32) -> bool {
    if year % 4 == 0 && year % 100 != 0 || year % 400 == 0 {
        return true;
    } 
    false
}

fn day_of_week(year: usize, month: usize) -> usize {
    let mut days_of_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

    if leap_year(year.try_into().unwrap()) {
        days_of_month[2] = 29;
    }

    let day = 1;
    let mut days = 0;

    for y in 1..year {
        if leap_year(y.try_into().unwrap()) {
            days += 366
        } else {
            days += 365
        }
    }

    for m in 1..month {
        days += days_of_month[m as usize]
    }

    days += day;
    return days % 7
}

fn main() {
    let days_of_week_name = ["日".to_string(), "月".to_string(),"火".to_string(),"水".to_string(),"木".to_string(),"金".to_string(),"土".to_string()];

    let mut days_of_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    let year = 2040;
    let month = 3;

    if leap_year(year.try_into().unwrap()) {
        days_of_month[2] = 29;
    }
    let first_day = day_of_week(year, month);

    println!("{}年 {}月", year, month);
    println!("日 月 火 水 木 金 土");
    let emp = " ".to_string();

    print!("{}", emp.repeat(first_day*3));
    for day in 1..(1 + days_of_month[month]) {
        print!("{:<2} ", day);
        if(day + first_day - 1) % 7 == 6 {
            print!("\n");
        }
    }
    print!("\n");
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.14s
Running `target/debug/basic`
2040年 3月
日 月 火 水 木 金 土
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

これは中々面白い！！！　そんなに難しくないけど、中々思いつかない!

4回くじを引くという条件から、nパターンの4回分を全通り試して、一致する組み合わせを探している。
全通りを探す場合、ループの中でループをするという書き方が多い。

static MAX_N: usize = 50;

fn main() {
    let mut n: i32;
    let mut m: i32;
    let mut k: Vec<i32> = Vec::new();

    println!("紙の枚数 n を入力してください。");
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let n = line.trim().parse::<i32>().unwrap();
    println!("期待する数字の和 m を入力してください。");
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let m = line.trim().parse::<i32>().unwrap();

    println!("紙に書かれている数字をそれぞれ入力してください。");
    for i in 0..n {
        println!("{}番目の数字:", i + 1);
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        let n = line.trim().parse::<i32>().unwrap();
        k.push(n);
    }

    let mut flg = false;

    for a in 0..n {
        for b in 0..n {
            for c in 0..n {
                for d in 0..n {
                    if k[a as usize] + k[b as usize] + k + k[d as usize] == m {
                        flg = true;
                        println!("発見! 組み合わせは{},{},{},{}", k[a as usize], k[b as usize], k, k[d as usize]);
                    }
                }
            }
        }
    }

    if !flg {
        println!("そのような組み合わせはありません。");
    }
}

紙の枚数 n を入力してください。
3
期待する数字の和 m を入力してください。
10
紙に書かれている数字をそれぞれ入力してください。
1番目の数字:
3
2番目の数字:
3
3番目の数字:
2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,2,2,3
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3

ここでは東北、秋田、山形新幹線の駅からそれぞれ一つづつランダムに駅を抽出する組み合わせを出力するという簡易的な実装例とする。
実際のどこかにビューーン!は、更に上越、北陸新幹線もあり、候補47駅、5つの新幹線の中から4つの駅を出力しているので、若干ロジックが異なるが、考え方はおおよそ同じだ。※[東北、秋田、山形、上越、北陸]から、4つをランダムに抽出して、そこから更にランダムに抽出しているのかもしれない。

サーバ側では、各駅がどの新幹線駅かというデータを持っておき、iteratorからfilterでそれぞれの新幹線ごとにvectorに入れて、そこからランダムに抽出する。下のサンプルでは、最後に往復料金でソートしてprintln!している。

use rand::prelude::IndexedRandom;

#[derive(Debug, Clone)]
struct Destination {
    bullet_train: String,
    station: String,
    ticket_price: u32
}

fn main() {
    let data = [
        Destination{ bullet_train: "東北".to_string(), station: "那須塩原".to_string(), ticket_price: 12040},
        Destination{ bullet_train: "東北".to_string(), station: "新白河".to_string(), ticket_price: 13580},
        Destination{ bullet_train: "東北".to_string(), station: "郡山".to_string(), ticket_price: 16680},
        Destination{ bullet_train: "東北".to_string(), station: "福島".to_string(), ticket_price: 18220},
        Destination{ bullet_train: "東北".to_string(), station: "白石蔵王".to_string(), ticket_price: 21080},
        Destination{ bullet_train: "東北".to_string(), station: "仙台".to_string(), ticket_price: 22180},
        Destination{ bullet_train: "東北".to_string(), station: "古川".to_string(), ticket_price: 23280},
        Destination{ bullet_train: "秋田".to_string(), station: "雫石".to_string(), ticket_price: 32200},
        Destination{ bullet_train: "秋田".to_string(), station: "田沢湖".to_string(), ticket_price: 32640},
        Destination{ bullet_train: "秋田".to_string(), station: "角館".to_string(), ticket_price: 34040},
        Destination{ bullet_train: "秋田".to_string(), station: "大曲".to_string(), ticket_price: 34700},
        Destination{ bullet_train: "秋田".to_string(), station: "秋田".to_string(), ticket_price: 36040},
        Destination{ bullet_train: "山形".to_string(), station: "米沢".to_string(), ticket_price: 21060},
        Destination{ bullet_train: "山形".to_string(), station: "高畠".to_string(), ticket_price: 21500},
        Destination{ bullet_train: "山形".to_string(), station: "赤湯".to_string(), ticket_price: 22240},
        Destination{ bullet_train: "山形".to_string(), station: "かみのやま温泉".to_string(), ticket_price: 22900},
        Destination{ bullet_train: "山形".to_string(), station: "さくらんぼ東根".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "村山".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "大石田".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "新庄".to_string(), ticket_price: 26000},
    ];

    let mut JR_Voom = Vec::new();

    let tohoku: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "東北")
        .collect();
    JR_Voom.push(tohoku.choose(&mut rand::thread_rng()).unwrap());

    let akita: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "秋田")
        .collect();
    JR_Voom.push(akita.choose(&mut rand::thread_rng()).unwrap());

    let yamagata: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "山形")
        .collect();
    JR_Voom.push(yamagata.choose(&mut rand::thread_rng()).unwrap());
    JR_Voom.sort_by(|a, b| a.ticket_price.cmp(&b.ticket_price));

    for (i, destination) in JR_Voom.iter().enumerate() {
        println!("{:}: {}駅 (往復{}円)", i + 1, destination.station, destination.ticket_price);
    }
    
}

何度か実行すると以下のようになる。うん、見たことある光景である。
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.55s
Running `target/debug/app`
1: 郡山駅 (往復16680円)
2: 新庄駅 (往復26000円)
3: 秋田駅 (往復36040円)

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.08s
Running `target/debug/app`
1: 米沢駅 (往復21060円)
2: 古川駅 (往復23280円)
3: 雫石駅 (往復32200円)

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.16s
Running `target/debug/app`
1: 福島駅 (往復18220円)
2: 米沢駅 (往復21060円)
3: 田沢湖駅 (往復32640円)

プログラムでランダムに抽出しているだけだが、これに一喜一憂しているのだからしょうがない。多分、●●駅の方が△△駅よりも出やすくするといった駅によっての重み付とかはないと思うが、実際のところは分かりません。。

use std::io::stdin;

fn main() {

    let mut memory = Memory {
        slots: vec![0.0; 10],
    }
    let mut prev_result: f64 = 0.0;
    for line in stdin().lines() {
        let line = line.unwrap();
        if line.is_empty() {
            break;
        }

        let tokens: Vec<&str> = line.split(char::is_whitespace).collect();

        let is_memory = tokens[0].starts_with("mem");
        if is_memory && tokens[0].ends_with('+') {
            add_and_print_memory(&mut memory, tokens[0], prev_result);
            continue;
        } else if is_memory && tokens[0].ends_with('-') {
            add_and_print_memory(&mut memory, tokens[0], -prev_result);
            continue;
        }

        let left = eval_token(tokens[0], &memory);
        let right = eval_token(tokens[2], &memory);
        let result = eval_expression(left, tokens[1], right);
        print_output(result);

        prev_result = result;
    }
}

struct Memory {
    slots: Vec<f64>,
}

fn add_and_print_memory(memory: &mut Memory, token: &str, prev_result: f64) {
    let slot_index: usize = token[3..token.len() - 1].parse().unwrap();
    memory.slots[slot_index] += prev_result;
    print_output(memory.slots[slot_index]);
}
fn eval_token(token: &str, memory: &Memory) -> f64 {
    if token.starts_with("mem") {
        let slot_index: usize = token[3..].parse().unwrap();
        memory.slots[slot_index]
    } else {
        token.parse().unwrap()
    }
}
fn eval_expression(left: f64, operator: &str, right: f64) -> f64 {
    match operator {
        "+" => left + right,
        "-" => left - right,
        "*" => left * right,
        "/" => left / right,
        _ => {
            unreachable!()
        }
    }
}
fn print_output(value: f64) {
    println!(" => {}", value);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.49s
Running `target/debug/app`
1 + 2
=> 3
mem1+
=> 3
3 + 4
=> 7
mem2-
=> -7
mem1 * mem2
=> -21

このソース見た時、凄い感慨したんよね。絵柄と1~13の数字でdeckを作るところ。
pocker chaseの裏側ってどうやってんだろうずっと思ってたんだけど、これを見ると、カードの配り方や、最後の役完成時の判定をどうやってるかがわかる。素晴らしい！

use rand::seq::SliceRandom;

#[derive(Debug, Clone, Copy, PartialEq)]
enum Suit {
    Club,
    Diamond,
    Heart,
    Spade,
}

#[derive(Debug, Clone, Copy, PartialEq)]
struct Card {
    suit: Suit,
    rank: i32,
}

fn main() {
    let mut deck: Vec<Card> = Vec::new();
    let suits = [Suit::Club, Suit::Diamond, Suit::Heart, Suit::Spade];

    for suit in suits {
        for rank in 1..=13 {
            deck.push(Card {suit, rank});
        }
    }
    let mut rng = rand::thread_rng();
    deck.shuffle(&mut rng);
    

    let mut hand: Vec<Card> = Vec::new();
    for _ in 0..5 {
        hand.push(deck.pop().unwrap());
    }

    hand.sort_by(|a, b| a.rank.cmp(&b.rank));

    for (i, card) in hand.iter().enumerate() {
        println!("{:}: {:?} {:}", i +1, card.suit, card.rank);
    }

    println!("入れ替えたいカードの番号を入力してください(例: 1 2 3)");
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();

    let numbers : Vec<usize> = input.split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<usize>>();
    for number in numbers {
        hand[number - 1] = deck.pop().unwrap();
    }

    hand.sort_by(|a, b| a.rank.cmp(&b.rank));

    for (i, card) in hand.iter().enumerate() {
        println!("{:}: {:?} {:}", i +1, card.suit, card.rank);
    }

    let suit = hand.first().unwrap().suit;
    let flash = hand.iter().all(|c| c.suit == suit);

    let mut count = 0;
    for i in 0..hand.len() - 1 {
        for j in i + 1..hand.len() {
            if hand[i].rank == hand[j].rank {
                count += 1;
            }
        }
    }

    if flash {
        println!("flash!");
    } else if count >= 3 {
        println!("スリーカード!");
    } else if count == 2 {
        println!("2ペア");
    } else if count == 1 {
        println!("1ペア");
    } else {
        println!("役なし...");
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.62s
Running `target/debug/app`
1: Spade 3
2: Spade 4
3: Club 5
4: Diamond 8
5: Spade 13
入れ替えたいカードの番号を入力してください(例: 1 2 3)
1 2 3 4
1: Diamond 10
2: Club 10
3: Diamond 12
4: Heart 12
5: Spade 13
2ペア

演算子を前に置くのをポーランド記法という　4 + 5 * 8 – 9 / 3 は、「- + 4 * 5 8 / 9 3」っと書く。
逆に、演算子を後ろに置くのを逆ポーランド記法という。「4 5 8 * + 9 3 / -」と書く。
逆ポーランド記法はスタックで処理しやすく、色々な場面で使われる。

fn calc(expression: String) {
    let mut stack: Vec<i32> = Vec::new();
    for i in expression.split(' ') {
        println!("{:?}", stack);
        if i == '+'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a + b);
        } else if i == '-'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a - b);
        } else if i == '*'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a * b);
        } else if i == '/'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a / b);
        } else {
            stack.push(i.parse::<i32>().unwrap());
        }
    }
    println!("{:?}", stack);
}

fn main() {
    calc("4 6 2 + * 3 1 - 5 * -".to_string());
}

[]
[4]
[4, 6]
[4, 6, 2]
[4, 8]
[32]
[32, 3]
[32, 3, 1]
[32, 2]
[32, 2, 5]
[32, 10]
[22]

なるほど、これは面白い。
コンパイラのOP_CODEでも同じようなことをやったような気がする。

use std::collections::HashMap;

fn main() {
    let text = ['J','A','P','A','N','H','O','L','D','I','N','G',];
    let pattern = ['H','O','L','D'];

    let mut skip = HashMap::new();
    for i in 0..(pattern.len() - 1) {
        skip.insert(
            pattern[i],
            pattern.len() - i - 1,
        );
    }
    println!("{:?}", skip);

    let mut i = pattern.len() - 1;
    while i < text.len() {
        let mut flg = true;
        for j in 0..pattern.len() {
            if text[i-j] != pattern[pattern.len()-1-j] {
                flg = false;
                break;
            }
        }
        if flg == true {
            println!("{}", i - pattern.len() + 1);
            break;
        } else if skip.get(&text[i]).is_some(){
            i += skip[&text[i]];
        } else {
            i += pattern.len();
        }
    }
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
{‘H’: 3, ‘O’: 2, ‘L’: 1}
5

線形ソートみたいな感じ
text[i + j] != pattern[j]とすることで、patterを一文字ずつ合致するか判定する。
regexもこれと同じアルゴリズムなんだろうか？？？

fn main() {
    let text = ['J','A','P','A','N','H','O','L','D','I','N','G',];
    let pattern = ['H','O','L','D'];

    for i in 0..text.len() {

        let mut flg = true;
        for j in 0..pattern.len() {
            if text[i + j] !=  pattern[j] {
                flg = false;
                break;
            }
        }
        if flg {
            println!("{}", i);
        }    
    }
}

Running `target/debug/rust`
5

fn dijkstra(edges: Vec<Vec<[usize; 2]>>, num_v: usize)  -> Vec<usize>{
    let inf = 999;
    let mut dist = Vec::new();
    for _ in 0..num_v {
        dist.push(inf);
    }
    dist[0] = 0;

    let mut q = Vec::new();
    for i in 0..num_v {
        q.push(i);
    }
    
    while *&q.len() > 0 {
        let mut r = q[0];
        for i in &q{
            if dist[*i] < dist[r] {
                r = *i;
            }
        } 
        let n = q.iter().position(|n| *n == r).unwrap();
        let u = q[n];
        q.retain(|&x| x != u);
        
        for i in edges[u].clone() {
            if dist[i[0]] > dist[u] + i[1] {
                dist[i[0]] = dist[u] + i[1];
            }
        }      
    }
    return dist;
}

fn main() {
    let edges = vec![
        vec![[1, 4], [2, 3]],
        vec![[2, 1], [3, 1], [4, 5]],
        vec![[5, 2]],
        vec![[4, 3]],
        vec![[6, 2]],
        vec![[4, 1], [6, 4]],
        vec![],
    ];
    println!("{:?}", edges);

    println!("{:?}", dijkstra(edges, 7));
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
[[[1, 4], [2, 3]], [[2, 1], [3, 1], [4, 5]], [[5, 2]], [[4, 3]], [[6, 2]], [[4, 1], [6, 4]], []]
[0, 4, 3, 5, 6, 5, 8]

おおおお、これは凄いな…