paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

【幼なじみ or 許嫁】国際プログラミング選手権を制したコード7選+α

f:id:paiza:20150527133241p:plain
2015年4月14日より開始いたしましたpaizaオンラインハッカソン Vol.5「俺の許嫁と幼なじみが修羅場すぎる」と「POH5+レナとミナミの国際プログラミング選手権」の結果レポートと模範解答コード、POH5+の上位コードについてお届けします。

paiza.jp

■POH5「俺の許嫁と幼なじみが修羅場すぎる」グラフ集計

f:id:paiza:20150527183336p:plain
f:id:paiza:20150527183349p:plain

ミナミルートとレナルートはほぼ半々でしたね!!

弊社ではミナミ派が多かったような気がしますが、制作段階では「幼なじみのミナミ一択待ったなし」と言っていたくせにビジュアルが完成したら「どう考えてもレナたんが最高」と言い出した社員もいました。

以下詳しく集計数を見ていきます!

f:id:paiza:20150408205301j:plain

■POH5「俺の許嫁と幼なじみが修羅場すぎる」参加言語ランキング

順位 言語 提出コード数 ミナミルート選択数 レナルート選択数
1 Java 3021提出 342回 301回
2 C++ 2833提出 278回 287回
3 C 2130提出 201回 190回
4 Python 1970提出 234回 217回
5 PHP 1706提出 179回 196回
6 Ruby 1608提出 207回 196回
7 C# 1573提出 175回 185回
8 JavaScript 800提出 59回 68回
9 Perl 347提出 40回 46回
10 Python3(Beta) 319提出 42回 39回
11 Haskell(Beta) 214提出 20回 40回
12 Go(Beta) 136提出 14回 16回
13 Scala(Beta) 133提出 14回 22回
14 Bash(Beta) 73提出 17回 16回
15 Clojure(Beta) 71提出 7回 12回
16 D(Beta) 44提出 10回 5回
17 R(Beta) 31提出 1回 1回
18 F#(Beta) 30提出 4回 7回
19 VB(Beta) 23提出 2回 3回
20 Objective-C(Beta) 22提出 2回 3回
20 Erlang(Beta) 22提出 4回 4回
22 CoffeeScript(Beta) 7提出 1回 1回
23 COBOL(Beta) 5提出 3回 1回

JavaC++、C勢が多いのはいつものことですが、今回はPythonでご参加いただいた方が多かったですね!

ミナミルートとレナルートは、両ルートクリアしていただいた方が多いようで(ありがとうございます!)割と僅差なのですが、Haskellユーザーの方にはレナたんがミナミの倍選択されていたりするのが興味深いです。

■国別ルート選択数

国名 ミナミルート選択数 レナルート選択数
日本 1247 1226
United States 50 55
China 71 75
Korea 2 2
France 2 1
Germany 2 2
Thailand 3 4
Indonesia 205 220
Italy 0 1
Russian 1 2
Malaysia 25 16
Viet Nam 1 2
Saudi Arabia 2 3
Taiwan 71 75
Canada 23 15
Sweden 3 2
Finland 2 2
Singapore 21 19
India 1 0
Philippines 86 77
Hong Kong 35 54
Mexico 4 3
Israel 2 2
Pakistan 1 0

こちらも人気は割とばらけていまして、割合でみるとフィリピンはミナミ、香港はレナたんの方がやや人気……ていうかインドネシアにものすごくやり込んでくださってる方がいらっしゃいますね!!ありがとうございます!!

■POH5+「レナとミナミの国際プログラミング選手権」ランキングトップ20

f:id:paiza:20150529111316p:plain
ランキングトップ50はPOH5+サイトに掲載しています。

◆各国の提出数

順位 提出数
1 日本 2844提出
2 Hong Kong 231提出
3 China 163提出
4 United States 112提出
5 Indonesia 80提出
6 Taiwan 60提出
7 Philippines 27提出
8 Canada 22提出
9 Netherlands 2提出
10 Sweden 1提出

※クリアできたコードの提出数が多い順のランキングとなっております。

プログラミング選手権の方は、日本以外だと中国や台湾の方が多いのかな~という予想はしていたのですが、インドネシアやフィリピンといった東南アジアの方々にもたくさんご参加いただけて嬉しいです!世界のエンジニアの皆さんありがとうございます!


■POH5「俺の許嫁と幼なじみが修羅場すぎる」模範解答(※全てPythonのコードです)

◆Mission1

paiza事務局作成コード

if __name__ == '__main__':
    print ''.join([v for k,v in enumerate(raw_input()) if k%2 == 0])

◆Mission2

paiza事務局作成コード

if __name__ == '__main__':
    n = input()
    l = map(int, raw_input().split())
    print '\n'.join([str(sum(k)) for k in zip(*[[l[i*7+j] for j in range(7)] for i in range(n/7)])])

◆Mission3

paiza事務局作成コード

if __name__ == '__main__':
    for i in xrange(input()):
        print sum(map(int, raw_input().split()))

◆Mission4(ミナミルート)

paiza事務局作成コード

x, y = map(int, raw_input().split())

mn = []
for i in xrange(y):
    t = raw_input().split()
    t = ['0' if i == '2' else i for i in t]
    mn.append(t)

res = []
for i in zip(*mn):
    t_1 = list(i)
    while '0' in t_1:
        t_1.remove('0')
    t_2 = ['0']*(y-len(t_1))
    t_2.extend(t_1)
    res.append(t_2)

for i in zip(*res):
    print ' '.join(i)

◆Mission5(ミナミルート)

x, y, t = map(int, raw_input().split())
xy = []
for i in xrange(y):
    xy.append(map(int, raw_input().split()))

add_list = []
for i in xrange(t):
    x_0, y_0, x_1, y_1 = map(int, raw_input().split())
    if y_1 == y_0:
        for add in [(x_0+_,y_0) for _ in xrange(x_1-x_0+1)]:
            if add not in add_list:
                add_list.append(add)
    else:
        for j in xrange(y_1-y_0+1):
            for add in [(x_0+_,y_0+j) for _ in xrange(x_1-x_0+1)]:
                if add not in add_list:
                    add_list.append(add)

ans = 0
for i in add_list:
    ans += xy[i[1]-1][i[0]-1]

print ans

■POH5+「レナとミナミの国際プログラミング選手権」

POH5+「レナとミナミの国際プログラミング選手権」は、「POH5本編が簡単すぎるぜ!」と言う方の為に用意したプログラミング選手権です。今回は実行時間ではなく、パズルを解くまでの最短手数で競う選手権でした。コンテスト期間中に手数をどこまで少なくできるのかが見所でしたが、uwiさんがいち早く最短平均手数である39.6手を出され、最終的には6名の方が最短平均手数に到達されました!

◆問題文

15パズルとは、1~15の数字が書かれたタイルを4x4の合計16マスからなる枠の中でスライドさせ、並び替えるゲームです。 タイルのない空マスの四方に隣接するタイルを空マスへ移動することでゲームを進行します。
例えば、次の図のようにゲームを進行することができます。

タイルをスライドさせ、盤面を完成させるプログラムを作成してください。 ただし、最短の手数でパズルを完成させる必要はなく、盤面を完成させることができるならば、どのような順番でタイルをスライドしても構いません。
https://paiza.jp/poh/enshura-special

以下paiza運営事務局が独断と偏見で選んだ、各言語の上位コードを公開致します。

Java

uwiさん 39.6手
qiitaの方に解き方の解説も書かれております。qiita.com

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

// びーむさーち
// String -> SLで20%高速化
// HashSet<Long> -> LongHashSetで50%高速化
// パターン列挙を10%高速化
public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
//	static String INPUT = "1 2 3 * 5 6 7 8 9 10 11 12 13 14 15 4";
	
	static void solve()
	{
		int n = 4;
		int[][] a = new int[n][n];
		int zr = -1, zc = -1;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				String x = ns();
				if(x.equals("*")){
					a[i][j] = 15;
					zr = i; zc = j;
				}else{
					a[i][j] = Integer.parseInt(x)-1;
				}
			}
		}
		
		int[][] to = new int[n][n];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				to[i][j] = i*4+j;
			}
		}
		
		int[] route = search(enc(a), enc(to));
		if(route == null)return;
		
		for(int i = 0;i < route.length;i++){
			int k = route[i];
			int nr = zr + dr[k];
			int nc = zc + dc[k];
			out.println(a[nr][nc]+1);
			a[zr][zc] = a[nr][nc];
			a[nr][nc] = 15;
			zr = nr; zc = nc;
		}
	}
	
	static final int[] dr = { 1, 0, -1, 0 };
	static final int[] dc = { 0, 1, 0, -1 };
	
	static int[] search(long start, long goal)
	{
		final byte[] gdA = dists(goal, new int[]{0, 1, 4, 8, 12});
		final byte[] gdB = dists(goal, new int[]{2, 3, 5, 6, 7});
		final byte[] gdC = dists(goal, new int[]{9, 10, 11, 13, 14});
//		if(true)return null;
		
		List<Datum> q = new ArrayList<Datum>();
		q.add(new Datum(start));
//		int SIZE = 55000;
		int SIZE = 50000;
		int phase = 0;
		LongHashSet pved = new LongHashSet();
		LongHashSet ved = new LongHashSet();
		int[] f = new int[200];
		while(true){
			tr(phase++, q.size());
			List<Datum> nq = new ArrayList<Datum>();
			LongHashSet nved = new LongHashSet();
			for(int i = 0;i < q.size() && i < SIZE;i++){
				Datum cur = q.get(i);
//				if(i < 1){
//					tr(cur.score(grc));
////					if(cur.score(grc) == 1){
////						int[][] ya = dec(cur.code);
////						for(int[] row : ya){
////							tr(row);
////						}
////						tr();
////					}
//				}
				if(cur.score(gdA, gdB, gdC) == 0){
					return cur.route.toArray();
				}
				long c = cur.code;
				int z = Long.numberOfTrailingZeros(c&c>>>1&c>>>2&c>>>3&0x1111111111111111L)>>>2;
				for(int k = 0;k < 4;k++){
					int nr = (z>>>2) + dr[k], nc = (z&3) + dc[k];
					if(nr >= 0 && nr < 4 && nc >= 0 && nc < 4){
						int t = 4*nr+nc;
						long move = (int)(cur.code>>>4*t&15);
						long ncode = (cur.code|15L<<4*t)&~((15^move)<<4*z);
						if(!nved.contains(ncode) && !pved.contains(ncode)){
							nved.add(ncode);
							Datum nex = new Datum(ncode, cur.route);
							nex.route.add(k);
							nq.add(nex);
						}
					}
				}
			}
			
			int scoremin = 999, scoremax = -1;
			for(Datum d : nq){
				d.score(gdA, gdB, gdC);
				f[d.score]++;
				scoremin = Math.min(scoremin, d.score);
				scoremax = Math.max(scoremax, d.score);
			}
			Datum[][] bucket = new Datum[scoremax-scoremin+1][];
			for(int i = scoremin;i <= scoremax;i++){
				bucket[i-scoremin] = new Datum[f[i]];
			}
			for(Datum d : nq){
				bucket[d.score-scoremin][--f[d.score]] = d;
			}
			
			q.clear();
			for(int i = scoremin;i <= scoremax;i++){
				for(Datum d : bucket[i-scoremin]){
					if(q.size() >= SIZE)break;
					q.add(d);
				}
			}
			
//			Collections.sort(nq, new Comparator<Datum>() {
//				public int compare(Datum a, Datum b) {
////					return a.score(grc) - b.score(grc);
//					return
//							a.score(gdA, gdB, gdC) - 
//							b.score(gdA, gdB, gdC);
//				}
//			});
//			tr(nq.get(0).score, nq.get(nq.size()-1).score);
			pved = ved;
			ved = nved;
//			q = nq;
		}
	}
	
	static void check(long c)
	{
		int[] f = new int[16];
		for(int i = 0;i < 4;i++){
			for(int j = 0;j < 4;j++){
				f[(int)(c>>>4*(4*i+j)&15)]++;
			}
		}
		for(int i = 0;i < 16;i++){
			if(f[i] != 1){
				tr(i, f);
				throw new RuntimeException();
			}
		}
	}
	
	static int[] q = new int[6000000];
	
	static byte[] dists(long a, int[] mask)
	{
		int m = mask.length;
		m++;
		byte[] d = new byte[1<<4*m];
		Arrays.fill(d, Byte.MAX_VALUE);
		int start = 0;
		for(int i = 0;i < 16;i++){
			int v = (int)(a>>>4*i&15);
			for(int k = 1;k < m;k++){
				if(mask[k-1] == v){
					start |= i<<4*k;
				}
			}
			if(15 == v){
				start |= i;
			}
		}
		
		int p = 0;
		q[p++] = start;
		d[start] = 0;
		
		int[] wh = new int[16];
		Arrays.fill(wh, -1);
		for(int v = 0;v < p;v++){
			int cur = q[v];
			
			for(int l = 1;l < m;l++){
				wh[cur>>>4*l&15] = l;
			}
			int zr = cur>>>2&3, zc = cur&3;
			for(int k = 0;k < 4;k++){
				int nr = zr + dr[k], nc = zc + dc[k];
				if(nr >= 0 && nr < 4 && nc >= 0 && nc < 4){
					int nex = cur&~(zr*4+zc)|nr*4+nc;
					if(wh[nr*4+nc] >= 1)nex = nex&~(nr*4+nc<<4*wh[nr*4+nc])|zr*4+zc<<4*wh[nr*4+nc];
//					for(int l = 1;l < m;l++){
//						if((cur>>>4*l&15) == nr*4+nc){
//							nex = nex&~(nr*4+nc<<4*l)|zr*4+zc<<4*l;
//						}
//					}
					if(d[nex] > d[cur] + 1){
						d[nex] = (byte)(d[cur] + 1);
						q[p++] = nex;
					}
				}
			}
			for(int l = 1;l < m;l++){
				wh[cur>>>4*l&15] = -1;
			}
		}
		
		return d;
	}
	
	static class Datum
	{
		long code;
		int score = -1;
		SL route;
		
		public Datum(long code) {
			this.code = code;
			this.route = new SL(1);
		}
		
		public Datum(long code, SL route) {
			this.code = code;
			this.route = new SL(route);
		}
		
		public int score(byte[] da, byte[] db, byte[] dc)
		{
			if(score == -1){
				score = 0;
				long pos = 0L;
				for(int i = 0;i < 16;i++){
					pos |= (long)i<<4*(int)(code>>>4*i&15);
				}
				/*
		final byte[] gdA = dists(goal, new int[]{0, 1, 4, 8, 12});
		final byte[] gdB = dists(goal, new int[]{2, 3, 5, 6, 7});
		final byte[] gdC = dists(goal, new int[]{9, 10, 11, 13, 14});
				 * 
				 */
				{
					int code = 0;
					code = code<<4|(int)(pos>>>4*12&15);
					code = code<<4|(int)(pos>>>4*8&15);
					code = code<<4|(int)(pos>>>4*4&15);
					code = code<<4|(int)(pos>>>4*1&15);
					code = code<<4|(int)(pos>>>4*0&15);
					code = code<<4|(int)(pos>>>4*15&15);
					score += da[code];
				}
				{
					int code = 0;
					code = code<<4|(int)(pos>>>4*7&15);
					code = code<<4|(int)(pos>>>4*6&15);
					code = code<<4|(int)(pos>>>4*5&15);
					code = code<<4|(int)(pos>>>4*3&15);
					code = code<<4|(int)(pos>>>4*2&15);
					code = code<<4|(int)(pos>>>4*15&15);
					score += db[code];
				}
				{
					int code = 0;
					code = code<<4|(int)(pos>>>4*14&15);
					code = code<<4|(int)(pos>>>4*13&15);
					code = code<<4|(int)(pos>>>4*11&15);
					code = code<<4|(int)(pos>>>4*10&15);
					code = code<<4|(int)(pos>>>4*9&15);
					code = code<<4|(int)(pos>>>4*15&15);
					score += dc[code];
				}
			}
			
			return score;
		}
	}
	
	public static class SL {
		long[] a;
		static final int w = 2; // width
		int p = 0; // index pointer
		int b = 0; // bit pointer
		int sz = 0; // size
		
		public SL(SL o) {
			this.p = o.p;
			this.b = o.b;
			this.sz = o.sz;
			a = Arrays.copyOf(o.a, o.a.length);
		}
		public SL(int n) { a = new long[n]; sz = 0; }
		public SL add(int n)
		{
			if(p+1 >= a.length && b+w >= 64 || p >= a.length)a = Arrays.copyOf(a, a.length*3/2+1);
			for(int i = 0;i < w;i++){
				if(n<<~i<0)a[p] |= 1L<<b;
				if(++b >= 64){
					b -= 64;
					p++;
				}
			}
			sz++;
			return this;
		}
		public int size() { return sz; }
		public SL clear() { p = 0; sz = 0; b = 0; return this; }
		public int[] toArray() {
			int[] ret = new int[sz];
			int lp = 0, lb = 0, lsz = 0;
			while(lp < p || lp == p && lb < b){
				for(int i = 0;i < w;i++){
					if(a[lp]<<~lb<0)ret[lsz] |= 1<<i;
					if(++lb >= 64){
						lb -= 64;
						lp++;
					}
				}
				lsz++;
			}
			return ret;
		}
	}
	
	static long enc(int[][] a)
	{
		long h = 0;
		for(int i = 3;i >= 0;i--){
			for(int j = 3;j >= 0;j--){
				h = h<<4|a[i][j];
			}
		}
		return h;
	}
	
	static int[][] dec(long c)
	{
		int[][] a = new int[4][4];
		for(int i = 0;i < 4;i++){
			for(int j = 0;j < 4;j++){
				a[i][j] = (int)(c&15);
				c>>>=4;
			}
		}
		return a;
	}
	
	public static class LongHashSet {
		public long[] keys;
		public boolean[] allocated;
		private int scale = 1<<2;
		private int rscale = 1<<1;
		private int mask = scale-1;
		public int size = 0;
		
		public LongHashSet(){
			allocated = new boolean[scale];
			keys = new long[scale];
		}
		
		public boolean contains(long x)
		{
			int pos = h(x)&mask;
			while(allocated[pos]){
				if(x == keys[pos])return true;
				pos = pos+1&mask;
			}
			return false;
		}
		
		public boolean add(long x)
		{
			int pos = h(x)&mask;
			while(allocated[pos]){
				if(x == keys[pos])return false;
				pos = pos+1&mask;
			}
			if(size == rscale){
				resizeAndAdd(x);
			}else{
				keys[pos] = x;
				allocated[pos] = true;
			}
			size++;
			return true;
		}
		
		public boolean remove(long x)
		{
			int pos = h(x)&mask;
			while(allocated[pos]){
				if(x == keys[pos]){
					size--;
					// take last and fill rmpos
					int last = pos;
					pos = pos+1&mask;
					while(allocated[pos]){
						int lh = h(keys[pos])&mask;
						// lh <= last < pos
						if(
								lh <= last && last < pos ||
								pos < lh && lh <= last ||
								last < pos && pos < lh
								){
							keys[last] = keys[pos];
							last = pos;
						}
						pos = pos+1&mask;
					}
					keys[last] = 0;
					allocated[last] = false;
					
					return true;
				}
				pos = pos+1&mask;
			}
			return false;
		}
		
		private void resizeAndAdd(long x)
		{
			int nscale = scale<<1;
			int nrscale = rscale<<1;
			int nmask = nscale-1;
			boolean[] nallocated = new boolean[nscale];
			long[] nkeys = new long[nscale];
			for(int i = next(0);i < scale;i = next(i+1)){
				long y = keys[i];
				int pos = h(y)&nmask;
				while(nallocated[pos])pos = pos+1&nmask;
				nkeys[pos] = y;
				nallocated[pos] = true;
			}
			{
				int pos = h(x)&nmask;
				while(nallocated[pos])pos = pos+1&nmask;
				nkeys[pos] = x;
				nallocated[pos] = true;
			}
			allocated = nallocated;
			keys = nkeys;
			scale = nscale;
			rscale = nrscale;
			mask = nmask;
		}
		
		public int next(int itr)
		{
			while(itr < scale && !allocated[itr])itr++;
			return itr;
		}
		
		
//		public int h(int x)
//		{
//			x ^= x>>>16;
//			x *= 0x85ebca6b;
//			x ^= x>>>13;
//			x *= 0xc2b2ae35;
//			x ^= x>>>16;
//			return x;
//		}
		
		private int h(long x)
		{
			x ^= x>>>33;
			x *= 0xff51afd7ed558ccdL;
			x ^= x>>>33;
			x *= 0xc4ceb9fe1a85ec53L;
			x ^= x>>>33;
			return (int)(x^x>>>32);
		}
		
		@Override
		public String toString()
		{
			StringBuilder sb = new StringBuilder();
			for(int i = next(0);i < scale;i = next(i+1)){
				sb.append(",");
				sb.append(keys[i]);
			}
			return sb.length() == 0 ? "" : sb.substring(1);
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

C++

orisanoさん 41.6手

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <deque>
#include <queue>

using namespace std;

typedef unsigned long long ull;
typedef unsigned short pos_t;

const int REV_STEP = 14;
const int BEAM_WIDTH = 5000;
const int DX[] = {1, -1, 0, 0};
const int DY[] = {0, 0, 1, -1};

inline int sq(int x){ return x * x; }
inline int ceval(int c, int x, int y){
  int rx = c & 3;
  int ry = c >> 2;
  return sq(abs(rx - x) + abs(ry - y));
}

inline pos_t pack_pos(int x, int y){ return (y << 8) | x; }
inline void unpack_pos(pos_t p, int& x, int& y){ x = p & 0x000F; y = (p >> 8) & 0x000F; }
inline void put_cell(ull& grid, int x, int y, int c){
  const int shift = ((y << 2) | x) << 2;
  const ull mask = ~(0xFULL << shift);
  grid = (grid & mask) | ((ull)c  << shift);
}

inline ull get_cell(ull grid, int x, int y){
  const int shift = ((y << 2) | x) << 2;
  const ull mask = (0xFULL << shift);
  return (grid & mask) >> shift;
}

struct Board {
  ull grid;
  pos_t cur;
  deque<char> ans;
  unsigned short eval;

  Board(){}
  bool operator<(const Board& b) const { return eval < b.eval; }
  void load(const vector<vector<string> >& raw_grid){
    eval = 0;
    for (int y = 0; y < 4; y++){
      for (int x = 0; x < 4; x++){
        if (raw_grid[y][x] == "*") put_cell(grid, x, y, 15), cur = pack_pos(x, y);
        else {
          int c = atoi(raw_grid[y][x].c_str()) - 1;
          put_cell(grid, x, y, c);
          eval += ceval(c, x, y);
        }
      }
    }
  }
  bool slide(int d){
    int x, y;
    unpack_pos(cur, x, y);
    int nx = x + DX[d];
    int ny = y + DY[d];
    if ((nx & 4) || (ny & 4)) return false;
    int c = 15;
    int nc = get_cell(grid, nx, ny);

    ans.push_back(nc);
    eval -= ceval(nc, nx, ny);
    put_cell(grid, x, y, nc);
    put_cell(grid, nx, ny, c);
    eval += ceval(nc, x, y);
    cur = pack_pos(nx, ny);
    return true;
  }
  bool is_ok(){ return eval == 0; }
  void print_answer(){
    for (int i = 0; i < ans.size(); i++){
      printf("%d\n", ans[i] + 1);
    }
  }
  void dump(){
    printf("eval: %d\n", eval);
    for (int i = 0; i < 4; i++){
      for (int j = 0; j < 4; j++){
        printf("%X", get_cell(grid, j, i));
      }
      puts("");
    }
  }
};

void build_rev_table(unordered_map<ull, Board>& rev_table)
{
  Board eb;
  eb.eval = 0;
  for (int i = 0; i < 4; i++){
    for (int j = 0; j < 4; j++){
      put_cell(eb.grid, j, i, i * 4 + j);
      eb.eval += ceval(i * 4 + j, j, i);
    }
  }
  eb.cur = pack_pos(3, 3);
  queue<Board> Q;
  Q.push(eb);
  rev_table[eb.grid] = eb;
  for (int i = 0; i < REV_STEP; i++){
    queue<Board> nQ;
    while (!Q.empty()){
      Board b = Q.front();
      Q.pop();
      for (int d = 0; d < 4; d++){
        Board nb = b;
        if (!nb.slide(d)) continue;
        if (rev_table.count(nb.grid)) continue;
        nQ.push(nb);
        reverse(nb.ans.begin(), nb.ans.end());
        rev_table[nb.grid] = nb;
      }
    }
    swap(Q, nQ);
  }
}

int main()
{
  vector<vector<string> > S(4, vector<string>(4));
  for (int i = 0; i < 4; i++){
    for (int j = 0; j < 4; j++){
      cin >> S[i][j];
    }
  }
  unordered_map<ull, Board> rev_table;
  build_rev_table(rev_table);

  Board b;
  b.load(S);
  deque<Board> beam;
  beam.push_back(b);
  unordered_set<ull> vis;
  vis.insert(b.grid);
  while (1){
    for (int i = 0, i_ = beam.size(); i < i_; i++){
      if (beam.front().is_ok()){
        beam.front().print_answer();
        goto END;
      }
      for (int d = 0; d < 4; d++){
        Board nb = beam.front();
        if (!nb.slide(d)) continue;
        if (vis.count(nb.grid)) continue;
        if (rev_table.count(nb.grid)){
          nb.print_answer();
          rev_table[nb.grid].print_answer();
          goto END;
        }
        vis.insert(nb.grid);
        beam.push_back(nb);
      }
      beam.pop_front();
    }
    if (beam.size() <= BEAM_WIDTH) sort(beam.begin(), beam.end());
    else partial_sort(beam.begin(), beam.begin() + BEAM_WIDTH, beam.end()), beam.erase(beam.begin() + BEAM_WIDTH + 1, beam.end());
  }
END:;
  return 0;
}

C++

hogeover30さん 40.4手

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <array>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

typedef unsigned long long ull;
const ull answer=1147797409030816545ULL;
const int bw=20000;//1<<13;
int ROW[]={3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3};
int COL[]={3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2};
int dr[]={-1, 0, 1, 0}, dc[]={0, -1, 0, 1};
vector<int> neighbor[16] = {
    {4, 1, }, {0, 5, 2, }, {1, 6, 3, }, {2, 7, },
    {0, 8, 5, }, {1, 4, 9, 6, }, {2, 5, 10, 7, }, {3, 6, 11, },
    {4, 12, 9, }, {5, 8, 13, 10, }, {6, 9, 14, 11, }, {7, 10, 15, },
    {8, 13, }, {9, 12, 14, }, {10, 13, 15, }, {11, 14, },
};

ull encode(const array<char, 16>& a)
{
    ull res=0;
    for(int i=0;i<16;++i) res|=(ull)a[i]<<(4*i);
    return res;
}

void decode(array<char, 16>& a, ull val)
{
    for(int i=0;i<16;++i) a[i]=(val>>(4*i))&15;
}

#define get(x, i) (int((x)>>4*(15-(i)))&15)
#define slide(x, v, i, j) { x|=(ull)(v)<<4*(15-(i)); x&=~(15ULL<<4*(15-(j))); }

int calcscore(const ull& x)
{
    int sumd=0, hoge=0;
    for(int i=0;i<16;++i) {
        int t=get(x, 15-i);
        if (t==0) continue;
        int d=abs(ROW[t]-i/4)+abs(COL[t]-i%4);
        for(int j: neighbor[15-i]) if (0<d and d<3 and abs(t-(int)get(x, j))==1) ++hoge;
        sumd+=d;
    }
    return -1024*sumd+hoge;
}

void input(array<char, 16>& a, int& k)
{
    char s[32];
    for(int i=0;i<4;++i) {
        int j=0;
        for(char *p=strtok(fgets(s, 32, stdin), " ");p;p=strtok(0, " ")) {
            int t=atoi(p);
            if (t==0) k=i*4+j;
            a[4*i+j]=t;
            ++j;
        }
    }
}

int main()
{
    array<char, 16> a;
    int f0;
    input(a, f0);

    unordered_map<ull, int> scores;
    unordered_map<ull, pair<int, ull>> seq;
    vector<pair<ull, int>> q(bw);
    f0=15-f0;
    q.emplace_back(encode(a), f0);
    seq[encode(a)]={-1, -1};
    while (true) {
        priority_queue<tuple<int, ull, int>> nq;
        for(auto& p: q) {
            auto b=p.first;
            int i=p.second;
            for(int j: neighbor[i]) {
                int t=get(b, j);
                slide(b, t, i, j);
                if (seq.count(b)==0) {
                    int score=calcscore(b);
                    nq.emplace(score, b, j);
                    seq[b]={t, p.first};
                }
                b=p.first;
            }
        }
        int N=min<int>(nq.size(), bw);
        for(int i=0;i<N;++i) {
            ull b;
            int j;
            tie(ignore, b, j)=nq.top();
            q[i]=make_pair(b, j);
            nq.pop();
        }
        if (q[0].first==answer) break;
    }

    vector<int> res;
    ull asr=answer;
    while (seq.count(asr)) {
        auto b=seq[asr].second;
        int x=seq[asr].first;
        if (x==-1) break;
        res.push_back(x);
        asr=b;
    }
    reverse(begin(res), end(res));
    for(int v: res) printf("%d\n", v);
}

Python

romain_liさん 46.0手

class Position(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y


GOAL_POSITION = [Position(3, 3),  # *
                 Position(0, 0),  # 1
                 Position(0, 1),  # 2
                 Position(0, 2),  # 3
                 Position(0, 3),  # 4
                 Position(1, 0),  # 5
                 Position(1, 1),  # 6
                 Position(1, 2),  # 7
                 Position(1, 3),  # 8
                 Position(2, 0),  # 9
                 Position(2, 1),  # 10
                 Position(2, 2),  # 11
                 Position(2, 3),  # 12
                 Position(3, 0),  # 13
                 Position(3, 1),  # 14
                 Position(3, 2)]  # 15


def main():
    state = InitialState(read_lines())
    for limit in xrange(state.distance, 1000000):
        if state.solution(limit):
            for step in state.steps:
                print step
            break


def read_lines():
    return [read_line(), read_line(), read_line(), read_line()]


def read_line():
    return map(lambda x: int(x) if x != '*' else 0, raw_input().split())


class State(object):
    def __init__(self, maze, blank_position, steps, step_length, distance):
        self.maze = maze
        self.blank_position = blank_position
        self.steps = steps
        self.step_length = step_length
        self.distance = distance

    def solution(self, limit):
        if self.distance == 0:
            return True
        # Move Blank Up
        if self.blank_position.x > 0:
            dx = self.blank_position.x - 1
            n = self.maze[dx][self.blank_position.y]
            if not self.steps or n != self.steps[-1]:
                distance_delta = -1 if GOAL_POSITION[n].x >= self.blank_position.x else 1
                self.distance += distance_delta
                if self.evaluation <= limit:
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[dx][self.blank_position.y] = \
                        self.maze[dx][self.blank_position.y], self.maze[self.blank_position.x][self.blank_position.y]
                    self.blank_position.x = dx
                    self.steps.append(n)
                    self.step_length += 1
                    if self.solution(limit):
                        return True
                    self.step_length -= 1
                    self.steps.pop()
                    self.blank_position.x += 1
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[dx][self.blank_position.y] = \
                        self.maze[dx][self.blank_position.y], self.maze[self.blank_position.x][self.blank_position.y]
                self.distance -= distance_delta
        # Move Blank Down
        if self.blank_position.x < 3:
            dx = self.blank_position.x + 1
            n = self.maze[dx][self.blank_position.y]
            if not self.steps or n != self.steps[-1]:
                distance_delta = -1 if GOAL_POSITION[n].x <= self.blank_position.x else 1
                self.distance += distance_delta
                if self.evaluation <= limit:
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[dx][self.blank_position.y] = \
                        self.maze[dx][self.blank_position.y], self.maze[self.blank_position.x][self.blank_position.y]
                    self.blank_position.x = dx
                    self.steps.append(n)
                    self.step_length += 1
                    if self.solution(limit):
                        return True
                    self.step_length -= 1
                    self.steps.pop()
                    self.blank_position.x -= 1
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[dx][self.blank_position.y] = \
                        self.maze[dx][self.blank_position.y], self.maze[self.blank_position.x][self.blank_position.y]
                self.distance -= distance_delta
        # Move Blank Left
        if self.blank_position.y > 0:
            dy = self.blank_position.y - 1
            n = self.maze[self.blank_position.x][dy]
            if not self.steps or n != self.steps[-1]:
                distance_delta = -1 if GOAL_POSITION[n].y >= self.blank_position.y else 1
                self.distance += distance_delta
                if self.evaluation <= limit:
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[self.blank_position.x][dy] = \
                        self.maze[self.blank_position.x][dy], self.maze[self.blank_position.x][self.blank_position.y]
                    self.blank_position.y = dy
                    self.steps.append(n)
                    self.step_length += 1
                    if self.solution(limit):
                        return True
                    self.step_length -= 1
                    self.steps.pop()
                    self.blank_position.y += 1
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[self.blank_position.x][dy] = \
                        self.maze[self.blank_position.x][dy], self.maze[self.blank_position.x][self.blank_position.y]
                self.distance -= distance_delta
        # Move Blank Right
        if self.blank_position.y < 3:
            dy = self.blank_position.y + 1
            n = self.maze[self.blank_position.x][dy]
            if not self.steps or n != self.steps[-1]:
                distance_delta = -1 if GOAL_POSITION[n].y <= self.blank_position.y else 1
                self.distance += distance_delta
                if self.evaluation <= limit:
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[self.blank_position.x][dy] = \
                        self.maze[self.blank_position.x][dy], self.maze[self.blank_position.x][self.blank_position.y]
                    self.blank_position.y = dy
                    self.steps.append(n)
                    self.step_length += 1
                    if self.solution(limit):
                        return True
                    self.step_length -= 1
                    self.steps.pop()
                    self.blank_position.y -= 1
                    self.maze[self.blank_position.x][self.blank_position.y], self.maze[self.blank_position.x][dy] = \
                        self.maze[self.blank_position.x][dy], self.maze[self.blank_position.x][self.blank_position.y]
                self.distance -= distance_delta


    @property
    def evaluation(self):
        """
        h(s) <= h*(s)
        f(s) = g(s) + h(s) = len(steps) + sum(distances)
        """
        return self.step_length + self.distance * 2.1


class InitialState(State):
    def __init__(self, maze):
        distance = 0
        blank_position = None
        for x in xrange(4):
            for y in xrange(4):
                n = maze[x][y]
                if n == 0:
                    blank_position = Position(x, y)
                else:
                    goal_position = GOAL_POSITION[n]
                    distance += abs(x - goal_position.x) + abs(y - goal_position.y)

        super(InitialState, self).__init__(maze, blank_position, [], 0, distance)


if __name__ == '__main__':
    main()

PHP

y_utiさん 46.4手
はてなブログではy-utiさんのコードを上手く表示できなかったのでy-utiさんのブログを張っておきます。y-uti.hatenablog.jp
github.com

Perl

Gasuさん 58.8手

#!/usr/local/bin/perl

my $t;
my $p;
my $zero;
my $count = 0;
my $start = 0;
my $done;
my $done_count = 0;
my $data;
my $max_done_count = 0;
my $pre_max_done_count = 0;
my $kill;
my $check_flag = 0;

_init();

my $y = 0;
while (my $line = <STDIN>){
    $y ++;
    chomp($line);
    my @split = split(/ /, $line);
    for my $x (1..4){
    my $val = $split[$x - 1];
    $val =~ s/\*/0/g;
    $val =~ s/[^0-9]//g;
    $p->[$x]->[$y] = $val + 0;
    }
}
_init_done();

$max_done_count = $done_count;
$pre_max_done_count = $done_count;

_init_register(_goban_to_hash());

$start = 1;
my $now = 0;

while ($pre_max_done_count < 14){
    $now ++;
    my $key_count = 0;
    my $key_count2 = 0;
    foreach my $k (sort {$data->{$a}->{"score"} <=> $data->{$b}->{"score"}} keys %$data){
	$key_count ++;
	if ($key_count < 900){
	    if ($data->{$k}->{"done_count"} == $pre_max_done_count){
		$key_count2 ++;
		my $history = $data->{$k}->{"output"};
		my $count = $data->{$k}->{"sum_count"};
		my $last = $data->{$k}->{"last"};
		my $ar = $data->{$k}->{"ar"};
		_hash_to_goban($k, $data->{$k}->{"done_hash"});
		if ($ar ne "r"){
		    my $char = _go_l();
		    if ($char > 0 && $char != $last){
			_register(_goban_to_hash(), $now, $history, $char, $count, "l");
		    }
		}		
		if ($ar ne "l"){
		    _hash_to_goban($k, $data->{$k}->{"done_hash"});
		    my $char = _go_r();
		    if ($char > 0 && $char != $last){
			_register(_goban_to_hash(), $now, $history, $char, $count, "r");
		    }
		}		
		if ($ar ne "d"){
		    _hash_to_goban($k, $data->{$k}->{"done_hash"});
		    my $char = _go_u();
		    if ($char > 0 && $char != $last){
			_register(_goban_to_hash(), $now, $history, $char, $count, "u");
		    }
		}		
		if ($ar ne "u"){
		    _hash_to_goban($k, $data->{$k}->{"done_hash"});
		    my $char = _go_d();
		    if ($char > 0 && $char != $last){
			_register(_goban_to_hash(), $now, $history, $char, $count, "d");
		    }
		}
	    }
	}
	_delete($k);
	_kill($k);
    }
    $pre_max_done_count = $max_done_count;
}

foreach my $k (keys %$data){
    $now ++;
    if ($data->{$k}->{"count"} < $now && $data->{$k}->{"done_count"} == $pre_max_done_count && $kill->{$k} != 1){
	my $history = $data->{$k}->{"output"};
	_hash_to_goban($k, $data->{$k}->{"done_hash"});
	_answer($history);
	last;
    }
}

exit;


sub _score {
    my $score = 0;
    my @scm;
    for my $y (1..4){
	for my $x (1..4){
	    my $v = $p->[$x]->[$y];
	    my $diffx = abs($t->[$v]->{"x"} - $x);
	    my $diffy = abs($t->[$v]->{"y"} - $y);
	    my $diff = $diffx + $diffy;
	    $scm[$v] = $diff;	    
	}
    }
    if ($scm[1]){
	$score = $scm[1] + 5000;
    } elsif ($scm[2] || $scm[5]){
	$score = $scm[2] + $scm[5] + 40000;
    } elsif ($scm[3] || $scm[4] || $scm[9] || $scm[13]){
	$score = $scm[3] + $scm[4] + $scm[9] + $scm[13] + 3000;
    } elsif ($scm[6]){
	$score = $scm[6] + 2000;
    } elsif ($scm[7] || $scm[8] || $scm[10] || $scm[14]){
	$score = $scm[7] + $scm[8] + $scm[10] + $scm[14] + 1000;
    } else {
	$score = 500;
    }
    return $score;
}


sub _kill {
    my $key = shift;
    $kill->{$key} = 1;
}

sub _delete {
    my $key = shift;
    delete $data->{$key};
}

sub _register {
    my $goban = shift;
    my $done_hash = shift;
    my $count = shift;
    my $history = shift;
    my $key = shift;
    my $ar = shift;
    my $sum_count = $shift;
    if ($done_count == 15){
	_answer($history.$key.",");
	exit;
    }
    
    if ($kill->{$goban} != 1 && $done_count >= $max_done_count){
	$data->{$goban}->{"done_hash"} = $done_hash;
	$data->{$goban}->{"output"} = $history.$key.",";
	$data->{$goban}->{"last"} = $key;
	$data->{$goban}->{"ar"} = $ar;
	$data->{$goban}->{"done_count"} = $done_count;
	$data->{$goban}->{"score"} = _score();
	if ($done_count > $max_done_count){
	    $max_done_count = $done_count;
	}
    }
}

sub _init_register {
    my $goban = shift;
    my $done_hash = shift;
    $data->{$goban}->{"output"} = "";
    $data->{$goban}->{"last"} = "";
    $data->{$goban}->{"count"} = 0;
    $data->{$goban}->{"sum_count"} = 0;
    $data->{$goban}->{"done_count"} = $done_count;
    $data->{$goban}->{"done_hash"} = $done_hash;
}

sub _goban_to_hash {
    my $char = "";
    my $char2 = "";
    for $y (1..4){
	for $x (1..4){
	    $char .=
		$p->[$x]->[$y].",";
	    $char2 .=
		$done->[$x]->[$y].",";
	}
    }
    return $char, $char2;
}

sub _hash_to_goban {
    my $char = shift;
    my $char2 = shift;
    my @split = split(/,/, $char);
    my @split2 = split(/,/, $char2);
    $done_count = 0;
    for $y (1..4){
	for $x (1..4){
	    $p->[$x]->[$y] = shift @split;
	    if ($p->[$x]->[$y] == 0){
		$zero->{"x"} = $x;
		$zero->{"y"} = $y;
	    }
	    $done->[$x]->[$y] = shift @split2;
	    if ($done->[$x]->[$y] == 1){
		$done_count ++;
	    }
	}
    }
}



sub _check {
    my $x = shift;
    my $y = shift;
    $check_flag = 0;
    if ($start){
	if (_q_same($x, $y)){
	    if ($x == 1 && $y == 1){
		_done($x, $y);
	    } elsif ($x * $y == 2){
		if ($done->[$x]->[$y - 1] && $done->[$x - 1]->[$y]){
		    _done($x, $y);
		}
	    } elsif ($x == 1 && $y < 3){
		if (_q_same(1, 3) && _q_same(1, 4)){
		    if ($done->[$x]->[$y - 1] && $done->[$x - 1]->[$y]){
			_done($x, $y);
		    }
		}
	    } elsif ($y == 1 && $x < 3){
		if (_q_same(3, 1) && _q_same(4, 1)){
		    if ($done->[$x]->[$y - 1] && $done->[$x - 1]->[$y]){
			_done($x, $y);
		    }
		}
	    } elsif ($x == 2 && $y == 2){
		if ($done->[1]->[1] && $done->[1]->[2] && $done->[1]->[3] && $done->[1]->[4] && $done->[2]->[1] && $done->[3]->[1] && $done->[4]->[1]){
		    _done($x, $y);
		}
	    } elsif ($x < 3 && $y > 2){
		if (_q_same($x, 3) && _q_same($x, 4)){
		    if ($done->[$x - 1]->[1] && $done->[$x - 1]->[2] && $done->[$x - 1]->[3] && $done->[$x - 1]->[4] && $done->[$x]->[2]){
			_done($x, 3);
			_done($x, 4);
		    }
		}
	    } elsif ($y < 3 && $x > 2){
		if (_q_same(3, $y) && _q_same(4, $y)){
		    if ($done->[1]->[$y - 1] && $done->[2]->[$y - 1] && $done->[3]->[$y - 1] && $done->[4]->[$y - 1] && $done->[2]->[$y]){
			_done(3, $y);
			_done(4, $y);
		    }
		}
	    } else {
		if (_q_same(3, 3) && _q_same(3, 4) && _q_same(4, 3)){
		    if ($done->[3]->[2] && $done->[4]->[2] && $done->[2]->[3] && $done->[2]->[4]){
			_done(3, 3);
			_done(4, 3);
			_done(3, 4);
		    }
		}
	    }
	}
    }
    if ($check_flag){
	_init_done();
    }
}


sub _done {
    my $x = shift;
    my $y = shift;
    $done->[$x]->[$y] = 1;
    $done_count ++;
    $check_flag ++;
}

sub _init_done {
    $done_count = 0;
    if (_q_same(1, 1)){
	_done(1, 1);
	if (_q_same(1, 2)){
	    _done(1, 2);
	    if (_q_same(1, 3) && _q_same(1, 4)){
		_done(1, 3);
		_done(1, 4);
	    }
	}
	if (_q_same(2, 1)){
	    _done(2, 1);
	    if (_q_same(3, 1) && _q_same(4, 1)){
		_done(3, 1);
		_done(4, 1);
	    }
	}
	if ($done_count > 6){

	    if (_q_same(2, 2)){
		_done(2, 2);

		if (_q_same(2, 3) && _q_same(2, 4)){
		    _done(2, 3);
		    _done(2, 4);
		}

		if (_q_same(3, 2) && _q_same(4, 2)){
		    _done(3, 2);
		    _done(4, 2);
		}
	    }

	    if ($done_count > 11){
		if (_q_same(3, 3) && _q_same(4, 3) && _q_same(3, 4)){
		    _done(3, 3);
		    _done(4, 3);
		    _done(3, 4);
		}
	    }
	}
    }
}

sub _q_same {
    my $x = shift;
    my $y = shift;

    my $v = $p->[$x]->[$y];
    if ($t->[$v]->{"x"} == $x && $t->[$v]->{"y"} == $y){
	return 1;
    } else {
	return 0;
    }
    return 0;
}



sub _answer {
    my $var = shift;
    $var =~ s/\A,//g;
    $var =~ s/,\Z//g;
    my @split = split(/,/, $var);
    for (0..$#split){
	print $split[$_]."\n";
    }
}




sub _go_l {
    if ($zero->{"x"} > 1){
	my $x0 = $zero->{"x"};
	my $y0 = $zero->{"y"};
	my $xx = $x0 - 1;
	my $yy = $y0;

	unless ($done->[$xx]->[$yy]){
	    my $target = $p->[$xx]->[$yy];
	    $zero->{"x"} = $xx;
	    $zero->{"y"} = $yy;

	    $p->[$xx]->[$yy] = 0;
	    $p->[$x0]->[$y0] = $target;
	    _check($x0, $y0);
	    return $target;
	}
    }
    return 0;
}

sub _go_r {
    if ($zero->{"x"} < 4){
	my $x0 = $zero->{"x"};
	my $y0 = $zero->{"y"};
	my $xx = $x0 + 1;
	my $yy = $y0;
	my $target = $p->[$xx]->[$yy];
	$zero->{"x"} = $xx;
	$zero->{"y"} = $yy;

	$p->[$xx]->[$yy] = 0;
	$p->[$x0]->[$y0] = $target;
	_check($x0, $y0);
	return $target;
    }
    return 0;
}

sub _go_u {
    if ($zero->{"y"} > 1){
	my $x0 = $zero->{"x"};
	my $y0 = $zero->{"y"};
	my $xx = $x0;
	my $yy = $y0 - 1;
	unless ($done->[$xx]->[$yy]){
	    my $target = $p->[$xx]->[$yy];
	    $zero->{"x"} = $xx;
	    $zero->{"y"} = $yy;

	    $p->[$xx]->[$yy] = 0;
	    $p->[$x0]->[$y0] = $target;
	    _check($x0, $y0);
	    return $target;
	}
    }
    return 0;
}

sub _go_d {
    if ($zero->{"y"} < 4){
	my $x0 = $zero->{"x"};
	my $y0 = $zero->{"y"};
	my $xx = $x0;
	my $yy = $y0 + 1;
	my $target = $p->[$xx]->[$yy];
	$zero->{"x"} = $xx;
	$zero->{"y"} = $yy;

	$p->[$xx]->[$yy] = 0;
	$p->[$x0]->[$y0] = $target;
	_check($x0, $y0);
	return $target;
    }
    return 0;
}

sub _init {

    $t = [
	{"x" => 4, "y" => 4},
	{"x" => 1, "y" => 1},
	{"x" => 2, "y" => 1},
	{"x" => 3, "y" => 1},
	{"x" => 4, "y" => 1},
	{"x" => 1, "y" => 2},
	{"x" => 2, "y" => 2},
	{"x" => 3, "y" => 2},
	{"x" => 4, "y" => 2},
	{"x" => 1, "y" => 3},
	{"x" => 2, "y" => 3},
	{"x" => 3, "y" => 3},
	{"x" => 4, "y" => 3},
	{"x" => 1, "y" => 4},
	{"x" => 2, "y" => 4},
	{"x" => 3, "y" => 4}
	];


    $done->[0]->[1] = 1;
    $done->[0]->[2] = 1;
    $done->[0]->[3] = 1;
    $done->[0]->[4] = 1;
    $done->[1]->[0] = 1;
    $done->[2]->[0] = 1;
    $done->[3]->[0] = 1;
    $done->[4]->[0] = 1;


}

Haskell

import Data.Array
import Data.List (sortBy)
import qualified Data.Set as S
import Data.Maybe (fromJust, isJust)

data Board = Board {
               board :: Array (Int, Int) Int,
               spacePos :: (Int, Int)
             } deriving (Show, Ord, Eq)

data Direction = U | D | L | R | Nowhere 
                   deriving (Bounded, Enum, Eq, Show)

type Cache = S.Set Board

boardSize :: Int
boardSize = 4

searchDepth :: Int
searchDepth = 260

main :: IO ()
main = do
  bs <- mapM (\_ -> getRow) [1..boardSize] 
  let board = constBoard bs
      path = reverse $ searchPath board
  mapM_ (putStrLn . show) $ formatAns board path

getRow :: IO [Int]
getRow = do
  str <- getLine
  return . map (\x -> if x == "*" then 0 else read x) $ words str

dist :: (Int, Int) -> Int -> Int
dist _ 0 = 0
dist (x, y) v = (abs $ (v-1) `div` 4 - x) + (abs $ (v-1) `rem` 4 - y)

calcCost :: Board -> Int
calcCost b = foldr (\i acc -> dist i (bs ! i) + acc) 0 $ 
             indices bs
  where bs = board b

constBoard :: [[Int]] -> Board
constBoard [] = Board (array ((0, 0), (0, 0)) []) (-1, -1)
constBoard xs = Board {
                  board = array ((0, 0), (r-1,  c-1)) assocs,
                  spacePos = fst $ sps !! 0
                }
  where 
    r = boardSize
    c = boardSize
    sps = filter ((== 0) . snd) assocs
    assocs = map (\(i, x) -> ((i `div` r, i `rem` r), x)) . zip [0..] $ concat xs
     
swap :: (Ix a) => Array a b -> a -> a -> Array a b
swap arr i1 i2 = accum (\_ x -> x) arr [(i1, arr ! i2), (i2, arr ! i1)]

getCoord :: (Int, Int) -> Direction -> (Int, Int)
getCoord (x, y) U = (x - 1, y)
getCoord (x, y) D = (x + 1, y)
getCoord (x, y) L = (x, y - 1)
getCoord (x, y) R = (x, y + 1)

isValidCoord :: (Int, Int) -> Bool
isValidCoord (x, y) = x >= 0 && x < boardSize && y >= 0 && y < boardSize 

proceed :: Board -> Direction -> Maybe Board
proceed b Nowhere = Just b
proceed b d = do 
  let (nx, ny) = spacePos b
      coord = getCoord (nx, ny) d
  nextPos <- if isValidCoord coord 
               then Just coord 
               else Nothing
  return $ Board (swap (board b) (nx, ny) nextPos) nextPos

compareBoard :: (Board, Int, Int, [Direction]) -> (Board, Int, Int, [Direction]) -> Ordering
compareBoard (_, x, lx, _) (_, y, ly, _) = 
  case compare x y of
    EQ -> compare lx ly
    _ -> compare x y

possibleStates :: (Board, Int, Int, [Direction]) -> [(Board, Int, Int, [Direction])]
possibleStates (b, _, len, ds) = 
  map (\(mb, len', ds') -> (fromJust mb, calcCost (fromJust mb), len', ds')) . filter (\(mb, _, _) -> isJust mb) 
  $ map (\d -> (proceed b d, len + 1, d:ds)) [U .. R]

bfsMinPath :: [(Board, Int, Int, [Direction])] -> Cache -> (Board, Int, Int, [Direction])
bfsMinPath [] _ = error "unsolvable"
bfsMinPath all@((b, cst, len, ds):bs) cache
  | cst == 0 = (b, cst, len, ds)
  | otherwise = bfsMinPath (extractStates nextStates) nextCache
  where 
    extractStates bs = take searchDepth $ sortBy compareBoard bs
    (nextCache, nextStates) = 
      foldr (\st@(b', c, l, ds') (nc, nss) -> 
               let ps = possibleStates st
               in foldr (\st'@(b'', c', l', ds'') (nc', nss') ->
                            if S.member b'' nc'
                              then (nc', nss')
                              else (S.insert b'' nc', st':nss'))
                  (nc, nss) ps) (cache, []) all

searchPath :: Board -> [Direction]
searchPath b = ds
  where 
    c = calcCost b
    (b', _, _, ds) = bfsMinPath [(b, calcCost b, 0, [])] S.empty

formatAns :: Board -> [Direction] -> [Int]
formatAns b ds = reverse . fst $ foldl (\(ns, b') d ->
                         let cd = getCoord (spacePos b') d
                         in (((board b') ! cd):ns, fromJust $ proceed b' d)) ([], b) ds

■コード公開について

「もっといろんな言語でいろんなコードが見てみたい!」という方は、以前こちらのブログでPOH5「俺の許嫁と幼なじみが修羅場すぎる」のコードを公開してくださっている方々をご紹介しておりますので、ぜひご覧ください!paiza.hatenablog.com

さらにPOH5+「レナとミナミの国際プログラミング選手権」のコードを公開してくださっている方も増えてきましたので、一部ではありますが追加でご紹介させていただきます!

「15パズル難しい!!」という皆様はぜひご参考になさってください!

mayokoex.hatenablog.com

sucrose.hatenablog.com

POHは毎回「ブログやSNS等でコードを公開していただいて構いません!」というスタンスで開催させていただいているオンラインイベントです。挑戦していただいた方々のコードが拝見できるのは毎回とても嬉しいです!

■まとめ

「模範解答見たけど何でこう書くといいのかいまいち分からん!」という方もいらっしゃるかもしれませんので、来週は模範解答コードのアルゴリズムについての解説記事を更新する予定です。そちらもぜひご覧くださいね!

■壁紙プレゼントについて

paizaに会員登録すると、下記の壁紙3種類がダウンロードできます!是非お気軽にご登録下さい!
f:id:paiza:20150520153816j:plain
f:id:paiza:20150520153830j:plain
f:id:paiza:20150520153838j:plain





paizaではスキルのあるエンジニアがきちんと評価されるようにし、技術を追い続ける事が仕事につながるようにする事で、日本のITエンジニアの地位向上を図っていければと考えています。特にpaizaではWebサービス提供企業などでもとめられる、システム開発力や、テストケースを想定できるかの力(テストコードを書く力)などが問われる問題を出題しています。

テストの結果によりS・A・B・C・D・Eの6段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。

http://paiza.jp


プログラミング入門講座|paizaラーニング

PHP入門編Ruby入門編Python入門編Java入門編JavaScript入門編C言語入門編C#入門編アルゴリズム入門編