listen to my digital heartbeat.

　競技プログラミング系の問題を解いていて、時々「優先度付きキュー」みたいなものが必要になる場合がある。

　プログラミング言語によっては実装済みコードがライブラリにあるのだろうが、僕が普段使っているRubyにはないっぽい（いや、ないワケないとは思うのだが…）。そこで、ヒープを使って自分で書いてみた。

　…と言うのはウソで、「ヒープ」そのものをパッと書けなかったのだが…（涙）。

def upheap value
　@heap << value
　node, parent = @heap.length - 1, (@heap.length - 1) / 2
　while parent != 0
　　break if @heap[parent] <= @heap[node]
　　@heap[parent], @heap[node] = @heap[node], @heap[parent]
　　node, parent = parent, parent / 2
　end
end

def downheap
　value = @heap[1]
　@heap[1] = @heap.last
　@heap.pop
　node = 1
　while true
　　child, val = nil, nil
　　child, val = node * 2, @heap[node * 2] if @heap[node * 2]
　　child, val = node * 2 + 1, @heap[node * 2 + 1] if @heap[node * 2 + 1] && val > @heap[node * 2 + 1]
　　break if val.nil? || @heap[node] <= val
　　@heap[child], @heap[node] = @heap[node], val
　　node = child
　end
　return value
end

@heap = [nil]
[5, 3, 7, 9, 0, 2].each{|v| upheap v}
arr = []
while @heap != [nil]
　arr << downheap
end
p arr
#=> [0, 2, 3, 5, 7, 9]

　こんな感じかなぁ…。もうちょっとスッキリ書きたいものだが…。

　ここでは、値を「昇順」で取り出しているが、赤字にした3か所の不等号を逆向きにすれば「降順」で取り出すことが出来る。


※　html上でインデントさせるために全角スペースを入力しています。そのため、このままコピーして実行してもエラーが出ると思います

　自宅のメインPCのOSはXubuntu。

　そのPC上で画像ファイルをGIMPを使って加工・編集していた際、ファイルを右クリックしたときに誤って「壁紙に設定」を選択してしまった（デスクトップの壁紙が即座に変更される）。すぐ元に戻そうとしたら、元のファイルの存在するフォルダ名がわからない！

　確か、インストール時のデフォルト画像のままだったハズ…。いや、その画像が含まれていたフォルダの中にあった画像を一通り見て、気に入ったものに変更したんだったか…。Googleってみたところ、そのフォルダはどうやら「/usr/share/xfce4/backdrops」だったようだ。何とか元に戻せた（汗）。

　『高校生からはじめるプログラミング』
　吉村　総一郎（著）
　2017年
　KADOKAWA
　★★☆☆☆

　普段PCを触っていないスマホ世代の中高生を対象としたプログラミング入門。数回で終わるクライエントサイドWEBプログラミング体験教室。全ページフルカラー（笑）。開発・実行環境としては、無料でダウンロード＆インストールすることの出来るMicrosoft Visual Studio Code（エディタ）と、WEBブラウザのGoogle Chromeの「デベロッパーツール」機能を使う。Windows、Mac対応。

　「やってみよう！」的な内容。4章構成で、HTML（第1章約60ページ）、JavaScript（第2章約70ページ）、CSS（第3章約20ページ）の仕組みを軽く紹介した後、「診断アプリ」を作成（第4章約60ページ）して終了。厚手の紙を使っているが、ページ数自体は220ページ程度と（プログラミング関連書籍としてはかなり）少なめ。文字も大きく行間も広い（笑）ため、スイスイ読み進んでいける。「ジックリ取り組む」というタイプの本ではなく、本書全体が「新学期1回目の授業」のような内容なので、既に「プログラミングを覚えたい！」と鼻息荒くなっている意欲的な学生さんには当然もの足りないだろう。その場合、本書を数日で終わらせて（初学者の独習でも1日1章進むことは可能だろうと思う）、もっと本格的な「入門書」にサッサと進むが吉。

　表紙に「N高校のプログラミング教育メソッドを大公開！」とあるが、通常の学校教科書のようなお堅い本ではない。何はともあれ、まずは生徒にプログラミングを体験させる、ということに主眼を置いたオリエンテーション的な内容で、角川ドワンゴ学園の運営する通信制高等学校「N高等学校」でも、本書を「教科書」として用いているワケではないと思う（どうやら、3か月間の課外授業の教材の冒頭部を掻い摘んで書籍化したものが本書のようだ。「N予備校」の有料会員（月額1000円（税抜））になれば、残りの教材を見ることが出来るだけでなく、ネット配信される生放送授業を視聴したり、WEB上のフォーラムで講師や他の受講生に質問したり出来るようだ）。私自身は習う立場ではなく教える立場で本書を手に取ってみたのだが、（第4章以外は）正直ほとんど参考にならなかった。

　本書の目的は、読者にプログラミングスキルを身に付けさせることそのものにではなく、「プログラミングって誰にでも出来るものなんだ！」「アプリやサービスの裏側にある仕組みって意外と単純なものなんだ！」と実感させることにある。その点は割り切っているようで、網羅的な内容ではないことはもちろんのこと、他の入門書なら説明するようなことすら説明を省き（笑）、かなり端折り気味。「薄い内容」と言わざるを得ないが（正直言って、ここまで内容の薄いプログラミング入門は見たことがない（笑））、本書の内容は、受講生に対してその場で情報を補う講師の存在を仮定するなど、「N高等学校」「N予備校」の特長の1つである「ネットを介した双方向授業」を前提として構成されている、ということなのかもしれない（そういう意味では、「独習書」というより、やはり「授業で用いる教科書」なのか）。

　ちなみに、表紙や裏表紙、各章の扉ページに人気コンテンツの『ソードアート・オンライン』のイラストが用いられているが、本書の内容とは全くの無関係（笑）。こういった見目麗しいCGを駆使したゲームを作る、という内容ではもちろんないし、RPG風に学習を進めていく、という趣旨の本でもないので、あまり表紙の印象に惑わされない方がいいと思う。単に、まずは表紙イラストで中高生のハートをつかむ、という作戦なのだろう（僕のようなオジサンのハートも射抜かれてしまいましたが（笑））。

　本文215ページ程度。



→　Kota's Book Review

　『入門者のPython』
　立山　秀利（著）
　2018年
　講談社
　★★★★☆

　「講談社ブルーバックス」の「B-2072」。全くのプログラミング未経験者を対象としたPythonプログラミング入門。「Python入門」というより「プログラミング入門」という印象（最近は純粋な「プログラミング入門」が減ってしまったように思うが、初心者には絶対にそういう本が必要なのだ！）。サブタイトルは「プログラムを作りながら基本を学ぶ」。Pythonのバージョンは3.6。強いて言えば、Windowsユーザー向け。

　全12章構成。Pythonの文法事項を1つずつ網羅的に紹介していくタイプの本ではなく、3つの作例を作りながら、その都度必要となる機能を学ばせていくスタイル。最初の3章はPython実行環境のインストールとウォーミングアップを行う準備編、1つ目の作例を作り終える10章までが入門編、WEBスクレイピングの初歩をかじり（11章）、数値データの統計処理（要約統計量の算出と散布図の表示）を行う（12章）最後の2章が発展編か。プログラミング未経験者でも何とか2〜3日で終えられる内容。

　400ページ弱と新書としてはかなりボリュームがあるが、見開き2ページでB5判の本の1ページに相当するような感じ、文章も繰り返しが多い（「同じことを少なくとも3回は書いている」と感じるホド（笑））ため、思いの外スイスイ読み進んでいける（200ページ弱のプログラミング入門と考えれば、むしろ薄い部類ではないか）。対象読者は全くのプログラミング未経験者で（ただし、PCの操作そのものにはある程度習熟している必要がある）、中高生や年配の読者を想定しているのか、開発・実行環境のAnacondaのインストールから手取り足取り懇切丁寧、「ただ1人の脱落者も出さない！」という気迫が伝わってくる冗長さ（笑）。Pythonはもちろん他のプログラミング言語経験者には適さないだろうと思う（他の入門書の途中で挫折してしまった、という人なんかにはいいかもしれないが…）。

　面白いもので、プログラミング関連書籍の世界には「入門書専門ライター」のような人が何人もいるのだが、この著者の特長は「1冊の本を通して読者に何を教え伝えるか」に関して「カリキュラム」がシッカリしている点だと思う。同じ「講談社ブルーバックス」の『入門者のExcel VBA』（2012年）、『入門者のJavaScript』（2014年）も凄く良かった。どちらも全くのプログラミング未経験者を対象にしており、到達目標は決して高くはないのだが、読者に直接語りかけるような口調で、言葉を尽くして確実にゴールまで導いてくれる。プログラミングの初心者が絶対に押さえなければいけないポイントは何か、それらを短時間で学習するのに最適な題材は何か、実によく考えられていると思う（目次を見ただけで、他のPython入門とはかなり異なる内容であることがわかる）。著者は個人を対象とした（Excel VBA等の）少人数のセミナーを行っているが、そういったセミナーの様子を紙上に再現したようなものなのではないか。マンツーマンで個人指導を受けているかのような雰囲気を味わえると思う。

　そういう意味では、本書はPython入門講座の講師にも役立つ内容だろう。プログラミング言語の文法項目を1つずつ解説していくのは講師にとっては簡単だろうが、受講者としては「プログラミングの楽しさ・面白さ」を実感しづらい。しかし、全くの未経験者が週末の2日間＋αで、「これなら自分にも何か作れそうだ！」という気になれるような教材を用意するのは難しい。それを用意している、というところがこの著者の抜きんでている点なのだ。

　もっとも、Pythonの文法項目や機能、主要ライブラリ、等を網羅的に取り上げていない以上、本書では全く触れられていないトピックも多い。本書で「入門」「初体験」を済ませた後に、通常の「Python入門」に進むのが良いだろうと思う。はじめは「新書で1400円は高いな…」と思っていたのだが、200ページ程度の薄手のPythonチュートリアル系入門書と考えればお買い得かもしれない。

　尚、本書では、Pythonの開発・実行環境として「Anaconda」をインストールし、（Anacondaに含まれている）統合開発環境の「Spyder」を用いている。また、AnacondaをインストールするOSとしてはWindows 8.1、Windows 10を例に挙げている。AnacondaはmacOSやLinuxでも利用可能、また、そもそもAnaconda以外の開発・実行環境（PyCharmやVisual Studio Code、あるいはPython 3そのもの）を用いても本書の内容を学習することは可能だと思うが、本書中に示されている画面画像と全く同じでないとダメ！という人は注意が必要かと思う。

　本書のサポートページから、作例で用いるファイル一式、付録PDF（実質5ページ）、等をダウンロードすることができる。また、補足説明、正誤表、等が掲載されている。

　本文380ページ程度（他に、索引として4ページ程度）。



→　Kota's Book Review

　ここのところ問題なく使えていた（と思っていた）我がXubuntuマシン、WEBブラウズ中に突然のクラッシュ！　リセットボタンを押してみても、電源を入れ直してみても、OSが起動しなくなってしまった（いつもと違う画面になり、OS起動を選んでも途中で止まってしまう）。

　メモリチェックをしてみたが、メモリに異常はないようだ。また、マシン筐体内部の埃を掃除機で吸い取ってみたがダメ。

　途中で止まってしまうOS起動画面の（英語の）エラーメッセージを読んでみると、OSをインストールしているメインのHDDのファイルシステムに不整合があるので手動でfsckせよ、と書いてある。嫌な予感がしたが、古いLinuxムック等を参考に修復を試みる。

　現在このマシンには2台のHDDが接続されており、OSがインストールされている1台目がsda（ファイルシステムはEXT4で、その中の唯一のパーティションがsda1）、2台目のHDDがsdb（ファイルシステムはNTFSで2つのパーティションに分かれており、それぞれsdb1とsdb2）と認識されているようだ。

　取り敢えず、

fsck /dev/sda1

とやってみると、ファイルシステムのチェックと修復が始まった。修復の必要のある箇所が現れる度に確認を求められキーボードの「y」キーを押さなければならなかったが、無事修復できたようだ。

　ちなみに、

fsck -y /dev/sda1

とやれば、確認を省略して全て「y」キーを押したことになるようだ。

　また、NTFS形式のファイルシステムが壊れた場合は、「fsck」ではなく「ntfsf」コマンドを使うようだ。

　自宅のデスクトップPCのHDDを交換しXubuntuをインストールして使い始めたのは、元々のHDDがブッ壊れてWindows Vistaが起動しなくなったから。このHDDは捨てるしかないと思っていたんだけど、奇跡的に（Xubuntuから）アクセス出来て、メールデータやダウンロードしていたファイルなんかを救い出すことが出来たから、完全に壊れているワケではないのかもしれない。ただ、それは本当に「奇跡」で、基本的には廃棄する方向。

　僕のPCのHDD内にハッカーが狙うような機密データや重要な個人情報なんて何もないから、悪意のある人物に中のデータを盗み出されるようなことを心配しても意味ないんだけど、一応こういう場合のHDDの処理の仕方を知っておきたい。

　調べてみると、HDDを廃棄する場合だけでなく譲渡したりする場合にも使えるプログラムがあるようだ。HDDの全領域にランダムな値を書き込んで、ハッカーでも元のデータの読み書きを出来なくする、というようなツール（ハッカーはHDDに残った残留磁気から元の値を推測したりするらしいんだけど、ランダムな値を何度も上書きして、それすら不可能にする、というような趣旨）。「HDDを壊す（読み書き出来なくする）」のではなく、「元の値を読み書き出来なくする」ためのツール。

　「端末」を開いて、

$ sudo shred -n 1 -v /dev/sdb

（「sdb」の部分は環境により異なるので注意。うちのPCだと2台目のHDDなのでこんな感じ。ここは慎重に。）

　コマンドラインのプログラムで、Xubuntu 18.04 LTSには最初から入っていた。

　ところが…、開始から8時間、延々と「書き込みエラー」の表示が出続けるので、「Ctrl+C」を押して中断。やっぱ壊れてるわ、このHDD。これやる必要なかったかな…。

　自宅のデスクトップPC（旧メインマシン）にXubuntu 18.04 LTSをインストールして1週間、結局FirefoxでWebブラウズしかしていない…。それじゃマズいだろ！ということで、DVDでも視るか！と。DVDをドライブにセットすると自動で（DVDが）マウントされ、「Parole メディアプレーヤー」が立ち上がって、再生が始ま…らない！

　コピー防止のプロテクト機能なのか、著作権関係のライセンスの問題なのか…。googleってみると、どうやらコーデックとか何とか追加でインストールしないといけないらしい。ただ、インストールは簡単そう…。お金がかかるワケでもないし…。

　「端末」を開いて、

$ sudo apt-get install ubuntu-restricted-extras
$ sudo apt install libdvd-pkg
$ sudo dpkg-reconfigure libdvd-pkg

（OSはXubuntuだが、"xubuntu-restricted-extras"ではないことに注意。）

　相変わらず意味のわからない呪文をただ入力しただけだけど…。須藤3連発でOSの再起動も必要なく、DVDをドライブにセットしたら今度は無事に再生が始まりました…。

　しかし、デフォルトではDVD視聴もできないんじゃ、ユーザーフレンドリーで有名なUbuntuでもLinuxはやっぱり敷居高いねぇ…。まぁ、OSSとしての建前があるからねぇ…。

　自宅のデスクトップPC、2008年3月に購入したショップブランドのWindows Vistaマシンですが、昨年からHDDの不具合が発生していました。これまで騙し騙し使ってきたんですが、7月末についにWindowsが起動しなくなってしまいました。

　で、とにかく行動力・決定力のない当方、今後の自宅のPC環境をどうするか決めあぐねていたんですが…、取り敢えずHDDを交換し、Linuxをインストールしてみることにしました。

　新しいHDDは何故か既にあるんですよね（笑）。2年前のゴールデンウィークだったか、普段行かないPCショップをブラブラ覗いていたら、2TBの内蔵型HDDがセールで安売りされていて、（僕には珍しく）衝動的に買ってしまいました。一応、過去にPC自作の経験があったので。で、その後放置（笑）。

　Linuxに関しては、常用したことはないんだけど、20世紀末の「Linuxブーム」以来、Linuxに関する雑誌やムックなんかはときどき見ていて、仕事でバリバリ使いたい！というのではなく、メールの送受信やWEB閲覧に使うだけなら、何の問題もなくすぐ使えるだろうということはわかっていました（でも、あれかな、無線LAN、スキャナ、プリンタ、等々、周辺機器の使用でハマるときはハマるかな。今ではトラブルはだいぶ起きなくなってきてるんだろうけど）。

　今回は（いつもボロクソに言っている）雑誌「日経Linux（2018年9月号）」の付録DVD-ROMに収められていた「Xubuntu 18.04 LTS」をインストール。情報量は圧倒的に「Ubuntu」の方が多いんだけど、Ubuntuは10年前のPCには荷が重過ぎる（うちのマシンのCPUはAMD Athlon64 X2 4200+（64ビットのデュアルコア）、メモリ2GBで、DVDからライブ起動すらできず）。インストールするならLubuntuかな？と思っていたんだけど、XubuntuをDVDからライブ起動してみると何とか動きそうだったので。ダメなら、改めてLubuntuをインストールする。

　5年ほど前に「日経Linux」を毎月買っていたことがあって（ほとんど読んでなかったけど（笑））、その頃は「WindowsのインストールされているHDDに後から追加でLinuxをインストールする際にHDDのパーティション分割を行い、デュアルブート環境を構築する」というのがメジャーだったのだけど、最近はその方法は推奨されていないようですね。

　で、インストールはあっけなく終了。日本語入力機能も最初から使えました。日本語入力機能ですら「後から追加でインストール」とか面倒臭くて嫌なんで良かったです。これまでWindows VistaやWindows 7をメインPCとして使っていた人間としては、Windows 10なんかよりもユーザーインターフェースに関して違和感ないです。

　ただ、あれですね、Linux系はプログラム開発環境が最初から充実している、というイメージを持っていたんだけど、プログラミング言語系は何もインストールされていないみたい。CもJavaもRubyもPythonも。まぁ、おいおい。

　で、まだ本格的なことは何もしていなくて、WEB閲覧くらいしかしていないんだけど、Firefox用（？）のフラッシュプレーヤーのインストールについて、将来の自分に向けてメモ。

　Xubuntuのメニューの「設定」から「ソフトウェアとアップデート」を起動、「他のソフトウェア」タブの「Canonicalパートナー」にチェックを入れる。

　で、「端末」を開いて、

$ sudo apt-get install adobe-flashplugin

を実行。WEB上の情報を見ると、

$ sudo apt install adobe-flashplugin

や、

$ sudo apt-get install flashplugin-installer

でもいいみたいですが（試してません）。

　ついでに（しなくてもいいのかもしれないけれど）、

$ sudo apt autoremove

で、フラッシュプレーヤーのインストール後に不要になったパッケージ（？）を削除。「sudo」ってのが「須藤」みたいで、如何にもLinux/UNIXだよな〜！って感じですよね！

　本当はこういうのも面倒臭いとも言えるけど、僕が最初にコンピューターにハマったのはMS-DOS時代なんで、CUIに対する抵抗はほとんどないんですよね。むしろ、楽しい（笑）。次は、Thunderbirdの設定だな〜！

　『基礎から学ぶ データ構造とアルゴリズム』
　穴田　有一・林　雄二（著）
　2009年
　共立出版
　★★☆☆☆

　情報系の大学や高専、専門学校での講義の教科書として使われることを念頭に置いた、典型的な「アルゴリズムとデータ構造」入門。理工系の教科書の文章は（僕のような文系人間から見ると）驚くほど素っ気ないもので、本書の記述も「アッサリ」した印象だが、言葉不足ではないので（文系読者の）独学にも使えると思う。140ページ程度の薄い本。

　全4章構成。「計算量（O記法）」「データ構造（配列・リスト、スタック・キュー、木構造）」「探索（2分探索木、2分探索法、ハッシュ法）」「整列（交換ソート・選択ソート・挿入ソート、シェルソート、ヒープソート、クイックソート、マージソート）」といった最小限の内容。ところどころに練習問題が設けられており、巻末に解答例が掲載されている。

　あっさりテイスト。意欲のある学生さんなら、「時間をかけてジックリ取り組む」というより、「土日の2日間でこの本に書いてある内容を全てマスターする！」くらいの意気込みでバリバリ読み進めていった方がいいと思う。類書と読み比べて基礎固めをするのも吉（特に第4章「整列」の解説はあまり良くないので、他の本と併読した方が良いと思う）。ただし、流し読みではなく、ちゃんと理解しながら読むこと！　掲載されているサンプルコード（JavaとC言語）やその解説が間違っている箇所があり（また、間違いではないにせよ不要な処理を行っていたり、適切とは思えない例もある）、間違いを全て発見し訂正するツモリで読むとシッカリ理解できると思う（笑）。僕が読んだのは「初版2刷」だが、些細な誤植は結構多い（特に「数値」に誤りが多い。出版社の本書のサポートページにも正誤表は掲載されていない（2017年05月現在））。何と問題の解答例にも誤りがある！　また、全てのアルゴリズムにサンプルコードが示されているワケではない。

　如何にも「基礎から学ぶデータ構造とアルゴリズム」という内容の本。講義用の「アルゴリズムとデータ構造」の教科書は類書が実に多い。本屋で立ち読みしてみても正直似たり寄ったりで、本書も特に個性はないような…（著者としては「説明に図表を多く用いている」点が本書の「個性」だと思っているのかもしれないが…、本書の「無個性」振りはタイトルからも窺えようというものだ（笑））。紙数も少なく、しかも何かと中途半端なので、定価で購入していたらかなりガッカリしていただろうと思う。できれば古本を数百円で買いたい本。私自身は「類書を片っ端から立ち読みした中では、最もシンプルな内容で、かつ、最も易しそうだったから」という理由で本書を選び、古本を購入した。

　ちなみに、著者2人は北海道情報大学の先生のようで、自らの授業で使うために執筆した本なのだろうか？（授業の配布資料をまとめた本なのかもしれない。）北海道情報大学・経営情報学部の偏差値は40程度で、それくらいの大学の講義用教科書として適切な内容・レベルということなのだろうと思う。

　本文140ページ程度（他に、参考図書、練習問題の解答例、索引として10ページ程度）。



→　Kota's Book Review

　先日、競技プログラミングの「AtCoder」の過去問題を解いていて、「組合せ」の数を算出する必要が出てきた。「順列・組合せ」のあの「組合せ」だ。

　実は僕は（まだ数学が得意科目だった）中学生くらいの頃から「順列・組合せ」「確率」の問題が苦手だ。全ての場合をシステマチックに列挙するような「樹形図」を頭の中にうまく描くことができないのだ。

　と言うワケで、愚直に「階乗」「順列」「組合せ」をボトムアップ式に求めていくことにした（幸い、問題の制約条件から「₀C₀」〜「₉₉C₉₉」を求めれば充分であることがわかっていた）。

factorial = Array.new(100, 1)
1.upto(99){|n|
　factorial[n] = n * factorial[n - 1]
}

permutation = Array.new(100){Array.new(100, 0)}
0.upto(99){|n|
　0.upto(n){|r|
　　permutation[n][r] = factorial[n] / factorial[n - r]
　}
}

combination = Array.new(100){Array.new(100, 0)}
0.upto(99){|n|
　0.upto(n){|r|
　　combination[n][r] = permutation[n][r] / factorial[r]
　}
}

　で、「できてるかな？」と途中まで出力してみて…、

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

　「何だこれ！？　『パスカルの三角形』じゃないかっ！？」と…。

　そうだった…。僕が「順列・組合せの公式」だとか「二項定理」だとかウロ覚えでも、センター試験レベルの「順列・組合せ」「確率・統計」や大学の統計学の初歩をしのいでいけたのは、問題・答案用紙やノートの片隅に「パスカルの三角形」さえ描くスペースがあれば何とかなったからだった…。

　と言うワケで、最初から「パスカルの三角形」を求めてやれば良かったのである。

pascal = Array.new(100){Array.new(100, 0)}
pascal[0][0] = 1
1.upto(99){|n|
　pascal[n][0] = pascal[n][n] = 1
　　1.upto(n / 2){|r|
　　　pascal[n][r] = pascal[n][n - r] = pascal[n - 1][r - 1] + pascal[n - 1][r]
　}
}

　「階乗」「順列」「組合せ」の配列作るだけで数十分かかっちゃったのにね…。