2018-11-11

Pythonでflatten

リストを連結して一つにすることをflattenという。例えばこんなことだ：

[[3, 1, 4], [1, 5], [9], [2, 6, 5]] --> [3, 1, 4, 1, 5, 9, 2, 6, 5]

Pythonの標準ライブラリのitertoolsには似たようなことのできるchainという関数がある。

In [1]: from itertools import chain
In [2]: list(chain([1,2,3], [4,5], [6,7,8]))
Out[2]: [1, 2, 3, 4, 5, 6, 7, 8]

*でunpackすればflattenらしく使える。

In [3]: x = [[1,2,3], [4,5], [6,7,8]]
In [4]: list(chain(*x))
Out[4]: [1, 2, 3, 4, 5, 6, 7, 8]

2018-10-28

GitのGUIツール：gitk

GitのGUIツールgitkがそこそこ使えるので、軽く紹介してみる。

初めての人はとりあえず触ってみるといいかもしれない。

`gitk`のいいところ

gitkのいいところをまとめると、

Gitインストール時点から入っている

初めから入っているので、アレコレとアカウントの登録をしたりすることがなくて済む。 SourceTreeとか結構めんどくさいので、これはかなりいいところ。

最低限の機能は揃っている

コミットの親子を（再帰的に）調べたり、コミットログを遡って調べたりするには十分な機能がある。 git log --graphよりかは圧倒的にわかりやすい。

左上にコミットのグラフが表示されていて、左下にdiffが表示される。 f:id:hazuhi:20181028123739p:plain

`gitk`の悪いところ：GUIにしてはわかりにくい

割とごちゃっとしているSourceTreeと比べても、わかりにくいインターフェイスになっている。古いので仕方ないのだが、右クリックメニューの中で選択できない項目の見た目が、選択できるものと同じなのは特にわかりにくい。

その他のGitのGUIツール

Gitのコミットログを見たりするのに使えるツールは色々あり、一長一短だと思う。

Github desktopはシンプルでわかりやすい・コミットの取り消しがワンクリック（ワーキングディレクトリに反映したまま取り消してくれる）だが、rebaseや難しい操作はできない。

SourceTreeは多機能でなんでもできるし、rebaseもインタラクティブにできるが、直感的じゃないので初学者は触りづらいし、Atlassianアカウントが必要なので導入が面倒だったりする。

僕はtigが一番好きなのだが、GUIじゃないので使いにくいって人もいそうだなと。

まとめ

とにかくgitkは、

最低限コミットグラフを見れて、ログが追える
初めからインストールされる

ことだけがいいところだ。それ以上は求めてはいけない。

ぜひgitkお試しあれ。

2018-10-07

iPythonを起動しようとするとModuleNotFoundError

つまづき

競プロに参加しようとして、いつものようにipythonを起動しようとしたら、なぜか動かなくなっていた。

$ ipython
Traceback (most recent call last):
  File "/Library/Frameworks/Python.framework/Versions/3.7/bin/ipython", line 7, in <module>
    from IPython import start_ipython
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/IPython/__init__.py", line 55, in <module>
    from .terminal.embed import embed
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/IPython/terminal/embed.py", line 16, in <module>
    from IPython.terminal.interactiveshell import TerminalInteractiveShell
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/IPython/terminal/interactiveshell.py", line 20, in <module>
    from prompt_toolkit.formatted_text import PygmentsTokens
ModuleNotFoundError: No module named 'prompt_toolkit.formatted_text'

"ModuleNotFoundError: No module named 'prompt_toolkit.formatted_text'"で調べると、 Jupyter-console incompatible with prompt-toolkit 2.0.2 · Issue #158 · jupyter/jupyter_console · GitHub

どうも、2系にアップデートされたprompt-toolkitに6系のipythonが対応していないらしい。 jupyterとipythonで必要なprompt-toolkitのバージョンがコンフリクトしているようだ。

解決方法

最新のパッケージでは依存関係の問題は解決されているので、いずれも最新バージョンにアップデートすれば動く。

仮想環境を作り直す or キャッシュ無効にしてインストールし直せば良さそうなのだが、 jupyterの依存パッケージが多いので、一から作り直した。

$ rm -rf venv
$ python3 -m venv venv
$ pip list
Package    Version
---------- -------
pip        10.0.1 
setuptools 39.0.1

$ pip install ipython jupyter
Collecting ipython
  Using cached https://files.pythonhosted.org/packages/a0/27/29d66ed395a5c2c3a912332d446a54e2bc3277c36b0bbd22bc71623e0193/ipython-7.0.1-py3-none-any.whl
Collecting pygments (from ipython)
...
Successfully installed MarkupSafe-1.0 Send2Trash-1.5.0 bleach-3.0.0 defusedxml-0.5.0 entrypoints-0.2.3 ipykernel-5.0.0 ipywidgets-7.4.2 jinja2-2.10 jsonschema-2.6.0 jupyter-1.0.0 jupyter-client-5.2.3 jupyter-console-6.0.0 jupyter-core-4.4.0 mistune-0.8.3 nbconvert-5.4.0 nbformat-4.4.0 notebook-5.7.0 pandocfilters-1.4.2 prometheus-client-0.4.0 python-dateutil-2.7.3 pyzmq-17.1.2 qtconsole-4.4.1 terminado-0.8.1 testpath-0.4.2 tornado-5.1.1 webencodings-0.5.1 widgetsnbextension-3.4.2

$ ipython
Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 26 2018, 23:26:24) 
Type 'copyright', 'credits' or 'license' for more information
IPython 7.0.1 -- An enhanced Interactive Python. Type '?' for help.

In [1]:

補足

どうやら、pipにはまだ依存関係を正しく解決するリゾルバ機能がないため、環境をアレコレ触っていると事故るみたい。

イシューはこちら： Pip needs a dependency resolver · Issue #988 · pypa/pip · GitHub

2018-09-17

「専門用語」を英語で言うと

jargon 専門用語

terminologyも専門用語と訳されますが、jargonと比べるとより学問的です。

jargonは特定のコミュニティスラングのようなものも意味します。

また、jargonの方が否定的意味合いが強く、
コミュニティ外の人に特別にわかりにくい言葉、という意味合いがあるようです。

ロングマン現代英英辞典より。

terminology | ロングマン現代英英辞典でのterminologyの意味 | LDOCE

jargon | ロングマン現代英英辞典でのjargonの意味 | LDOCE

いつも職場の日報に、その日覚えた英語を書き込んでいるのだけど（義務ではない）、

せっかくなのでブログにも書いていこうという試み。

割と面白いなと思ったものだけピックアップしていこうと思います。

また、ロングマン英英辞典よりと書いているけれど、相当独自解釈が入っています。

2018-09-12

git: 同じレポジトリを別名でクローンする

Stack over flowより

How do you clone a Git repository into a specific folder? - Stack Overflow

レポジトリURIの後に、フォルダ名を指定すれば良い。

git clone git@github.com:whatever folder-name

2018-09-09

AtCoder Beginner Contest 109 参加ログ

AtCoder

ABC109に参加しました

AtCoder Beginner Contest 109 | AtCoder

実力：緑色 / 現R: 945

40分遅れて参加。

今回は久々に全完できた。いつもよりも簡単だったんじゃないだろうか？

少なくとも計算量の点で困るところはなかった。

A - ABC333

FizzBuzzと同程度の難易度。落ち着いてやれば問題ない。

ちなみに僕はYesをyesと出力してしまって1 WAでした、、、、

問題文をよく読んだ方がいい。

B - Shiritori

$N$ が小さいので、一つ一つ見ていけば良いが、同じ単語があったかどうかもチェックする必要がある。

状態を管理するのは面倒なのと、余計なクエリが発生するので、重複チェックを先にやってしまうといい。

サンプルコード

n = int(input())
w = []
for _ in range(n):
    w.append(input())

judge = len(w) == len(set(w))

for pre, post in zip(w[:-1], w[1:]):
    judge &= pre[-1] == post[0]

if judge:
    print('Yes')
else:
    print('No')

C - Skip

問題文の解釈

何回でも $D$ だけ移動しても良いのだから、 $D$ の倍数だけ $X$ から離れた座標はどこにでも到達できる。

f:id:hazuhi:20180909123638j:plain

つまり図の中で、小さく線を引いた部分が、座標 $X$ から訪れることのできる座標になる。

図の中で、座標 $x, y$ は、座標 $X$ から差分 $D$ の積み重ねで到達できる。

座標 $z$ には到達できない。

考察

もし座標 $X$ から全ての座標 $x_i$ に到達できるということは、

座標 $x_i$ から座標 $X$ にも移れるということだ。

これはつまり、任意の座標から他の任意の座標に移れるということでもある。

よって $X$ も含めて全ての座標は等価だと考えることができる。

この全ての座標の集合を、 $\{\ p_i: \ p_j ＜ p_k \ (where. \ j ＜ k )\}$ とすると、

一番左の座標 $p_0$ から、その右隣の座標 $p_1$ に移ることができる必要十分条件は、

$p_1 - p_0 \equiv \ 0 \ mod \ D$

になる。

計算

最も左の座標から、順に右隣の座標に移って行って、最も右の座標まで進むことができれば、全ての座標に到達することができる。

よって、 $p_{i+1} - p_i$ の最大公約数を求めれば、 $D$ の最大値を求めたことになる。

サンプルコード

atcoderのpythonは3.4なので、mathライブラリにはまだgcdがない。

これは結構忘れがちなので、気をつける。

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_(list):
    result = list[0]
    for el in list[1:]:
        result = gcd(result, el)
    return result


n, x = LI()
X = LI()

X.append(x)
X.sort()

X_ = [post - pre for pre, post in zip(X[:-1], X[1:])]

print(gcd_(X_))

D - Make Them Even

所感

題意をみたすようなデータを生成する問題。出力形式には十分注意する必要がある。

たかだか $500 \times 500$ 個のセルしかないので、全部調べる時間がある。

あとは、奇数を右下に掃き出していけば良いことに気がつけば、実装力の問題になると思う。

問題文の解釈

偶数になるセルを最大化する必要がある。

これを逆に考えると、奇数になるセルを最小化する問題と同じだ。

盤面をミクロに捉えてみよう。

隣接する二つのセルを考えると、この二つのセルの関係は、00, 01, 10, 11の４種類しかない。

ここで、0は偶数、1は奇数を表す。

重要なのは、11の時、片方のコインを移動して両方偶数にできることだ。

つまり、奇数のセルが集まっていれば、それを端から消していくことができる。

奇数のセルを掃き出していく

$a_{11}, a_{12}$ のセルに着目して、コインの移動を考えてみる。

00の時：何もしない
01の時：何もしない
10の時： $a_{11}$ から $a_{12}$ へ１枚コインを移動することで、01になる
11の時： $a_{11}$ から $a_{12}$ へ１枚コインを移動することで、00になる

2, 3のように、奇数のセルを右にずらしていくか、1, 4のように両方偶数にすることができる。

この操作を、次に図のように左から右へ、上から下へ行っていけば、奇数を右下に掃き出すことができる。

f:id:hazuhi:20180909150743j:plain:w300

エッジケース

あるセルのコインの数が0枚の時、そこからコインを移動することはできない。ただ、0は偶数なので、ここからコインを移動することはない。よって無視できる。

サンプルコード

個々の掃き出しの計算は、xorでできるので、a[i+1][-1] ^= 1のような計算が出てくる。

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]


h, w = LI()
a = []
for _ in range(h):
    a.append([x%2 for x in LI()])

operations = []
for i in range(h):
    for j in range(w-1):
        if not a[i][j]:
            continue
        else:
            a[i][j+1] ^= 1
            operations.append(' '.join(map(str, [i+1, j+1, i+1, j+2])))

for i in range(h-1):
    if not a[i][-1]:
        continue
    else:
        a[i+1][-1] ^= 1
        operations.append(' '.join(map(str, [i+1, w, i+2, w])))

print(len(operations))
for row in operations:
    print(row)

結果

R945 => R985 (Up)

もっと早く参加してれば、、、、、

2018-09-08

Dockerにhello worldしました

Tech

今更ですがDockerってなんですか？

コンテナ型の仮想化環境を提供するオープンソースソフトウェア

Docker - Wikipedia

アプリケーションは、それだけでは動かない。環境とセットで初めて動く。

なのでみんな環境構築に四苦八苦するのだけれど、その泥臭くてきつい作業から解放するために生まれたのがDockerだそうだ。

そこで、環境ごとまるっとアプリケーションを包み込むように開発すれば、余計な作業がなくなる。

このような開発スタイルを、コンポーネント志向と呼ぶらしい。

仮装マシンと違うのは、コンポーネントにはOSは含まれないところだ。ゆえに仮想マシンよりも軽量に動く。

Dockerに入門するのに、以下の記事を読んだので、自分用にまとめる。

英語：Get Started, Part 1: Orientation and setup | Docker Documentation

日本語：Part 1：概要説明とセットアップ — Docker-docs-ja 17.06.Beta ドキュメント

Hello world!

docker run hello-world

このコマンドを叩くと、ターミナルに次の文字列が流れてくる。

Hello from Docker!

This message shows that your installation appears to be working correctly.



To generate this message, Docker took the following steps:

1. The Docker client contacted the Docker daemon.

2. The Docker daemon pulled the "hello-world" image from the Docker Hub.

    (amd64)

3. The Docker daemon created a new container from that image which runs the

    executable that produces the output you are currently reading.

4. The Docker daemon streamed that output to the Docker client, which sent it

    to your terminal.

~~~

訳してみると、

Dockerの世界からこんにちは！
このメッセージを受け取っているということは、インストールはうまくいっているようですね。

このメッセージを生成するために、Dockerは次のような手順で動いています。

1. DockerクライアントがDockerデーモンを呼び出す
2. デーモンはDocker Hubから"hello-world"イメージを落としてくる
3. デーモンは"hello-world"イメージから新たにコンテナを作る。このコンテナが動いて、
　今あなたが読んでいる文章を提供する
4. デーモンがDockerクライアントの出力を読みだして、ターミナルに流す

とても分かりやすい。

flask on Docker

今度はpythonの公式ランタイム上でflaskアプリを動かし、redisでホスト名を返す簡単なアプリを作る。

Part 2：コンテナ — Docker-docs-ja 17.06.Beta ドキュメント

こんな感じになる。

f:id:hazuhi:20180908114316p:plain

Dockerfileのシンタックスハイライト

主要エディタならだいたいプラグインがある。

例えばSublime textなら、

Dockerfile Syntax Highlighting - Packages - Package Control

ちなみに、はてなにDockerfileのシンタックスハイライトはない。

はてなで綺麗にDockerfileを見せたい場合は、Pythonを指定しておくと比較的マシに見える。

例えば、

# 公式 Python ランタイムを親イメージとして使用
FROM python:2.7-slim

# 作業ディレクトリを /app に設定
WORKDIR /app

# 現在のディレクトリの内容を、コンテナ内の /app にコピー
ADD . /app

# requirements.txt で指定された必要なパッケージを全てインストール
RUN pip install -r requirements.txt

# ポート 80 番をコンテナの外の世界でも利用可能に
EXPOSE 80

# 環境変数の定義
ENV NAME World

# コンテナ起動時に app.py を実行
CMD ["python", "app.py"]

ビルド -> アプリの実行

docker build -t friendlyhello .
docker run -p 4000:80 friendlyhello

buildコマンドには、-tオプションでタグを指定できる。

このとき、現在のディレクトリを表す.がコマンドの最後に必要になる（ゴミじゃないよ）。

次にrunコマンドには、-pオプションでポート番号のマッピングを指定できる。

左側がDocker外部、右側が内部のポート番号になる。

イメージの公開と共有

Dockerをインストールしているのなら、https://hub.docker.com/のアカウントはもう持っているはずだ。

このアカウントでdocker hubにログインする。

docker login

ログインした後は、アカウントのレポジトリにpushして共有する。

ただしレポジトリにpushする前に、タグとリモートレポジトリを紐付ける必要がある。

タグはバージョン管理に使えるので、指定しておくと良い（指定しないと、latestとしてpushされる）。

docker tag image username/repository:tag
docker push username/repository:tag

こうしておけば、どのマシンからでも動かすことができるようになる。

docker rm image tag
docker run -p 4000:80 username/repository:tag

A bolt out of the blue

競プロ、その他勉強したことなど

Pythonでflatten

GitのGUIツール：gitk

`gitk`のいいところ

`gitk`の悪いところ：GUIにしてはわかりにくい

その他のGitのGUIツール

まとめ

iPythonを起動しようとするとModuleNotFoundError

つまづき

解決方法

補足

「専門用語」を英語で言うと

jargon 専門用語

git: 同じレポジトリを別名でクローンする

AtCoder Beginner Contest 109 参加ログ

ABC109に参加しました

A - ABC333

B - Shiritori

サンプルコード

C - Skip

問題文の解釈

考察

計算

サンプルコード

D - Make Them Even

所感

問題文の解釈

奇数のセルを掃き出していく

エッジケース

サンプルコード

結果

Dockerにhello worldしました

今更ですがDockerってなんですか？

Hello world!

flask on Docker

Dockerfileのシンタックスハイライト

ビルド -> アプリの実行

イメージの公開と共有

gitkのいいところ

gitkの悪いところ：GUIにしてはわかりにくい

その他のGitのGUIツール

まとめ

つまづき

解決方法

補足

jargon 専門用語

ABC109に参加しました

A - ABC333

B - Shiritori

サンプルコード

C - Skip

問題文の解釈

考察

計算

サンプルコード

D - Make Them Even

所感

問題文の解釈

奇数のセルを掃き出していく

エッジケース

サンプルコード

結果

今更ですがDockerってなんですか？

Hello world!

flask on Docker

Dockerfileのシンタックスハイライト

ビルド -> アプリの実行

イメージの公開と共有

`gitk`のいいところ

`gitk`の悪いところ：GUIにしてはわかりにくい