Dersler ve öğrenme oyunu

Özyineleme ve geri izleme

Kendini çağıran işlevler, bir geri sayımdan bir Sudoku çözücüsüne, Raspberry Pi 4 üzerinde, motorun gerçek derinlik sınırı dürüstçe öğretilerek.

Kurs

Özyineleme ve geri izleme, Python from zero ve Fix the bug derslerinden sonra gelen, yedi derslik orta seviye bir Kodlama kursu. Çoğu galerideki iki LED'li Pi kurulumunda çalışır (GPIO17'de kırmızı, GPIO27'de sarı) ve boss trafik lambası modülünü kullanır. Her adım, Pi'nin yazdırdıklarıyla veya pinlerinin yaptıklarıyla kontrol edilir ve derslerdeki her sayı, programın gerçekten yazdırdığı bir sayıdır.

  1. Kendini çağıran çağrılar: döngüsüz bir geri sayım, sarılırken ve çözülürken girinti olarak çizilen çağrı yığını, tam büyük tamsayılarla faktöriyel (25! tam haliyle), metin olarak yazdırılan bir Sierpinski üçgeni ve özyinelemeyle beş kez yakıp söndürülen bir LED.
  2. Temel durumlar: tabanı olmayan ve yığını taşıran bir mağara dalışı, onu durduran bir temel durum, ölçülen derinlik sınırı (küçük bir fonksiyon için 1.000 çağrının biraz altı), kareleyerek üs alma (2^100 sadece 8 çağrıda) ve düz bir iş neden döngüye ait olmalı.
  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. Permütasyonlar: bir mürettebatın her sıralaması, 720'ye kadar sayılan n!, bir kelime kümesine karşı çözülen karışık bir uzaylı sinyali, dahil et veya atla deseniyle paketlenen gezici yükleri ve sonucun itertools.permutations ile kontrol edilmesi.
  5. Geri izleme: seç, keşfet, seçimi geri al ile N vezir; 4'ten 8'e her çözüm sayılıyor (satranç tahtası için 92); 16 milyon tahta yerine 15.720 kare kontrol ediliyor; her geri izlemede sarı LED yanıp sönüyor; ve bir deniz mağarası labirentinden kaçılıyor.
  6. Notlama (memoization): saf Fibonacci'nin fib(20) için 21.891 çağrısı, bunu 39'a indiren bir sözlük, isabet ve ıska sayılarıyla functools.lru_cache, bir ızgara boyunca 601.080.390 gezici rotası ve bir doları oluşturmanın 242 yolu.
  7. Boss: bir Sudoku çözücü: final.

Final

Boss, yaklaşık yirmi satırda tam bir Sudoku çözücü kuruyor. Gerçek bir bulmaca yükler, kuralları bir fonksiyon olarak yazar ve tek bir hücrede test eder, sonra ızgarayı geri izlemeyle çözer: ilk boş hücreyi bul, uyan her rakamı dene, gerisini çöz ve bu başarısız olursa rakamı geri al. Bağımsız bir kontrol her satır, sütun ve kutunun 1'den 9'a olduğunu kanıtlar (bu bulmaca için 4.208 yerleştirme), trafik lambaları düşünürken amber, çözülünce yeşil gösterir ve bir koruma, kural bozan bir bulmaca için çözücü vakit harcamadan önce lambayı kırmızıya çevirir.

Pi motoru neyi farklı yapar

Pi, CPython değil MicroPython 1.29 çalıştırıyor ve bu en çok özyinelemede kendini gösteriyor:

  • Çok derin bir özyineleme RuntimeError: maximum recursion depth exceeded ya da çok yerel değişkenli bir fonksiyon için RuntimeError: pystack exhausted hatası verir. CPython'ın adı olan RecursionError burada tanımlı değildir. Dersler her ikisinde de çalışan RuntimeError'ı yakalar, çünkü CPython'ın RecursionError'ı bir çeşit RuntimeError'dır.
  • Sınır sabit bir sayı değil, yığın belleğidir: minik bir fonksiyon için yaklaşık 980 çağrı, daha büyük biri için daha az. sys.setrecursionlimit yoktur.
  • Dict'ler anahtarların giriliş sırasını korumaz, bu yüzden ağaçlar listeler ve tuple'lar olarak saklanır ve os.listdir ile kümeler yazdırmadan önce sıralanır.
  • str.ljust ve str.rjust eksiktir, bu yüzden dolgular " " * count ile kurulur. Tamsayıların boyut sınırı yoktur, CPython'daki gibi.

Kurstaki geri kalan her şey, functools.lru_cache, itertools ve os, gerçek bir Pi'deki gibi çalışır.