Pengawal Gallivant

Kedatangan Kod 2024 Hari ke-6

Bahagian 1

Jenis teka-teki yang sangat biasa

• Grid 2D
• Halangan sepanjang
• Jejaki laluan
• Kira jubin unik yang dilawati

Mari kita lakukannya!

Satu langkah pada satu masa

Menghuraikan grid:

let grid = input.split('\n').map(el => el.split(''))

Mengenal pasti lokasi permulaan pengawal dan menggantikannya dengan jubin kosong:

let guard = null;
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

Mencipta objek untuk menjejaki putaran semasa pengawal:

let facing = [
  [-1,0],
  [0,1],
  [1,0],
  [0,-1]
]

• Pengawal mula menghadap ke utara, jadi pergerakan seterusnya memerlukan melawati barisan indeks yang lebih rendah
• Setiap halangan, pengawal mesti membelok ke kanan
• Itu akan menjadikan dia menghadap ke timur, jadi pergerakan seterusnya memerlukan melawati lajur indeks yang lebih besar
• Setiap kali sel seterusnya menjadi halangan, algoritma saya akan menarik item pertama daripada senarai dan mengalihkannya ke belakang

Menjejaki sel yang dilawati:

let visited = new Set()

Setiap langkah, saya akan cuba menambah koordinat bertali ke Set().

Menggerakkan pengawal:

while (true) {
  visited.add(guard.join(","));
  let next = [guard[0] + facing[0][0], guard[1] + facing[0][1]];
  if (
    next[0] >= 0 &&
    next[0] < grid.length &&
    next[1] >= 0 &&
    next[1] < grid[0].length
  ) {
    if (grid[next[0]][next[1]] == ".") {
      guard = next;
      console.log(guard);
    } else if (grid[next[0]][next[1]] == "#") {
      let oldDirection = facing.shift();
      facing.push(oldDirection);
    }
  } else {
    break;
  }
}

Penjelasan:

Keep going until manually broken out of
  Add the current coordinate to the tracked list
  Record the next location to visit
  If it is within the grid
    If it is empty cell
      Move the guard
    Else If it is an obstacle
      Rotate the guard
  Else
    Break out of the loop

Algoritma ini berjaya menghasilkan senarai sel yang dilawati sebanyak 41 untuk input contoh!

Adakah ia akan menjana jawapan yang betul untuk input teka-teki saya?

Ya!!!

Hebat.

Bersambung ke Bahagian 2!

Bahagian 2

Saya agak melihat ini datang, dan takut

Ol', semak setiap pilihan yang mungkin untuk satu teka-teki yang sah.

Persoalan besar saya apabila membaca ialah:

• Bagaimanakah saya akan mengenal pasti apabila pengawal memasuki gelung?

Tetapi saya rasa saya tahu:

• Saya akan menjejaki arah menghadap serta koordinat
• Jika senarai termasuk salinan yang seterusnya ditambah, maka gelung akan bermula

Masa untuk membuat perkara menjadi lebih rumit!

Menggulung setiap sel untuk mencari semua gelung

Pertama, saya ingin menjana senarai semua sel dengan ., tidak termasuk sel permulaan pengawal:

let empties = [];
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == ".") {
      empties.push([r, c]);
    }
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

Kemudian, gunakan pengurangan untuk melelaran setiap . dalam grid, menyalin grid dan kedudukan pengawal asal, mengalihkan banyak kod asal di dalam pengurangan, mengembangkan gelung sementara untuk memasukkan syarat bagi senarai koordinat dan putaran yang dijejaki yang mempunyai kejadian keadaan semasa:

let part2 = empties.reduce((count, coord) => {
    let guardCopy = guard.slice()
    let gridCopy = grid.map(row => row.slice())
    gridCopy[coord[0]][coord[1]] = "#"
    let facing = [
        [-1,0],
        [0,1],
        [1,0],
        [0,-1]
      ]
    let visited = new Set()
    while (true) {
        let stamp = guardCopy.join(',') + facing[0].join(',')
        if (visited.has(stamp)) {
            count++
            break;
        } else {
            visited.add(stamp);
            let next = [guardCopy[0] + facing[0][0], guardCopy[1] + facing[0][1]]
            if (
              next[0] >= 0 &&
              next[0] < gridCopy.length &&
              next[1] >= 0 &&
              next[1] < gridCopy[0].length
            ) {
              if (gridCopy[next[0]][next[1]] == ".") {
                guardCopy = next;
              } else if (gridCopy[next[0]][next[1]] == "#") {
                let oldDirection = facing.shift();
                facing.push(oldDirection);
              }
            } else {
              break;
            }
        }
    }
    return count
}, 0)

Memang banyak.

Tetapi ia berkesan! Sekurang-kurangnya pada input contoh.

Adakah ia berfungsi pada saya, walaupun???

Nah...ia mengambil masa 30 saat untuk dijalankan.

Tetapi...ia menjana jawapan!

Dan ia adalah...

JAWAPAN BETUL!!!

Woohoo!!!

Bahagian 1 adalah mudah. Dan Bahagian 2 adalah peningkatan yang sukar tetapi dialu-alukan.

Dua lagi bintang emas dalam beg!

Pada Hari ke-7.

Atas ialah kandungan terperinci Pengawal Gallivant. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!