Pembaikan Jambatan

Kedatangan Kod 2024 Hari ke-7

Bahagian 1

Ulangan pertama tahun ini

Sekurang-kurangnya itulah cara saya berhasrat untuk memperoleh satu bintang emas hari ini:

• Mulakan dengan senarai penuh
• Semak kedua-dua penambahan dan pendaraban
• Untuk setiap hasil, teruskan dengan baki senarai
• Sehingga saya telah melebihi atau menyamai jumlah keseluruhan

Kesukarannya adalah dalam butirannya.

Jom buat ini!

Mencipta algoritma saya

Pertama, saya perlu menghuraikan setiap baris ke dalam senarai nombor:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Elemen pertama ialah jumlah yang diingini.

Selebihnya ialah operan tertib persamaan.

Saya perlu mengambil kira perkara ini dalam fungsi rekursif saya.

Berikut ialah fungsi rekursif saya:

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

Dan inilah pengurangan yang menggunakannya:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

Seperti yang saya harapkan tetapi tidak pernah jangka, ia menghasilkan jawapan yang betul untuk input contoh!

Adakah ia akan selesai memproses input teka-teki saya?

Dan jika ya, adakah ia akan menjana jawapan yang betul?

Sejujurnya saya tidak pasti...

TIDAK DAH!!!

Wah!!!

Walaupun saya teruja, saya bimbang bahagian seterusnya akan sama ada menambah lebih banyak operator atau memerlukan beberapa CS lanjutan untuk menjadikan rekursi bukan lagi penyelesaian yang berdaya maju.

Bahagian 2

Benar-benar tidak dijangka! Dan jauh lebih sukar

Bagaimanakah saya akan melakukan ini?

...

Beberapa hari kemudian...

Imbas kembali proses pemikiran saya:

• Adakah ia semudah menambah klausa ketiga pada syarat pemulangan saya? Tidak
• Adakah fungsi rekursif Bahagian 1 saya dikonfigurasikan dengan betul untuk berjaya? Tidak
• Oh tidak, adakah mungkin untuk mengakru amaun hasil daripada operasi terdahulu? Tidak
• Adakah saya benar-benar perlu mendekati ini dengan strategi baharu? Ya

Memandangkan semua variasi baru

Untuk persamaan ini:

292: 11 6 16 20

Ini semua persamaan yang mungkin diberikan kepada tiga operator:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Mungkin saya boleh membina rentetan bagi setiap persamaan dan menilai secara manual di dalam fungsi rekursif saya.

Contohnya:
Saya mulakan dengan rentetan kosong dalam panggilan fungsi paling luar:

""

Dari situ, saya mencipta tiga variasi menggunakan nombor seterusnya:

"" + "+N"
"" + "*N"
"" + "N"

Hmm, tetapi ini tidak akan berfungsi untuk nombor pertama.

Saya perlu memulakan panggilan fungsi pertama saya dengan nombor pertama, bukan rentetan kosong:

"N"

Perkara yang sama dari sana:

"N" + "+N"
"N" + "*N"
"N" + "N"

Ya, itu sepatutnya berkesan.

Pada akhirnya, saya akan mempunyai variasi sampel ini, semuanya boleh dinilai:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Langkau ke: Saya mengekodkannya...dan menemui isu yang lebih besar

Saya menulis kod yang berjaya menjana semua variasi persamaan.

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

• saya digunakan untuk melihat senarai nombor
• Fasal terakhir hanya diteruskan jika i sebelum atau pada indeks kedua hingga terakhir

Fungsi mendapat empat nilai:

1. Salinan senarai nombor, tolak jumlah yang dijangkakan
2. Indeks seterusnya
3. Rentetan persamaan dengan satu daripada tiga rentetan yang digabungkan dengannya
4. Nombor ujian yang sama

Saya memanggil fungsi menggunakan tandatangan yang hampir sama seperti dalam Bahagian 1:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

Perbezaannya adalah pada apa yang saya sampaikan sebagai hujah:

1. Senarai tanpa jumlah amaun yang dijangkakan
2. Mulakan pada indeks 0
3. Rentetan yang mengandungi nombor pertama
4. Jumlah jumlah yang dijangkakan

Berita baik:

• Ia menjana semua variasi persamaan

Berita buruk:

• Ia menilai semua persamaan menggunakan PEMDAS, bukan kiri-ke-kanan

Saya sepatutnya lebih tahu...bahawa penilai JavaScript terbina dalam akan lalai kepada susunan operasi yang betul, bukan dari kiri ke kanan.

Ini benar-benar melemparkan sepana yang lebih besar ke dalam algoritma saya:

• Saya perlu memecahkan setiap persamaan dan menilai bahagian demi bahagian

Uggghhh.

Syukurlah, saya rasa saya tahu cara melakukannya.

Melakukan matematik secara manual

Saya perlu mendapatkan JavaScript untuk menilai persamaan seperti ini:

292: 11 6 16 20

Dalam susunan ini:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Saya ingin membahagikan persamaan itu kepada bahagian-bahagiannya:

""

Satu-satunya cara saya melihatnya ialah dengan ungkapan rantai tiga ini:

"" + "+N"
"" + "*N"
"" + "N"

Saya melapik setiap operator dengan ruang putih sahaja untuk menggunakannya sebagai pemisah.

Fakta tentang senarai bahagian persamaan ini:

• Ia akan sentiasa mengandungi jumlah ganjil item iaitu 3 atau lebih

Bagaimanakah saya boleh memanfaatkan fakta itu dalam beberapa gelung yang berulang melalui setiap pasangan pengendali-pengendali-pengendali?

Inilah idea saya:

• Alih keluar tiga item pertama
• Sertai mereka sebagai rentetan dan nilaikannya sebagai ungkapan matematik
• Lampirkan semula keputusan pada permulaan senarai persamaan
• Ulang sehingga senarai persamaan kosong

Semoga ia berkesan!

Simulator matematik saya yang berfungsi dalam JavaScript:

"N"

Berita baik:

• Ia menunjukkan kepada saya nilai pengiraan yang dijangkakan

Berita buruk:

• Saya masih tidak mendapat jawapan yang betul untuk satu persamaan dalam input contoh

Jawapan contoh tak boleh salah...boleh tak??

Jawapan yang terus saya hasilkan adalah lebih kurang 7k daripada jawapan yang dijangkakan.

Itu membuatkan saya fikir algoritma saya tidak mengenal pasti persamaan ini sebagai betul:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Dalam penjelasan input contoh, ini ialah persamaan kemenangan:

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

Algoritma saya menilai persamaan itu dan menjana hasil ini:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

Itu kerana algoritma saya berjalan seperti ini:

292: 11 6 16 20

Saya tidak nampak bagaimana ia boleh menjadi nombor lain.

Jadi...saya Google.

Dan saya menemui jawapan saya, yang bersembunyi di tapak kosong dalam penjelasan, seperti biasa:

Semua pengendali masih dinilai dari kiri ke kanan.

Saya telah menyatukan nilai dengan setiap panggilan fungsi rekursif.

Sebaliknya, algoritma saya sepatutnya melakukan ini:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Sekarang saya faham perkara yang sepatutnya berlaku, bolehkah saya melaraskan algoritma saya untuk memadankan gelagat pemprosesan itu?

Kiri-ke-kanan...sebenarnya kali ini

Syukurlah, melaraskan algoritma saya agak mudah.

Saya menambahkan klausa replaceAll() pada akaun ||.

Gelung sementara baharu di mana saya memproses setiap tiga item kelihatan seperti ini:

""

Dan saya melaraskan penyata pemulangan saya || klausa untuk memasukkan aksara tersebut, bukannya menggabungkan kedua-dua nombor dengan serta-merta.

Menguji dan menguji semula

Saya menjalankan algoritma pada input contoh.

Ia akhirnya menjana jawapan yang betul!!

Lega sangat!!

Saya tertanya-tanya jika ia akan selesai berjalan dan menjana jawapan yang betul pada input teka-teki saya.

Menekan larian...

...

...

Saya mendapat jawapan!

Ia besar, jadi itu mungkin petanda yang baik.

Adakah jawapan yang betul?

...

Tidak. Terlalu tinggi.

Mengecewakan.

Adakah saya kehilangan kes tepi?

Syarat saya untuk persamaan yang menang ialah matematik yang diproses bersamaan dengan jumlah ujian.

Tetapi, bagaimana jika salah satu persamaan varian membenarkan subset nombor menjana jawapan yang betul?

Untuk menangkap dan mengecualikan senario ini, saya mengemas kini syarat if saya untuk memasukkan satu lagi klausa:

"" + "+N"
"" + "*N"
"" + "N"

Dengan cara ini, hanya jika semua nombor diproses dan jumlah yang terhasil sama dengan nombor ujian, persamaan akan dikira.

Persoalan besar:

• Adakah ini mengubah jawapan yang saya dapat?

Tekan larian lagi...

...

Hmm, pasti jawapannya masih sama.

Oh, tunggu, ada dua digit dekat hujung yang berbeza!

Jawapan baharu saya betul-betul 80 kurang daripada sebelumnya.

Adakah terdapat persamaan dengan 80 sebagai jumlah yang dijangkakan?

Ya!

"N"

Adakah cara untuk membuat 80 tanpa menggunakan semua nombor?

Ya!

"N" + "+N"
"N" + "*N"
"N" + "N"

Adakah ini satu-satunya sarung tepi yang perlu saya kecualikan?

Menyerahkan jawapan baharu saya...

BETUL!!!

Woohoo!!!

Saya berjaya!!!

Itu. Adakah. meletihkan. Dan menggembirakan. Dan benar-benar berlari. Dan mencabar.

Dan setiap sebab mengapa saya suka melakukan teka-teki ini.

Maju ke yang seterusnya!

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