私が歌川です

@utgwkk が書いている

ボタンを押すとそのボタンと周囲4近傍のボタンの ON/OFF が反転して,全てのボタンを ON にすればクリアのパズルゲームを解くやつ(5x5はライツアウトと言うらしい)の3x3の場合のソルバを書いて,考察してみる

記事タイトルが長すぎる.

はじめに

みなさんは,ボタンを押すとそのボタンと周囲4近傍のボタンの ON/OFF が反転して,全てのボタンを ON にすればクリアのパズルゲーム(5x5はライツアウトと言うらしい)をやったことがありますか? 私はああいったパズルが苦手で,なかなか解くことができません.

したがって,機械に頼ることになります.

ソースコード

gist.github.com

解説

C++11 以降を使わないとコンパイルできません.

場の状態は,下の表の対応するビット(下から数えたビットの位置,1-index)が立っているかどうかで表されています.

0 1 2
0 9 8 7
1 6 5 4
2 3 2 1

したがって,例えば 0b010001110 は,次のような場の状態を表しています.

0 1 2
0 OFF ON OFF
1 OFF OFF ON
2 ON ON OFF

ボタンを押すと ON/OFF が反転する,という操作は排他的論理和によって表されるので,これによって次に遷移するべき状態を網羅することができます. そして,場の状態を頂点,ボタンの押し方を辺とすると,これは初期状態から目的状態への最短経路問題を解くことに帰着されます.

私はダイクストラ法を実装しました*1

startgoal を適宜変更して実行すると,最短手数とその解き方が表示されます.

解の存在性

さて,全ての問題(初期状態と目的状態の組)に対して解が存在するのか,という疑問が生じてきます.

まず,初期状態として 0b000000000 を考えることにします.

次に,目的状態として 0b1000000000b0100000000b000010000 の3つの状態を考えます. それぞれ,「左上のみON」「真ん中上のみON」「真ん中のみON」を表しています.

この3つの組に対して,上記のプログラムに入力として与えて(goal を書き換えて)実行したところ,結果は以下の通りになりました.

0b0000000000b100000000

5
0,0
2,0
2,1
0,2
1,2

0b0000000000b010000000

4
1,1
0,2
1,2
2,2

0b0000000000b000010000

5
1,2
2,1
1,1
1,0
0,1

どうやらこの3つの組に対しては解が存在します. そして,「全てのボタンがOFFの状態から始めて,9つのボタンのうちどれか1つだけをONにする」という場合は,先述した3つの操作をそれぞれ線対称/(1,1)に対して90度回転,などしてやれば網羅することができます.

これらの解は,どれも「最終的には,目的とするボタン以外のボタンのON/OFFは変化させずに,目的のボタンのみをONにする」という操作になっています.

さらに,あらゆる初期状態とあらゆる目的状態に対して,いま生成された9つの操作を組み合せて所望の状態にし,奇数回行った操作は1回分だけ残し,偶数回行った操作は除外してやれば,最短解を生成することができます.

こうして,全ての組合せに対して最短解が存在することが分かりました.

5x5 の場合

5x5 の場合は実装していないのですが,興味深い考察をしているサイトがありました.

場合によっては解が存在せず,パズルの解の存在条件は連立合同方程式を解くことによって導出することができる,とのことです.

おまけ

ボタン(略)ゲームの体感ができるページをだいぶ前に作ってました.

初期状態を与えることができない仕様になっている…….

*1:最短経路となる押し方を記録したかったんだけど,幅優先探索でもできそう??

『プリンシプル オブ プログラミング 3年目までに身につけたい一生役立つ101の原理原則』を読んだ

私は-3年目です.

コードをただ漠然と書いているとそのうち破綻する. したがって先人の知恵とか,有益な慣習とか,そういったものに従ってうまくやっていくしかない. それらのことが101個も掲載され,詳細に説明されている本です.

具体的なコードの書き方よりは,コードを書く際のベターな思考法を述べた本であるといえましょう. こういうことを知っておくと,将来,とくに多人数で協調するときに大いに役に立つかと思われます.

ところで私は,最初からこうできないと失格である,とは思っていなくて,泥臭いところから始めてどれだけ洗練されていくかが重要だと考えています. 手を動かすところまでが一セットです. そしてこれは自戒でもあります.

カワイイボクと生活の質

はじめに

これは アイドルマスター Advent Calendar 2016 12/12分の記事です。

www.adventar.org

@utgwkk です。知り合いにデレステを勧められたところ、瞬く間にハマってしまいました。したがって新人です。

カワイイボク

みなさんは、カワイイですか? カワイイボクも、そうでないと思っているボクも、生きているといろいろなことがあります。 ここでは、カワイイボクになりきって生活をうまくやっていく方法を伝授していこうと思います。

苦しいとき

苦しいのは、神様がボクの余りのカワイさに嫉妬していて、ボクに試練を与えているためです。

楽しいとき

楽しいのは、ボクが余りにカワイイので世界が平和になっているからです。

勉強をしているとき

カワイイボクの書くノートは当然カワイイので、ノートも分かりやすくなります。これをカワイさの継承と言います。

運動をしているとき

カワイイボクはカンペキなので、運動も人一倍できるんですよ! フフーン!

それに、運動は健康にとても良いですからね!

カワイイ人を見つけたとき

ボクほどではないけどカワイイ人も、きっといろいろなことを乗り越えてきたのでしょうね。話を聞いてみると、何か学びがあるかもしれませんよ!

カワイイコミュニティーの中ではボクが一番かもしれませんが、他の人の話を聞くともっとカワイくなれるかもしれません。

おわりに

いかがでしょうか? カワイイボクの方は、もっとカワイくなっていきましょう。 そうでもないボクの方は、これを機に、自分に自信が持てるようになっていきましょう。

次回予告

次回は @raka3456 さんで「ゲッサンミリオン完結に寄せて」です。楽しみですね。

今年買ってよかったもの

お題その2「今年、買ってよかった物」

大判本も入って値段も手頃なのでよかった。

USBポートが5つあって、同時にいっぱい充電できて最高。友達が泊まりにきたときに重宝した。

冬に備えて買った。しっかり手の保温をしてくれるので便利。

特別お題「2016年を買い物で振り返ろう」 sponsored by 三菱東京UFJ-VISAデビット

Python の unittest で標準出力に表示される内容のテストをする

tl;dr

  • 出力する文字列を生成する関数を作り、そのテストを書くべきだと私は思う
  • sys.stdout をキャプチャすれば表示内容のテストが書ける
  • test.support.capture_stdout()コンテクストマネージャを使うべき
  • そもそも unittest でやるべきではない

はじめに

いろいろな環境があります。ほとんど標準ライブラリしか使えないとか、莫大な量の print があるとか、いろいろあります。 我々はそういった環境においてもやっていくことになります。したがって、やっていきましょう。

暗黙のうちに Python 3.5 以降を前提としています。

sys.stdout をキャプチャする

コード

import sys
from io import StringIO

io = StringIO()

# 標準出力を io に結びつける
sys.stdout = io

print('hoge')

# 標準出力を元に戻す
sys.stdout = sys.__stdout__

print('captured: {}'.format(io.getvalue())) # captured: hoge\n

解説

ご存知の通り、UNIX 世界において標準出力はファイルです。そして、Python においてもそうです。 さらに、Python にはファイルを模倣したようなオブジェクトが用意されています。それが io.StringIO です。 これを sys.stdout に放り込めば、標準出力を変数にリダイレクトするといったことができます。

import sys
from io import StringIO

io = StringIO()
sys.stdout = io

さてあとは普段通りに print するだけです。そうすると、io に、出力されるはずだった文字列が蓄積されていきます。

print('this')
print('is')
print('test')

満足しましたか? それでは io に蓄積されたものを見ていきましょう。おっと sys.stdout を元の標準出力に戻すことを忘れずに。

sys.stdout = sys.__stdout__
print('captured: {}'.format(io.getvalue()))

sys.__stdout__ には、プログラム起動時の標準出力を示すオブジェクトが格納されています。 こうして、我々は標準出力に表示される内容をキャプチャする方法を知りました。

標準出力に表示される内容のテストを書く

コード

import sys


def method_one():
    print('called method_one()')


def method_two():
    print('called method_two()')
    print('not captured', file=sys.stderr)
import sys
import unittest
import hoge
from io import StringIO


class HogeTest(unittest.TestCase):
    def setUp(self):
        self.captor = StringIO()
        sys.stdout = self.captor

    def tearDown(self):
        sys.stdout = sys.__stdout__

    def test_method_one(self):
        hoge.method_one()
        self.assertEqual(self.captor.getvalue(), 'called method_one()\n')

    def test_method_two(self):
        hoge.method_two()
        self.assertEqual(self.captor.getvalue(), 'called method_two()\n')

if __name__ == '__main__':
    unittest.main()

解説

さて、キャプチャされた文字列を取得する方法まで分かれば、あとは unittest の流儀に沿って書いていけばよいです。 改行コードのことだけ忘れないように!

まとめ

もっとテストの書きやすい設計にしてくれ

局所最適を狙うこと

www.adventar.org

こんにちは。今月は仕送りが例月より-2万円されているので、覚悟を持ちながら暮らしております。人間はいつか必ず覚悟しなければならない時が来ます。

さて、人が生きるからには、交渉があります。両親、親族、交友、学校、職場、社会、……。我々は嫌でも交渉の連続のうちに身を置かなければなりません。我々の目標とすることはやはり大域最適解でありますが、常にそうしていけるとも限りません。そこに事情があります……。

私はつい最近までは、たいていの場合においては局所最適解を狙うような振舞いをしておりました。それは負担が軽く、また失うものも比較的少なかったため、もう少し言えば現状維持にかなり近かったためです。そして今でもそうしているつもりなのですが、果たして本当にそうできているのかにはいささか疑問があります。またそのような姿勢でないという指摘も受けるようになったと感じています。打算的に動くという感覚を忘れつつあるような気がしており、社会に絶対に飲まれないという決意を再び固めるよりほかにありません。

生きることは、近似解を求めることの連続です。近似を繰り返すことによって、我々はいつしか大域最適解に辿り着くことを夢見ています。そこに人がいる限りは難しそうであるという現状に目を背けつつ……。

これは 局所最適解 Advent Calendar 2016 - Adventar の記事です。

あわせて読みたい

utgwkk.hateblo.jp

こふ語の変化(souiukannjide)

はじめに

この記事は「こふ語 / ブチミリ Advent Calendar 2016」12/5の記事です。

www.adventar.org

前回の担当は、あっきぃさんでした。

akkiesoft.hatenablog.jp

記事自体をこふ語で書くことを考えましたが、けんこふさんがやってくれていると思うので割愛します。

こふ語とは

こふ語とは、アッシュヒョークを持つ京都で産声を上げた言語です。日本語にかなり似た性格を持っているため、日本語の方言とも考えられています。表立った特徴としては、

  • 半角カタカナ
  • 句読点を用いない文
  • 文節区切り*1の「っ」
  • アンッ!アンッ!アンッ!アンッ!

先行研究

こふ語話者の数に対して、こふ語に関する研究文献は、まだ数が多いとは言えません。

karubabu.hateblo.jp

この記事には、こふ語初心者がこふ語を使って意思疎通をしたいときに何をするとよいか、またこふ語の綴りに関する問題などが記述されています。

手前味噌ですが、私は昨年のこの時期に、京都で生まれたこふ語と北海道(ゆきすごいところ)で生まれたかるなべ語を関連付けた記事を執筆しました。

utgwkk.hateblo.jp

こふ語の変化

私がこふ語の変化——というよりは、こふ語における新文法といったほうが適切だろうか——に気づいたのは、10月末のことでした。

また、次の例にはさらに高度なこふ語の新文法が用いられています。

おわりに

宇宙に飛び去ってしまったとされている「こふ語研」、かるなべ語との融合、——謎は深まるばかりのこふ語の情勢、我々がこの先生きのこるにはどうすればよいか——

次回はかるはげくん (id:karubabu) の「こふろいどさんをフォローして月旅行を当てよう! - karubabuの日記」です。

*1:必ずしもそうとは限らないが、そのようにすると意思疎通がしやすいと筆者は考えています。