Haskellで凸包を求めるGraham Scanアルゴリズムを実装する

夏休みなので、Haskellのリハビリのために、「Real World Haskell」を読んでいます。 3章の練習問題に、平面上の点の集合の凸包を求めるGraham scanアルゴリズムを求めよ、という問題があります。

Graham scan - Wikipedia

以下のように書きました。まだ、あまりテストしていません。 この本でQuick Checkを学んでテストしてみようと思います。

import Data.List

data Point2D = Point2D { x::Int, y::Int } deriving (Eq, Show)
data Direction = CounterClockWise | ClockWise | Collinier deriving (Eq, Show)

-- 線分abの延長線上に点cがあるならば、Collinier
-- 線分abの延長線の左側に点cがあるならば、CounterClockWise
-- 線分abの延長線の右側に点cがあるならば、ClockWise
-- ベクトルabとベクトルbcの外積のz座標の符号で上記を判定する
direction :: Point2D -> Point2D ->Point2D -> Direction
direction a b c
    | crossProductZ > 0 = CounterClockWise
    | crossProductZ < 0 = ClockWise
    | otherwise = Collinier
    where
        crossProductZ = abx * bcy - aby * bcx
            where
               abx = (x b) - (x a)
               aby = (y b) - (y a)
               bcx = (x c) - (x b)
               bcy = (y c) - (y b)

-- 平面上の点の集合の凸包をGraham Scanアルゴリズムで求める
convexHull :: [Point2D] -> [Point2D]
convexHull xs = convexHullSub ys
    where
        ys = [p] ++ sortForGrahamScan p pRemoved ++ [p]
            where
                p = startPoint xs
                pRemoved = filter (\x->x/=p) xs

convexHullSub :: [Point2D] -> [Point2D]
convexHullSub (a:b:c:xs)
    | direction a b c == CounterClockWise = a:(convexHullSub (b:c:xs))
    | otherwise = convexHullSub (a:c:xs)
convexHullSub xs = xs

-- 平面上の点をソートする
-- 点pとソートする点を通る直線とx軸の成す角度の昇順でソートする
sortForGrahamScan :: Point2D -> [Point2D] -> [Point2D]
sortForGrahamScan p xs = sortBy compareAngle xs
    where
        compareAngle a b
            | cosVal a < cosVal b = GT
            | otherwise = LT
            where
                cosVal point = (fromIntegral pointX) / sqrt (fromIntegral (pointX * pointX + pointY * pointY))
                    where
                        pointX = (x point) - (x p)
                        pointY = (y point) - (y p)

-- 点pを求める
-- 点pはy座標が最小の点の中で、x座標が最小の点である
startPoint :: [Point2D] -> Point2D
startPoint xs = head (sortByCoordinates xs)
    where
        sortByCoordinates = sortBy compareXY
            where
                compareXY a b
                    | (y a) < (y b) = LT
                    | (y a) > (y b) = GT
                    | (x a) < (x b) = LT
                    | otherwise = GT

Markdownによるプレゼンテーション用スライド作成

0. 環境

ArchLinux

1. Pandocのインストール

sudo pacman -S pandoc

2. reveal.jsのインストール

git clone https://github.com/hakimel/reveal.js.git

3. スライドのMarkdownファイル作成

vim slide.md

4. Pandocによる変換

pandoc -t revealjs -s slide.md -o slide.html

slide.htmlは、git cloneしたreveal.jsディレクトリと同じディレクトリに配置します。

5. 確認

firefox slide.html

ArchLinuxのインストール方法

この記事は主に自分用のメモであるため、誤りやわかりにくい点があるかもしれません。インストールガイド - ArchWikiや他サイトと比較しながら、参照することをオススメします。

0. 環境

ASUS X553M (CPU: Intel BYT-M 2Core 2840, up to 2.58GHz)

1. LiveCDからの起動

LiveCDをDVDドライブに入れ、BIOSで、ブートデバイスをDVDドライブに指定して起動します。

2. 日本語キーボード設定

以下のコマンドを入力します。

loadkeys jp106

3. wifi接続

以下のコマンドを入力します。ここで、「wlp2s0」は僕のマシンのwifiインターフェース名です。

ip link set wlp2s0 up
cd /etc/wpa_cupplicant
echo ctrl_interface=/run/wpa_supplicant > wifi.conf
echo update_config=1 >> wifi.conf
wpa_supplicant -B -i wlp2s0 -c /etc/wpa_supplicant/wifi.conf

次に、wpa_cliコマンドを実行します。

wpa_cli

すると、CLIが表示されるので、以下を入力していきます。プロンプトを「>」で表しています。ssidとpsk(プライマリキー)は各自の環境に合わせてください。ダブルクォーテーションで囲む必要があるようです。

> add_network 0
> setnetwork 0 ssid "XXXXXX"
> setnetwork 0 psk "XXXXXX"
> enable_network 0
> save_config
> q

次に、wifiインターフェースにIPアドレスを割り当てるため、以下のコマンドを実行します。

dhcpcd wlp2s0

4. パーティション作成

4.1 現在のパーティション確認

以下のコマンドで現在のパーティションを確認します。

lsblk

4.2 fdiskを使用したパーティション作成

以下のパーティションを作成します。メモリが4GBなので、swap領域は2倍の8GBにしました。

領域 容量 バイスファイル
/boot 512M /dev/sda1
swap 8G /dev/sda2
/ 64G /dev/sda3
/home 残り /dev/sda4

fdiskでこれらのパーティションを作ります。

fdisk /dev/sda
Command : o
Command : n
Partition type: Select : p
&Partition number : 1
First sector : Enter を押す
Last sector, +sectors or +size{K,M,G} : +512M

Command : n
Partition type: Select : p
&Partition number : 2
First sector : Enter を押す
Last sector, +sectors or +size{K,M,G} : +8G

Command : n
Partition type: Select : p
&Partition number : 3
First sector : Enter を押す
Last sector, +sectors or +size{K,M,G} : +64G

Command : n
Partition type: Select : p
&Partition number : 4
First sector : Enter を押す
Last sector, +sectors or +size{K,M,G} : Enter を押す

# /bootのパーティションタイプ設定
Command: a
Partition number: 1

# swap領域のパーティションタイプ設定
Command: t
Partition number: 2
Hex code: 82

4.3 ファイルシステムの設定

mkfs.ext2 /devsda1
mkswap /dev/sda2
swapon /dev/sda2
mkfs.ext4 /dev/sda3
mkfs.ext4 /dev/sda4

4.4 パーティションのマウント

mount /dev/sda3 /mnt
mkdir /mnt/boot
mount /dev/sda1 /mnt/boot
mkdir /mnt/home
mount /dev/sda4 /mnt/home

5. ミラーサイト設定

vi /etc/pacman.d/mirrorlist

以下を一番上に移動させます。

## Japan
Server = http://ftp.jaist.ac.jp/pub/Linux/ArchLinux/$repo/os/$arch

6. 必須パッケージのインストー

pacstrap /mnt base base-devel

7. マウント設定ファイル生成

genfstab -U -p /mnt >> /mnt/etc/fstab

8. chroot環境での各種設定とインストー

以下のコマンドで、/mntを一時的にルートディレクトリにします。これを実行した後の環境をchroot環境と呼ぶことにします。

arch-chroot /mnt /bin/bash

chroot環境になりましたので、各種設定とインストールをしていきます。

8.1 言語の設定

ロケール生成ファイルを開きます。

vi /etc/locale.gen

以下の行をコメントアウトします。

en_US.UTF-8 UTF-8
ja_JP.UTF-8 UTF-8 

以下のコマンドでロケールを生成します。

locale-gen

言語の環境変数を設定します。

echo LANG=en_US.UTF-8 > /etc/locale.conf
export LANG=en_US.UTF-8

日本語キーボードの設定をします。

loadkeys jp106
echo KEYMAP=jp106 > /etc/vconsole.conf

8.2 時間の設定

タイムゾーンを設定します。

ln -fs /usr/share/zoneinfo/Asia/Tokyo /etc/localtime

ハードウェアクロックを設定します。

hwclock -w -u 

8.3 ホスト名設定

以下のようにホスト名を設定します。

echo <ホスト名> > /etc/hostname

/etc/hostsにもホスト名を書いておきます。

vi /etc/hosts
#<ip-address> <hostname.domain.org> <hostname>
127.0.0.1   localhost.localdomain   localhost <ホスト名>
::1     localhost.localdomain   localhost <ホスト名>

8.4 ネットワーク設定

systemctl enable dhcpcd.service

8.5 rootパスワード設定

passwd

8.6 ブートローダgrubのインストールと設定

pacman -Sy
pacman -S intel-ucode
pacman -S grub
grub-install --target=i386-pc --recheck /dev/sda
grub-mkconfig -o /boot/grub/grub.cfg

8.7 chroot環境から抜ける

exit

8.8 パーティションのアンマウント

umount -R /mnt

8.9 再起動

reboot

Pythonで数学の勉強

SymPy

SymPy

pythonの数式処理ライブラリ。 CAS(Computer Algebra System)といい、式変形をすることで方程式などを解いてくれるようだ。

数式処理システム - Wikipedia

CASには以前から興味があった。これぞ人工知能という感じだ。

Jupyter

Project Jupyter | Home

pythonのREPLをブラウザ上で実行し、その結果を書き留めておくことができるWebアプリ。

ArchLinuxへのSymPyとJupyterのインストー

SymPy

sudo pacman -S python-sympy

Jupyter

sudo pacman -S jupyter-notebook
sudo pacman -S python-ipywidgets

グラフを描きたいので、pythonのライブラリmatplotlibをインストールする。 あと、数式をLatex形式で表示したいのでMathJaxをインストールする。

sudo pacman -S python-matplotlib
sudo pacman -S mathjax

実行方法

まず、localhostでJupyterを起動する。

jupyter notebook

表示されたURLをブラウザで開く。 右端の「New」をclickして「Python3」を選択すると、REPLが表示される。 以下のようにして、グラフが描ける。

from sympy import *
x=symbols("x")
from sympy.plotting import plot
plot(sin(x)/x)

やりたいこと

Lispの勉強は続けている。この前、ハノイの塔のコードを読んで感動した。

(defun hanoi (n &optional (from 'from) (to 'to) (other 'other))
    (cond ((= n 1) (list (cons from to)))
          (t (append (hanoi (1- n) from other to)
                     (hanoi 1 from to other)
                     (hanoi (1- n) other to from)))))

Common Lispの仕様は大きくて大変だけど、最近zealというドキュメント閲覧
ソフトを知ってCommon Lispの仕様をダウンロードして見ていだ。

あと、最近は、仕事でweb系の技術に触れることが多くなった。
node, npm, postgresなど
結局、ドキュメントしらべて、ツールインストールしたり、ツール使ったりするだけで
あまりおもしろみはない。

自分の進む方向性としては、他の人があまりやりたがらないような
基礎的なことを極めたい。
最近流行の、シェル芸やアセンブラ短歌など、僕は大好きだ。

効率化だけでなく、基礎的で、わくわくするものを求めたい。

振り子の同期

勉強しなくちゃ。他の人に遅れをとらないように情報収集しなくちゃ。
そんなことばかり考えていた。
勉強しているときや情報収集しているときは安心するし、いいことしてる気がしてた。
でも、最近、このようなことをしていると頭が痛くなってくることに気づいた。
僕の心の中のもう一人がこう言っている。
それは本当にやりたいことかな? やりたいことが他にあって、その手段として
勉強をしているのだとしたら、もっといいやり方があるんじゃないか。

どうしたら頭が痛くならないようにできるかな。
少しずつ、わかってくるはず。
やりたいことも見えてくるよ。
ゆっくり、ゆっくり生きていこう。

揺れる振り子も、はじめは周期がずれているけれど
だんだん同期してくる。

「わからない」という方法

わからないって大切だよね。だって、わからないって続けるっていうことだもんね。人と話してて、「わかりました。」って言うのは、「コミュニケーションを終了します。」っていうことだもんね。わからないは、もっと知りたいってことだもんね。

「幸せになる」ってわからないなぁ。だって、幸せになるって、おしまいってことだもんね。おしまいって、本当はないよね。道が続いてて、寄り道したり、あっちこっち行って、いろんなもん、変なもんとか、拾うのがいいんだよね。

でも、「わかったぁ!」は大切だよね。「わかりました。」じゃなくて「わかったぁ!!」だよ。「わかったぁ!」は道の途中に置いておくパンくずみたいなものだよ。