11 Temmuz 2018

Euler Projesi 244. Soru

Kayan Desenler

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)p244_start.gif, (E)p244_example.gif

Her yol için sağlama toplamı (pseudocode) aşağıdaki gibi hesaplanır:

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

Buradaki mk, hareket dizisindeki k. harfin ASCII değeridir ve hareketler için ASCII değerleri şu şekildedir:
L76
R82
U85
D68

Yukarıda verilen LULUR dizisi için sağlama toplamı 19761398'dir.

Şimdi, (S) konfigürasyondan başlayarak (T) konfigürasyonuna ulaşmanın en kısa yollarını bulun.

(S)p244_start.gif, (T)p244_target.gif

Minimum uzunluğa sahip yollar için tüm sağlama toplamlarının toplamı nedir?
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, Queue 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");
 }

Python:
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="">