سرفصل‌ها درس 134 از 148 · غول خود را شکست بده
غول خود را شکست بده

بدون کش: تخفیف‌های ارث‌بری‌شده

چرا اهمیت دارد: «این کار را تکرار می‌کند، پس پاسخ‌ها را به خاطر بسپار» یکی از قوی‌ترین عادات در برنامه‌نویسی، چه انسان و چه هوش مصنوعی است. گاهی اصلاً نیازی به تکرار کار نیست.

دسته‌بندی‌های یک فروشگاه درختی را تشکیل می‌دهند: «باغ» زیر «خانه»، «ابزار» زیر «باغ» و غیره. یک مدیر بازاریابی می‌تواند برای هر دسته تخفیفی تعیین کند و این تخفیف برای همه زیرمجموعه‌های آن اعمال می‌شود مگر اینکه دسته‌ای نزدیک‌تر تخفیف خاص خود را تعیین کرده باشد. صفحه تسویه حساب به‌طور هم‌زمان تخفیف‌های مؤثر هزاران دسته را بررسی می‌کند.

داده‌ها

parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25}           # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]

راه حل بدیهی برای تکرار مسیر بالا رفتن در درخت، استفاده از کش است. در این مسئله، استفاده از کش ممنوع است. به دنبال راهی باشید که اصلاً کار را تکرار نکند.

نوبت شما

نوشتن effective_discounts(parents, own, queries). parents هر دسته‌بندی را به والد خود نگاشت می‌کند، یا None برای یک دسته‌بندی سطح بالا (ممکن است چندین مورد وجود داشته باشد و دیکت هیچ ترتیب خاصی ندارد). own برخی از دسته‌بندی‌ها را به تخفیف خاص خودشان نگاشت می‌کند. برای هر دسته‌بندی در queries، تخفیف نزدیک‌ترین دسته‌بندی در مسیر آن به سمت بالا، از خودِ آن شروع، که در آن یک مورد وجود دارد را بازمی‌گرداند own؛ ۰ اگر هیچ‌کدام نداشته باشد. قاعده: بدون کش یا ممو: بدون functools تزئین‌کننده‌های حافظه پنهان، بدون نامی که شامل «cache» یا «memo» باشد، و بدون ارائه پاسخ‌های کاری همزمان با دریافت آن‌ها از پرس‌وجوها و نگهداری‌شان (یک memo با نامی دیگر). ابتدا کل درخت را بررسی کنید، سپس پرس‌وجوها را بخوانید. بودجه: حداکثر ۵۰۰٬۰۰۰ گام (steps()) برای ۳۰۰۰ دسته‌بندی، درخت‌هایی با عمق چند صد سطح و ۲۰٬۰۰۰ جست‌وجو.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.