Pelajaran dan game belajarnya

Rekursi dan backtracking

Fungsi yang memanggil dirinya sendiri, dari hitung mundur sampai pemecah Sudoku, di Raspberry Pi 4, dengan batas kedalaman sungguhan dari engine diajarkan dengan jujur.

Kursusnya

Rekursi dan backtracking adalah kursus Coding menengah dalam tujuh pelajaran, setelah Python dari nol dan Fix the bug. Sebagian besar berjalan di build Pi dua LED milik galeri (merah di GPIO17, kuning di GPIO27), dan boss memakai modul lampu lalu lintas. Setiap langkah diperiksa terhadap apa yang dicetak Pi atau apa yang dilakukan pin-pinnya, dan setiap angka dalam pelajaran adalah angka yang benar-benar dicetak program.

  1. Panggilan yang memanggil dirinya sendiri: hitungan mundur tanpa loop, call stack digambar sebagai indentasi saat terisi dan terurai, faktorial dengan bilangan bulat besar yang persis (25! selengkapnya), segitiga Sierpinski dicetak sebagai teks, dan sebuah LED berkedip lima kali lewat rekursi.
  2. Base case: penyelaman gua tanpa dasar yang meluapkan stack, base case yang menghentikannya, batas kedalaman yang terukur (sedikit di bawah 1.000 panggilan untuk fungsi kecil), pemangkatan dengan pengkuadratan (2^100 dalam 8 panggilan) dan mengapa alur kerja garis lurus sebaiknya memakai loop.
  3. Tree walks: a cave of tunnels stored as nested tuples, printed as an outline, its 9 rooms counted, its deepest point found, a route to the glow worm grotto by depth-first search, then the Pi's own folders walked with the same pattern.
  4. Permutasi: setiap urutan sebuah kru, n! dihitung sampai 720, sinyal alien teracak yang didekode terhadap satu himpunan kata, muatan rover yang dikemas dengan pola include-atau-skip, dan hasilnya diperiksa terhadap itertools.permutations.
  5. Backtracking: N queens dengan pilih, jelajahi, batal pilih; setiap solusi dihitung dari 4 sampai 8 (92 untuk papan catur); 15.720 kotak diperiksa, bukan 16 juta papan; LED kuning berkedip di setiap backtrack; dan pelarian dari labirin gua laut.
  6. Memoization: 21.891 panggilan Fibonacci naif untuk fib(20), dictionary yang memangkasnya jadi 39, functools.lru_cache dengan hitungan hit dan miss-nya, 601.080.390 rute rover melintasi grid, dan 242 cara membayar satu dolar.
  7. Boss: solver Sudoku: penutup.

Babak final

Boss membangun solver Sudoku lengkap dalam sekitar dua puluh baris. Ia memuat teka-teki sungguhan, menulis aturannya sebagai fungsi dan mengujinya pada satu sel, lalu memecahkan grid dengan backtracking: cari sel kosong pertama, coba setiap digit yang cocok, pecahkan sisanya, dan ambil kembali digit itu bila gagal. Pemeriksaan independen membuktikan setiap baris, kolom dan kotak berisi 1 sampai 9 (4.208 penempatan untuk teka-teki ini), lampu lalu lintas menyala kuning saat berpikir dan hijau saat terpecahkan, dan sebuah penjaga membuat lampu merah untuk teka-teki yang melanggar aturan sebelum solver membuang waktu sedetik pun padanya.

Yang berbeda dari engine Pi

Pi menjalankan MicroPython 1.29, bukan CPython, dan rekursi adalah tempat hal itu paling terlihat:

  • Rekursi yang terlalu dalam memunculkan RuntimeError: maximum recursion depth exceeded, atau RuntimeError: pystack exhausted untuk fungsi dengan banyak variabel lokal. RecursionError, nama dari CPython, tidak terdefinisi di sini. Pelajaran menangkap RuntimeError, yang bekerja di keduanya, karena RecursionError milik CPython adalah salah satu jenis RuntimeError.
  • Batasnya adalah memori stack, bukan hitungan tetap: sekitar 980 panggilan untuk fungsi kecil, lebih sedikit untuk yang lebih besar. Tidak ada sys.setrecursionlimit.
  • Dict tidak menyimpan urutan masuknya key, jadi pohon disimpan sebagai list dan tuple, dan os.listdir serta set diurutkan sebelum dicetak.
  • str.ljust dan str.rjust tidak ada, jadi padding dibuat dengan " " * count. Bilangan bulat tidak punya batas ukuran, seperti di CPython.

Selebihnya di kursus ini, functools.lru_cache, itertools dan os, berjalan seperti di Pi sungguhan.