JUNのブログ

JUNのブログ

活動記録や技術メモ

放送大学2021年2期が終わった

日記

初めに

2022年1月14日〜1月21日まで放送大学単位認定試験がありました。

今期は14科目を受講していましたが、42Tokyoやら就活やら車の免許合宿やらで結局あまりしっかり勉強できず、2022年に入ってから急いでやりました。正直もう少し受講科目数を減らせばよかったと思います。

結局自宅受験ということもあり、教科書を見ながらなんとか期限ギリギリに提出をしました。結果はまだ届いていないのでわからないですが、合格点(60点)を超えていると嬉しいです。

1度落ちても次の学期で再び単位認定試験を受けられますが、その次以降は再履修(1科目2単位 11000円)が必要なので単位を取っておきたいのです。

各科目の感想

受けた科目は以下の通りです。

初歩からの数学

中学〜高校までの基本的な数学を学べてよかったです。順列や組み合わせの説明がわかりやすかったです。三角関数の公式らへんも忘れていたので思い出せました。

演習初歩からの数学

「初歩からの数学」の演習です。

入門微分積分

難しかったです。高専時代に微分積分などはやっていましたが、知らない微積の問題がいくつも出てきてついていくのが大変でした。

演習微分積分

上記の演習です。練習問題に解説が付いているので教科書の章末問題を解くよりもわかりやすい気がします。

入門線型代数

線形代数は相変わらず計算が多かったです。個人的に線形代数はプログラミングと結びつけながら考えるのが好きなので「プログラミングのための線形代数」を読み直そうと思いました。

プログラミングのための線形代数

プログラミングのための線形代数

Amazon

自然科学はじめの一歩

天文学、生物、物理学、化学、数学 と自然科学の全分野をその分野の担当の先生から大まかな内容を紹介してもらう授業。実験や取材が多くて面白かった。

初歩からの物理

実験が多くて面白かった。ただ、授業動画では実験がメインで計算や導出などはあまり行わないので教科書を見る必要がありそれが大変でした。

初歩からの化学

難しすぎた。自分は高校化学を殆ど習ったことが無いので全然わかりませんでした。履修登録するまえにもっと調べたほうが良いですね。

耳から学ぶ英語

面白い話が多くてよかったです。基本的には会話の内容を聞いてそれを耳だけで聞き取るための解説とかが日本語で入る形でした。日本語と英語が交互に来るで自分の脳が混乱しました。ストーリーの解説は良いのですが、自分は英文法とかは英語で勉強したので日本語の英文法の単語がわからなくて文法解説はよくわかりませんでした。

グローバル化時代の日本国憲法

とても面白かったです。こういう現代社会みたいな授業は中学の時は全くおもしろくなかった記憶があるのですが、今聞くと憲法や法律の成り立ち、海外から受けた影響や与えた影響、そしてそれが現代に繋がっているという感覚が面白かったです。ある程度年齢を重ねてから歴史や現代社会などを勉強すると自分の経験と繋がるのが良いのかもしれませんね。

情報・メディアと法

ラジオ授業で法律の名前が沢山出てきて眠くなりました。日本の情報通信技術に関連する法律、例えば著作権法や意匠権、不正電磁的記録に関する罪や高度情報通信ネットワーク社会形成基本法などについて色々説明していました。個人的には Winny事件 や Coinhive事件、アラートループ事件 などの国家権力(警察)の情報通信技術に関する知識不足に起因する不当な身柄校則や取り調べ、逮捕などを知っているので法律が目指した理想と現実のギャップを感じました。

情報理論とデジタル表現

難しかったけど面白かったです。こういうガッツリ理論に寄った情報系の授業は受けたことがなかったので新鮮でした。前半の情報量やエントロピーなんかは全く知らなかったです。こんなんどこで使うねんとか思いながら情報量の講義とかを聞いてましたが中盤のネットワーク上でのデータ伝送でガッツリ出てきてスマンというお気持ちになりました。後半は画像や音声の圧縮と暗号化の話でした。画像や音声の圧縮は拡張子を知ってる程度の知識だったのでおおまかな圧縮手順などが知れて良かったです。個人的には実際にこれらの画像や音声圧縮を実装してみると面白そうだなと思いました。これらの圧縮アルゴリズムなどを考えた人は賢いなぁと思いました(小並感)。

計算の科学と手引き

前半は人間と数や計算の関わりや歴史について、中盤はPythonを用いた簡単なプログラミングとアルゴリズム、最後は論理などについて でした。個人的には知っている内容が多かったです。最後の論理のところは論理的思考というのをちゃんと定義した感じで面白かったです。

情報ネットワーク

TCP/IP について。基本的には TCP/IP とその周辺技術とかについてでした。既知の内容でしたが、うろ覚えだったので今回もう一度学習出来て良かったです。オンライン授業方式で音声付きスライドで講義を受ける形でしたが結構良かったです。

来期について

来期は授業を履修しないか、もしくは履修するとしても1、2科目だと思います。理由としては就活や42Tokyoでの学習など放送大学をやる余裕が恐らく無いからです。

また、現在は 自然と環境コース に属していますが、情報系の授業で面白そうなのが結構あるので 情報コース に変えようと思います。

とりあえず今期は初めての学期で多く授業を取りすぎてあまり楽しんで学習する余裕が無かったので来期以降は調子に乗ってあまり取りすぎないようにしていきたいですね。

HHKB Professional HYBRID Type-S を買った

日記

HHKB Professional HYBRID Type-S 英語配列／墨 を買いました。

HHKB Professional HYBRID Type-S 英語配列／墨

HHKB Professional HYBRID Type-S 英語配列／墨

  • HHKB
Amazon

1週間くらい使ったので感想的なものを書いておく。

キーボード歴

キーボード歴としては、

色んなノートパソコンのキーボード5年くらい → Thinkpadのキーボード3年くらい → HHKB Professional Type-S 英語配列 2年くらい → HHKB Professional HYBRID Type-S 英語配列

って感じです。

前は会社支給の HHKB Professional Type-S を2年くらい使ってました。ちょうど以下の記事を書いた後くらいから使い始めました。

jun-networks.hatenablog.com

で、そのキーボードを会社に返却したので自分用を買ったという感じです。

1週間使った感想

めっちゃ良いです。HHKBの打ち心地やキー配置が良いのは知っていましたが、相変わらず良いです。

HHKB Professional Type-S との違いですが、個人的には底面のラバーが改善され、入力した際に机に響かなくなっていて打ち心地と静音性が上がった様に思います。あと、今回色は墨を選んだのですが、カッコよくてとても良いです。

また、有線とBluetooth両方対応しているのも嬉しいですね。自分のメインマシンはLinuxでBluetoothがあまり安定しないイメージがあるので、有線で繋いでいますが、iPadなどで文字入力作業をする場合なんかにはBluetoothで繋げられるのでとても良いですね。

こんな感じでHHKB, iPad, iSHを使えば開発も出来なくは無さそうです。

iSH Shell

iSH Shell

  • Theodore Dubois
  • Developer Tools
  • Free
apps.apple.com

自分は前HHKBを使っていた時に買ったパームレストがあるのでそれを使っていますが、もし新規にHHKBを買うならパームレストを買った方が良いと思います。HHKB自体にある程度高さがあるのでパームレストが無いと手首が痛くなります。また、個人的にはHHKB公式のパームレストが高さがちょうど良く触り心地も良いのでおすすめです。

www.pfu.fujitsu.com

自分は昔Amazonで買った安い布製のパームレストを使っていましたが、汗とかが染み込んで凄く汚くなって最後らへんは手が痒くなったりしたので公式パームレストじゃないにしても木製のものをおすすめします。

逆にちょっとだけ不満点があるとするならば、HHKB Professional Type-S で使えていた音量上げ下げとかのキーの挙動が不安定になっていることですね。自分はDIPスイッチの設定をMacモードで使っており、これによりUbuntuであればMacと同じ様にFnキーと他のキーを組み合わせて音量調整やマイクのミュートなどが出来ていました。しかし、今回のモデルではこの動作が少し不安定なように思えます。具体的には音量調整は機能したりしなかったりといった感じで、マイクミュートに関してはなぜか別のキーが割り当てられています。前のモデルでは上手く動いていたのですが、今回のモデルは今の所このあたりの機能は安定しないです。もしかしたら何か別途Ubuntu側で設定する必要があるのかも知れません。まぁ、今の所さほど困ってはいないので良いのですが。

てな感じで新しく買ったHHKBが良いというお話でした。自分のように1日の大半をモニター前でキーボックスを叩いているような人ならばキーボードはケチらず自分に合った良いものを使うと良いと思います。

ではでは〜〜👋👋

AtCoder緑になりました

Algorithm Python

5ヶ月くらい前ですが, 2021年7月31日にAtCoder緑になったのでその振り返り記事を今更ながら書きます.

f:id:JUN_NETWORKS:20211231232320p:plain
レーティング変動

自分のスペック

  • 高校数学は多少やったけど大体忘れてる
  • 42Tokyoでプログラミング勉強してる
  • 数学オリンピックとかとは無縁の人間
  • 言語はPython

やったこと

  • 毎朝典型90の問題を1問解く
  • 新しく知ったアルゴリズムやデータ構造などは手元にメモしてコピペで使えるようにライブラリ化する
  • ABCにはなるべく毎回参加する

毎朝典型90の問題を1問解く

これは書いてある通りで, 毎朝典型90の問題を解きました. ★2から★4の問題までを一日1問ずつやりました. これのおかげでABCで頻出のアルゴリズムや考え方を知ることが出来ました.

自分は競プロの精進をめっちゃやってるような人でも無いので, そもそも手札(選択肢)が無いので, 手札を増やすという意味でも典型90は素晴らしい教材だと思います.

今回緑レートに達成できたのは典型90のおかげだと思います.

新しく知ったアルゴリズムやデータ構造などは手元にメモしてコピペで使えるようにライブラリ化する

これはかなり役に立っています.

UnionFindやセグメント木, BFS, DFS, ダイクストラ など新たに知ったアルゴリズムやデータ構造はある程度汎用的に使えるようにライブラリ化してローカルのマークダウンファイルにアルゴリズムの説明と共に書いています.

ABCにはなるべく毎回参加する

ABCに参加して解けた問題, 解けなかった問題を振り返ると, 「成長したな」と思うこともあれば, 「もっと頑張らねば」と思うこともあり, ちょっと無理してでも毎回出るのはモチベーション的にも大事だと思います.

使ったアルゴリズムやデータ構造

自分の手元にある 競プロメモ.md の目次をコピペします.

- 競プロで使えるコード, テクニック集
    - 計算量
        - Python の処理速度の目安
        - リスト
        - collections.deque
        - set
        - 辞書
    - 設定
        - 入力高速化
        - 再帰呼び出し上限
    - 注意すべき点
        - float('inf') の生成は整数リテラルとは違い生成に時間がかかる
    - プロファイラ
    - データ構造
        - デキュー
        - 辞書型
            - defaultdict
            - Counter
        - UnionFind
        - Priority Queue
            - 使い方
            - 最大値の取り出し
        - セグメント木 (RMQ)
            - 遅延評価セグメント木 (RUQ)
            - 遅延評価セグメント木 (RAQ)
    - グラフ
        - 用語
        - グラフの表しかた
            - 隣接リスト (Adjacency list)
            - 隣接行列 (Adjacency matrix)
        - 探索
            - 幅優先探索 (BFS)
                - 応用
                    - 01BFS
            - 深さ優先探索 (DFS)
        - 最短経路探索 (重み付きグラフ)
            - ダイクストラ法
                - 特徴
                - 実装
            - ワーシャルフロイド法
                - 特徴
                - 実装
            - ベルマンフォード法
                - 特徴
                - アルゴリズム
            - ジョンソン法
        - 強連結成分分解 (SCC)
        - 辺に対する周遊性
            - 用語
            - オイラーグラフの判定
            - オイラー回路の求め方
        - 巡回セールスマン問題 (TSP)
        - 木の直径
        - 最小全域木
            - クラスカルのアルゴリズム
            - プリムのアルゴリズム
        - 最近共通祖先(LCA)
        - 木の表現方法
            - 左子右兄弟表現
            - 二分木
    - ソート
        - 複数のキーでソート
        - 複数のキー(1 つはリバース)
        - 比較関数を基にソート
        - トポロジカルソート
    - 探索
        - 二分探索
            - ライブラリを使う場合
        - bit 全探索
    - 文字
        - 全アルファベットのリスト
    - 数学
        - 素数で割った余りを求めよ
            - 割り算の余り
        - 倍数の性質
        - 総和
        - 順列・組み合わせ
        - 繰り返し二乗法(二分累乗法) (a^b % c を高速に求める)
        - 累積和
        - いもす法 (多次元対応累積和的なやつ)
        - 2 つの数の最大公約数 (GCD)
        - 最小公倍数 (LCM)
        - 素数判定
        - 素数列挙
        - 素因数分解
        - 約数取得
        - 平方数の判定

こんなに無くても緑コーダーになれるかもしれないですが, ある程度典型的な使い方を知っておくだけでもコンテスト中の選択肢が増えるので良いと思います.

その他

言語はPythonを使っています. 最初はC++とかを使おうかとも思ったのですが, 自分が最も慣れている言語がPythonだったのでPythonを使っています. 勿論提出時はPyPy3です.

完走した感想

緑レート達成した時に記事書けばよかったなーとおもってたんですけど, 友人と喋っていたら, 「別に今から書いてもよくね?」と言われ, 確かに〜 って感じだったので書きました.

AtCoder始めて3年経っての緑レートってことでとても嬉しいです. (まぁ1年単位で空白の期間があるわけですが)

自分は競プロ200問解くとか,C問題埋めとかは特にせずに緑コーダーになったわけですが, これは完全に典型90のおかげだと思います.

余談ですが, この記事を2021年中に公開しようと思って書いていたらいつの間にか日付が変わって2022年になっていました. あけましておめでとうございます.

ではでは〜〜👋👋

2021年振り返り

日記

2021年も今日で終わりなので毎年恒例振り返り記事を書きます.

去年のやつ

jun-networks.hatenablog.com

大雑把な感想

今年1年は家に籠もってコード書いたり, アニメ見たり, ゲームしたり, って感じで本当に家から出ることが少なかったです. そのせいもあってか今年はなんだか体感時間が短かったような気がします. また, 生活リズムの乱れが酷く, 活動時間が深夜帯に寄っていたのも原因かもしれないです.

42Tokyoはオンラインで学習出来ていいのですが, 42Tokyoしかやってなくてなおかつオンラインだと家族以外との交流が殆ど無くて刺激が少ないですね. なんだかんだ言ってオフラインで交流するのが好きなのかも知れないです.

なんだか今年は何をやったか具体的には思いだしにくいような気がしてこの年末振り返り記事も書くのが乗り気じゃなかったのですが, 今年書かなかったら来年以降も書かなくなりそうだし, 自戒と反省の意味も込めて書いてみることにしました.

去年立てた目標について

去年の年末振り返り記事でこんなことを書いてました.

目標は高くすると年末に振り返った時に悲しくなるので2021年は今年の反省も踏まえ以下のように設定したいと思います.

  • 生産性の高い日々を送れるように努力する. 具体的には1ヶ月単位で目標を立てて, それを達成するような方針で生きる. (もしかしたら変わるかも)
  • Twitter, YouTube などを触らないようにし, メリハリのある生活をする.
  • 30日OS本, Nand2Tetris, アルゴリズムイントロダクションを完遂する.
  • 42Tokyoの退学システム(通称ブラックホール)に飲まれないようにする. 2021年は振り返った時に, 完遂したものが今年より多くなれるように頑張りたいと思います.

で結果としては

  • 生産性の高い日々を送れるように努力する. 具体的には1ヶ月単位で目標を立てて, それを達成するような方針で生きる. (もしかしたら変わるかも) : いまいち. 正直結構だらけていることが多かったような気がする.
  • Twitter, YouTube などを触らないようにし, メリハリのある生活をする.: メリハリは無い.
  • 30日OS本, Nand2Tetris, アルゴリズムイントロダクションを完遂する.: どの本も読み終わってない. なんなら30日OSは途中までやって放置中.
  • 42Tokyoの退学システム(通称ブラックホール)に飲まれないようにする.: これは大丈夫

って感じでズタボロですね...

というかこの年末振り返り記事, 書いてからはずっと放置してたので今見たら「こんな目標も立てたなぁ」って感じです. 目標を立てたならば定期的に見返しておくべきですね.

生産性はが高い日々を過ごすってやつは, 2021年前半は割と過ごせていた気がしますが, 後半はあまり良くなかった気がします. ずっと家にいてメリハリは無かったでしょう.

30日OS本を読むとかの, 積読消化の目標は30日OS本だけは途中まで良い感じに進んでたんですけど, 途中で2週間くらい免許合宿で空いたらいつの間にかやらなくなっていましたね. やらねば.

42Tokyoの退学システム(ブラックホール)に呑まれないようにするというのは達成出来ました. というか今年は42Tokyoの課題してるかだらけてるかって感じだったのでまぁこれは行けますね. あとこのブラックホールってシステムがかなり緩くなったので, それも大きいです. 今から入学する人とかは多分ブラックホールに怯える必要はあまりないと思います.

プログラミングの話

プログラミング関係の話でいうと, ちゃんと成長したんじゃないのかな? って気はしてます.

今年できるようになったこととしては

って感じでしょうか. まぁどれも42Tokyoで学んだことですね.

競プロ緑レート達成は記事書くべきでしたね. なんか記事書こうかなぁと思っていたら日が過ぎていて書くタイミングを逃しました.

他にも色々やったような気がするのですが, どうも思い出せないのでまぁこんなもんでしょう.

逆に今年足りなかったなぁというところに関しては

  • サービスを作るなどと言った技術を使って何かを作る経験が不足してる.
  • 42Tokyoの課題以外だとイマイチぱっとしない.

って感じですかね.

とは言ってもなんだか多少はやっていて, そんで多少は記事書いてるんで, そっち見ると意外と何かしらやっていたりもする.(HackDayとかにも出たしね)

jun-networks.hatenablog.com

目標に関しては, 毎年目標を立てるんですけど, 目標があると目標と現実とのギャップでなんだか辛くなるタイプっぽいので2022年はあまり目標立てずに気ままにやっていきたいですね.

来年どうすんの

来年は就活などもしつつ気ままにやりたいことをやりたいと思います.

目標とかは立てないです. やりたいことをやるのが良い気がします.

どうも自分は目標を書くと書いたことで満足しちゃうような気がするので目標は立てないし, 書かないです.

今年は記事の数が少なかったので, もっと軽率に書いた方が良かった気がします. AtCoder緑レートとかも軽率に適当でも良いからその時に勢いで記事を書いておくべきでしたね. そうすれば何をしたかわかりやすかったかも?

追記: 記事書きました.

jun-networks.hatenablog.com

そんで, 振り返り記事は月一で書いたほうが良いのかも知れないです. 文量は少なくていいから記事を書いて, その過程で今月を振り返るというのが大切な気がします. 書くぞー!

総括

今年も元気に生きれて偉い!

完走した感想

ノリと勢いで書いた歴代一適当な年末振り返り記事になってしもうた.

書く気が無いという気持ちがこの記事の適当さに現れてしまってるな.

ブログ記事はちゃんと書かなきゃーって思うと書き始めるのが億劫になってしまうから, 適当でいいかーくらいで書くほうがいいな. 実際緑レートの記事も「ちゃんと書かなきゃ」とか「書いた後にレート落ちたらださいなぁ」とかくっっっっそどうでもいいことを考えて書かなかった気がするし, そんなことうだうだ考えるよりかはノリと勢いでガーっと書いてしまったほうがいいじゃろな.

まぁ言うても個人ブログなんだし, この"完走した感想"のコーナーみたいに敬語とか書き言葉とか全部捨てていつものTwitterのノリで書いてしまう方が書いてて気持ちが良いかもしれんな. (読んでる方は読みづらくてしゃーないかもしれんけども)

てなわけで来年も頑張って良い感じに生きるんでよろしく〜

ではでは〜〜👋👋

Ubuntuマシンから WSL2 にデータを移行する

Linux

自作ゲーミングデスクトップPCを組んだので, そっちでも開発できるように開発環境を整えます.

やりたいこととしては以下のとおりです.

  • WSL2で開発したい.
  • 既存のUbuntuを搭載したノートパソコンに入っている作業中のプロジェクトとかのデータをWSL上のファイルシステムにコピーしたい.

OSは本当はWindows11が良かったのですが, まだ自分にはWindows11のアップデートの案内が来ていないのでとりあえずWindows10でやります.

WSL2でUbuntuを動かす

これは簡単です. 以下のマイクロソフトが出してる記事を見ながらやればおk.

docs.microsoft.com

一応Tipsとしては

# copy to clip clipboard
if hash clip.exe 2> /dev/null
then
        alias pbcopy='clip.exe'
else
        alias pbocpy='xsel --clipboard --input'
fi

これは dotfiles みたいなリポジトリ作って, 各OS共通の .zshrc を作ってる人向けですね. WSL2上でしか使わないなら特に必要ないです.

ちなみにこれだけだとVimのヤンクとかうまくWindows側のクリップボードにコピー出来ないのですが, そのあたりは以下のIssueのコメントとか見ると良いかもです.

github.com

既存のUbuntuマシンからファイルをWSLにコピーする.

こっちが今日の本題. 最初はext4(Linuxのファイルシステム)の外付けHDDをNTFS(Windowsのファイルシステム)に変換するソフトとか使おうかと思っていたが, でもそれだとWSLからのアクセスはどうすれば...とか思っていたが, 同じLANにつないであるマシンならUSBとか経由せずネットワーク上でコピーすればよくね? ってことに気づいた.

今回は rsync というコマンドを使って行う.

以下やり方を書きますがここでは以下のように想定して文章を書いてるので注意して読んでください.

  • ノートパソコン: 元々使っていたUbuntuマシンのこと
  • WSL2: 新しいWindowsパソコンのWSL2のこと

Ubuntu on ノートパソコン の設定

WSL2ではネットワークがWindowsのものと完全に分けられていて, 外部からWSL2にアクセスするのは難しいので今回はWSL2から外部のコンピュータ(Ubuntu on ノートパソコン)にアクセスする形にします.

なので, ノートパソコン側ではSSH接続できるようにSSHサーバーの起動と, 22番ポートを許可します.

$ sudo systemctl start ssh  # SSH起動
$ sufo ufw allow  from <Powershellなどで確認したIPアドレス> to any port 22  # 22番ポートへのアクセスを許可

これでノートパソコン側はWindowsマシンからの22番ポートの接続を許可するようになりました. (<Powershellなどで確認したIPアドレス> は ipconfig と Powershell に打つと確認できます)

WSL2 の設定

設定というか, こっちはやること簡単で, rsync 使ってノートパソコン側からWSL2にコピーしてくるだけです. 以下のコマンドをWSL2内で実行します.

rsync -avzhr <ノートパソコン側のユーザー名>@<ノートパソコンのIPアドレス>:<ノートパソコン側のコピーしたいディレクトリやファイル> <WSL2のどこにコピーしてほしいか>

各オプションは以下のような意味です.

  • a: ファイルを再帰的にコピーできる&ファイルのパーミッションやタイムスタンプなどを維持する.
  • v: 進捗状況の可視化
  • z: ファイル圧縮して転送
  • h: 人間が読める形で進捗表示する
  • r: 再帰的にコピーする.

例: LAN内のノートパソコン(IP 192.168.50.94)のwork_spaceディレクトリをWSL2にコピーする場合は

rsync -avzhr jun@192.168.50.94:/home/jun/Desktop/work_space ~/

をWSL2で実行すれば良い. そしたら WSL2 内に ~/work_space のような形でコピーされる.

後片付け

ノートパソコン側のポート開きっぱなしになっており, これはよろしくないのでちゃんと使い終わったら閉じましょう.

$ sudo ufw status numbered
Status: active

     To                         Action      From
     --                         ------      ----
[ 1] 22                         ALLOW IN    192.168.50.232            
$ sudo ufw delete 1
Deleting:
 allow from 192.168.50.232 to any port 22
Proceed with operation (y|n)? y
Rule deleted

感想

調べてもいい感じの情報出てこなかったしメモ代わりに書いた.

久しぶりにWindows使ったが, 最近のWindowsは普通に開発できそうでいい感じ. VM使って環境構築してもいいけど, WSL2のほうが軽いし, 問題なければこれでやっていきたいね.

あとは, 自分のdotfilesが整備されてなさすぎて流石にきちんと綺麗にしたい.

github.com

では今日はこのへんで. ではでは～👋👋

おまけ

Powerline フォントのインストール

stackoverflow.com

ダイクストラ法試してみた

Algorithm Python

最近早水先生の講義を見ているのですが, そこでダイクストラ法の説明があり, 実装したくなったので実装した.

www.youtube.com

import heapq

INF = float("inf")

# 各駅間の道を (行き先, 重み) という要素の隣接リストの形で保持する.
graph = [
    [(1, 16), (2, 8), (3, 15)],
    [(0, 16), (2, 13), (4, 27), (6, 78)],
    [(0, 8), (1, 13), (3, 21), (4, 10), (5, 17)],
    [(0, 15), (2, 21), (5, 33)],
    [(2, 10), (1, 27), (6, 15)],
    [(2, 17), (3, 33), (6, 52)],
    [(1, 78), (4, 15), (5, 52)],
]
# 英語バージョン
"""
stations = [
    "Tokyo",
    "Shibuya",
    "Shinagawa",
    "Sinjuku",
    "Shinyokohama",
    "Yokohama",
    "Odawara",
]
"""
# 日本語バージョン
stations = [
    "東京",
    "渋谷",
    "品川",
    "新宿",
    "新横浜",
    "横浜",
    "小田原",
]


def dijkstra(s, n):  # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)]  # (distance, node)
    heapq.heapify(hq)
    dist[s] = 0
    prevs = [-1] * n  # 前の駅(経路復元用)
    seen = [False] * n  # ノードが確定済みかどうか
    while hq:
        cost, v = heapq.heappop(hq)  # ノードをpopする
        seen[v] = True
        for to, cost in graph[v]:  # ノードvに隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                print(f"{stations[to]}のコストを更新! {dist[to]} -> {dist[v]+cost}")
                dist[to] = dist[v] + cost
                prevs[to] = v
                heapq.heappush(hq, (dist[to], to))
    return dist, prevs


# (出発, 到着)
start, end = input().split()

if start not in set(stations) or end not in set(stations):
    print("指定された駅は無いよ!")
    exit(1)

dist, prevs = dijkstra(stations.index(start), len(stations))
print(f"{start}から{end}の所要時間は {dist[stations.index(end)]}")

# 経路復元
def restore_path(prevs, v):
    if prevs[v] != -1:
        restore_path(prevs, prevs[v])
    print(f"{stations[v]}", end="->" if v != stations.index(end) else "\n")

restore_path(prevs, stations.index(end))

実行すると

$ python3 dijkstra.py
東京 小田原
渋谷のコストを更新! inf -> 16
品川のコストを更新! inf -> 8
新宿のコストを更新! inf -> 15
新横浜のコストを更新! inf -> 18
横浜のコストを更新! inf -> 25
小田原のコストを更新! inf -> 94
小田原のコストを更新! 94 -> 33
東京から小田原の所要時間は 33
東京->品川->新横浜->小田原

とこんな感じで講義動画と同じような経路更新が出来ている.

f:id:JUN_NETWORKS:20210801130052p:plain
「離散数学入門#5: 最短経路問題：ダイクストラ法とワーシャル–フロイド法」より

他の経路も試してみる

$ python3 dijkstra.py
渋谷 新宿
東京のコストを更新! inf -> 16
品川のコストを更新! inf -> 13
新横浜のコストを更新! inf -> 27
小田原のコストを更新! inf -> 78
新宿のコストを更新! inf -> 34
新横浜のコストを更新! 27 -> 23
横浜のコストを更新! inf -> 30
新宿のコストを更新! 34 -> 31
小田原のコストを更新! 78 -> 38
渋谷から新宿の所要時間は 31
渋谷->東京->新宿

$ python3 dijkstra.py
渋谷 横浜
東京のコストを更新! inf -> 16
品川のコストを更新! inf -> 13
新横浜のコストを更新! inf -> 27
小田原のコストを更新! inf -> 78
新宿のコストを更新! inf -> 34
新横浜のコストを更新! 27 -> 23
横浜のコストを更新! inf -> 30
新宿のコストを更新! 34 -> 31
小田原のコストを更新! 78 -> 38
渋谷から横浜の所要時間は 30
渋谷->品川->横浜

$ python3 dijkstra.py
小田原 東京
渋谷のコストを更新! inf -> 78
新横浜のコストを更新! inf -> 15
横浜のコストを更新! inf -> 52
品川のコストを更新! inf -> 25
渋谷のコストを更新! 78 -> 42
東京のコストを更新! inf -> 33
渋谷のコストを更新! 42 -> 38
新宿のコストを更新! inf -> 46
横浜のコストを更新! 52 -> 42
小田原から東京の所要時間は 33
小田原->新横浜->品川->東京

正しく求められているっぽい.

感想

早水先生の講義わかり易すぎてビビる.

乗り換えアプリとかも基本的にはこういう感じで作られているのかなぁと思った.

最小値を取り出すところはPriotiryQueueを使うと最小値を計算時間(O(log N))で取得出来て良い感じ.

参考にしたサイト

Linux環境でも放送大学の授業を受けたい!

備忘録

放送大学の授業はテレビ,ラジオ,ブラウザで視聴することが可能なのですが, このブラウザ視聴の対応OSにLinuxが入っていません.

www.ouj.ac.jp

Linux(Ubuntu 20.04) の Chrome から放送大学の授業科目動画のサンプル(授業の第一回目)を視聴しようとするとエラーメッセージが表示されてページにアクセス出来ません.

f:id:JUN_NETWORKS:20210722014401p:plain
Ubuntu20.04のGoogle Chromeから視聴ページにアクセスするとエラーが発生する

www.ouj.ac.jp

解決方法

以下のページに書いてある通り推奨環境はPCの場合はWindowsかMacです.

www.ouj.ac.jp

じゃあどうやって放送大学側はLinuxのChromeからのリクエストを識別しているかと考えれば, まぁ普通はHTTPの User-Agent だろうなという予想はつくわけです. なのでChrome側のUser-AgentをWindowsのChromeの文字列に書き換えてメッセージを送ってみます.

f:id:JUN_NETWORKS:20210722014759p:plain
`User-Agent` をWindowsのChromeに書き換えることで視聴できる

User-Agentの書き換え方はChrome公式が紹介しているのでそれを参考にしました.

developer.chrome.com

で, 毎回毎回こんな感じでChromeのデベロッパーツールを開いてUser-Agentを書き換えるのはめんどいのでUser-Agentをドメインごとに切り替えるChrome拡張を入れます.

chrome.google.com

User-Agent Switcher and Manager のオプションを開いて, 以下の内容を貼り付ければ放送大学ドメインではWindowsのChromeのUser-Agentでリクエストを送信するようになります.

{
  "ouj.ac.jp": "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.114 Safari/537.36"
}

これで放送大学の授業をLinux環境のChromeから視聴出来るようになりました!

感想

Linux環境のChromeから放送大学の授業を視聴できなくて, 調べても情報が無かったので備忘録として書いておきました.

放送大学さん, Linux環境からも普通に授業が視聴できるようにしてくれると嬉しいです.