BlueskyのTUI Client Appを作り始めてしまった

memo.sugyan.com

の続き…?

I've published `tuisky`, a TUI Client for Bluesky, as v0.0.1. (It's still a work in progress.) Were there already other clients available for use in the terminal? #atdev #bluesky-client #tui crates.io/crates/tuisky

[image or embed]

— すぎゃーん (@sugyan.com) Jul 1, 2024 at 12:12 AM

経緯

TauriでのDesktop Clientはある程度動くところまで出来たが、問題点も発覚してきた。

大きくはmulti columnへの対応問題。React Routerで画面管理していたが、複数の画面を管理することになると厄介そう。 そもそもの問題点として、フロントエンドとバックエンドで画面状態やデータをどう持つか、が上手く役割分担できていなくて中途半端で複雑になってしまっていた。

なので、まずはバックエンド側での状態保持やデータ更新の仕組みを整理して作り直してみよう、と思い立った。

だが、その動作確認にいちいちTauriビルドしてフロントエンドで表示して…というのが面倒だなと思い。 一旦Tauriから離れてターミナル上だけでどうにかしたくなった。

しかしunit testだけで完結するのも難しく、動作確認のための何らかの表示UIは欲しい。

そこで TUI(terminal user interfaces)。

最近のTUIフレームワークなど全然知らなかったが、それなりに高機能なものも作れそうで面白そうだったので、やってみることにした。

RatatuiによるTUI開発

選択したのは Ratatui。

ratatui.rs

詳しい経緯は知らないが、元々は tui-rs という個人で作られた人気ライブラリがあったが、メンテナンスできなくなってきた結果コミュニティでforkして引き続き開発されている、というもののようだ。いい話(?)。

有名どころでは bottom などで使われているっぽい。

Ratatuiの主な特徴としては、複数のターミナルライブラリをbackendとして選択でき、UI widgetを配置して描画するための枠組みを提供している(そして基本的なwidgetがbuilt-inされている)、というところだろうか。

ターミナルのbackendは crossterm, termion, そして termwiz の3つから選択できるようだが、基本的にはcrosstermを使っておくのが無難そうだ。

Comparison of Backends | Ratatui

Asynchronous Event Handling

Ratatuiで簡単なTUIアプリケーションを作る場合、以下のようなループ処理を書くだけで実装できる。

    loop {
        terminal.draw(|frame| {
            // draw the UI
        })?;
        match event::read()? {
            Event::Key(key_event) if key_event.kind == KeyEventKind::Press => {
                // handle key events
            }
            _ => {}
        };
    }

メインのループの中で描画処理があり、キー操作などのEventを待ち受けて、そのEventによって状態変更するなどして描画内容を更新する、という基本的な流れ。

だが、このような作りだとEventを受け取るまでblockingして待ち続けるしかないし、バックグラウンドで処理されたものをUIに反映させるのも難しい。

より複雑なアプリケーションを作る際には、非同期Event処理を導入する。

Full Async Events | Ratatui

crossterm には event-stream featureがあり、これを有効にすることで非同期でEventを受け取ることができるようになる。

use futures::{FutureExt, StreamExt};
use tokio::{sync::mpsc, task::JoinHandle};

fn async_events() {
    let task = tokio::spawn(async move {
        let mut reader = crossterm::event::EventStream::new();
        let mut interval = tokio::time::interval(std::time::Duration::from_millis(250));
        loop {
            let delay = interval.tick();
            let crossterm_event = reader.next().fuse();
            tokio::select! {
                maybe_event = crossterm_event => {
                    match maybe_event {
                        Some(Ok(evt)) => {
                            ...
                        }
                        _ => { ... }
                    }
                },
                _ = delay => {
                    ...
                },
            }
        }
    });
    ...
}

このようにして、 crossterm からのEventを非同期で待ち受けることができるし、定期的なEventなども tokio::select! によって非同期で受け付けられるようになる。あとはここから tokio::sync::mpsc::unbounded_channel() などを使ってメインのUIスレッドに通信することでそれらを処理できるようになる。 キー操作など受け付けつつ定期的に描画するEventを発火させることで安定した画面更新もできるし、逆に特定のEventが発生しない限り無駄な描画をしない、といった調整も可能だ。

Components Architecture

様々なUI widgetを使用して複雑なアプリケーションを作る場合の設計パターンとして、幾つかのアーキテクチャが提案されている。その中の一つとして、「Component Architecture」というものがある。

Component Architecture | Ratatui

Component というTraitを定義し、これが

  • 初期化
  • 設定やAction handlerの登録
  • Event handling
  • Actionを受けての状態更新
  • Rendering

などのメソッドを持つ。メインのApp内でこれを実装した componentsVec<Box<dyn Component>> で持つようにして、メインループ内で「Eventを渡しActionを受ける、そのActionを処理して状態を更新、そして描画」という流れをそれぞれのComponentに対し透過的に行うようにする設計だ。

impl App {
  pub async fn run(&mut self) -> Result<()> {
    ...
    // componentsの初期化など 事前準備
    for component in self.components.iter_mut() {
      component.register_action_handler(action_tx.clone())?;
    }
    for component in self.components.iter_mut() {
      component.register_config_handler(self.config.clone())?;
    }
    for component in self.components.iter_mut() {
      component.init(tui.size()?)?;
    }
    // メインループ
    loop {
      // Event処理 (Actionへの変換)
      if let Some(e) = tui.next().await {
        ... // メインのEvent処理
        for component in self.components.iter_mut() {
          if let Some(action) = component.handle_events(Some(e.clone()))? {
            action_tx.send(action)?;
          }
        }
      }
      // Action処理
      while let Ok(action) = action_rx.try_recv() {
        match action {
          ...
          Action::Render => {
            // 各Componentの描画
            tui.draw(|f| {
              for component in self.components.iter_mut() {
                component.draw(f, f.size());
              }
            })?;
          }
        }
        for component in self.components.iter_mut() {
          if let Some(action) = component.update(action.clone())? {
            action_tx.send(action)?
          };
        }
      }
      if self.should_quit {
        break;
      }
    }
    Ok(())
  }
}

それぞれのComponentが独立したAppとして動作する感じになり、新しい要素を追加する場合も Component Traitを実装して components に追加するだけで良い。

自作Clientでは、これを参考にアレンジして設計してみた。

自作Client用の設計

機能

まずは盛り込みたかった機能について。

完全に分離された Multi Column

まずやりたかったのが、Multi Columnでの分割表示。ログインセッションなども完全に分離し、互いに干渉しない。あるColumnに対して操作をする際はそれ以外のColumnは表示のみで同時に操作することは無い。

履歴を保持しての画面遷移

Feedの一覧からPost詳細を見て、ThreadのReplyなどを辿り、またPost詳細を見てそのユーザのAuthorFeedを見て…、そしてまた最初のFeedまで戻って、と ブラウザで遷移して履歴から戻るような操作を各Columnで

Feedなどの自動更新

自分で操作しなくても定期的に新しいFeedを取得して自動で更新してくれる機能。

FocusとColumnを管理する MainComponent

まず適当に画面を縦に分割して複数のColumnを作るが、前述のComponents Architectureでそのまま各Columnを実装すると、どのColumnもすべて同じEventを受けて同じActionを処理してしまうことになる。

なので、このMainComponentでそこを整理して各ColumnへのEventやActionの伝達を行うようにした。

struct State {
    selected: Option<usize>,
}

pub struct MainComponent {
    columns: Vec<ColumnComponent>,
    state: State,
}


impl Component for MainComponent {
    ...

    fn handle_key_events(&mut self, key: KeyEvent) -> Result<Option<Action>> {
        // 選択中のColumnに対してのみEventを渡す
        if let Some(selected) = self.state.selected {
            self.columns[selected].handle_key_events(key)
        } else {
            Ok(None)
        }
    }
    fn update(&mut self, action: Action) -> Result<Option<Action>> {
        match action {
            Action::NextFocus => {
                self.state.selected = ...;
                return Ok(Some(Action::Render));
            }
            ...
            _ => {
                for column in self.columns.iter_mut() {
                    if let Some(action) = column.update(action.clone())? {
                        return Ok(Some(action));
                    }
                }
            }
        }
    }
}

Eventは選択中のColumnだけに渡すが、Actionは基本的にすべてのColumnに対して伝播させる。操作はしていないが非同期的にデータが更新される、といった場合に通知する必要があるからだ。 そういったもの以外は、受け取るColumn側でIDを保持し、Action発行時に自分のIDを載せるようにした。そして自分のIDと異なるIDのActionは無視するようにしている。

履歴を保持する ColumnComponent

各Columnでは、 ViewComponent Traitを実装したものを Vec<Box<dyn ViewComponent>> で保持し、その末尾要素に対してのみEvent/Actionを渡し、Renderする。 画面遷移するごとに新しいViewComponentを push() し、戻るときには pop() する。 ViewComponent Traitは概ね Component と同じだが、activate() deactivate() というメソッドを追加している。末尾のViewComponentのみActiveな状態として機能し、それ以外は非Activeな状態としてバックグラウンドでのデータ更新などを停止する。

    pub(crate) fn transition(&mut self, transition: &Transition) -> Result<Option<Action>> {
        match transition {
            Transition::Push(view) => {
                if let Some(current) = self.views.last_mut() {
                    current.deactivate()?;
                }
                let mut next = self.view(view)?;
                next.as_mut().activate()?;
                self.views.push(next);
            }
            Transition::Pop => {
                if let Some(mut view) = self.views.pop() {
                    view.deactivate()?;
                }
                if let Some(current) = self.views.last_mut() {
                    current.activate()?;
                }
            }
            ...
        }
        Ok(Some(Action::Render))
    }

設計まとめ

Component Architectureを倣って各Componentsで独立してEvent処理やRenderをできるようにしつつ、

  • Mainでは分割されたColumnsのFocus中のものだけにEventを渡し、またActionの伝播を行う
  • 各Columnでは履歴で最新のものだけをActiveなものとしてEvent処理/描画などを行う

という制御をいれることでMulti Columnで画面遷移を可能にした。

IndexMapを使ったFeed管理

ちょっとだけアルゴリズムとデータ構造的な話を。

Following feedでのtimelineに限った話ではあるけれど、ここではFeedの内容としてfollowingからのPostが流れてくる。 基本的には同じものが流れることは無いが、一つだけ例外があって、followingユーザがRepostしたものだけは同じものが複数回出現し得る。この場合は .post の内容は同一だが .reason が異なるものになる。

で、公式と同様の挙動を実現しようと思うと、表示すべきfeedの配列は

  • 基本的には出現した順に表示される
  • 一意なID(cidなど)で区別され、同一のものは出現しない
  • 既に存在するが.reasonだけ異なるものが出現した場合は、先頭に挿入(移動)される

という形であることが望まれる。 つまり A,B,C,D,B,E という順で出現した場合は、 A,B,C,D の後に B の再出現により A,C,D,B という並びになり、最終的な出力は A,C,D,B,E という表示になる。

基本的には Vec で管理して、既に存在するか否かを毎回 .contains() で検索するか または HashSet でID管理しておけば判定できる。しかし末尾に移動することになると 一旦 .remove() して .pop() する必要があり、そもそも何番目にそれが存在するのかを調べる必要も出てくる。 HashMap でindexを管理するようにすれば良さそうだが 移動によってそのindexも変化するので厳しそうだ。

別に何百万とか何億とかのデータを扱うわけでもないのでそんなにパフォーマンスを気にせず O(N)で処理しても困ることは無さそうではあるが、できるなら効率的に処理したい。

…ってことでどうするのが良いかChatGPTに相談したところ、「Pythonなら OrderedDict を使うことで効率的に処理できます」ということだった。Rustで同等な機能を持つものとして IndexMap があるようだったので、それを使うことにした。

    let mut feed_map: IndexMap<Cid, FeedViewPost> = Default::default();
    for post in feed {
        if let Some(entry) = feed_map.get_mut(&post.post.cid) {
            // Is the feed view a new repost?
            if ... {
                // Remove the old entry
                feed_map.swap_remove(&post.post.cid);
            } else {
                continue;
            }
        }
        feed_map.insert(post.post.cid.clone(), post.clone());
    }

ほぼ HashMap と同様の使い方で、こうして更新されたものから feed_map.values().rev().cloned().collect::<Vec<_>>() といった感じで出現順に並べられたFeedの配列を取得できる。

これなら重複時の移動も O(1)で実現できている、はず?

まとめ

  • Ratatuiを使ってTUIアプリケーションを作ってみた
    • TUIアプリちゃんと作ったことなかったので色々な知見を得られて楽しい
    • ターミナルで色々動かせるとテンション上がる
  • Clientのバックエンド処理を整理してブラッシュアップできそう
  • Blueskyクライアント欲しいだけなのにどんどん寄り道してる

Expressに22個以上の要素の配列クエリを渡すときは気をつける

自作ライブラリを使ったBlueskyクライアントを実装していて遭遇したバグ。

ATriumからのfeed.getPostsでurisが21個までなら大丈夫だが22個以上だとエラーになることが発覚した。問題切り分け中… ここまで自作クライアント実装してようやく気付く問題があるんだから やっぱりドッグフーディング大事やな、、

— すぎゃーん (@sugyan.com) Apr 21, 2024 at 10:21 AM

問題の詳細と対応は以下の通り。

Expressで使っている qs が、[] を含むキーのときに配列として扱おうとするが、そのindexの大きさによって結果がarrayではなくobjectになったりする、というもの。 その境界のdefault値が20なので、順番にindexをつけているとuris[0]=...&urls[1]=...&uris[20]=... という 21個までなら問題ないが 22個になると突然objectとして扱われるようになってしまう、と。

www.npmjs.com

確かにindex指定したものを読んでくれるのは便利だが… そんな挙動があると知らずにrequestを送っているとハマる。

const qs = require("qs");

console.log(qs.parse("ids=foo&ids=bar"));
console.log(qs.parse("ids[]=foo&ids[]=bar"));
console.log(qs.parse("ids[0]=foo&ids[1]=bar"));
console.log(qs.parse("ids[1]=foo&ids[0]=bar"));
console.log(qs.parse("ids[20]=foo"));
console.log(qs.parse("ids[21]=foo"));
{ ids: [ 'foo', 'bar' ] }
{ ids: [ 'foo', 'bar' ] }
{ ids: [ 'foo', 'bar' ] }
{ ids: [ 'bar', 'foo' ] }
{ ids: [ 'foo' ] }
{ ids: { '21': 'foo' } }

わりとみんなハマっているようで困っている人も多そうではあるが、とにかくそういう仕様なようなので express なserverにリクエストを送るときは気をつけるしかなさそう。

github.com

BlueskyのDesktop Client Appを作り始めている

ATProtocolのRustライブラリを作っている 活動の続きとして、ライブラリの動作確認も兼ねてDesktop Applicationを作ってみることにした。

Tauri

RustでDesktop Application作成、といえば今もっとも普及しているのがTauriだろう。

tauri.app

ステータスとしてはMobile Application対応を含む v2のリリースに向けてBeta versionが公開されている、という状態のようだ。

Tarium

で、AT ProtocolのためのRustライブラリである ATrium をバックエンドで使ったTauri製のBluesky Client、ということで「Tarium」という名前にした。

github.com

Frontend

フロントエンドは各プラットフォームでのWebView上で動くわけで、結局HTMLやJavaScriptで用意することになる。 気合いでFull Rustで実装しようとすれば Yew などで構築することもできるようだったが、自分はまだ使ったことがなく学習が大変そうだったので、結局 Vite + React でTypeScriptで書くことにした。あとは React RouterTailwind

Backend

普通にWeb Applicationが作れるので、Bluesky Clientとしてはatproto公式のTypeScriptライブラリを使ってフロントエンドで完結するものも作れてしまう。

しかし自分の目的としては ATriumの動作確認なので、意地でもAT Protocolの処理はバックエンドにやらせることにしている。 結局バックエンドは command を介してフロントエンドからのXRPC Requestをproxyするだけ、になってしまいがちで 何のためにRustバックエンドが存在しているんだ… という感じにはなってしまうけど。

一応役割としては内部のStateとしてAtpAgentを持ってSession管理などをしている、くらい。単にproxyするだけだと悔しいので、feedの取得などはバックグラウンドタスクで定期的に実行して新しく表示すべきものをEventのemitによってフロントエンドに通知する、という方式にしている。まぁそれもフロントエンドでsetIntervalで実装するのとたいして変わらないんだろうけど…。

今のところPWAと比較して「Native Appならでは」というのはあまり無く、ようやくデスクトップ通知ができるようになった、くらいか? 今後はもしかしたらショートカットキーを使った操作などが実装できるとNativeならでは感がでるかもしれない。

型定義生成

ということで結局は書くコードの大半はTypeScriptになる。 そしてデータはバックエンドから取得するが IPC を介して結局JSONでやりとりすることになるので、Lexiconに沿った型にmappingさせて表示に使うにはどうしても型定義が必要になる。

最新のLexiconから対応する型定義などを生成したものが @atproto/api パッケージなどに含まれていて、公式appや他の多くのWeb Clientなどではこれを使っているはず。 Tariumのフロントエンドでもこれを素直に使えば良いが、この api パッケージにはXRPCのためのClient機能なども含まれていて、折角バックエンドでXRPC処理するようにしているのに本末転倒、というか「負けた」感じになってしまう…。

なので、意地でも @atproto/api は使わずに必要な型定義だけを得たい!ということで この api のためのコードを生成している @atproto/lex-cli をハックして必要なものだけを生成して使う、ということをした。

https://github.com/sugyan/tarium/tree/main/gen-types

現在の状況

v0.0.8 で、FollowingのタイムラインとCustom Feeds、あと通知がようやく表示できるようになって あとはテキストのみの単純な投稿ならできる、というくらい。まだまだ足りない機能だらけではあるが ちょっとずつ使えるようになってきている、とは思う。 自分が満足いくところまでは頑張って機能実装していくつもり。

実際、ここまで実装する過程でATriumがgetPreferencesを正しく取得できないバグに気付いたりできたので、当初の目的としては正しく達成できている。

Rustのserdeで、データフォーマットによって異なる型にserialize/deserializeする

背景

BlueskyのAT ProtocolのRust版ライブラリを作っている。

memo.sugyan.com

github.com

その中で最近実装した機能の話。

AT Protocolで扱うデータモデルのSpecは、以下のページで書かれている。

atproto.com

この中に、Lexiconでcid-linkという名前で扱われる型がある。

https://atproto.com/specs/lexicon#cid-link

つまりIPLDのLinkCIDで表現する型、ということのようだ。

で、これらのデータを扱うわけだが、そのデータフォーマットが2種類ある。 IPLDではデータ送信のためのCodecとして、binary formatのDAG-CBORと human-readable formatのDAG-JSONを定めている。

https://ipld.io/docs/codecs/

AT Protocolでは、効率的にデータを扱いたい場合にはDAG-CBORを用い、XRPCのHTTP APIなどではDAG-JSONとは異なる規約のJSONフォーマットを扱う、らしい。

で、cid-linkについては以下のように書かれている。

link field type (Lexicon type cid-link). In DAG-CBOR encodes as a binary CID (multibase type 0x00) in a bytestring with CBOR tag 42. In JSON, encodes as $link object

DAG-CBORでは、以下のようなバイナリ表現のCIDを含むバイト列、

0xd8, 0x2a, 0x58, 0x25, 0x00, 0x01, 0x71, 0x12, 0x20, 0x65, 0x06, 0x2a, 0x5a, 0x5a, 0x00, 0xfc,
0x16, 0xd7, 0x3c, 0x69, 0x44, 0x23, 0x7c, 0xcb, 0xc1, 0x5b, 0x1c, 0x4a, 0x72, 0x34, 0x48, 0x93,
0x36, 0x89, 0x1d, 0x09, 0x17, 0x41, 0xa2, 0x39, 0xd0,

JSONでは、以下のような $link という単一のキーを含むオジェクト、

{
  "$link": "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a"
}

として表現されるらしい。

serde_json, serde_ipld_dagcbor

RustでJSONなどのデータフォーマットで Serialize/Deserialize する、となるとまず間違いなく serde を使うことになるだろう。 serde自体は Serialize/Deserialize を行うわけではなく、あくまでRustのデータ構造に対して汎用的にそれらを可能にするためのフレームワーク、という感じ。

ATriumではLexiconから生成された各XRPCに関連するデータの型をライブラリとして提供するので、それらの型に対して基本的にはserdeのattributesを付与するだけで、実際に何らかのデータフォーマットに対応した Seriazlier/Deserializer を使って変換操作をするのはライブラリのユーザ、ということになる。

実際のところ、JSONデータを扱うなら serde_json 一択だろう。 DAG-CBORについては、CBORデータを扱うことができるライブラリが幾つか存在しているが、2024-03時点でIPLDのLinkを正しく扱えるものとしては serde_ipld_dagcbor が現実的な選択肢になるようだった。

ので、この2つを使って実際に使われるデータに対して正しく Serialize/Deserialize できるようにする、ということを考える。

問題点: データフォーマットによって対象の型が異なる

JSONの場合/DAG-CBORの場合をそれぞれ独立して考えれば、構造に合わせて型を定義するだけなので簡単だ。

#[derive(Serialize, Deserialize, Debug)]
struct CidLink {
    #[serde(rename = "$link")]
    link: String,
}

fn main() {
    let cid_link_from_json = serde_json::from_str::<CidLink>(...);
    println!("{cid_link_from_json:?}");
    // => Ok(CidLink { link: "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a" })
}
#[derive(Serialize, Deserialize, Debug)]
struct CidLink(cid::Cid);

fn main() {
    let cid_link_from_dagcbor = serde_ipld_dagcbor::from_slice::<CidLink>(...);
    println!("{cid_link_from_dagcbor:?}");
    // => Ok(CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)))
}

で、問題は両方に対応しようとする場合。ライブラリのユーザがJSONを使うか DAG-CBORを使うかどちらかだけであればまだ feature flags で切り替えるなどの対応が可能だが、「どちらも使う」というユースケースも考えられるので、

  • serde_json を使っている場合は $link キーを含むオブジェクト
  • serde_ipld_dagcbor を使っている場合は cid::Cid

として同じ CidLink という名前の型に情報を格納できるようにしたい。

最初の解決策: is_human_readable() による分岐

基本的には serde 自体は、呼ばれる Serializer/Deserializer についての情報を知ることができない。 が、 SerializeDeserialize を自分で実装すると、そのときに引数に含まれる serializerdeserializer に対して .is_human_readable() というメソッドを呼ぶことで一つ情報を得られる。 これは serde_json を使っていると true になり、 serde_ipld_dagcbor を使っていると基本的には false になるので、以下のように分岐させることで統一した CidLink で両方のデータフォーマットを扱うことができる。

#[derive(Debug)]
struct CidLink(Cid);

#[derive(Serialize, Deserialize)]
struct LinkObject {
    #[serde(rename = "$link")]
    link: String,
}

impl Serialize for CidLink {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        if serializer.is_human_readable() {
            LinkObject {
                link: self.0.to_string(),
            }
            .serialize(serializer)
        } else {
            self.0.serialize(serializer)
        }
    }
}

impl<'de> Deserialize<'de> for CidLink {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        if deserializer.is_human_readable() {
            let obj = LinkObject::deserialize(deserializer)?;
            Ok(Self(
                Cid::try_from(obj.link.as_str()).map_err(serde::de::Error::custom)?,
            ))
        } else {
            Ok(Self(Cid::deserialize(deserializer)?))
        }
    }
}

これで解決、めでたしめでたし… といきたいところだが、そうもいかない。

うまくいかないケース

CidLink 単体が上手く処理されていても、それを子にもつ enum を "Internally tagged" や "Untagged" で区別しようとすると、問題が生じるようだ。

例えば、以下のようなもの。

#[derive(Serialize, Deserialize, Debug)]
#[serde(tag = "tag", rename_all = "lowercase")]
enum Parent {
    Foo(Child),
    Bar(Child),
}

#[derive(Serialize, Deserialize, Debug)]
struct Child {
    cid: CidLink,
}

これは、 "tag" キーで指定されたvariantとしてdeserializeを試みる。JSONでいうと

[
  {
    "tag": "foo",
    "cid": {
      "$link": "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a"
    }
  },
  {
    "tag": "bar",
    "cid": {
      "$link": "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a"
    }
  }
]

といった配列で渡されたとき、1つめの要素は Parent::Foo(Child) 、2つ目の要素は Parent::Bar(Child) としてdeserializeすることになる。

これと同様の構造を持つDAG-CBORのデータを serde_ipld_dagcbor でdeserializeすると (そもそもこういうケースでCidを含むものをdeserializeできないという問題 もあったが)

Error: Msg("invalid type: newtype struct, expected struct LinkObject")

といったエラーになってしまう。

deserializer.is_human_readable() で分岐しているところでdebug printしてみると分かるが、このような構造のデータをdeserializeするときは、 serde_ipld_dagcbor を使っていても .is_human_readable()true になってしまうらしい。 serde の細かい挙動を知らないけど、 Internally tagged や Untagged の場合は一度mapデータとして保持してからtagや内容を見て型を決定する必要があるため?そこから目的の型にマッピングする際に使われるdeserializerはまた別物になるらしく、 .is_human_readable() は意図したものにはならないようだ。 おそらくこのあたり。

なので、上述のように enum を使っている箇所の下では .is_human_readable() による分岐は機能しない。

解決策(?): Ipld を経由しデータの構造によって分岐する

serde_ipld_dagcbor という名前の通り、これは Ipld というデータモデルを利用することを想定されている。このデータモデルは(互換性どれくらいか把握できていないけれど) serde_json::Value と同じように構造化されたデータを保持できる。JSONには無い Link というものがある点でJSONの上位互換と考えても良いかもしれない。

ということで、deserializeしたいデータを一度 Ipld に変換してしまい、その構造を見てデータフォーマットを推定して分岐する、という手段をとった。

use libipld_core::ipld::Ipld;

impl<'de> Deserialize<'de> for CidLink {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        let ipld = Ipld::deserialize(deserializer)?;
        match &ipld {
            Ipld::Link(cid) => {
                return Ok(Self(*cid));
            }
            Ipld::Map(map) => {
                if map.len() == 1 {
                    if let Some(Ipld::String(link)) = map.get("$link") {
                        return Ok(Self(
                            Cid::try_from(link.as_str()).map_err(serde::de::Error::custom)?,
                        ));
                    }
                }
            }
            _ => {}
        }
        Err(serde::de::Error::custom("Invalid cid-link"))
    }
}

少なくとも CidLink としてのデータであれば、 Ipld::deserialize(deserializer) は問題なく成功する。その結果は Ipld::Link か、 "$link"キーを含む Ipld::Map かどちらか、になるはずで、前者ならそのまま得られるCidを利用し、後者であればその "$link" の値からCidを復元する。

この手法であれば、 .is_human_readable() に依存せずに正しく判別でき、どちらのデータも同様にdeserializeできる。

fn main() {
    let parents_json = serde_json::from_str::<Vec<Parent>>(...)?;
    println!("{parents_json:?}");
    // => Ok([Foo(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) }), Bar(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) })])

    let parents_dagcbor = serde_ipld_dagcbor::from_slice::<Vec<Parent>>(...)?;
    println!("{parents_dagcbor:?}");
    // => Ok([Foo(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) }), Bar(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) })])
}

今回のようなケースでしか機能しないかもしれないが、一応これで問題は解決した。

(他にもっと良い方法をご存知の方がいれば教えてください…)

汎用的? な解決策: Untagged

一般的には、このように場合によって異なる型にdeserializeしたい場合は Untagged なenumを使うのが良いのかもしれない。

#[derive(Serialize, Deserialize)]
#[serde(untagged)]
pub enum CidLink {
    Raw(Cid),
    LinkObject {
        #[serde(rename = "$link")]
        link: String,
    },
}

serde(untagged) の場合はvariantを順番に試し、最初にdeserializeに成功したものを結果として返す。 ので、上の例の場合はまず Cid 単体としてdeserializeしてみて、失敗したら "$link" キーを持つオブジェクトとしてdeserializeしてみる、という動作になる。記述の順序を変えれば試行の順序も変化する。

ベンチマーク

上述した"Untagged"の場合は、記述の順序が大事になる。上の例の通りだとJSONのデータは毎回最初にCidとしてdeserialize試行して失敗してようやくオブジェクトとして試行、となり効率が悪い。しかし順序を逆にすると今度はDAG-CBORのデータを処理する際に毎回オブジェクトとして試行して失敗して…となる。 今回は対象が2種類だけなので差は小さいかもしれないが、これが何種類もあると…。

その点ではIpldを経由する手法の方が、中間の変換処理は入るが安定した効率は期待できる。

当然ながら、JSONなら最初からオブジェクトとして DAG-CBORなら最初からCidとしてdeserializeするのが最も効率的で速い。 それぞれを基準として、「Raw→LinkObjectのuntagged (untagged_1)」「LinkObject→Rawのuntagged (untagged_2)」「Ipld経由 (via_ipld)」のそれぞれのdeserializeをベンチマークとってみた。

running 8 tests
test bench_cbor_only       ... bench:          59 ns/iter (+/- 1)
test bench_cbor_untagged_1 ... bench:          83 ns/iter (+/- 2)
test bench_cbor_untagged_2 ... bench:         172 ns/iter (+/- 8)
test bench_cbor_via_ipld   ... bench:          63 ns/iter (+/- 1)
test bench_json_only       ... bench:          77 ns/iter (+/- 2)
test bench_json_untagged_1 ... bench:         276 ns/iter (+/- 4)
test bench_json_untagged_2 ... bench:         134 ns/iter (+/- 9)
test bench_json_via_ipld   ... bench:         325 ns/iter (+/- 6)

DAG-CBORに関しては、 untagged_2 がやはり毎回LinkObjectの試行の後になるので3倍ほど遅くなってしまう。一方で via_ipld はほぼ同等の速度で処理できているようだ。

JSONに関しては、どれも大きく遅くなるようだ。意外にも untagged_2 でも2倍くらい遅くなる…。via_ipld はcidのparse処理も入るので当然ながら最も遅くなってしまう、という結果だった。

実装結果

ということで、

  • どうしてもJSONだけを扱うときと比較すると遅くなる
  • そもそもXRPC RequstにはJSONしか使わない
    • DAG-CBORが必要になるのはSubscriptionなどrepoデータを読むときのみ

ということもあって、dag-cbor featureを有効にしたときのみ、Ipldを経由する方式で両方のデータフォーマットに対応するようにした。

その後

この実装をした後、 types::string::Cid という型が導入されて、Cidの文字列表現であるものはこの型でvalidationするようになった。LinkObjectのものも値は String ではなくこの types::string::Cid を使うべきで、そうなるともはやJSONの速度差もそんなに気にしても仕方ない感じになってくる。

running 8 tests
test bench_cbor_only       ... bench:          59 ns/iter (+/- 0)
test bench_cbor_untagged_1 ... bench:          78 ns/iter (+/- 3)
test bench_cbor_untagged_2 ... bench:         169 ns/iter (+/- 3)
test bench_cbor_via_ipld   ... bench:          63 ns/iter (+/- 3)
test bench_json_only       ... bench:         227 ns/iter (+/- 4)
test bench_json_untagged_1 ... bench:         426 ns/iter (+/- 6)
test bench_json_untagged_2 ... bench:         288 ns/iter (+/- 5)
test bench_json_via_ipld   ... bench:         324 ns/iter (+/- 6)

もはや feature flags での切り替えは廃止して、必ずIpldを経由する方式にしてしまって良いかもしれない。

Cloudflare Workersで、自分のはてブをBlueskyに流す

bsky.app

そういえば、古き良き時代は自分のブックマークは自動でTwitterに投稿されていたのだった。 今はBlueskyがメインになっているので、同じ仕組みが欲しい、と思った。ので、作った。

github.com

要件

自分のブックマークはRSSで取得できる。定期的にチェックして新しいのがあれば、といったロジックで検出できる。 なので、基本的にはプログラムを定期実行できる場所があればGitHub Actionsとかでも良い。 ただ、対象のブクマ内容をpostする前に、それを既にpostしているか否かを知る必要がある。

専用のbotアカウントとかであれば、そのアカウントのpost feedを取得して最近のものをチェックすれば確認可能だが、自分のアカウントに流す場合はその方法だと手動で大量にpostしたりしているタイミングだと埋もれてしまう。 よって、何らかの方法でpost済みのものを保持しておく必要がある。

先行事例

で、良いなと思ったのがこれ。

github.com

Cloudflare Workersでも Cron Triggers で定期実行できて、また Workers KV のようなものでデータを保存しておくことができる。 上述要件を満たすプラットフォームとしてはちょうど良さそう。

Rust版

前述のをそのまま使わせていただいても良かったのだけど、折角 ATProtocolのRustライブラリを作っている のだし、Rustで同じような機能のものを作ってみることにした。

WASM対応

まず拙作 ATrium を使ってみようとしたところ、早速ビルドに失敗した。 あまり考えていなかったが、 wasm32-unknown-unknown のtargetでビルドしようとすると失敗する箇所が多々あった。

ので、まずはそこから。

github.com

主に問題は async-trait を使っているところで、これが Send を要求するため wasm32 targetの場合に問題になるようだった。 これは (?Send) を追加することで回避できるとのこと。 wasm32 targetのときだけこれを追加する形に変更した。他のtargetの場合は何も影響を受けない。

#[cfg_attr(target_arch = "wasm32", async_trait(?Send))]
#[cfg_attr(not(target_arch = "wasm32"), async_trait)]

あとは atrium-xrpc-client という専用の非同期HTTP Clientを幾つか提供していたが、それらは reqwest backendのもの以外はすべてwasm32には対応していなかったので、諸々変更して wasm32 の場合は reqwest のClientだけが利用可能になるようにした。

Cloudflare Workersでの実装

以前の記事 でも書いた通り、Cloudflare WorkersはRust環境でも作成することができる。今回のものもJavaScript/TypeScriptを1行も書かずに作成できた。

Cron Triggers用に #[event(scheduled)] をつけた関数を実装するだけ。

1MB制限との戦い

うっかり色んなライブラリを依存に入れていると、ビルド後のサイズが無料枠上限の1MBを超えてしまう。

RSSの解析に最初は feed-rs を使っていたが、ちょっと大きいようだったのでもっとシンプルにRSS 1.0のものだけ扱える rss に変更したりした。

Fetch API

ローカル実行する時の感覚で reqwest を、コンテンツ取得や atrium-xrpc-client のバックエンドとして使っていたが、実は必要なかった… worker-rs には worker::Fetch があり、これを使うことでHTTPリクエストを処理できる。

ATriumでは、非同期HTTP Clientとしてはどんなものを使っても良いようにTraitだけ用意して開発者が自由にClientを実装・選択できるように設計していた。 ので、今回は worker::Fetch を使うように少し繋ぐ部分を書くだけでXRPC Clientとして問題なく利用できるようになった。

github.com

ただ、本来このFetch APIを使って Transform images もできるはずなのだが、どうもRust版はまだ対応できていないっぽい。

Add support for the `cf.image` field in `fetch()` properties by jakubadamw · Pull Request #351 · cloudflare/workers-rs · GitHub

無理矢理やればできるのかな… とはいえOGPの画像はわりと変換かけずにそのまま uploadBlob しても失敗することは少なそう?なのでしばらく様子見でいいかな。

KVでのSessionStore?

ちなみに atrium-api ではセッション情報を管理する AtpAgent というのも用意していて、ここでは SessionStore も自分で実装することで認証情報を保持しておくことができるように設計していた。 通常は memoryに保持するだけの MemorySessionStore を利用するが、今回のようなケースで KV を使ってそこに保持しておくことができないか? と試みたが、やはり Send trait要求の壁があり上手くいかなかった… これはちょっと対応するのも難しいかなぁ。

そもそも今回のように難しい並列処理とか無いような場合はわざわざsession保持しておかなくても都度ログイン(createSession)する、で問題なさそうではある。

Rustで将棋の局面画像生成、そしてCDN Edgeで動的生成

背景

先行・類似事例

その他、自分でも過去にGoで作成したものがあったが、もう今はメンテしていなくて動かない。画像素材を公開してくださっていたサイトも消滅してしまっている。

自作のメリット

  • 自分好みの画像を生成できる
    • 形式もまずはPNGで、SVGも後で追加するなど可能かも
  • Rustのプログラムから使えるライブラリとして存在していると嬉しい
    • WASM化してWebアプリ化もしやすいかもしれない

Rustで局面画像生成

基本的には、透過PNGの素材を組み合わせて盤上に駒を配置するだけ。

あとは持ち駒の表現が様々な表示方法があるが、歩は最大18枚なので重ねて並べるのは微妙で、素直に個数を数字としてレンダリングした方が分かりやすいと思う。

盤・駒画像の素材

最近では Electron将棋 のKubo, Ryosukeさんが使いやすい形で素材画像を公開してくださっている。

sunfish-shogi.github.io

ので、これを使わせていただくことにした。 二文字駒もあると嬉しかったが、一時期追加されていたものの諸事情で削除されてしまったようだ。 今後 誰かがオリジナルで作成してここに追加してくれたりするようになるといいな…。

画像処理

image というライブラリが画像処理によく使われているようだ。 PNG以外にも様々な画像形式に対応していて、拡大縮小や重ね合わせなどの基本的な処理も簡単にできる。

作成時にはPNG画像を合成する操作だけなので、もっと軽いライブラリで同様のものが実現できるならそちらの方が良いかもしれない。とりあえずはimageで実装してみた。

入出力

入力は局面の情報を持つものとして shogi_corePartialPosition を使うことにした。出力はimageRgbaImage

ライブラリ使用者は必要に応じて例えば shogi_usi_parse を使ってSFEN文字列からPartialPositionを作り、それを元に生成した結果のRgbaImageを加工したり好きな形式でファイルに書き出したりすれば良い、という想定。

pub fn pos2img(position: &shogi_core::PartialPosition) -> image::RgbaImage {
    Generator::default().generate(position)
}

Generatorと下準備

局面画像を作成する際の計算負荷が減るよう、Geenratorという構造体を用意した。 スタイルを指定してnewした時点で必要な駒などの素材データを読み込んでおき、generateを呼ばれた際にはそれらを貼り合わせるだけ、にする。 これによって、同じスタイルで複数の局面を生成する場合には、素材の読み込みが一度で済んで高速に生成できるようになる、はず。

盤と駒の画像は事前にサイズを決めておき、それぞれ切り出した上で最適化したPNGファイルとして置いておく。ファイル読み込みはせず、include_bytes!でメモリ上から読み込んで使う。

Publish

というわけで出来上がったので crates.io に公開した。 ご自由にお使いください。

Web Appで使う

せっかくライブラリとして作ったので、ちょっと加工してWeb Appとしても使えると嬉しいかもしれない、と思って作ってみることにした。

局面を表現するSFEN文字列は lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1 のように表現される。これをURLのPathとして受け取って、対応する局面画像を返すようなものを考えた。

例:

https://example.com/3sks3/9/4S4/9/1+B7/9/9/9/9%20b%20S2rb4g4n4l18p%201

スペースは %20エンコードする必要があるのでちょっとカッコ悪いが…。

CDN Edgeで動かす

最近よく聞くようになったEdge Computingをまだ試したことがなかったので、この機会に色々触ってみることにした。

wasm-packでWebAssembly作成

まずは簡単なインタフェースを決めて、WebAssemblyで使えるようにパッケージを用意した。 簡単に扱えるように、入力はSFEN文字列としshogi_usi_parseでそれをparseし局面情報を取得、出力は生成した画像のPNG形式バイナリデータとした。

use shogi_img::{image, pos2img, shogi_core};
use shogi_usi_parser::FromUsi;
use std::io::Cursor;
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn sfen2png(sfen: &str) -> Vec<u8> {
    let pos = shogi_core::PartialPosition::from_usi(sfen).unwrap_or_default();
    let mut cursor = Cursor::new(Vec::new());
    pos2img(&pos)
        .write_to(&mut cursor, image::ImageFormat::Png)
        .ok();
    cursor.into_inner()
}

あとは wasm-pack でビルドすればいい感じにwasmファイルが生成される。

Deno Deploy

上記のwasmを使って最も簡単に実現できたのが、Deno Deploy だった。 wasm-pack build --target deno するとDeno用のwasmファイルが生成され、あとはそれを読み込んで使うだけ。

import { sfen2png } from "./pkg/sfen2png.js";

Deno.serve((req: Request) => {
  const sfen = `sfen ${decodeURI(new URL(req.url).pathname).slice(1)}`;
  return new Response(sfen2png(sfen), {
    headers: {
      "content-type": "image/png",
    },
  });
});

これだけのコードを書いて、あとはdeployすれば動く。簡単すぎてすごい。

$ curl -I https://sfen2img.deno.dev/
HTTP/2 200
content-type: image/png
vary: Accept-Encoding
date: Wed, 24 Jan 2024 14:39:32 GMT
content-length: 447458
via: http/2 edgeproxy-h
server: deno/gcp-asia-northeast1

Vercel Edge Functions

同様にwasmを読み込んで使えるものとして、Vercel Edge Functions を試してみた。

ドキュメントには wasm-pack を使った例が無いようで、他の人が作っているexample repositoryなどを参考にしてどうにか。 wasm-pack build --target web で生成し、Next.jsで/src/app/[[...slug]]/route.ts で使う。

// @ts-ignore
import wasm from "@/pkg/sfen2png_bg.wasm?module";
import init, { sfen2png } from "@/pkg/sfen2png.js";

export const runtime = "edge";
export const dynamic = "force-dynamic";

export async function GET(request: Request) {
  await init(wasm);
  const sfen = `sfen ${decodeURI(new URL(request.url).pathname).slice(1)}`;
  return new Response(sfen2png(sfen), {
    headers: {
      "content-type": "image/png",
    },
  });
}

とりあえずこれでローカルでは動いた。deployしてみようとしたが

Error: The Edge Function "[[...slug]]" size is 1.62 MB and your plan size limit is 1 MB.

となってしまった。wasmだけで1.3MBくらいあり、Hobbyプランでは1MBまで という制限を超えてしまうようだ。 Pro以上のプランにするか、もっと軽いバイナリになるように工夫が必要になる…。

Cloudflare Workers

よく名前を聞くので是非試してみたかった、Cloudflare Workers

wrangler でプロジェクトを作成する際に worker-rust のテンプレートを使うと、Rustで worker を使うRustプロジェクトが生成される。

wrangler generate [name] https://github.com/cloudflare/workers-sdk/templates/experimental/worker-rust

そして lib.rs を以下のように編集するだけ。

use sfen2png_wasm::sfen2png;
use urlencoding::decode;
use worker::*;

#[event(fetch)]
async fn main(req: Request, _env: Env, _ctx: Context) -> Result<Response> {
    let decoded = decode(&req.path())
        .map(String::from)
        .expect("decode failed");
    let sfen = format!("sfen {}", decoded.strip_prefix('/').expect("invalid path"));
    Ok(Response::from_bytes(sfen2png(&sfen))?
        .with_headers(Headers::from_iter([("content-type", "image/png")])))
}

JavaScriptdecodeURI同等のものは標準には無いようなので urlencoding ライブラリを使っている。

あとは wrangler deploy するだけ。その中で worker-build によってCloudflare Workers用に諸々ビルドされるようで、worker-buildが内部でwasm-packを実行したりしているようだ。 Rustだけで完結し、JS/TSのコードを書く必要がない。wranglerのためにnpmを使うくらい。

Cloudflare WorkersもVercel Edge Functionsと同様に Free planでは 1 MB まで という制限があるが、こちらは size after compression ということで事前にgzip圧縮して送信してくれるおかげで660KB程度になり、制限に引っかかることなくdeploy成功する。

Total Upload: 1414.62 KiB / gzip: 659.91 KiB
$ curl -I https://sfen2img.sugyan.workers.dev/
HTTP/2 200
date: Thu, 25 Jan 2024 06:16:53 GMT
content-type: image/png
content-length: 447458
report-to: {"endpoints":[{"url":"https:\/\/a.nel.cloudflare.com\/report\/v3?s=cT5XwLyJxYgiWXTJ85RHOGIRSxlpJSnl%2F6iPDoQW097set8BelY7M%2Fc6mRULGktwSqBU2Jlv6UoJ3w6eYFDM4bBjNHmZPGvfrnipB8u4Fxmkc3T%2BjFVUyF80dEFkxsn5X1Lp9OzTRhytCWAf%2BLA%3D"}],"group":"cf-nel","max_age":604800}
nel: {"success_fraction":0,"report_to":"cf-nel","max_age":604800}
server: cloudflare
cf-ray: 84ae63d57d908370-KIX
alt-svc: h3=":443"; ma=86400

Fastly Compute@Edge

最後に Cloudflare Workersと並んでよく名前を聞く、Fastly Compute@Edge

こちらは fastly というCLIツールを使う。

$ fastly compute init

...

Language:
(Find out more about language support at https://developer.fastly.com/learning/compute)
[1] Rust
[2] JavaScript
[3] Go
[4] Other ('bring your own' Wasm binary)

このあたりから選べそう。今回はRustで。Cloudflare Workersと同様にRustプロジェクトが生成されるので、同じようにmain.rsを編集していく。

use fastly::http::header;
use fastly::{Error, Request, Response};
use sfen2png_wasm::sfen2png;
use urlencoding::decode;

#[fastly::main]
fn main(req: Request) -> Result<Response, Error> {
    let decoded = decode(req.get_path())?;
    let sfen = format!("sfen {}", decoded.strip_prefix('/').expect("invalid path"));
    Ok(Response::from_body(sfen2png(&sfen)).with_header(header::CONTENT_TYPE, "image/png"))
}

Request/Responseなどのインタフェースは worker とは多少異なるが、おおまかには同じなのでこれくらいの内容であればほぼ同じような感覚で書ける。

あとは fastly compute publish するだけ。こちらは wasm-pack なども使わない。

$ curl -I https://sfen2img.edgecompute.app/
HTTP/2 200
content-type: image/png
x-served-by: cache-nrt-rjtf7700062-NRT
date: Thu, 25 Jan 2024 07:26:11 GMT

その他

Edge Computing系のサービスは他にも多くあるようだが、今回はこれくらいで。 大抵はJSからwasmを呼び出す形でVercel Edge Functionsと同様に動かせる、と予想している。

サイズ制限は厳しい場合が多いので、.wasmが1MBを切る程度には軽量できた方が望ましそうではある…。

まとめ

局面画像生成ライブラリを作ったおかげで、詰将棋画像を投稿するBluesky BotをRustだけで作ることができた。

bsky.app

スクレイピングして得たkifファイルをparseして局面情報を取得する部分も 自作ライブラリ を使っているので、

  • kifから PartialPosition への変換
  • PartialPosition から画像生成
  • 生成画像を含むPostをBlueskyに投稿

の3つを自作のライブラリを使って実現していることになる。

副産物として、Edgeで動的生成するWeb Appが複数できた。 無料枠でそのまま置いておくので、使える限りはご自由にお使いください。

Repository

Advent of Code 2023 を完走した

毎年12月に開催されている Advent of Code に、2019年から参加している。

過去記事:

2023年のAdvent of Codeにも挑戦していて、年が明けてしまったが先日ようやく25日すべての問題に解答して 50 個のスターを集めることができた。

bsky.app

2023年は例年と比較しても難易度が高いものが多かったように思う(英語のストーリーを読解しきれない、のは毎年のことだが)。 いちおう「他の人の解答を見たりせずにまずは自力で回答する」という目標は達成してとりあえずの自力完答はできたが、正直どうするのが正しかったのか分からん…というものも多かった。

github.com

これから Reddit での議論を見たり他の言語でも解いてみたりして、もうちょっと勉強しておこうと思っているところ。

問題の概要と解いた感想

ネタバレしない程度に。

day01

行の文字列の中から数値(数値)を見つける。

1日目の小手調べにしてはpart2がちょっと面倒だった

day02

3色の石の数を推測するゲーム。

正しく入力をparseして処理できれば特に問題ない

day03

2次元の図ではあるが横に並ぶ数字は数値として見る必要がある、というもの。

数値と記号の位置関係をうまく判定できれば、という感じ

day04

クラッチカードの得点計算。

part2はAoCらしいメタな感じでちょっと頭を使う面白い問題

day05

数値の範囲から別の範囲へのマッピング、を繰り返す。

急に難易度が上がって大変だった…!

day06

チャージ時間を調整してボートが進める距離を予測する。

入力のフォーマットが不自然だったのは意味があったか…

day07

トランプのポーカーの役の強さでソートする。

またしてもpart2の展開を予測できなかった

day08

2分岐の迷路を指定された方向に無限に進み続ける。

part2がやはり少し難しく。入力が上手く作られていることに救われている感じ

day09

数列から差分を使って次の値を予測する。

スッと解けると気持ち良い

day10

2次元grid内でループする経路を検出。

part2はだいぶ苦労した… 理論を知っていればもっと簡単だったのだろうか

day11

膨張し続ける宇宙空間で銀河間の距離を求める。

これはpart2はこうなるだろうな、というのが予想できた

day12

イラストロジック的なもの。

そろそろ探索の実装も一筋縄ではいかなくなってくる

day13

2次元grid上で鏡写しになっている境界を見つける。

簡単な方法を自力では思いつけなくて悔しい

day14

2次元grid上で丸い石を一方向に動かして詰めていく。

今年は2次元gridモノが多いな…。

day15

HashとHashMapの独自実装。

工夫のしどころが見つからなかった…

day16

光の反射と分裂シミュレーション。

また2次元grid… しかしこういうのはvisualizationが面白そう

day17

動き方に制約のある最短経路探索。

制約ひとつで色んな考え方が生まれて面白いなぁ

day18

命令の通りに線を引いて囲んだ面積を求める、というもの。

AoCではよく出てくるタイプのもの、かな? すごい苦労したが…

day19

4つの値に対して分岐していくworkflowに流し込んで結果を得る。

どんどん実装が大変になってきた…!

day20

状態を保持する回路を使い、通るpulseのシミュレーション

しばらく悩んで色々ためして一応どうにか解を出せたが… という感じ

day21

2次元grid迷路内で、偶数歩で辿り着き得る範囲は。

これはめっちゃ難しくて悩みまくった… 何度も試行錯誤して解は出せたが

day22

3次元空間でジェンガを積んでいく。ブロックを取り除くとどうなる?

かなり考え込んでようやくどうにか解けた、、という感じ

day23

2次元gridでの一筆書き(同じ点を二度と通らない)最長経路。

計算は大変だったけどどうにか

day24

3次元空間内で移動する座標たち…!

おそらく2023で一番の難問だったと思う、しかし解けるとスッキリする。。

day25

グラフを3辺切断して2つのグループに分ける。

最小カット問題、というのか?アルゴリズム知らなくてちょっと泥臭いやり方で解いた