Kuku Ia

Kedatangan Kod 2024 Hari 10

Bahagian 1

Kengerian singkat, kemudian keterujaan

Saya biasanya menyelak halaman sebelum membaca semuanya dengan teliti.

Hari ini, saya melihat:

• Sebuah grid
• dan yang kelihatan seperti laluan

Dan saya bimbang ini akan menjadi satu lagi cabaran laluan terpendek.

Kemudian saya membacanya.

Dan menarik nafas lega...sekurang-kurangnya untuk Bahagian 1.

Saya perlu mencari semua laluan yang sah.

Itu...saya boleh buat!

Mula dari 0

Saya perlu mencari semua 0s:

input = input
  .split('\n')
  .map(
    line => line.split('').map(char => +char)
  )
let zeros = []
for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        if (input[r][c] == 0) {
            zeros.push([r,c])
        }
    }
}

0s: ditemui!

Percubaan untuk bergerak dalam kenaikan 1

Dari setiap 0, laluan yang sah ialah sembilan langkah di mana setiap nombor adalah satu lebih besar daripada yang terakhir, berakhir pada 9.

Ini kelihatan seperti kerja untuk pengulangan.

Saya memerlukan kes asas:

1. Nombor semasa tidak betul-betul satu lebih besar daripada sebelumnya
2. Nombor semasa ialah 9

Begini cara algoritma saya harus berfungsi:

Input:
1. Originating number
2. Current coordinates

Get current number

If it is not exactly one greater than the originating number
  Return false
Else
  If it is 9
    Return the current coordinates
  If it is not 9
    Continue with the coordinates in each orthogonal direction

Setelah menulisnya, bahagian yang saya terlepas ialah menjejaki lejar koordinat akhir yang sah.

Saya bergelut dengan perkara ini untuk beberapa lama.

Saya terus mendapat ralat yang tersilap membuatkan saya fikir saya tidak boleh lulus dalam Set mahupun tatasusunan.

Tetapi, syukurlah, saya terlupa untuk meneruskannya ke dalam panggilan lanjut fungsi rekursif.

Berikut ialah algoritma rekursif saya yang berfungsi:

let dirs = [[-1,0],[0,-1],[0,1],[1,0]]
function pathFinder(num, coord, memo) {
    let current = input[coord[0]][coord[1]]
    if (current - num !== 1) {
        return false
    } else if (current == 9) {
        memo.add(coord.join(','))
        return
    } else {
        dirs.forEach(dir => {
            if (
                coord[0] + dir[0] >= 0 &&
                coord[0] + dir[0] < input.length &&
                coord[1] + dir[1] >= 0 &&
                coord[1] + dir[1] < input[0].length
            ) {
                pathFinder(
                  current, 
                  [coord[0] + dir[0], coord[1] + dir[1]], 
                  memo
                )
            }
        })
    }
}

Memandangkan saya mesti bermula dengan koordinat 0s, panggilan pertama saya menggunakan -1:

pathFinder(-1, zeroCoordinate, matches)

Akhir sekali, untuk mendapatkan skor yang betul, saya mengulangi setiap sifar, menjana set unik destinasi 9s, menyimpan dan meringkaskan saiz set:

let part1 = zeros.map(z => {
    let matches = new Set()
    pathFinder(-1, z, matches)
    return matches.size
}).reduce((a, c) =>  a + c)

Ujian cepat, keputusan cepat

Ia menghasilkan jawapan yang betul untuk input contoh kecil.

Dan untuk input contoh yang lebih besar.

Dan...

...untuk input teka-teki saya!!!

Woohoo!!!

Apa yang akan dicabar oleh Bahagian 2 saya?

Bahagian 2

Umm, nampaknya terlalu mudah

Adakah mungkin cara saya menulis algoritma saya dalam Bahagian 1 bermakna ini hanya memerlukan beberapa perubahan kecil untuk mendapatkan jawapan yang betul?

Kira mereka semua!

Sekarang, saya menambah setiap 9 yang sah pada satu set.

Untuk Bahagian 2, saya rasa saya hanya perlu menambah satu pembilang untuk setiap 9 yang sah.

Berbaloi untuk dicuba!

Tukar Set kepada Array dan voila!

Jawapan yang betul untuk contoh.

Jawapan yang betul untuk input teka-teki saya.

Wah. Wah. Wah.

Bersambung ke hari berikutnya...yang mungkin lebih sukar.

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