LoginSignup
2
0

More than 3 years have passed since last update.

@HMMNRST

社内Slackに #algorithm チャンネルを作って毎週ネタ投下した記録

Posted at

タイトル通りです。どうにか3ヶ月間に渡って続けられたので、一旦まとめることにしました。

ネタ＋αは以下の3パターンに分かれています。詳細な項目はQiita右側の目次を参照してください。

  • 出題系
  • 知識共有系
  • （他の人からの情報提供）

※記録を書き連ねているだけであり、取り組み全体への考察などはありません。

チャンネルの様子

本来望んでいた状態

Purpose: 「問題を機械に解かせる方法」をみんなで考えるチャンネルです。仕事で必要な計算、プライベートで出会った問題などを持ち込んだら、誰かが解決してくれるかもしれません。

競技プログラミング的なものが好きな人（私など）が、その能力を活かして他の社員の役に立てれば、お互いに幸せだよね。という気持ちでチャンネルを作りました。

また、「アルゴリズム」というもの自体に興味を持ってくれたら嬉しいという気持ちもあります。プログラミング技術は必須ではないため、サーバー／ネットワークエンジニアの人でも楽しめる可能性があります。

アルゴリズムとは何か (一般人向けの解説) - 国立情報学研究所

「アルゴリズム」というのは、コンピューターで計算を行うときの「計算方法」のことなんですが、広く考えれば、何か物事を行うときの「やり方」のことだと言っていいでしょう。

例：おやつ選び

子供が遠足に行くので、300円以内でなるべくたくさんのお菓子を持たせたい。どう選べばいいか？

もちろんこれだけの情報では適切な回答ができません1ので、質問者に聞き取りして条件を明確にしていく必要があります。

実際の状況

まだ誰も問題を持ち込んでくれないので、自分が知っている面白そうなものを紹介して場を繋ぎ続けています。

出題系

「アルゴリズム」というものに興味を持ってもらうため、例題同様に身近なところにある具体的な問題を出しています。ただ、問題を作るのがとても難しくて量を提供できていません…。

年齢当て

ある社員から年齢を聞き出そうとした。直球で聞くのは気が引けたので、いくつかの数で割った余りだけを聞いた。返答は以下の通り。

「私の年齢は、3で割ると2余り、4で割っても2余り、5で割ると3余ります。」
  1. その社員の年齢はいくつか？
  2. 余りが他のパターンの場合はどう求めればいいか？

反応：

  • (正答)歳か(正答+60)歳だよね。(正答+120)歳は長寿記録的に考えにくい。
  • 総当たりくらいしか思いつかないけど、かっこいい方法あるの？

百五減算を元に数字を変えた問題です。数式で求める方法はもちろんあり、中国の剰余定理によって数式を導けますが、この程度なら総当たりで解いても構わないと思っています。

山手線の方向選択

山手線内回りにおける、前駅からの距離と所要時間の一覧を添付した。これを元に、乗降駅の番号が与えられたとき内回りと外回りのどちらが早く着くか判定しなさい。

※正確な時間で判定したいときは、これでなく乗換案内で調べましょう。

snippet: yamanote.csv
yamanote.csv
#,駅名,距離[km],時間[分]
1,東京,0.8,2
2,神田,1.3,2
3,秋葉原,0.7,2
4,御徒町,1.0,2
5,上野,0.6,2
6,鶯谷,1.1,2
7,日暮里,1.1,2
8,西日暮里,0.5,2
9,田端,0.8,2
10,駒込,1.6,2
11,巣鴨,0.7,2
12,大塚,1.1,2
13,池袋,1.8,2
14,目白,1.2,3
15,高田馬場,0.9,2
16,新大久保,1.4,2
17,新宿,1.3,2
18,代々木,0.7,2
19,原宿,1.5,2
20,渋谷,1.2,3
21,恵比寿,1.6,2
22,目黒,1.5,3
23,五反田,1.2,2
24,大崎,0.9,2
25,品川,2.0,3
26,高輪ゲートウェイ,1.3,2
27,田町,0.9,2
28,浜松町,1.5,3
29,新橋,1.2,2
30,有楽町,1.1,2

反応：

  • 内回りでの駅間の時間 > 一周の合計時間/2 で判定ぐらいしか浮かばなかった。
  • 高輪ゲートウェイ ← 気が早いｗ
  • 時間や距離のデータを見てみんな雑談

最初の反応がほぼ答えですが、累積和によって駅間の時間を計算することを想定しています（そのためにデータを「前駅からの所要時間」にし、新駅追加で欠番を埋めました）。新駅を抜いた場合についてはその後Qiitaにまとめました。 → 山手線の2駅間の所要時間を計算

「こおりのぬけみち」

ポケモン金銀のダンジョン「こおりのぬけみち」。この中の迷路（添付ファイル参照）を抜ける手順を見つけるアルゴリズムを考えてください。

参考： https://dic.nicovideo.jp/a/こおりのぬけみち

snippet: ice_path_map.txt
ice_path_map.txt
17x15
#################
#        #     ##
#   #          ##
#         #    ##
# #            ##
##       #     ##
#             ###
#      #       G#
#  #           G#
#             ###
#       #      ##
#     #   #    ##
#              ##
##############S##
#################

凡例
#:岩。プレイヤーは通れない。
 :氷の床。プレイヤーは岩にぶつかるまで止まらない。
S:スタート地点。ここも氷の床と考えて構わない。
G:ゴール地点。複数あるうちのどこに着いてもよい。ここも氷の床と考えて構わない。

幅優先探索が便利な問題です。盤面の広さのわりに状態が少ないため、手作業で解いてもさほど大変ではありません。

地図に順路を加えて出力するコードを書いてくれた人がいました（クリスタル版の迷路でもきちんと動作しました）。チームメンバーに聞いたところ、絵で見れる問題は楽しいと感じるようです。

手作りケーキでゲーム

クリスマスっぽい確率の問題をシミュレーションで解きましょう。（※元ネタを知っている人はネタばらし厳禁）

snippet: 「当たり」のケーキ
「当たり」のケーキ
親がケーキを4個作った。そのうち1個だけは、中にイチゴが丸ごと入っている「当たり」である。次の手順で子と簡単なゲームをする。
​
1. 子は「当たり」を狙って、食べるケーキを1個選ぶ。（※外見では見破れない）
2. 親は答えを知っているので、子が選ばなかったケーキのうち「ハズレ」を1個取って中を見せる。
3. 子はその様子を見て、食べるケーキを選び直せる。
​
このとき、子は「当たり」を引くためにどうするのが適切か？
​
* 選び直す（他の2個から選択する）
* 最初に選んだもののままにする
* どちらでも変わらないので気にしない
​
※残った2個のケーキは、親子で仲良く食べました。

反応：

  • 元ネタを知っているので黙秘。
  • 元ネタは知ってるけど腹落ちしてない。
  • 実測値見て確率の計算方法を理解した。
  • 確率論だけでなく心理学的な研究も盛んということで、興味深い。
    → http://the-apon.com/coffeedonuts/problems.html

モンティ・ホール問題を題材に、数字を少し変えた問題です[^monty-hall]。ゲームマスターのみが当たりを知っている状況を作るのに何が良いか考えた結果、単純にクリスマスが近かったので手作りケーキにしました。

最初に「シミュレーションで」と書いておいたので、アルゴリズムとしてはモンテカルロ法を想定しています。何人かが実装して、みんな妥当な確率を導けていました。ルールに対して別の解釈や仮定をした人はいなかったようです。

[^monty-hall]: 親が取り除く「ハズレ」の候補が常に2個以上になるため、ルールを理解しやすいと考えました

敷き詰めパズル

地図の空き領域に、その下に列挙したピースを全て収めてください。ピースは回転させてもいいですが、裏返してはいけません。

snippet: puzzle#42
puzzle#42
###########
###.....###
##.###...##
#..#......#
#.........#
##.......##
###.....###
####...####
#####.#####
###########

.......
.#####.
.......
.#.....
.####..
.......
.##....
..###..
.......
.###...
..##...
.......
.#.....
.##....
..##...
.......
.#.....
.###...
..#....
.......
.##....
.##....
.......
.###...
..#....
.......
.##....
..##...
.......

反応：

  • なんもわからん（Slack絵文字）

私が遊んでいる某ゲームのミニゲームに出てくる問題のひとつです。攻略まとめwikiに全問の解答があるのでパズルが苦手でもクリアできますが、それを見たら負けな気がしたので妥協点としてプログラミングして解いた過去があります。

単純には深さ優先探索で再帰的に考えることになるでしょう。ピースをひとつ仮置きすれば、残りの空き領域とピースが減り、より小さな問題を解くことになります。こうして最後まで置ければ成功で、詰んだら戻ってピースの位置を変えて再度解く、ということを繰り返します。ただし、人間ならすぐ除外するような置き方[^piece]まで試してしまうため、あまり効率は良くないと思われます。

数学的には集合の厳密被覆（exact cover）[^ecp]に関係し、パズルでは数独などにも適用できます。有名な解法はクヌースのAlgorithm Xで、特にdancing linksという手法と組み合わせたものはDLXと呼ばれます。Xも深さ優先探索ですが、選択肢の少ないところ[^x]から試すよう実装できます。

正月休みで十分な時間があるため出した問題であり、実装までするとなれば他と比べて桁違いに難しいです。アルゴリズムの本質に集中しやすいよう、1次元にして簡略化した問題も作りました。

ヒント、というか簡易版の問題です。
1行目の空き領域に、下3行のピースをはめ込んでください。（回転可 不要）

snippet: puzzle-1D
puzzle-1D
#.#.........#..#

#..#.##
#.#..##
##...##

[^piece]: この問題であればピースの大きさが4以上なので、3マス以下の空き領域ができてしまう置き方は解になり得ません
[^ecp]: 用語の日本語訳は「Knuth先生の『TAOCP 7.2.2.2 Satisfiability』を読む」より引用しました
[^x]: 「このピースを置けるのは2ヶ所だけ」や「このマスを埋められるのは3ピースだけ」という感じです

知識共有系

「世の中にはこんな考え方、テクニックがあるよ」というものの紹介です。業務中の些細な疑問から見つけたものも含んでいます。

Hashlife

アルゴリズムによって爆速になる例として最初に投下しました。しかしライフゲーム自体そんなに馴染みが無さそうで、方向性を間違ったと感じました…。

簡単に実装できる「ライフゲーム」も、優れたアルゴリズムだと大規模なパターンを超々々高速でシミュレーションできるようになる

https://en.wikipedia.org/wiki/Hashlife

The 6,366,548,773,467,669,985,195,496,000 (6 octillionth) generation of a Turing machine in Life computed in less than 30 seconds on an Intel Core Duo 2GHz CPU using Hashlife in Golly.
（ライフゲームに構築したチューリングマシンの約6000𥝱世代目の様子。シミュレーションソフトGollyに実装されたHashlifeエンジンを使い、Intel Core Duo 2GHz CPUによって30秒未満で計算された。）

反応：

  • 「メモ化」という手法を初めて知った。

ビットカウント

出題風ですが、身近ではないだろうということで知識共有側の扱いです。ネットワークエンジニアならIPアドレスなどでビットの扱いに慣れているかもしれないと思い、ビット演算に関する話題を選んでみました。

ある整数について、フラグ :triangular_flag_on_post: が立っている個数（ビットが1の個数）を数える "population count" 。

例えば十進数の 20191003 は二進数で 00000001001101000001011100011011 なので、個数は12になる。これをなるべく速く数えるにはどうするか？

※言語によって違いが出ると思うので、ひとまず「C言語・32bit整数」で。ライブラリやCPU命令は禁止。

その後、複数の手法を試しているページを紹介しました。

いくつかの方法をまとめている記事。ビット演算なので難しいが、性能測定だけ見ても楽しいかも。
http://www.nminoru.jp/~nminoru/programming/bitcount.html

反応：

  • ループを使わずに求められることに驚き。
  • bits &= bits - 1 って何をやっているの？？？[^bit-tech]

[^bit-tech]: 一番下に立っているフラグを降ろします（例： 0b1010 → 0b1000 ）

変数の入れ替え

ビット演算を利用した話をもう少ししたくて、「XOR交換アルゴリズム」があったので紹介しました。

一時変数を使わずに中身を入れ替え（使う機会はまず無い）

swap_integers.py
a, b = 2019, 1017
print(a, b)
​
if a != b:
    a ^= b
    b ^= a
    a ^= b
​
print(a, b)

文字列の繰り返し

案件で文字数制限のテストを書く際に、「Javaで文字列の繰り返しに良い方法は無いか」という話が出たのがきっかけです。Java以外でも使える場面がありそうです。

文字列の繰り返し str * n を古いjavaでやる技があったので共有。賢い。
https://stackoverflow.com/a/4903603/9140111

Java
str.repeat(n); // Java >= 11
​
new String(new char[n]).replace("\0", str); // Java >= 1.5

反応：

  • JavaならcommonsのStringUtilsにあるよ。
  • n < 0 のときの動作を検証
    • Java11のメソッドだと例外発生
    • StringUtilsだと空文字列
    • Pythonでも空文字列

そうしていたら別解が現れました。Javaでは利用しにくいですが、言語によっては使える…？

Go
import (
  "strings"
  "fmt"
)

func main(){
  n := 5
  s := make([]string, n+1)
  x := strings.Join(s, "a")
  fmt.Println(x)
}

並列処理

案件の中で私自身が並列処理の知識に弱いと感じて投下しました。

https://ja.wikipedia.org/wiki/食事する哲学者の問題

そしたら並列処理について書いてある本をいくつか貸してくれました。

JSFuck

完全にネタ枠です。

JavaScriptは6つの記号だけで書ける
https://github.com/aemkei/jsfuck

反応：

誕生日攻撃

これもネタ枠です。とはいえちょっと気になっています。

「誕生日攻撃」という言葉を聞いて、一般人は何を想像するだろう

反応：

  • :scream:
  • :scream:
  • :scream:

正規表現と有限オートマトン

別のチャンネルでオートマトンなどの理論に興味を持っている人がいたので投下しました。

以前に遊びで作った正規表現。

bash
PATTERN='^([0-9]*((0[48]|[2468][048]|[13579][26])(00)?|0000)|[048]?(00)?)$'
seq 2001 2400 | grep -E "${PATTERN}"

その後、これをε-NFAやDFAに変換した図を貼り付けていきました。何にマッチするのかは内緒のままです。

反応：

  • 00 や 000 にもマッチするのが奥ゆかしい。
  • 有限状態機械で覚えていて、オートマトンとも言うのは知らなかった。
  • 『正規表現技術入門 最新エンジン実装と理論的背景』
    • 会社の本棚にあるよ。
    • amazonポチります！

ネタ元 → 閏年を判定する正規表現を構築し、その完全性を理論的に検証

他の人からの情報提供

グラフ彩色

そういえば、グラフ彩色について勉強してたら「数独も一種のグラフ彩色」って書いてあって衝撃を受けました。
確かに色分けが数字に置き換わっただけだもんな... :thinking:

https://ja.wikipedia.org/wiki/グラフ彩色

グラフ理論入門

グラフ理論の入門にいい本ないですか？

↓

調べたらまとめられていました。

「グラフ理論」と「組み合わせ最適化アルゴリズム」の教科書PDF。離散数学の入門用の教科書 - 主に言語とシステム開発に関して

ゲームの地形生成

ゲームの地形生成アルゴリズム、楽しそうです。結果が視覚的に確認できるのもモチベーションに

ゲーム開発 - 地形生成 アルゴリズム | SPLOUT BLOG

あとがき

発信に対する反応はあり、違う視点からの知識ももらえるため、そこそこ楽しくやれています。本来望んでいた状態である、色々な人が問題を持ち込んでくれるようになるまでは、頑張って続けていきます。

  1. 「5円チョコを55枚買う」（＝297円）という回答が出ました ↩

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0