در طی نوروز ۱۴۰۱، در ۸ توویت با هش‌تگ #پیک‌نوروزی ۸ سوال و تمرین مطرح کردم. در این بلاگ‌پست و چند بخش بعدی این سوال‌ها و پاسخ‌ها را می‌آورم.

در این بخش:

• روز ۱. فشرده‌سازی اعداد شبهه‌تصادفی
• روز ۲. کاشی‌کاری فیبوناچی
• روز ۳. نمودار اشتراک ۴ مجموعه
• روز ۴. مقدار بازگشتی تابع fork

روز ۱. فشرده‌سازی اعداد شبهه‌تصادفی

لینک توویت: https://twitter.com/pykello_fa/status/1505806994241859585

می‌خواهیم خروجی برنامه‌ی زیر را که تعدادی عدد با استفاده از ماژول random پایتون تولید می‌کند را فشرده کنیم و به یکی ارسال کنیم.

با فرض اینکه گیرنده سورس‌کد برنامه‌ی ما را از قبل دارد و دقیقا می‌داند خروجی چگونه تولید شده، چه روش فشرده‌سازی پیشنهاد می‌دهید؟

پاسخ و بحث

لینک توویت پاسخ: https://twitter.com/pykello_fa/status/1506122913828667393

جواب‌های خوبی با فرض‌هایی که هر کسی کرده بود داده شد.

هدفم از این سوال تاکید بر این بود که تابع random.randint تصادفی کامل نیست، و شبهه‌تصادفی‌است. یعنی اگر random.seed «یکسان» اول هر کدی بگذارید که با استفاده از کتابخانه‌ی random مقادیری رو تولید می‌کند، هر دفعه دقیقا خروجی یکسان خواهید گرفت.

مثلا کد زیر حتی اگر ۱۰ بار هم اجرا کنم، نتیجه همان خواهد بود:

دقت کنید که اگر seed رو ریست نکنیم، دنباله متفاوت خواهد بود (دو لیست اول رو با لیست آخر مقایسه کنید):

حال اگر بجای t = int(time.time()) در کد مساله‌ی اصلی یک عدد ثابت بگذارم، خروجی حتی پس از ۱۰۰ بار اجرا باز هم همان خروجی اولیه خواهد بود.

پس مقدار t است که مشخص‌کننده‌ی خروجی است، و با توجه به اینکه فرض کردیم گیرنده سورس‌کد تولید کننده را دارد، کافی‌است t را به گیرنده بفرستیم تا همان خروجی را بگیرد.

❓ سوال: ما الان فقط خروجی رو داریم و t رو چاپ نکردیم، چه کنیم؟

💭 هر روز ۸۶۴۰۰ ثانیه بیشتر ندارد، می‌تونید از زمان حال شروع کنید و ثانیه به ثانیه عقب بروید و دنباله رو تولید و دنباله‌ی چاپ شده مقایسه کنید تا t ای که دنباله رو تولید کنه رو پیدا کنید من این کار رو کردم، و برای هر روز ۰/۷ ثانیه بیشتر طول نمی‌کشید.

چند نکته:

1. کد تولید عدد رندوم پایتون رو می‌تونید در فایل‌های زیر بیابید:
   • _randommodule.c
   • random.py
2. پیاده‌سازی randint بین نسخه‌ی پایتون ۳.۱ و ۳.۲ فرق کرده. یعنی اگه کد اصلی رو روی پایتون قبل یا مساوی ۳.۱ اجرا کنید یک جواب می‌گیرید، و روی پایتون ۳.۲ و بعد یک جواب دیگر.

روز ۲. کاشی‌کاری فیبوناچی

لینک توویت: https://twitter.com/pykello_fa/status/1506162255359987712

فرض کنید یک صفحه‌ی شطرنجی 2xn دارید. می‌خواهیم این صفحه را با کاشی‌هایی با اندازه‌ی 1x2 یا 2x1 پر کنیم. در زبان دلخواه خود برنامه‌ای بنویسید که با گرفتن n تصویر همه‌ی کاشی‌کاری‌های ممکن را تولید کند.

مثلا برای ۴:

تصویر را به طریق دلخواه تولید کنید (صفحه‌ی وب، کشیدن روی gui، فایل، یا اگر repl زبانتان مقادیر تصویری پشتیبانی می‌کند مقادیر تصویری، …)

از نتیجه اسکرین‌شات بگیرید یا در جایی به اشتراک بگذارید و کامنت کنید 🌼

پاسخ و بحث

لینک توویت پاسخ: https://twitter.com/pykello_fa/status/1506485589721305090

کد من با استفاده از زبان Pyret:

include image
include color

fun tilings(n) -> List<Image>:
  single_vertical = rectangle(20, 40, "outline", "black")
  double_horizontal =
    above(
      rectangle(40, 20, "outline", "black"),
      rectangle(40, 20, "outline", "black"))

  if n == 0:
    [list: empty-image]
  else if n == 1:
    [list: single_vertical]
  else:
    for map(subtiling from tilings(n - 1)):
        beside(single_vertical, subtiling)
    end
    +
    for map(subtiling from tilings(n - 2)):
        beside(double_horizontal, subtiling)
    end
  end
end

سوال نمره‌اضافی

برای تمرین بیشتر و حل مساله‌ای کمی سخت‌تر، برنامه‌ای بنویسید که لیست همه‌ی کاشی‌کاری‌های ممکن صفحه‌ی شطرنجی 2xn رو با دقیقا دو تا 1x1 و تعداد دلخواهی 1x2 و 2x1 پیدا کنه.

روز ۳. نمودار اشتراک ۴ مجموعه

لینک توویت: https://twitter.com/pykello_fa/status/1506518858374389760

می‌دونیم ۸ حالت اشتراک ۳ مجموعه رو می‌شه با استفاده از ۳ دایره به شکل زیر نشون داد.

آیا می‌شه ۱۶ حالت اشتراک ۴ مجموعه رو با استفاده از ۴ دایره نشون داد؟ اگه آره، شکلش رو بکشین. اگه نه، ۱. چرا؟ ۲. آیا با ۴ بیضی می‌شه؟

پاسخ و بحث

لینک توویت پاسخ: https://twitter.com/pykello_fa/status/1506843010012643332

این سوال رو از تمرینات فصل اول کتاب «Concrete Mathematics» برداشته بودم. راه‌حل‌های خیلی خوبی ارائه شد.

توضیح اینکه چرا با دایره نمی‌شود، توسط جالینوکس:

نمونه جواب با بیضی توسط علی بیگی:

نمونه جواب با بیضی توسط Mohsen the Scripter:

نمونه جواب با بیضی توسط NAJMEH:

روز ۴. مقدار بازگشتی تابع fork

لینک توویت: https://twitter.com/pykello_fa/status/1506878360684703744

در لینوکس تابع fork یک پروسس فرزند ایجاد می‌کند که کپی پروسس اصلی است و از همان نقطه به بعد به اجرا ادامه می‌دهد. با این تفاوت که در پروسس اصلی مقدار شناسه‌ی فرزند برگردانده می‌شود و در پروسس فرزند مقدار 0.

با نگاه به کد لینوکس 1.0، پیدا کنید که fork چگونه دو مقدار متفاوت در پروسس اصلی و فرزند برمی‌گرداند؟

کد سیستم‌کال fork در لینوکس 1.0: https://github.com/kalamangga-net/linux–1.0/blob/master/kernel/fork.c

طریقه‌ی فراخوانی و برگرداندن مقدار بازگشتی سیستم‌کال‌ها: https://en.wikibooks.org/wiki/X86_Assembly/Interfacing_with_Linux

پاسخ و بحث

لینک توویت پاسخ: https://twitter.com/pykello_fa/status/1507255396414590982

پاسخ خلاصه اینه که لینوکس پاسخ سیستم‌کال‌ها رو در معماری x86 میذاره در رجیستر eax، پس همونطور که چند نفر از دوستان ( @shahriarshm ، @kafkakh ، @SoroushRabiei ) اشاره کردند، مقدار صفر توسط سطر هایلایت شده به فرزند برگردونده میشه.

@mr_pouriya هم مسیر همین اتفاق رو در FreeBSD پیدا کرد