آمین میزور ‏| تمرین برنامه‌نویسی ‏| Quera

یک مسابقه‌ی انتخابی سخت و پرچالش بعد...

آمین چیپس‌خور (Aaaamin Chipskhor)، از دیگر آمین‌های تاثیرگذار کوئرا که این روزها پس از بازگشت زودهنگام از خدمت مقدس سربازی، هنوز وظایف قبلی خود را در کوئرا دوباره تحویل نگرفته‌است، میزور (Mizzor) این سری از #المپیک‌فناوری پردیس شده‌است. از آن‌جایی که تعداد تیم‌های شرکت‌کننده امسال چندین برابر سال گذشته شده، او باید برای همه‌ی آن‌ها میز مشخصی تعیین کند تا نظم مسابقه حفظ شود. با این حال، آمین علاقه‌ای به استفاده از روش‌های ساده و تصادفی ندارد و تصمیم می‌گیرد از یک روش محاسباتی خاص و منحصربه‌فرد برای محاسبه‌ی شماره میز تیم‌ها استفاده کند. این روش عجیب که در کوئرا شهره‌ی خاص و عام است، سیستم میزور (Mizzor System) نام‌ دارد.

در این سیستم، هر کدام از تیم‌های شرکت‌کننده در سری جدید #المپیک‌فناوری پردیس، از تعدادی عضو تشکیل شده و نام هر عضو در محاسبه‌ی شماره‌ی میز تأثیر دارد. آمین میزور برای این کار ابتدا برای هر عضو گروه یک مقدار هش‌شده محاسبه می‌کند که از ترکیب کد عددی کاراکترها و دنباله‌ی فیبوناچی (Fibonacci sequence)، که در مدت زمان سربازی مطالعات زیادی بر روی این سری اعداد داشته، به دست می‌آید. سپس با جمع کردن این مقادیر و درنظر گرفتن تعداد اعضا، یک عدد نهایی برای هر تیم محاسبه می‌کند. در نهایت، شماره‌ی میز تیم برابر با باقی‌مانده‌ی این عدد بر تعداد میزهای موجود در سالن خواهد بود.

تصویر سوال آمین میزور

پروژه‌ی اولیه

برای دانلود پروژه‌ی اولیه روی این لینک کلیک کنید.

جزئیات پروژه

تابعی که شما باید در این سوال پیاده‌سازی کنید، تابع assign_tables می‌باشد و دو آرگومان ورودی می‌گیرد؛ یکی groups که دیکشنری‌ای از نام تیم‌ها و اعضایشان است و دیگری tables_num تعداد کل میزهای موجود. همچنین این تابع در خروجی به ترتیب دو مقدار بر خواهد گرداند: دیکشنری‌ای شامل شماره‌ی میز اختصاص‌یافته به هر تیم و لیستی از برخوردهایی (Collisions) که در طی تخصیص میز رخ داده‌اند. اگر برخوردی پیش بیاید، باید در خروجی مشخص شود کدام تیم جدید با کدام تیم قبلی روی یک میز افتاده‌است.

برای مثال، فرض کنید دیکشنری تیم‌ها شامل سه گروه باشد که بعضی از آن‌ها هش یکسان دارند. پس از اجرای تابع، خروجی شامل شماره‌ی میز هر تیم خواهد بود. اگر دو تیم مقدار هش (Hash) یکسانی داشته باشند در یک میز مشترک قرار می‌گیرند. سیستم در این حالت آن را به‌عنوان یک برخورد ثبت می‌کند و در خروجی نمایش می‌دهد تا آمین بتواند موقتاً با مشغول کردن اعضای این تیم‌ها با بسته‌های طعم‌های مختلف چیپس، تصمیم بگیرد کدام‌یک باید به میز دیگری منتقل شود!

تابع هش برای نام اعضای تیم‌ها:

$$H(\text{name}) = \sum_{i=1}^{L} \big( \text{ord}(c_i) \times F(i) \big)$$

که در آن $ord(c_i)$ کد عددی یونیکد (Unicode code point) کاراکتر $i$-ام نام عضو تیم، مقدار $L$ طول نام آن عضو مشخص و $F(i)$ عنصر $i$-ام سری فیبوناچی $F$ است که به شکل زیر تعریف می‌شود:

$$F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2) \quad \forall n \ge 2$$

حال برای محاسبه شماره میز برای هر تیم به شکل زیر اقدام می‌کنیم که در آن مقدار $k$ برابر با تعداد اعضای تیم است و در این رابطه مجموع مقدار هش شده‌ی اسامی اعضای تیم را با هم جمع کرده، در تعداد اعضای تیم ضرب و در نهایت باقی‌مانده آن را بر $N$ (تعداد میز‌های مسابقه) محاسبه می‌کنیم:

$$T(G) = \Bigg( \big( \sum_{j=1}^{k} H(M_j) \big) \times k \Bigg) \bmod N$$

همچنین تعریف برخورد به شکل زیر خواهد بود: $$T(G_1) = T(G_2) \implies \text{Collision} = (, G_2,, T(G_2),, G_1 ,)$$

ورودی

توجه داشته باشید که این مسئله ورودی استاندارد ندارد. به‌جای آن، تابع زیر را در فایل solution.py پیاده‌سازی کنید. این تابع ورودی‌ها را به‌صورت آرگومان توسط سیستم داوری، دریافت خواهد کرد.

def assign_tables(groups: dict[str, list[str]], tables_num: int) -> tuple[dict[str, int], list[tuple[str, int, str]]]:
    return {}, []

پارامتر groups: یک دیکشنری است که در آن کلیدها به صورت نام تیم‌های شرکت‌کننده و مقدار هر کلید**، فهرستی از اسامی اعضای آن تیم** است. هر عضو با رشته‌ای نمایش داده می‌شود و ترتیب اعضا در فهرست اهمیتی ندارد. تابع باید بر اساس ترکیب نام اعضا برای هر تیم، شماره‌ی میز اختصاصی را محاسبه کند.
پارامتر tables_num: یک عدد صحیح است که نشان‌دهنده‌ی تعداد کل میزهای موجود در سالن برگزاری مسابقه است. تمامی شماره‌های میز باید در بازه‌ی [0, tables_num - 1] قرار داشته باشند. شماره‌ی میز هر تیم با استفاده از عملیات باقی‌مانده نسبت به این عدد محاسبه می‌شود.

نکته: اگر در فرایند تخصیص میز، دو تیم به یک شماره‌ی میز مشابه برسند، به این وضعیت برخورد میز (Table Collision) گفته می‌شود. در این صورت، تابع باید آن برخورد را در خروجی گزارش دهد تا مشخص شود کدام تیم‌ها روی یک میز افتاده‌اند. برخوردها باید در قالب فهرستی از سه‌تایی‌ها شامل (نام تیم جدید، شماره‌ی میز، نام تیم قبلی) بازگردانده شوند.

خروجی

تابع به ترتیب باید یک تاپل (Tuple) با دو مقدار برگرداند. مقدار اول، یک دیکشنری است که کلیدهای آن نام تیم‌ها و مقادیرشان شماره‌ی میز اختصاص‌یافته است و مقدار دوم، فهرستی از برخوردهای احتمالی است که در فرایند تخصیص میز شناسایی شده‌اند.

مثال

ورودی نمونه‌ ۱

groups = {
    "Team1": ["Ali", "Sara"],
    "Team2": ["Reza", "Nina"],
    "Team3": ["Ali", "Sara"]
}

assign_tables(groups, 4)

خروجی نمونه ۱

({'Team1': 0, 'Team2': 0, 'Team3': 0}, [('Team2', 0, 'Team1'), ('Team3', 0, 'Team2')])

توضیحات نحوه محاسبه مقادیر برای ورودی ۱

محاسبات را مرحله به مرحله برای داده‌ها به شکل زیر انجام می‌دهیم:

groups = {
    "Team1": ["Ali", "Sara"],
    "Team2": ["Reza", "Nina"],
    "Team3": ["Ali", "Sara"]
}

ابتدا برای نام Ali سه حرف (A, l, i) داریم. مقدار ord برای آن‌ها به ترتیب 65، 108 و 105 است. با توجه به دنبالهٔ فیبوناچی $(F(i$ داریم:

$$65 \times F(1) = 65 \times 1 = 65$$ $$108 \times F(2) = 108 \times 1 = 108$$ $$105 \times F(3) = 105 \times 2 = 210$$

جمع این سه مقدار برابر است با:

$$65 + 108 + 210 = 383$$

بنابراین:

$$H("Ali") = 383$$

برای نام Sara چهار حرف (S, a, r, a) داریم. مقدار ord برای آن‌ها به ترتیب 83، 97، 114 و 97 است. محاسبات به شکل زیر است:

$$83 \times F(1) = 83 \times 1 = 83$$ $$97 \times F(2) = 97 \times 1 = 97$$ $$114 \times F(3) = 114 \times 2 = 228$$ $$97 \times F(4) = 97 \times 3 = 291$$

جمع چهار حاصل‌ضرب:

$$83 + 97 + 228 + 291 = 699$$

در نتیجه:

$$H("Sara") = 699$$

برای نام Reza چهار حرف (R, e, z, a) داریم که مقدار ord آن‌ها به ترتیب 82، 101، 122 و 97 است. بنابراین:

$$82 \times F(1) = 82 \times 1 = 82$$ $$101 \times F(2) = 101 \times 1 = 101$$ $$122 \times F(3) = 122 \times 2 = 244$$ $$97 \times F(4) = 97 \times 3 = 291$$

جمع این چهار مقدار برابر است با:

$$82 + 101 + 244 + 291 = 718$$

پس:

$$H("Reza") = 718$$

برای نام Nina چهار حرف (N, i, n, a) داریم که مقادیر ord آن‌ها به ترتیب 78، 105، 110 و 97 است. محاسبات به شکل زیر است:

$$78 \times F(1) = 78 \times 1 = 78$$ $$105 \times F(2) = 105 \times 1 = 105$$ $$110 \times F(3) = 110 \times 2 = 220$$ $$97 \times F(4) = 97 \times 3 = 29$$

و جمع آن‌ها برابر است با:

$$78 + 105 + 220 + 291 = 694$$

بنابراین:

$$H("Nina") = 694$$

اکنون مقدار شماره میز هر تیم را با استفاده از $(T(G$ محاسبه می‌کنیم. طبق فرمول:

$$T(G) = \Big( \big(\sum_{j=1}^{k} H(M_j) \big) \times k \Big) \bmod N$$

برای Team1 با اعضای Ali و Sara داریم:

$$T(Team1) = ((383 + 699) \times 2) \bmod N = (1082 \times 2) \bmod N = 2164 \bmod 4 = 0$$

برای Team2 با اعضای Reza و Nina داریم:

$$T(Team2) = ((718 + 694) \times 2) \bmod N = (1412 \times 2) \bmod N = 2824 \bmod 4 = 0$$

برای Team3 که اعضایش همانند Team1 هستند:

$$T(Team3) = ((383 + 699) \times 2) \bmod N = 2164 \bmod 4 = 0$$

در نتیجه مقدار نهایی شماره میز هر گروه (پیش از محاسبهٔ باقی‌مانده بر $N$) برابر است با:

$$T(Team1) = 0, \quad T(Team2) = 0, \quad T(Team3) = 0$$

چون (T(Team1) = T(Team3))، این دو تیم به یک میز اختصاص داده می‌شوند و در نتیجه یک برخورد رخ می‌دهد:

$$Collision = ('Team2', 1, 'Team1')$$ $$Collision = ('Team3', 1, 'Team2')$$

در این ورودی خاص، هر سه تیم در نهایت عدد صفر را به‌عنوان شماره‌ی میز خود به دست می‌آورند. دلیل این موضوع این است که مجموع هش‌های تولیدشده برای اعضا، پس از ضرب در اندازه‌ی تیم و گرفتن باقی‌مانده بر ۴، برابر با صفر شده است. به همین خاطر، تمام تیم‌ها روی یک میز (میز شماره ۰) قرار گرفته‌اند و تابع در خروجی، علاوه‌بر دیکشنری شماره میزها، لیستی از برخوردها را نیز برمی‌گرداند. در این لیست مشخص است که تیم دوم با تیم اول برخورد کرده (('Team2', 0, 'Team1')) و تیم سوم هم با تیم دوم (('Team3', 0, 'Team2')) به یک میز اختصاص داده شده‌اند، که نشان‌دهنده‌ی تداخل در تخصیص میزها است.

ورودی نمونه ۲

groups = {
    "QuantumCoders": ["Amir", "Reza", "Sara"],
    "AIWarriors": ["Nina", "Ali", "Mina"],
    "DataTitans": ["Omid", "Reza", "Sina", "Tara"],
    "BugHunters": ["Amir", "Reza"],
    "CyberFalcons": ["Nina", "Ali"],
    "PixelLords": ["Mina", "Sina", "Tara"]
}

assign_tables(groups, 6)

خروجی نمونه ۲

({'QuantumCoders': 3, 'AIWarriors': 0, 'DataTitans': 4, 'BugHunters': 2, 'CyberFalcons': 0, 'PixelLords': 0}, [('CyberFalcons', 0, 'AIWarriors'), ('PixelLords', 0, 'CyberFalcons')])

توضیحات نحوه محاسبه مقادیر برای ورودی ۲

محاسبات را مرحله به مرحله برای داده‌ها به شکل زیر انجام می‌دهیم:

groups = {
    "QuantumCoders": ["Amir", "Reza", "Sara"],
    "AIWarriors": ["Nina", "Ali", "Mina"],
    "DataTitans": ["Omid", "Reza", "Sina", "Tara"],
    "BugHunters": ["Amir", "Reza"],
    "CyberFalcons": ["Nina", "Ali"],
    "PixelLords": ["Mina", "Sina", "Tara"]
}

ابتدا برای نام Amir چهار حرف (A, m, i, r) داریم. مقدار ord آن‌ها به ترتیب 65, 109, 105, 114 است. محاسبات با دنباله فیبوناچی:

$$65 \times F(1) = 65 \times 1 = 65$$ $$109 \times F(2) = 109 \times 1 = 109$$ $$105 \times F(3) = 105 \times 2 = 210$$ $$114 \times F(4) = 114 \times 3 = 342$$

جمع مقادیر:

$$65 + 109 + 210 + 342 = 726$$

بنابراین:

$$H("Amir") = 726$$

برای نام Reza همانند قبل:

$$H("Reza") = 718$$

برای نام Sara:

$$H("Sara") = 699$$

حال برای تیم QuantumCoders با اعضای Amir, Reza, Sara داریم ((k=3)):

$$T(QuantumCoders) = ((726 + 718 + 699) \times 3) \bmod 6 = (2143 \times 3) \bmod 6 = 6429 \bmod 6 = 3$$

برای تیم AIWarriors با اعضای Nina, Ali, Mina:

$$H("Nina") = 694$$ $$H("Ali") = 383$$ $$H("Mina") = 693$$

$$T(AIWarriors) = ((694 + 383 + 693) \times 3) \bmod 6 = (1770 \times 3) \bmod 6 = 5310 \bmod 6 = 0$$

برای تیم DataTitans با اعضای Omid, Reza, Sina, Tara:

$$H("Omid") = 698$$ $$H("Reza") = 718$$ $$H("Sina") = 699$$ $$H("Tara") = 700$$

$$T(DataTitans) = ((698 + 718 + 699 + 700) \times 4) \bmod 6 = (2815 \times 4) \bmod 6 = 11260 \bmod 6 = 4$$

برای تیم BugHunters با اعضای Amir, Reza:

$$T(BugHunters) = ((726 + 718) \times 2) \bmod 6 = (1444 \times 2) \bmod 6 = 2888 \bmod 6 = 2$$

برای تیم CyberFalcons با اعضای Nina, Ali:

$$T(CyberFalcons) = ((694 + 383) \times 2) \bmod 6 = (1077 \times 2) \bmod 6 = 2154 \bmod 6 = 0$$

برای تیم PixelLords با اعضای Mina, Sina, Tara:

$$T(PixelLords) = ((693 + 699 + 700) \times 3) \bmod 6 = (2092 \times 3) \bmod 6 = 6276 \bmod 6 = 0$$

در نتیجه مقدار نهایی شماره میز هر گروه برابر است با:

$$T(QuantumCoders) = 3, \quad T(AIWarriors) = 0, \quad T(DataTitans) = 4, \quad T(BugHunters) = 2, \quad T(CyberFalcons) = 0, \quad T(PixelLords) = 0$$

چون شماره میز بعضی تیم‌ها یکسان است، برخوردها (Collision) به شکل زیر رخ می‌دهد:

$$Collision = ('CyberFalcons', 0, 'AIWarriors')$$ $$Collision = ('PixelLords', 0, 'CyberFalcons')$$

برای مثال، تیم QuantumCoders متشکل از سه عضو است و هش نام‌های آن‌ها طوری محاسبه شده که مجموع نهایی پس از اعمال عملیات مشخص‌شده در تابع، منجر به تخصیص میز شماره ۳ می‌شود. در همین حال، تیم‌های AIWarriors، CyberFalcons و PixelLords همگی به میز شماره ۰ اختصاص داده شده‌اند، چون مقدار محاسبه‌شده‌ی نهایی آن‌ها در تقسیم بر ۶، باقی‌مانده‌ی صفر داده‌است. از آن‌جا که چند تیم به یک میز مشترک تخصیص یافته‌اند، تابع علاوه‌بر دیکشنری اصلی از شماره‌ی میزها، لیستی از برخوردها را نیز بازمی‌گرداند. در این لیست مشخص است که تیم CyberFalcons با AIWarriors بر سر میز شماره ۰ برخورد داشته و پس از آن تیم PixelLords نیز با CyberFalcons در همان میز تداخل پیدا کرده‌است.

زیرمسئله‌ها

سیستم داوری برای این سوال به زیرمسئله‌های زیر برای نمره‌دهی تقسیم‌بندی شده است که می‌توانید امتیاز مربوط به هر کدام را در جدول زیر مشاهده کنید. زیرمسئله‌های این جدول ابتدا بر اساس اولویت و پیشنیازی پیاده‌سازی و سپس بر اساس امتیاز آن‌ها مرتب‌سازی شده‌اند. لذا پیشنهاد می‌شود در پیاده‌سازی از زیرمسئله‌ی ابتدایی آغاز کنید.

زیرمسئله	امتیاز
پیاده‌سازی تابع `assign_tables`	`100`

آن‌چه باید آپلود کنید

توجه: پس از پیاده‌سازی تابع خواسته‌شده، فایل solution.py را برای سیستم داوری ارسال کنید.
توجه: شما مجاز به افزودن فایل جدیدی در این ساختار نیستید و تنها باید تغییرات را در فایل‌ solution.py اعمال کنید.
توجه: ایجاد هرگونه تغییرات اضافی در امضا (Signature) و خروجی تابع assign_tables که خارج از تعریف سؤال باشد، در سیستم داوری مورد پذیرش قرار نگرفته و نمره‌ای دریافت نخواهد کرد.
توجه: فایل solution.py نباید هیچ عملکرد اضافه‌ای برای گرفتن ورودی استاندارد (stdin) و دادن خروجی استاندارد (stdout) مانند print کردن پاسخ را شامل باشد، در غیر این صورت نمره‌ای دریافت نخواهد کرد. سیستم داوری خود مسئول فراخوانی تابع assign_tables، دادن آرگومان‌های ورودی به آن و بررسی خروجی است.

ارسال پاسخ برای این سؤال