Muhtemelen On Beş Yapbozunu biliyorsunuzdur. Burada numaralı desenler yerine yedi kırmızı ve sekiz mavi desen var.
Bir hareket, desenin kaydırıldığı yönün (Sol-L, Sağ-R, Yukarı-U, Aşağı-D) baş harfiyle ifade ediliyor, örn. (S) konfigürasyondan başlayarak LULUR dizisi ile (E) konfigürasyona ulaşırız:
| (S) |  | , (E) |  |
checksum = 0
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
…
checksum = (checksum × 243 + mn) mod 100 000 007
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
…
checksum = (checksum × 243 + mn) mod 100 000 007
| L | 76 |
| R | 82 |
| U | 85 |
| D | 68 |
Şimdi, (S) konfigürasyondan başlayarak (T) konfigürasyonuna ulaşmanın en kısa yollarını bulun.
| (S) |  | , (T) |  |
(Project Euler)
Cevap: 96356848
C++:
#include#define s 0xcccc #define t 0x5a5a //#define t 0xff00 //#define t 0xeb714 //#define t 0xf3333 char *dirs="LRUD",moves[16][4]; int dist[65536*16]; unsigned long long ways[65536*16]; unsigned long long *checksum[65536*16]; unsigned long long pathcs[2291880],npathcs; void create_moves() { int gap,dir; for (gap=0;gap<16 dir="=0?(gap&3)==3:dir==1?(gap&3)==0:dir==2?gap" for="" gap="" if="">=12:gap<4 dir="=0?1:dir==1?-1:dir==2?4:-4);" else="" gap1="" gap2="" gap="" inline="" int="" moves="" next="" pos="" return="" xffff="">>gap1&1)< >gap2&1)< >16,dir,gap2,pred,preds[4]; for (dir=0;dir<4 all="" break="" check="" checksum="" comment="" create_moves="" dir="" dirs="" dist="" else="" for="" gap2="" gap="pos" get_checksums="" i="" if="" int="" lastntodo="" long="" main="" ndone="" npathcs="" ntodo="" pathcs="" paths="" pos2="" pos="todo[ndone++];" positions="" pred="" preds="" s="" step="" t="" to="" todo="" unsigned="" ways="" while="">>16; for (dir=0;dir<4 all="" checksum="" checksums="" comment="" dir="" dist="" for="" gap2="moves[gap][dir])!=-1)" get="" get_checksums="" i="" if="" long="" ntodo="" pos2="" pos="" pre="" printf="" step="" sum="" t="" to="" todo="" unsigned="" ways="" x=""> C#: // state is 20 bits, 0=red, 1 = blue, in lower 16, then bits 17-20 store // value 0-15 where open spot is. Open spot always stored as 0 // for each state, store shortest path to get there as a string, or "" if not visited static string [] states = new string[1 << 20]; static int [] pathCount = new int[1<<20 1="" 4="" a="" an="" b="" c="=" char="" convert="" current="" decode="" else="" for="" grid="" i="" if="" image="" index="" int="" j="" mask="" number="" of="" out="" paths="" return="" shortest="" start="index" startx="" starty="" state="" static="" string="" the="" to="" uint="" void="" x="">> 16; for (int j = 0; j < 4; ++j) for (int i = 0; i < 4; ++i) { if ((index & 1) == 1) grid[i, j] = 'b'; else grid[i, j] = 'r'; index >>= 1; } startx = start & 3; starty = start / 4; grid[startx, starty] = 'x'; } // convert grid to index static uint Encode() { int index = 0; int start = 0; int mask = 1; for (int j = 0; j < 4; ++j) for (int i = 0; i < 4; ++i) { char c = grid[i, j]; if (c == 'b') index |= mask; else if (c == 'x') start = i + j * 4; mask <<= 1; } return (uint)(index + (start << 16)); } static ulong Checksum(string s) { ulong check = 0; foreach (char c in s) { check *= 243; if (c == 'U') check += 85; if (c == 'D') check += 68; if (c == 'L') check += 76; if (c == 'R') check += 82; check %= 100000007; } return check; } static void Check(uint x, uint y, int dx, int dy, string path, QueuePython:nodes, string dir, int pCount) { char c; c = grid[x +dx, y + dy]; grid[x + dx, y + dy] = grid[x, y]; grid[x, y] = c; uint move = Encode(); if (states[move] == "") { states[move] = path + dir; nodes.Enqueue(move); } else if (states[move].Length == path.Length + 1) pathCount[move] += pCount; c = grid[x + dx, y + dy]; grid[x + dx, y + dy] = grid[x, y]; grid[x, y] = c; } static void BreadthSearch(Queue nodes) { uint pass = 0; int lastLength = 0; // last seen path length while (nodes.Count > 0) { uint x,y; uint index = nodes.Dequeue(); Decode(index, out x, out y); string path = states[index]; int pCount = pathCount[index]; if (path.Length < lastLength) Console.WriteLine("ERROR!"); lastLength = path.Length; if (0 < x) Check(x, y, -1, 0, path, nodes, "R", pCount); if (x < 3) Check(x, y, 1, 0, path, nodes, "L", pCount); if (0 < y) Check(x, y, 0, -1, path, nodes, "D", pCount); if (y < 3) Check(x, y, 0, 1, path, nodes, "U", pCount); } } // fill in final grid static void FinalGrid() { for (int j = 0; j < 4; ++j) for (int i = 0; i < 4; ++i) { if (((i+j)&1)==1) grid[i, j] = 'b'; else grid[i, j] = 'r'; } grid[0, 0] = 'x'; } public static void Run(bool sample) { if (!sample) Console.WriteLine("Check " + Checksum("LULUR") + "=19761398"); for (int i = 0; i < states.Length; ++i) states[i] = ""; // fill initial grid for (int j = 0; j < 4; ++j) for (int i = 0; i < 4; ++i) { if (i < 2) grid[i, j] = 'r'; else grid[i, j] = 'b'; } grid[0, 0] = 'x'; Queue nodes = new Queue (); nodes.Enqueue(Index()); pathCount[Index()] = 1; BreadthSearch(nodes); FinalGrid(); uint finalIndex = Index(); string ans = states[finalIndex]; if (pathCount.Max() == 1) Console.WriteLine("Ans {0}=96356848", Checksum(states[finalIndex])); // answer is unique else Console.WriteLine("Needs more work - path not unique"); } def TT(L): return tuple([tuple(l) for l in L]) def LL(T): return list([list(t) for t in T]) def move(grid, direction): grid = LL(grid) zero = None for r in range(4): for c in range(4): if grid[r][c] == 0: zero = r, c break if zero: break r, c = zero #grid = copy.deepcopy(grid) if direction == "L": if c == 3: raise ValueError grid[r][c], grid[r][c+1] = grid[r][c+1], grid[r][c] return TT(grid) if direction == "R": if c == 0: raise ValueError grid[r][c-1], grid[r][c] = grid[r][c], grid[r][c-1] return TT(grid) if direction == "U": if r == 3: raise ValueError grid[r][c], grid[r+1][c] = grid[r+1][c], grid[r][c] return TT(grid) if direction == "D": if r == 0: raise ValueError grid[r-1][c], grid[r][c] = grid[r][c], grid[r-1][c] return TT(grid) def show(grid): s = '' for row in grid: for col in row: if col == 0: s += ' ' if col == 1: s += '#' if col == 2: s += '%' s += "\n" print s S = ((0, 1, 2, 2), (1, 1, 2, 2), (1, 1, 2, 2), (1, 1, 2, 2)) E = ((0, 2, 1, 2), (2, 1, 2, 1), (1, 2, 1, 2), (2, 1, 2, 1)) @memoized def recurse(N, grid): if grid == E: print "x", return [-1] if N == 0: return [None] res = [] for p in "LRUD": try: L = move(grid, p) except ValueError: continue tmp = [p] + recurse(N-1, L) if "-1" in str(tmp): res.append(tmp) return res tmp = recurse(32, S) # Heh... tmp = str(tmp).replace('[','').replace(']','').replace(',','').replace("'",'').replace(' ','').replace('-1','') def checksum(moves): checksum = 0 for m in moves: checksum = (checksum * 243 + ord(m)) % 100000007 return checksum print checksum(tmp)Mathematica:let _ = let (l, r, u, d) = (76, 82, 85, 68) in let e = Array.make_matrix 16 (1 lsl 16) [] in for i = 0 to 15 do for j = 0 to (1 lsl 16) - 1 do if j land (1 lsl i) = 0 then ( let x = i land 3 and y = i lsr 2 in if x < 3 then ( let v = (j lor ((j land (1 lsl (i + 1))) lsr 1)) land (lnot (1 lsl (i + 1))) in e.(i).(j) <- 1="" ::="" e.="" i="" if="" j="" l="" v="" x=""> 0 then ( let v = (j lor ((j land (1 lsl (i - 1))) lsl 1)) land (lnot (1 lsl (i - 1))) in e.(i).(j) <- -="" 1="" 3="" 4="" ::="" e.="" i="" if="" in="" j="" land="" let="" lnot="" lor="" lsl="" lsr="" r="" then="" u="" v="" y=""> 0 then ( let v = (j lor ((j land (1 lsl (i - 4))) lsl 4)) land (lnot (1 lsl (i - 4))) in e.(i).(j) <- -="" 0="" 100000007="" 16="" 2000000="" 243="" 4="" ::="" bfs="" c="Array.make_matrix" csum="" d="" done="" e.="" false="" i="" in="" j="" l1="" l2="if" let="" lsl="" mod="" q1="" q2="" rec="" s="" u="Array.make_matrix" v=""> 0 then ( l2 := 0; for i = 0 to !l1 - 1 do let (ui, uj) = q1.(i) in u.(ui).(uj) <- -="" 1="" dir="" do="" done="" for="" fun="" i="" in="" l1="" let="" list.iter="" q1.="" to="" true="" ui="" uj="" vi="" vj=""> if not u.(vi).(vj) then ( c.(vi).(vj) <- 0xcccc="" :="1;" bfs="" c.="" csum="" d="" dir="" done="" e.="" in="" incr="" l1="" l2="" n="" pre="" printf.printf="" q1.="" q1="" q2.="" q2="" res="" true="" u.="" ui="" uj="" vi="" vj="" x5a5a="" xcccc="">