ソースコードの貼り付けができるmintedをpLaTeXで使ってみた

mintedとは

導入方法

  • Pygmentsのインストール
  • minted.styの導入
  • 使う

     Pygmentsのインストール

    Pygmentsが入っていない場合は以下のコマンドでインストールします。

sudo apt-get install python-pygments

 minted.styの導入

Pygmentsが入りましたら次にminted.styをダウンロードします。以下のサイトからダウンロードしてください。
CTAN: Package minted
下の"Down­load the con­tents of this pack­age in one zip archive"からダウンロードできます。 ダウンロードしたらダウンロード先のディレクトリまで進み、ファイルの解凍を行います。 解凍したディレクトリに入りmakeコマンドを実行してください。 実行が終わりますとディレクトリ内にminted.styというファイルがありますので。texmfの中に入れるなりして導入してください。

使う

ここまで来たら後は必要なことを記述して使うだけです。 記述の例はTeXLive2014と2015で違いますので気をつけてください。 mintedを使うTeXファイルの中で次の命令をプリアンブル部に記述します。

TeXLive2014の場合
\makeatletter\chardef\pdf@shellescape=\@ne\makeatother
\usepackage{minted}
TeXLive2015の場合
\usepackage[cache=false]{minted}

これでmintedを使うことができます。以下はmintedを使った例です。

\documentclass{jsarticle}
\chardef\pdf@shellescape=\@ne
\usepackage{minted}
\begin{document}
\begin{minted}{c}
#include<stdio.h>
int main(void){
  printf("Hello World!\n");
  return 0;
}
\end{minted}
\end{document}

コンパイルしたいころですがここで問題が発生します。なんとmintedは不具合のためかタブスペースが^^Iと変換されて表示されます。 試行錯誤を重ねたのですが原因はわからず...結局テキストエディタでタブをスペースに変換することにしました。タブをスペースに自動変換する方法は自分の使っているテキストエディタ毎に調べてください。設定ができましたらこれをコンパイルしていきます。 コンパイルの時はオプションをつけなければなりません。次のようにオプションをつけてコンパイルを行ってください。

platex -shell-escape [filename]

latexmkでコンパイルをする場合もshellescapeの設定を行えばコンパイルをすることができます。

latexmkの導入についての記事は以下をご覧ください。
muscle-keisuke.hatenablog.com 一度ターゲットを決めたら変更のたびにコンパイルを自動でやるので便利ですよ!
実行結果は以下のようになります。 f:id:muscle_keisuke:20151108030711p:plain

また、texファイル内に直接ソースコードを記述せずソースファイルを外部から読み込んで表示することも可能です。先ほどの例にあるCのソースコードhoge.cという名前で保存したとしましょう。それをLaTeXでmintedを使って読み込んで表示したい場合は以下のように記述します。  

\inputminted{c}{hoge.c}

言語を指定する引数がソース直書きの時と違い最初に来ていることに注意してください。長いソースコードの場合はこの方がすっきりしていいと思います。

mintedの例

ソースコードを行番号つきで載せる

ソースコードを行番号つきで載せる時は以下のmintedのオプションにlinenosと付けます。

\begin{minted}[linenos]{c}

f:id:muscle_keisuke:20151108133243p:plain

ソースコードのコメントに数式を付ける

LaTeXに載せたソースコードのコメントを付ける時に数式を使った方がわかりやすい場合があります。次のようにLaTeX用の数式コマンドを使っても オプションにmathescapeを付ければLaTeXと同じように数式を表示することができます。

\begin{minted}[linenos,mathescape]{c}
#include<stdio.h>
int main(void){
    int k=0;
    int x=0;
    // This code mean \sum_{k=0}^{100} k^2+2k+1
    for(k=0;k<100;++k){
        x=k*k + 2*k +1;
    }
    printf("x=%d\n");
    return 0;
}
\end{minted}

結果は次のように綺麗な数式でコメントを残すことができます。 f:id:muscle_keisuke:20151108133326p:plain

その他のオプション

そのほかにも枠を付けたり図や表のようなキャプションやラベルをつけることも可能です。

\definecolor{bg}{rgb}{0.95,0.95,0.95}
\begin{listing}
\begin{minted}[linenos,
       mathescape,
       numbersep=5pt,
       frame=lines,
       framesep=2mm,
       bgcolor=bg]{c}
#include<stdio.h>
int main(void){
    int k=0;
    int x=0;
    // This code mean \sum_{k=0}^{100} k^2+2k+1
    for(k=0;k<100;++k){
        x=k*k + 2*k +1;
    }
    printf("x=%d\n");
    return 0;
}
\end{minted}
\caption{mintedの例}
\label{lst:example}
\end{listing}
ソース\ref{lst:example}はmintedの例である。

引用したい時も助かります。 f:id:muscle_keisuke:20151108135308p:plain

新しいmintedマクロ

ここまでmintedに関する様々なオプションを紹介してきました。しかし、たくさんのオプションを使うときにいちいち記述していたらごちゃごちゃしたり面倒くさかったりします。そこでmintedには新しいminted用のマクロを作れるマクロがあります。それが\newmintedと\newmintedfileです。2つのマクロの違いは外部からソースを読み込むかどうかの違いしかありません。次のソースを元に\newmintedと\newmintedfileで書き換える次のようになります。

\begin{minted}[linenos,
       mathescape,
       numbersep=5pt,
       frame=lines,
       framesep=2mm
       ]{c}
#include<stdio.h>
int main(void){
    printf("Hello World!\n");
    return 0;
}
\end{minted}

\inputminted[linenos,
       mathescape,
       numbersep=5pt,
       frame=lines,
       framesep=2mm]{c}{hoge.c}

書き換えると

\newminted[myMinted]{c}{
    linenos,
    mathescape,
    numbersep=5pt,
    frame=lines,
    framesep=2mm
}
\newmintedfile[myMintedfile]{c}{
    linenos,
    mathescape,
    numbersep=5pt,
    frame=lines,
    framesep=2mm
}

\begin{myMinted}
#include<stdio.h>
int main(void){
    printf("Hello World!\n");
    return 0;
}
\end{myMinted}

\myMintedfile{hoge.c}

ソースが長くなった気がしますがそれは最初に定義を書いているからです。newminted、newmintedfileマクロによって新しいminted用のマクロmyMintedとmyMintedfileを定義してそれを使っています。普段から同じオプションを使う人はこのように定義をしておくとコードがすっきりするかもしれません。

Exact Cover Problemとそれを応用した数独解読アルゴリズム

Exact Cover Problemを知ったきっかけ

先日、演習の一環で数独を解読を行うアルゴリズムJavaで書くという演習がありました。どうせなら早く解けるようにしたいということで何かいいアルゴリズムはないかと調べました。そしたらこのような記事を見つけました。 d.hatena.ne.jpこの記事で紹介されている問題とアルゴリズムを使うと数独を解くプログラムができるらしいです。 Exact Cover Problemとそれを解くKnuth's Algorithm Xについては引用元の記事をご覧ください。

Exact Cover Problemを数独に応用する

数独問題=Exact Cover Problem

人間が数独を解くときは「ここには何が入りそうだ」とかを考えて解候補をマスの端に書いたりして考えます。今回紹介するExact Cover Problemもそれに似た感じです。

数独をExact Cover Problemとしてみる

数独として成り立つには次のような条件があります。

  • 各行と各列が交差する部分つまり各セルには必ず正確な数字が入っている必要がある。...行と列の関係
  • 各行には正確な数字が重複しないようにはいっている必要がある。...行と数字の関係
  • 各列には正確な数字が重複しないように入っている必要がある。...列と数字の関係
  • 各ボックスには正確な数字が重複しないように入っている必要がある。...ボックスと数字の関係

上記の4つの条件をすべての行、列、ボックスにおいてすべて満たすと数独的に正しいことになります。Exact Cover Problemとして考えるには人間がマスの端に可能性のある数字を書き込むようにこの各条件と考え得るすべての場合と照らし合わせて考えます。考え得るすべての場合というのは「1行1列に1が入る場合」、「1行1列に2が入る場合」、...「9行9列に9が入る場合」までを考えます。そしてそれらは各条件を持った集合です。例えば「1行1列に1が入る場合」というのは{1行1列に数字がある、1行目に1がある、1列目に1がある、一つ目のボックスに1がある}という4つの元を持った集合です。そしてこれらの元は他の場合と重複して持っていてはいけません。かつすべての条件を網羅していてなくてはいけません。つまり数独はExact Cover Problemなのです。

Knuth's Algorithm Xに数独を適用する

数独がExact Cover Problemであることは前節でわかっていただけたでしょうか。ここからはExact Cove Problemとして数独を見たときにそれをコンピュータにどう解かせるかを考えていきます。引用させていただいたJAPL JさんのブログによるとKnuth's Algorithm Xのアルゴリズムでは各元とそれを持った集合の関係行列を用意していました。これを前節で説明したものに適用する前に表現を定義しておきます。まずすべての考え得る場合からです。「m行n列に数字pがはいる場合」というのはRmCn#pと記述することにします。例えば「3行6列に数字8が入る場合」というのはR3C6#8となります。次に条件について考えます。行と列の関係についてm行n列に数字が入っているという条件はRmCnと記述することにします。行と数字の関係についてm行目に数字pが入るという条件はRm#pと記述します。列と数字の関係についてn列目に数字pが入るという条件はCn#pと記述します。ボックスと数字の関係についてx番目のボックスに数字pがはいるという条件はBx#pと記述します。定義をまとめると以下のようになります。

  •  m行n列に数字pが入る場合:= RmCn\verb|#|p
  •  m行n列に数字が入る条件:= RmCn
  •  m行に数字pが入る条件:= Rm\verb|#|p
  •  n列に数字pが入る条件:= Cn\verb|#|p
  •  x番目のボックスに数字pが入る条件:= Bx\verb|#|p

これを基に数独の関係行列を作成すると以下のようになります。( 729 \times 324の行列なので間を省略)

R1C1 R1C2 \cdots R9C9 R1#1 R1#2 \cdots R9#9 C1#1 C1#2 \cdots C9#9 B1#1 B1#2 \cdots B9#9
R1C1#1 1 0 \cdots 0 1 0 \cdots 0 1 0 \cdots 0 1 0 \cdots 0
R1C1#2 1 0 \cdots 0 0 1 \cdots 0 0 1 \cdots 0 0 1 \cdots 0
\vdots
R1C1#9 1 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0
R1C2#1 0 1 \cdots 0 1 0 \cdots 0 0 0 \cdots 0 1 0 \cdots 0
R1C2#2 0 1 \cdots 0 0 1 \cdots 0 0 0 \cdots 0 0 1 \cdots 0
\vdots
R1C9#9 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 1 0 0 \cdots 0
R2C1#1 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0 1 0 \cdots 0
R2C1#2 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0 0 1 \cdots 0
\vdots
R9C9#9 0 0 \cdots 1 0 0 \cdots 1 0 0 \cdots 1 0 0 \cdots 1

しかし、この関係行列は数独問題が全くの空白の場合です。数独の問題を解く時は大抵、所々に初期値が入っているのものです。例えば3行2列目に数字9が入っていることがわかっていたとしましょう。そうすると関係行列のR3C2、R3#9、C2#9、B1#9の列はすべて1になります。なぜならどの場合を考えたとしてもそれらの列の条件を満たしているのは明らかだからです。そしてR3C2#1~R3C2#8の8行はすべて消えます。なぜならこれらの行の場合はあり得ないからです。この行列を解いて残った解候補が答えとなります。

プログラムを書く

数独アルゴリズムで解くビジョンが見えてきたと思います。次にこれをプログラムに解かせるにはどうすれば効率がよいかを考えます。

今回の演習はJavaの演習なのでJavaで実装しければなりません。 考えた末全然実装方法が思いつかなかったのでネットの力を頼ることにしました。そしたらGitHubにExact Cover Problemを実装したソースコードがありました。それが以下になります。

github.com

rafalioさんという方が数独Knuth's Algorithm Xで解くプログラムをJavaで実装されていました。最初プログラムを見た時はちんぷんかんぷんでしたが時間をかけながら一つずつ理解していきました。rafalioさんが書かれたプログラムにできるだけ細かくコメントを記述したものをGitHubに上げました。以下になります。

※ただし、演習で使う用に改造したので元のソースコードとは異なる部分があります。

github.com

メソッドなどの詳しい動作説明

自分が解釈や理解に苦しんだクラスやメソッドを選んで説明させていただきます。

Dancing Links

引用元のブログでも紹介している通りDancing Linksという概念を用いてKnuth's Algorithm Xを解きます。DancingLinksについて概要だけ述べます。

  • 上下左右に双方向に繋がる自己参照型リスト
  • 今回の場合行列の1になる部分だけリンクする疎行列のスタイル
  • 各列の一番上にはカラムノードという列を表すノードがある
    hookRigntメソッドとhookDownメソッド
    ノード同士の連結にはノードを引数に取るhookRightメソッドとhookDownメソッドで実装されています。それぞれ引数にとったノードを右または下にリンクさせる関数です。この関数だけで双方向のリンクを実現するので左または上にリンクさせる関数は不要です。hookRight関数を例にリンクの様子を説明すると以下のようになります。 f:id:muscle_keisuke:20150919060738j:plain 図はn1が端のノードではないことを前提に作っています。もしn1が端のノードの場合はn1.Rは循環して最初のノードとなります。hookDownメソッドも同様です。 このメソッドを繰り返すことでDancingLinksを形成します。
    DancingNodeクラスとColumnNodeクラス
    Knuth's Algorithm Xには「列の中で一番1が少ない列を選択する」という動作があります。この時使うのがColumnNodeです。ColumnNodeはフィールドにString型を持ち自分が何列目かをそこに格納します。各DancingNodeはフィールドにColumnNodeを持ち、自分自身が何列目かがわかることができます。
    unLinkUDメソッド,unLinkLRメソッド
    次に削除の手順を示します。DancingNodeのメソッドにunLinkLR,unLinkUDの2つのメソッドがあります。これらを使って削除を行います。f:id:muscle_keisuke:20150919065412j:plainこれらのメソッドによって違うノードからの参照ができなくなります。
    coverメソッド
    前節で説明したunLinkUD,unLinkLRメソッドを使い列ごとの削除を行います。正確にいうと削除ではありません。正確に言うとノードを覆い(cover)、見えなくします。そうすることによって列を削除したと見なして処理を続けます。なぜいっそのこと削除しないのかという話になります。それは後で列の復元をする必要があるからです。Knuth's Algorithm Xでは列を選択した後、「その列に1が含まれる行を1つだけ選択するという動作」があります。その行の選択の仕方によって解が変わる可能性があります。最悪の場合解が出ないことがあります。しかし、それを事前に判断することができません。rafalioさんのソースコードではすべての行をfor文で網羅しています。そして再帰関数によって最後まで処理を試みます。ここで解なしが発生した場合再帰処理から復帰しなければなりません。その際に列を完全に削除してしまうと復元ができないのでcoverするにとどまるというわけです。
    reLinkUDメソッド,reLinkLRメソッド
    unLinkUD,unLinkLRメソッドによって参照不能になったメソッドを再び双方向に戻します。UDのほうが上下に双方向,LRが左右に双方向を復元させます。
    uncoverメソッド
    coverメソッドによって覆った列を復元するメソッドです。他のノードからは参照できませんが自分自身のノードからは参照できるのでそこからreLinkUD,reLinkLRによって双方向に戻します。coverメソッドを発動した時点でガベージコレクションに削除されない理由を次の節で説明します。
    knuthsAlgoritmXメソッド

    プログラムの心臓部です。内部でselectColumnNodeHeuristicメソッドという1が最も少ないColumnNodeを返すメソッドを呼んでいます。そのメソッドによって返されたColumnNode及びそこから参照できるすべてのDancingNodeが属するColumnNodeをcoverメソッドで参照できなくします。その際にガベージコレクションによって回収されないようにanswerというコレクションに対象のDancingNodeを追加します。内部でknuthsAlgoritmXメソッドを再帰的に呼び出し、行列が0になるかもしくはリンクするDancingLinkがなくなるまで行います。行列が0になった場合は成功なのでanswerをhandlerクラスのhandleSolutionメソッドという解を決定づけるメソッドの引数に渡します。リンクするDancingLinkがなくなるつまり1を全く含まない列が出てきた場合は解なしなのでそのままメソッドを終了していきます。関数を終了するとその後に復元処理をする必要があります。次の行について調べる必要があるからです。ガベージコレクションに回収されないようにanswerに格納していたDancingNodeを取り出します。answerからはDancingNodeを削除します。取り出したDancingNode及びそこからたどれるすべてのDancingNodeについてuncoverを行い列を復元させます。そのレベルにおいて全ての行の探索が終われば列を復元させて同じ処理を行います。このような具合に解を見つけていきます。以下にknuthsAlgorithmXの簡単なフローチャートを載せておきます。

f:id:muscle_keisuke:20151104090643p:plain

LaTeX覚書その3

{\LaTeX}のマクロを用いて\sectionの番号部分を変更する

問題と解決

  • \sectionを使うと番号の部分が1,2,3...と表示される
  • これを例えば問題1,問題2,問題3としたいときどうするか
  • 最近覚えた{\LaTeX}のマクロを使って解決する

{\TeX}のマクロを使ってなんとかしてみる

とりあえず覚えたてなので俺の知ってるコマンドだけでなんとかしてみる。

\makeatletter
\newcommand{\Section}[1]{{%
        \newcount\@m
        \@m = 1
        \section*{問題 \the\@m #1}%
        \advance \@m by 1
}}%
\makeatother
\documentclass{jsarticle}
\begin{document}
\Section{ほげ}
\Section{ふが}
\end{document}

結果...失敗した
二回目に\Sectionを使うときでも番号がカウントされない
というわけで調べました。
{\LaTeX}のマクロコマンドに\refstepcounterなるものがあるらしい。
これがあるとコマンドを実行するたびに変数の値を一回カウントするという。しかも\labelによるラベル付と\refによる参照も可能である。 これを用いて書きなおすと次のような感じになった。

\makeatletter
\newcounter{m}
\setcounter{m}{0}
\newcommand{\Section}[2][]{{%
        \refstepcounter{m}#1
        \section*{問題 \arabic{m} #2}%
}}%
\makeatother
\documentclass{jsarticle}
\begin{document}
\Section[\label{hoge}]{ほげ}
\Section{ふが}
\end{document}

これできちんと番号がカウントされるようになった。

LaTeX覚書 その2

makeやomakeに変わる{\LaTeX}コンパイルスクリプトlatexmk

インストール手順

  • perlで書かれている
  • MacTeXや2009年以降のTeXLiveには標準で入っている
  • ない場合は以下のようにしてインストール
$ sudo apt-get install latexmk

環境設定

  • 設定は.latexmkrcファイルに書く
  • ~/.latemkrcファイルを作成
  • dviからpdfの変換にdvipdfmxをpdfを開くのにxdg-openを使う場合は次の設定
#!/usr/bin/env perl
$latex            = 'platex -shell-escape -synctex=1 -halt-on-error';
$latex_silent     = 'platex -shell-escape -synctex=1 -halt-on-error -interaction=batchmode';
$bibtex           = 'pbibtex';
$dvipdf           = 'dvipdfmx %O -o %D %S';
$makeindex        = 'mendex %O -o %D %S';
$max_repeat       = 5;
$pdf_mode     = 3; # generates pdf via dvipdfmx

$pvc_view_file_via_temporary = 0;

$pdf_previewer    = "xdg-open";

使い方

tex -> pdfへのタイプセット

$ latexmk hoge.tex
  • texからpdfへ変更してかつそれを監視(texが変更される度にpdfを更新)
  • 以下のコマンドを実行すると監視が始まるのでターミナル上で動くテキストエディタ以外を使う場合はそのままの状態でtexを編集
  • vi,vimを使う場合は別のターミナルウィンドウを開いて編集する
  • 監視を終えるにはCtrl+C
$ latexmk -pvc  hoge.tex

beamerの図挿入で図番号を出力する方法

  • 標準ではbeamerで図にキャプションを付けても図番号が表示されない
  • プリアンブルに以下を書き込むと表示される
\setbeamertemplate{caption}[numbered]
  • 図xや表yなどの表示にしたい場合は以下のように記述
\renewcommand{\figurename}{}
\renewcommand{\tablename}{}

LaTeX覚書 その1

{\LaTeX}のbeamerでxcolorを使う方法

  • listingsを用いてソースコードを載っける際にxcolorを使うことがある

  • しかしbeamerだとxcolorを次のように適用することができない

\usepackage[svgnames,dvipsnames]{xcolor}
  • beaemerでxcolorを使うときは\usepackage{}を使わずにbeamerのオプションとして次のように指定する
\documentclass[xcolor={svgnames,dvipsnames}]{beamer}

beamerのframe環境で使うオプションfragileについて

  • frame環境内でverbatim環境を使う場合はframe環境のオプションにfragileをつける必要がある
  • listing環境を使う場合も一緒である
  • 以下のように記述する
\begin{frame}[fragile]
\begin{vervatim}
...
\end{verbatim}
\end{frame}
\begin{frame}[fragile]
\begin{lstlisting}[caption=hoge,label=fuga]
...
\end{lstlisting}
\end{frame}