الگوریتم خوشهبندی که از بازی با مگنا-تایل دراومد
جاوااسکریپتClaude Opus 5خلاصهٔ کاملتر
کسیدو ویلیامز تو پست جدیدش تعریف میکنه که داشته با مگنا-تایلهای بچهش بازی میکرده و از الگوی مرتبکردنشون یه هیوریستیک ساده برای خوشهبندی لیستها درآورده. فرض کن یه لیست داری که هر عنصرش میتونه b، g، o یا r باشه، مثل bgogbrbroorrgbgorrbggo؛ هدف اینه که آخرش همهٔ همنوعها کنار هم جمع شن.
قاعدهش یه خط بیشتر نیست: مقدار انتهای لیست رو نگاه کن، نزدیکترین تکرار همون مقدار از سمت راست رو پیدا کن و هر چی بین اون دوتاست رو برعکس کن. همین کارو تکرار میکنی؛ هر بار یه گروه کاملتر میشه و وقتی گروه انتهایی تموم شد، میری سراغ اولین گروه ناقص از سمت راست.
نویسنده میگه این تابع رو عمداً بدون کمک AI و بهعنوان یه تمرین ذهنی نوشته و تا تمیز بشه چند بار آزمونوخطا کرده. هستهٔ کار همون برعکسکردن یه بازه از لیسته:
function reverse(arr, left, right) {
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}نسخهٔ نهایی بهجای بازگشتی، دوتا حلقهٔ while تودرتو داره و برای همین پیچیدگی زمانیش O(n²) درمیاد. خودش هم قبول داره که این روش بهینه نیست و حریصانهست، چون فقط به بهترین حرکت همین لحظه نگاه میکنه. نزدیکترین ایدهٔ شناختهشدهای که براش پیدا کرده مرتبسازی پنکیکی (pancake sort) هست، با این تفاوت که اونجا بحث مرتبسازی روی پشتهست، نه گروهکردن روی لیست.
نکتهٔ جالب پست از نگاه نویسنده اینه که این مسئله برای یه آدم با قطعههای واقعی جلوش خیلی راحتتره تا برای کامپیوتر: چشم ما وضعیت کل صفحه رو انگار با هزینهٔ O(1) میخونه و یه گروه رو با یه حرکت برمیگردونه، ولی کامپیوتر باید همین کارو با کلی مقایسه و جابهجایی انجام بده.
نکات کلیدی:
- گروهکردن مقادیر یه لیست فقط با برعکسکردن پیاپی زیرلیستها
- الگوریتمی حریصانه با پیچیدگی زمانی O(n²) و پیادهسازی با حلقههای while تودرتو
- نزدیکترین ایدهٔ شناختهشده: مرتبسازی پنکیکی
- خوندن آنی وضعیت توسط انسان چیزیه که کامپیوتر ارزون بهدستش نمیاره
