Emacs: How to Insert Same String at the Beginning of Each Line

Emacs: 複数の行頭に文字を挿入する方法

• まずリージョンを選択
  
  C-SPACE -> カーソル移動
  (文書全体を選択する場合は C-x h)
   
• 各行の先頭にスペースを挿入する場合は
  
  C-x C-i
   
• 各行の先頭に特定の文字列を挿入する場合は
  
  C-x r t

 

References

No. 54
GNU Emacs Frequently Asked Questions (FAQ), part 2/5

How to Install GNU Octave

GNU Octave のインストール方法

 

Machine Learning | Coursera の Week 2 の課題のため、Octave をインストールする。

Octave とは、フリーの数値解析ソフトウェア(プログラミング言語)。
行列の計算やグラフ描画(gnuplotと連携して可視化)が簡単にできることが特徴。

 

Windows

こちらからインストーラをダウンロードして実行。
Octave Forge - Browse /Octave Windows binaries at SourceForge.net 

Coursera の手順に書かれていたのは Octave-3.2.4_i686-pc-mingw32_gcc-4.4.0_setup.exe だった。

インストーラの Choose Components の画面で、"image" パッケージを追加するとよい。

 

Mac

こちらから Mac 用のディスクイメージをダウンロードしてマウント。
Octave Forge - Browse /Octave MacOSX Binary at SourceForge.net

最初、最新版(3.7.7)を入れたらグラフ表示でプログラムが落ちてしまう状態になったので
古いバージョン(3.4.0)をインストール。 

• 事前に X.11 (XQuartz) をインストール
• 例によって Octave.app を Applications フォルダにコピー。
• 次に Gnuplot をインストールするのだが、ここに書いてあるとおり、MacOS Lion 以降だと実行時にエラーとなってしまう。
  Octave Forge - Browse /Octave MacOSX Binary/2011-04-21 binary of Octave 3.4.0 at SourceForge.net
• Extras 配下の Gnuplot のディスクイメージもマウントし、Gnuplot.app を Applications フォルダにコピー。
• シェルスクリプト /Applications/Gnuplot.app/Contents/Resources/bin/gnuplot をエディタで開き、
  「DYLD_LIBRARY_PATH」を「DYLD_FALLBACK_LIBRARY_PATH」に全て置換。
  (全部で4ヶ所。「=」の前後双方を置換する必要があるので注意。) 
• .zshrc (.bashrc) にエイリアスを設定すると便利。
  

  alias octave="/Applications/Octave.app/Contents/Resources/bin/octave --persist --eval \"PS1('>> ')\""

 

実行例

octave-3.4.0:1> x=-5:5 x =     -5  -4  -3  -2  -1   0   1   2   3   4   5   octave-3.4.0:2> y=2*x y =     -10   -8   -6   -4   -2    0    2    4    6    8   10   octave-3.4.0:3> plot(x,y)

 

とりあえずグラフが描画できた。

Algorithm: Bipartite Graph Matching

二部グラフの最大マッチング

 

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	""""
	Bipartite graph matching algorithm
	"""
	import collections
	class Graph(object):
	"""
	Simple graph model.
	"""
	def __init__(self, num_nodes):
	self.edges = collections.defaultdict(dict)
	self.num_nodes = num_nodes
	def make_edge(self, from_, to, value):
	self.edges[from_][to] = value
	class BipartiteGraph(object):
	"""
	Bipartite undirected graph model.
	"""
	def __init__(self):
	self.edges = set()
	self.num_u = 0
	self.num_v = 0
	def make_edge(self, u, v):
	self.edges.add((u, v))
	self.num_u = max(self.num_u, u + 1)
	self.num_v = max(self.num_v, v + 1)
	def to_graph(self):
	g = Graph(self.num_u + self.num_v)
	edges = [(u, v + self.num_u) for u, v in self.edges]
	for from_, to in edges:
	g.make_edge(from_, to, 1)
	return g
	def bipartite_matching(bipartite_graph):
	"""
	Returns one of the combinations for the maximum bipartite matching
	"""
	# Convert to normal graph.
	g = bipartite_graph.to_graph()
	def dfs(v):
	used.add(v)
	for u in g.edges[v]:
	w = match.get(u)
	if w is None or w not in used and dfs(w):
	match[v] = u
	match[u] = v
	return True
	return False
	ret = 0 # maximum number of matching
	match = {} # result of matching
	for v in xrange(g.num_nodes):
	if not v in match:
	used = set()
	if dfs(v):
	ret += 1
	# Put back to bipartite graph's index.
	return [(u, v - bipartite_graph.num_u) for u, v in match.items() if u < bipartite_graph.num_u]
	if __name__ == '__main__':
	a = BipartiteGraph()
	for p, q in [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1)]:
	a.make_edge(p, q)
	#
	# 0 0
	# X
	# 1 - 1
	# X
	# 2 2
	#
	b = BipartiteGraph()
	for p, q in [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1), (2, 2)]:
	b.make_edge(p, q)
	#
	# 0 0
	# X
	# 1 - 1
	# X
	# 2 - 2
	#
	c = BipartiteGraph()
	for p, q in [(1, 0), (1, 2)]:
	c.make_edge(p, q)
	#
	# 0 0
	# /
	# 1 1
	# \
	# 2
	#
	d = BipartiteGraph()
	for p, q in [(0, 1), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3), (3, 2), (3, 4), (4, 3)]:
	d.make_edge(p, q)
	#
	# 0 0
	# X
	# 1 - 1
	# /
	# 2 - 2
	# X
	# 3 3
	# X
	# 4 4
	#
	for g in a, b, c, d:
	print bipartite_matching(g)

view raw a10_a_bipartite_matching.py hosted with ❤ by GitHub

output

[(0, 1), (1, 0)] [(0, 1), (1, 0), (2, 2)] [(1, 0)] [(0, 1), (1, 0), (2, 2), (3, 4), (4, 3)]

FizzBuzz Short Coding in Scala

Scala で FizzBuzz ショートコーディング

 

@lyrical_logical さんの素晴らしい資料からほぼ丸パクリ。

FizzBuzz golf in Scala - Google ドライブ

 

for(i<-1 to'd')println(Seq("Fizz"*(1-i%3)+"Buzz"*(1-i%5),""+i)max)

view raw FizzBuzzShortCoding.scala hosted with ❤ by GitHub

max を使う事で 1文字短縮でき、66 Bytes で書けた。

Algorithm: Testing If a Graph is Bipartite

二部グラフの判定

 

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	"""
	Check if the graph is bipartite.
	"""
	import collections
	class Graph(object):
	"""
	Simple graph model.
	"""
	def __init__(self, num_nodes):
	self.edges = collections.defaultdict(dict)
	self.num_nodes = num_nodes
	def make_edge(self, from_, to, value):
	self.edges[from_][to] = value
	def is_bipartite(graph):
	"""
	Returns True if the graph is bipartite.
	"""
	def bfs(v):
	q = [(v, 1)]
	while q:
	x, val = q.pop(0)
	if x in memo:
	continue
	memo[x] = val
	ts = graph.edges.get(x, {}).keys()
	if any(memo.get(a) == val for a in ts):
	return False
	q += [(a, -val) for a in ts]
	return True
	memo = {}
	return all(w in memo or bfs(w) for w in xrange(graph.num_nodes))
	if __name__ == '__main__':
	a = Graph(4)
	a.make_edge(0, 1, 1)
	a.make_edge(1, 2, 1)
	a.make_edge(2, 3, 1)
	a.make_edge(3, 0, 1)
	#
	# 0 - 1
	# | |
	# 3 - 2
	#
	b = Graph(5)
	b.make_edge(0, 1, 1)
	b.make_edge(0, 2, 1)
	b.make_edge(0, 3, 1)
	b.make_edge(0, 4, 1)
	#
	# 1 2
	# \ /
	# 0
	# / \
	# 4 3
	#
	c = Graph(3)
	c.make_edge(0, 1, 1)
	c.make_edge(1, 2, 1)
	c.make_edge(2, 0, 1)
	#
	#
	# 0 - 1
	# \ /
	# 2
	#
	print([is_bipartite(g) for g in (a, b, c)])

view raw a02_a_is_bipartite_graph.py hosted with ❤ by GitHub

output

[True, True, False]

Getting Started with Elixir - New Functional Programming Language

関数型言語 Elixir (エリクサー) を触ってみた

Erlang VM 上で動作する新しい関数型言語 Elixir (エリクサー) 。

FFファンならずともテンションの上がるネーミングだが
Ruby ライクなシンタックスで、動的型付けのカジュアルFPを目指しているようだ。

とりあえず環境を整えて、Hello world するまでの記録。

インストール

1 Introduction - Elixir　に従って作業すればOK。

• Erlang (R16B 以上) のインストール

  パッケージをここからダウンロードして実行
  Download Erlang OTP | Erlang Solutions 


• Elixir のインストール

  とりあえず、Mac にインストール。
  手っ取り早くインストールするなら HomeBrew で。

  $ brew install elixir

  最新版を入れるなら、以下の手順。

  $ cd <インストール先> $ git clone https://github.com/elixir-lang/elixir.git $ cd elixir $ make test $ bin/elixir -v    # Elixir のバージョンが表示されればOK $ sudo make install

  /usr/local/bin 配下にコマンドへのリンクが作成された。

iex - インタラクティブ シェル

モダンな言語なので当然(?)、REPL が標準で付いている。

• 起動

  $ iex Erlang R16B02 (erts-5.10.3) [source-b44b726] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]   Interactive Elixir (0.10.4-dev) - press Ctrl+C to exit (type h() ENTER for help) iex(1)>

• Hello world

  iex(1)> "Hello Elixir!" "Hello Elixir!" iex(2)> "こんにちは　エリクサー" "こんにちは　エリクサー" iex(3)> 'こんにちは　エリクサー' [12371, 12435, 12395, 12385, 12399, 12288, 12456, 12522, 12463, 12469, 12540]

  ダブルクオートで囲むと UTF-8 でエンコードされたバイナリとして、
  シングルクオートだと 1文字ずつの数値のリストとして認識される。

• FizzBuzz

  手探り状態で書いてみた。もっと改善できるはず。

  f = fn   x when rem(x, 15) == 0 -> "FizzBuzz"   x when rem(x, 3) == 0 -> "Fizz"   x when rem(x, 5) == 0 -> "Buzz"   x -> to_string(x) end   1..20 |> Enum.map(f) |> Enum.map(&1 <> "\n") |> IO.write

  文字列の連結(<>)が分からずに小一時間悩んだ。

  output

  iex:58: partial application without capture is deprecated 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz

  警告が出たけど、解決策がすぐには分からない。

 

まとめ

Erlang も Ruby も慣れていない私にはかなり異次元の文法に見える。
とはいえ、Erlang の強力な機能を利用したプログラムを手軽に実装できるなら魅力的だ。

日本人は最後までエリクサーを使わないという定説もあるけど、やっぱりそれはもったいない。

 

References

• Elixir
  公式サイト
• Shinjuku.ex
  日本最大? の Elixir 勉強会コミュニティ
• Try Elixir
  対話式のチュートリアル。すぐ終わるけど雰囲気は掴める。
• elixir cheat sheet
  ポイントが 2ページほどにまとまったチートシート
• Introducing Elixir - O'Reilly Media
  Early Release ながらオライリー本もある。
  今ならセール中 Save 50% on Functional Programming Ebooks & Videos - Deals - O'Reilly Media
• The Pragmatic Bookshelf | Programming Elixir
  こちらは完成された教科書。

Combinatorial Optimization: Merge-Sort Algorithm

組合せ最適化: アルゴリズム 1.2 マージソートアルゴリズム

B.コルテ/J.フィーゲン 著「組合せ最適化 理論とアルゴリズム 第2版」の例を Python で実装してみる。

 

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	"""
	Combinatorial Optimization - B.Korte, J.Vygen
	Algorithm 1.2
	Merge-Sort Algorithm
	"""
	def merge_sort(a):
	"""
	Recursive Merge-Sort
	Returns mapping function {0 .. n-1} -> {0 .. n-1}
	"""
	n = len(a)
	# step 1 (stopping condition)
	if n == 1:
	return lambda x: x # Returns identity mapping.
	# step 2 (call recursive function)
	m = n / 2
	r = merge_sort(a[:m])
	s = merge_sort(a[m:])
	# step 3 (merge two lists)
	ret = [None] * n
	k = 0
	l = 0
	while k < m and l < n - m:
	if a[r(k)] <= a[m + s(l)]:
	ret[k + l] = r(k)
	k += 1
	else:
	ret[k + l] = m + s(l)
	l += 1
	while k < m:
	ret[k + l] = r(k)
	k += 1
	while l < n - m:
	ret[k + l] = m + s(l)
	l += 1
	return lambda x: ret[x]
	def merge_sort_simple(a):
	"""Returns sorted list."""
	n = len(a)
	if n == 1:
	return a
	r, s = (merge_sort_simple(xs) for xs in (a[:n / 2], a[n / 2:]))
	ret = []
	while r and s:
	ret.append(r.pop(0) if r[0] <= s[0] else s.pop(0))
	return ret + r + s
	if __name__ == '__main__':
	for a in ([1, 3, 5, 2, 4, 90, -1, 0, -2],
	['ac', 'c', 'bc', 'ca', 'bb', 'b'],
	[9.9, 8.8, 7.7, 6.6, 5.5, 4.4, 3.3, 2.2, 1.1, 0.0]):
	f = merge_sort(a)
	print([a[f(i)] for i in range(len(a))])
	print(merge_sort_simple(a))
	print(sorted(a)) # builtin function

view raw a01_2_merge_sort_algorithm.py hosted with ❤ by GitHub

output

1 2 3 4 5 6 7 8 9

[-2, -1, 0, 1, 2, 3, 4, 5, 90] [-2, -1, 0, 1, 2, 3, 4, 5, 90] [-2, -1, 0, 1, 2, 3, 4, 5, 90] ['ac', 'b', 'bb', 'bc', 'c', 'ca'] ['ac', 'b', 'bb', 'bc', 'c', 'ca'] ['ac', 'b', 'bb', 'bc', 'c', 'ca'] [0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9] [0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9] [0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9]

identity が出てくるのが面白い。

Combinatorial Optimization: Path Enumeration Algorithm

組合せ最適化: アルゴリズム 1.1 パス列挙アルゴリズム

B.コルテ/J.フィーゲン 著「組合せ最適化 理論とアルゴリズム 第2版」の例を Python で実装してみる。

 

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	"""
	Combinatorial Optimization - B.Korte, J.Vygen
	Algorithm 1.1
	Path Enumeration Algorithm
	"""
	def back_track(n):
	"""Generate all permutations of 0 .. n-1"""
	# step 1: initialize
	p = range(n)
	yield p
	i = n - 2
	while i >= 0:
	# step 2: find 'k'
	aux = [False] * n
	for j in range(i):
	aux[p[j]] = True
	k = p[i] + 1
	while k < n and aux[k]:
	k += 1
	# step 3
	if k < n:
	p[i] = k
	if i == n - 1:
	yield p
	if i < n - 1:
	p[i + 1] = -1
	i += 1
	if k == n:
	i -= 1
	def minimum_path(points):
	def distance(p, q):
	return max(abs(p[0] - q[0]), abs(p[1] - q[1]))
	ret = None
	n = len(points)
	for p in back_track(n):
	x = sum(distance(points[p[i]], points[p[i + 1]]) for i in range(n - 1))
	if not ret or x < ret[0]:
	ret = (x, [points[i] for i in p])
	return ret
	if __name__ == '__main__':
	import itertools
	for x in back_track(4):
	print x
	print len(list(back_track(5)))
	# Using built-in function.
	for x in itertools.permutations(range(4)):
	print x
	print minimum_path([(1, 1), (5, 2), (1, 4), (3, 3), (4, 8), (2, 10)])

view raw a01_1_path_enumeration_algorithm.py hosted with ❤ by GitHub

output

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

[0, 1, 2, 3] [0, 1, 3, 2] [0, 2, 1, 3] [0, 2, 3, 1] [0, 3, 1, 2] [0, 3, 2, 1] [1, 0, 2, 3] [1, 0, 3, 2] [1, 2, 0, 3] [1, 2, 3, 0] [1, 3, 0, 2] [1, 3, 2, 0] [2, 0, 1, 3] [2, 0, 3, 1] [2, 1, 0, 3] [2, 1, 3, 0] [2, 3, 0, 1] [2, 3, 1, 0] [3, 0, 1, 2] [3, 0, 2, 1] [3, 1, 0, 2] [3, 1, 2, 0] [3, 2, 0, 1] [3, 2, 1, 0] 120 (0, 1, 2, 3) (0, 1, 3, 2) (0, 2, 1, 3) (0, 2, 3, 1) (0, 3, 1, 2) (0, 3, 2, 1) (1, 0, 2, 3) (1, 0, 3, 2) (1, 2, 0, 3) (1, 2, 3, 0) (1, 3, 0, 2) (1, 3, 2, 0) (2, 0, 1, 3) (2, 0, 3, 1) (2, 1, 0, 3) (2, 1, 3, 0) (2, 3, 0, 1) (2, 3, 1, 0) (3, 0, 1, 2) (3, 0, 2, 1) (3, 1, 0, 2) (3, 1, 2, 0) (3, 2, 0, 1) (3, 2, 1, 0) (13, [(5, 2), (3, 3), (1, 1), (1, 4), (4, 8), (2, 10)])