Serpihan Cakera

Kedatangan Kod 2024 Hari 9

Bahagian 1

Sarung tangan tiga fasa. mengujakan!??

Fasa seperti yang saya lihat dinyatakan:

1. Mewakili ingatan sebagai senarai
2. Pindahkan nilai dari hujung ke permulaan
3. Berbaris untuk mengira jumlah semak

Tiada satu pun yang terasa amat sukar.

Dan sebahagian daripadanya sebenarnya kelihatan seperti satu lagi cabaran algoritma yang menyeronokkan!

Membuat senarai

Saya mahu mengubah ini:

12345

Ke dalam ini:

0..111....22222

Saya perlu mempertimbangkan:

• Menggunakan gelung
• Menyemak indeks genap dan ganjil
• Menambah nilai sebanyak 1, bermula daripada 0

Berikut ialah algoritma penjanaan cakera saya:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

Berfungsi seperti azimat!

Memindahkan nilai dari hujung ke permulaan

Apa yang akan menjadikan ini lebih mudah ialah mempunyai senarai semua tempat kosong pada cakera.

Saya perlu mengemas kini algoritma saya di dua tempat:

1. Pembolehubah baharu: biarkan kosong = []
2. Tindakan baharu selepas memasukkan .: empty.push(disk.length - 1)

Mengujinya pada contoh menunjukkan nombor indeks yang dijangkakan bagi setiap satu .!

Ini ialah senarai yang akan saya ulangi semasa saya mengalihkan nilai dari penghujung senarai ke permulaan dan seterusnya.

Tetapi tunggu.

Ini mungkin lebih sukar daripada yang saya fikirkan.

Bagaimanakah saya akan tahu bila hendak berhenti cuba mengalihkan nilai?

• Adakah saya mengulangi senarai indeks kosong? Bilakah saya harus berhenti?
• Adakah saya mengundur ke belakang melalui cakera? Bilakah saya harus berhenti?

Epiphany: nombor ajaib 10

Ini ialah keadaan terakhir contoh ringkas:

022111222......

Dan contoh pertama:

0099811188827773336446555566..............

Maksudnya ada satu titik di mana semua id berada di sebelah kiri dan semua ruang kosong berada di sebelah kanan.

Bagaimanakah saya akan menyemak keadaan itu?

Masukkan: nombor 10.

Jumlah ruang kosong bersebelahan tidak akan lebih tinggi daripada 9.

Jadi, jika saya terjumpa ruang kosong, lihat ke hadapan 9 ruang (atau pada penghujung senarai cakera) dan lihat semua ruang kosong, saya tahu saya akan selesai memecah belah.

Saya rasa saya tahu cara menulis baki algoritma ini!

Menulis algoritma pemecahan saya

Berikut ialah algoritma yang berfungsi:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

Cara ia berfungsi:

Two trackers:
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

Syukurlah, saya melihat output yang sama seperti dalam kedua-dua contoh!

Mengira checksum

Ini nampaknya agak mudah dan mudah:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

Dalam pseudokod:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

Berjaya! Ia menjana jawapan yang betul untuk input contoh!

Adakah ia melakukan perkara yang sama untuk input teka-teki saya?

...

YA!!!

Woohoo!!!

Apakah kelainan untuk Bahagian Kedua? Sedikit pelarasan peraturan atau beberapa cabaran skala?

Bahagian 2

Satu kelainan yang menarik

Adalah bahagian. Kini lengkap.

Ini pasti memerlukan sedikit pelarasan algoritma saya.

Mungkin penjejakan saiz celah dan blok yang lebih mantap.

Bekerja melalui strategi pertama saya

Saya telah menjejaki di mana setiap kosong.

Saya rasa saya perlu menjejaki di mana - dan berapa besar - setiap kosong.

Apakah rupanya?

Cakar itu. Mungkin strategi baharu.

Menggunakan contoh pertama:

12345

Saiz blok fail ialah nombor ganjil:

0..111....22222

Saiz sel kosong ialah nombor genap:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

Bermula dari penghujung nombor ganjil dan permulaan nombor genap, saya mencari nombor genap yang lebih besar daripada atau sama dengan nombor ganjil:

022111222......

Saya segera mencari padanan.

Hasilnya:

• Nombor ganjil bergerak
• Nombor genap berkurangan
• Tetapi sekarang dua nombor ganjil itu tidak mempunyai jurang
• Dan saya telah kehilangan ID 2s kedua

0099811188827773336446555566..............

Strategi ini pasti tidak akan berjaya.

Bekerja melalui strategi kedua saya

Saya tidak suka implikasi prestasi yang satu ini.

Tetapi saya percaya ia akan berkesan...selagi ia selesai dijalankan.

Untuk setiap nombor dalam input cakera, saya akan merekodkan sebagai item senarai:

1. Blok fail atau sel kosong
2. Panjang
3. ID

Sebagai contoh:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

Akan menjadi:

Two trackers:
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

Eh, jom bersihkan:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

Saya akan membezakan jurang daripada blok fail mengikut jenis data.

Mengalih blok fail akan kelihatan seperti ini dalam input contoh yang diubah:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

Ini akan melibatkan setiap 100k lelaran:

• Mencari item dalam susunan yang besar
• Memutasi tatasusunan di tempat

Kedua-duanya adalah tugas yang sangat mahal.

Tetapi ini satu-satunya cara yang saya boleh fikirkan untuk menyelesaikan teka-teki ini.

Jadi, inilah pendekatan saya.

Mengkodkan strategi saya

Berikut ialah JavaScript yang memberikan saya seni bina data di atas:

2333133121414131402

Bagaimanakah saya akan memulakan dan menamatkan gelung utama saya?

Cuba untuk mengalihkan setiap fail tepat sekali mengikut urutan mengurangkan nombor ID fail bermula dengan fail dengan nombor ID fail tertinggi

Nampaknya bergerak ke belakang ke hadapan akan melakukan apa yang saya perlukan.

Rangka gelung ini sepatutnya berfungsi:

[2,4,1,4,2,5,5,3,5,2]

Cari, pindah dan ganti

[3,3,3,1,1,1,1,1,0]

Fasal kedua dalam if itu ialah nyahpepijat terakhir saya. Ia meletakkan ID terendah terlalu awal.

Mengekodkan pencetak cakera

Saya menyedari bahawa saya terpaksa melihat cakera saya dipecahkan dalam masa hampir-nyata. Sekurang-kurangnya log itu, seperti dalam contoh panduan.

Syukurlah, pengekodan tidak sukar. Hanya bahagian di mana saya mencampurkan dua indeks dan melihat beberapa output pelik sebenar:

12345

• Saya membina rentetan
• Berdasarkan jenis item dalam cakera
• Sama ada cara saya membuat tatasusunan dan mengisinya dengan sama ada .s atau ID blok

Ia berfungsi hebat! Saya dapat melihat tempat fail sedang dialihkan dan menyelesaikan masalah kod saya dengan lebih mudah!

Suka dengan apa yang saya lihat

0..111....22222

Nampaknya algoritma pemindahan fail saya berfungsi!

Langkah terakhir ialah mengira jumlah semak baharu.

Akhir sekali, lebih banyak matematik

Dengan cara pengurangan dua kali:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

• Pengurangan pertama memberi saya pelbagai id dan .s
• Penurunan kedua melakukan matematik yang sesuai apabila item itu ialah id dan tiada matematik apabila ia adalah .

Adakah ia berfungsi?

Pada input contoh teka-teki? YA!

Pada input teka-teki saya?

...

YEEESSSSSS!

Wah. saya terkejut. Nombor yang saya serahkan untuk Bahagian 2 hampir sama dengan Bahagian 1. Saya fikir ia akan lebih tinggi.

Saya tidak berminat untuk menyiasat lebih lanjut.

Saya lebih suka mengambil dua bintang emas saya yang susah payah dan berjalan ke Hari 10.

Byeeeeee Hari ke-9!

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