2015年4月14日より開始いたしましたpaizaオンラインハッカソン Vol.5「俺の許嫁と幼なじみが修羅場すぎる」と「POH5+レナとミナミの国際プログラミング選手権」の結果レポートと模範解答コード、POH5+の上位コードについてお届けします。
■POH5「俺の許嫁と幼なじみが修羅場すぎる」グラフ集計
ミナミルートとレナルートはほぼ半々でしたね！！
弊社ではミナミ派が多かったような気がしますが、制作段階では「幼なじみのミナミ一択待ったなし」と言っていたくせにビジュアルが完成したら「どう考えてもレナたんが最高」と言い出した社員もいました。
以下詳しく集計数を見ていきます！
■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回 |
Java、C++、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
ランキングトップ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パズル難しい！！」という皆様はぜひご参考になさってください！
POHは毎回「ブログやSNS等でコードを公開していただいて構いません！」というスタンスで開催させていただいているオンラインイベントです。挑戦していただいた方々のコードが拝見できるのは毎回とても嬉しいです！
■まとめ
「模範解答見たけど何でこう書くといいのかいまいち分からん！」という方もいらっしゃるかもしれませんので、来週は模範解答コードのアルゴリズムについての解説記事を更新する予定です。そちらもぜひご覧くださいね！
■壁紙プレゼントについて
paizaに会員登録すると、下記の壁紙３種類がダウンロードできます！是非お気軽にご登録下さい！
paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。
自分のスキルを磨いていきたいと考えている方におすすめなのが「paizaラーニング」。オンラインでプログラミングしながらスキルアップできる入門学習コンテンツです。初心者でも楽しくプログラミングの基本を学ぶことができます。
そして、paizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
