どきどきトロッコ


(今回楽過ぎませんか…あーでも、これぐらいの難易度のほうが安心できる…)

ちなみにメモ化は趣味。今回の問題サイズならメモ化しなくても十分高速に解けます。

## Ruby

`||=`を使っていないのはnilもfalseもfalseyだからです。若干悔しい。

```rb:tyama_henae05.rb
#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/c516875b13a4d282affe
#http://nabetani.sakura.ne.jp/hena/orde05dokitruck/

T={
	1=>{0=>[0,1],1=>[1,2],2=>[2]},
	2=>{0=>[0,2],1=>[1],2=>[1,2]},
	3=>{0=>[0,2],1=>[0,1],2=>[2]},
	4=>{0=>[0],1=>[0,1],2=>[1,2]},
	5=>{0=>[0],1=>[1,2],2=>[0,2]},
	6=>{0=>[0,1],1=>[1],2=>[0,2]},
	7=>{0=>[0],1=>[],2=>[2]},
	8=>{0=>[],1=>[1],2=>[2]},
	9=>{0=>[0],1=>[1],2=>[]},
}

def dfs(d,cur)
	return true if d==$line.size
	return $m[[d,cur]] if $m.has_key?([d,cur])
	$m[[d,cur]]=T[$line[d]][cur].any?{|e|dfs(d+1,e)}
end

if __FILE__==$0
	while gets
		$line=$_.chomp.chars.map(&:to_i)
		$m={}
		r=(0..2).select{|e|
			dfs(0,e)
		}.map{|e|(e+97).chr}*''
		puts r.empty? ? '-' : r
		STDOUT.flush
	end
end
```

## C++

よく考えたら[nil].any?も[].any?もfalseだったので、nilが使えないC++でも実装できるでしょと。
initializer-listが使えない言語は知らない。

```cpp:tyama_henae05.cpp
//http://qiita.com/Nabetani/items/c516875b13a4d282affe
//http://nabetani.sakura.ne.jp/hena/orde05dokitruck/
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

map<int,map<int,vector<int>>>T={
	{1,{{0,{0,1}},{1,{1,2}},{2,{2}}}},
	{2,{{0,{0,2}},{1,{1}},{2,{1,2}}}},
	{3,{{0,{0,2}},{1,{0,1}},{2,{2}}}},
	{4,{{0,{0}},{1,{0,1}},{2,{1,2}}}},
	{5,{{0,{0}},{1,{1,2}},{2,{0,2}}}},
	{6,{{0,{0,1}},{1,{1}},{2,{0,2}}}},
	{7,{{0,{0}},{1,{}},{2,{2}}}},
	{8,{{0,{}},{1,{1}},{2,{2}}}},
	{9,{{0,{0}},{1,{1}},{2,{}}}},
};

string line;
map<pair<int,int>,bool>m;

int dfs(int d,int cur){
	if(d==line.size())return true;
	if(m.find({d,cur})!=m.end())return m[{d,cur}];
	return m[{d,cur}]=any_of(
		T[line[d]-'0'][cur].begin(),
		T[line[d]-'0'][cur].end(),
		[&](int e){return dfs(d+1,e);}
	);
}

int main(){
	for(;getline(cin,line);){
		m.clear();
		string r;
		for(int i=0;i<3;i++)if(dfs(0,i))r+=i+'a'; // charキャスト不要でした
		cout<<(r.empty()?"-":r)<<endl;
	}
}
```

## Crystal

Crystalだと逆に[nil]の方が書きやすそうです。

```rb:tyama_henae05.cr
#!/usr/bin/env crystal
#http://qiita.com/Nabetani/items/c516875b13a4d282affe
#http://nabetani.sakura.ne.jp/hena/orde05dokitruck/

T={
	1=>{0=>[0,1],1=>[1,2],2=>[2]},
	2=>{0=>[0,2],1=>[1],2=>[1,2]},
	3=>{0=>[0,2],1=>[0,1],2=>[2]},
	4=>{0=>[0],1=>[0,1],2=>[1,2]},
	5=>{0=>[0],1=>[1,2],2=>[0,2]},
	6=>{0=>[0,1],1=>[1],2=>[0,2]},
	7=>{0=>[0],1=>[nil],2=>[2]},
	8=>{0=>[nil],1=>[1],2=>[2]},
	9=>{0=>[0],1=>[1],2=>[nil]},
}

def dfs(d,cur)
	return true if d==$line.size
	return $m[[d,cur]] if $m.has_key?([d,cur])
	$m[[d,cur]]=T[$line[d]][cur].any?{|e|e&&dfs(d+1,e)}
end

while line=gets
	$line=line.chomp.chars.map(&.to_i)
	$m=Hash(Array(Int32),Bool).new
	r=(0..2).select{|e|
		dfs(0,e)
	}.map{|e|(e+97).chr}.join
	puts r.empty? ? "-" : r
	STDOUT.flush
end
```

## Python

**`r or '-'`と書けるのがなにげに嬉しい。**

```py:tyama_henae05.py
#!/usr/bin/env python
#http://qiita.com/Nabetani/items/c516875b13a4d282affe
#http://nabetani.sakura.ne.jp/hena/orde05dokitruck/

T={
	1:{0:[0,1],1:[1,2],2:[2]},
	2:{0:[0,2],1:[1],2:[1,2]},
	3:{0:[0,2],1:[0,1],2:[2]},
	4:{0:[0],1:[0,1],2:[1,2]},
	5:{0:[0],1:[1,2],2:[0,2]},
	6:{0:[0,1],1:[1],2:[0,2]},
	7:{0:[0],1:[],2:[2]},
	8:{0:[],1:[1],2:[2]},
	9:{0:[0],1:[1],2:[]},
}

def dfs(d,cur):
	if d==len(line): return True
	if (d,cur) not in m: m[(d,cur)]=any(dfs(d+1,e) for e in T[line[d]][cur])
	return m[(d,cur)]

import sys
for l in sys.stdin:
	line=list(map(int,l.strip()))
	m={}
	r=''.join(chr(e+97) for e in range(3) if dfs(0,e))
	print(r or '-')
	sys.stdout.flush()
```