| پروژهٔ اولیهٔ این سوال را می‌توانید از [این لینک](/contest/assignments/103145/download_problem_initial_project/356752/) دانلود کنید. | | :-: | در **مرحلهٔ گروهی جام جهانی فناوری پردیس ۲۰۲۶**، نتیجهٔ هر بازی بلافاصله بعد از سوت پایان ثبت می‌شود. **دوین** برگزاری می‌خواهد مطمئن شود که تغییر دادن یک نتیجهٔ ثبت‌شده **قابل تشخیص** و **دوین‌آزمایی** باشد! برای همین نتایج در قالب یک **زنجیرهٔ هش** *(hash chain)* ذخیره می‌شوند: هر رکورد علاوه بر دادهٔ خودش، هش رکورد قبلی را هم نگه می‌دارد. اگر رکوردی عوض شود ولی هش‌های بعدی به‌روز نشوند، ناسازگاری از همان نقطه پیدا خواهد بود و لو می‌رود! شما باید *Bash* اسکریپتی بنویسید که این فایل را بررسی کند و رکوردهای دارای هش **نادرست** و **پیوندهای نامعتبر** را گزارش دهد.  # **پروژهٔ اولیه** برای دانلود **پروژهٔ اولیه** روی [این لینک](/contest/assignments/103145/download_problem_initial_project/356752/) کلیک کنید. این پروژه شامل یک فایل `solution.sh` با چند خط کامنت راهنما و بدنهٔ خالی است. <details class="grey"> <summary>**نکته: محتوای پروژهٔ اولیه**</summary> ``` . └── <mark class="green" title="این فایل را تکمیل کنید.">solution.sh</mark> ``` </details> # **جزئیات** هر تست در سیستم داوری با یک `ledger.txt` جدید در پوشهٔ پروژه شروع می‌شود و بعد اسکریپت با دستور `bash solution.sh` اجرا می‌شود. پس **لازم نیست** فایل را اجرایی کنید. چیزی روی *stdin* ظاهر نمی‌شود؛ خود اسکریپت باید فایل را از مسیر فعلی باز کند. محیط داوری این سوال یک اینستنس *Linux* است و دستور `sha256sum` در محیط داوری نصب می‌باشد. |  | | :-: | | از فایل ورودی تا پنج مقدار خروجی. | ## **قالب فایل `ledger.txt`** هر خط فایل یک رکورد است و از چهار قسمت تشکیل شده که با فاصله از هم جدا می‌شوند: ```text ledger.txt terminal INDEX PREV_HASH PAYLOAD HASH ``` | قسمت | معنی | | --: | --: | | `INDEX` | شمارهٔ رکورد، از `1` شروع شده و افزایش‌ می‌یابد | | `PREV_HASH` | هش رکورد قبلی | | `PAYLOAD` | دادهٔ رکورد، مثلاً `IRAN-PORTUGAL:2-1` | | `HASH` | هش ذخیره‌شدهٔ همین رکورد | - مقدارهای `PREV_HASH` و `HASH` رشته‌های ۶۴ کاراکتری *hex* با **حروف اکیدا کوچک‌اند.** - مقدار `PAYLOAD` **نه فاصله دارد** و **نه کاراکتر** `|`، چون `|` جداکنندهٔ ورودی هش است. - تضمین می‌شود `INDEX`ها معتبر و به‌ترتیب‌اند، پس **لازم نیست درستی‌شان را بررسی کنید**. ولی توجه کنید که `INDEX` در محاسبات فرمول هش استفاده می‌شود. - خط‌های خالی رکورد **نیستند** و در `ENTRIES` **هم شمرده نمی‌شوند.** ## **فرمول هشِ هر رکورد:** هشِ هر رکورد به این شکل ساخته می‌شود: سه مقدار `INDEX` و `PREV_HASH` و `PAYLOAD` را با کاراکتر `|` به هم می‌چسبانید و *SHA-256* آن رشته را می‌گیرید. ```text hashing terminal HASH = sha256( "INDEX|PREV_HASH|PAYLOAD" ) ``` > نکتهٔ مهم این است که این رشته **هیچ خط جدیدی در انتها ندارد**. اگر آن را با `echo` بسازید، یک `\n` به انتهایش اضافه می‌شود و هشِ خروجی کاملاً عوض می‌شود، پس حتماً از `printf '%s'` استفاده کنید. - برای رکورد اول، مقدار مورد انتظار `PREV_HASH` **یک ثابت به نام** `GENESIS` است: رشته‌ای شامل دقیقاً ۶۴ کاراکتر `0`. - برای هر رکورد بعدی، `PREV_HASH` باید برابر `HASH` رکورد خط قبل باشد. یک فایل سالم سه‌رکوردی به این شکل است: ```text ledger.txt terminal 1 0000000000000000000000000000000000000000000000000000000000000000 IRAN-PORTUGAL:2-1 b3cab6bb27a591f57af530a2b95e1739cc2b1a5d8a011114b57dbbb110b13714 2 b3cab6bb27a591f57af530a2b95e1739cc2b1a5d8a011114b57dbbb110b13714 SPAIN-BRAZIL:0-3 c1c32daf6f99c6bdbfb769727dc6bd464aaf7f9388dca9c0b4998adc5e597834 3 c1c32daf6f99c6bdbfb769727dc6bd464aaf7f9388dca9c0b4998adc5e597834 DENA-ALBORZ:1-1 88154d4c9b568635f95fe2d87c74c4c5cbb4deadfbc06e52796747dcd626ff9c ``` > با این نمونه می‌توانید فرمول هش خود را قبل از ارسال بررسی کنید. هش رکورد اول از رشتهٔ `1|0000...0000|IRAN-PORTUGAL:2-1` ساخته شده و مقدارش `b3cab6bb...` است. اگر همین رشته را با `echo` بسازید یعنی یک `\n` هم به انتهایش اضافه شود، نتیجه `fc21bead...` می‌شود که کاملاً غلط است. دقت کنید که `PREV_HASH` رکورد دوم دقیقاً همان `HASH` رکورد اول است. |  | | :-: | | هر رکورد هشِ خود را از `INDEX` و `PREV_HASH` و `PAYLOAD` می‌سازد و رکورد بعدی همین هش را در `PREV_HASH` خود تکرار می‌کند. | ## **دو بررسی مستقل روی هر رکورد** اسکریپت شما باید روی هر رکورد دو بررسی جدا انجام دهد و نتیجه را تفکیک‌شده گزارش کند: - **درستی هش:** هشِ رکورد را از روی سه مقدار ذخیره‌شدهٔ همان خط دوباره حساب کنید و با مقدار `HASH` ذخیره‌شده مقایسه کنید. اگر این دو یکسان نبودند، شمارهٔ آن رکورد در فهرست `BAD_HASH` می‌آید. - **درست بودن پیوند به رکورد قبلی:** برای رکورد اول، `PREV_HASH` باید برابر `GENESIS` باشد. برای بقیه باید برابر **`HASH` ذخیره‌شدهٔ** رکورد خط قبل باشد. اگر برابر نبود، شمارهٔ آن رکورد در فهرست `BAD_LINK` می‌آید. + **توجه:** مقایسه با `HASH` **ذخیره‌شدهٔ** رکورد قبلی انجام می‌شود، نه با هشِ بازمحاسبه‌شدهٔ آن. یعنی اگر رکورد قبلی خودش خراب باشد ولی مقدار `HASH` نوشته‌شده‌اش دست‌نخورده مانده باشد، پیوند رکورد فعلی همچنان معتبر است. یک رکورد می‌تواند هم‌زمان در هر دو فهرست بیاید. این حالت ممکن است رخ دهد و باید دقیقاً به همین شکل گزارش شود. |  | | :-: | | دستکاری در متن رکورد بررسیِ هش را می‌شکند؛ اصلاحِ هش بدون به‌روزرسانی رکورد بعدی، سلامتِ حلقه را می‌شکند. | ## **خروجی اسکریپت** اسکریپت باید پنج مقدار زیر را، هرکدام در قالب `KEY=VALUE` و هرکدام در یک خط، چاپ کند: ```text output terminal STATUS=VALID ENTRIES=5 BAD_HASH=NONE BAD_LINK=NONE FIRST_BREAK=NONE ``` > **بلوک بالا یک نمونهٔ کامل از خروجی برای یک فایل سالم است.** سیستم داوری خروجی را **بر پایهٔ کلید** می‌خواند، پس ترتیب خط‌ها اهمیتی ندارد، ولی نام کلیدها و قالب مقدارها باید دقیق باشد. هر پنج کلید همیشه باید چاپ شوند، حتی وقتی مقدارشان `NONE` است. معنی هر کلید به این شرح است: | **کلید** | **مقدار** | | --: | --: | | `STATUS` | اگر هیچ رکوردی نه در `BAD_HASH` و نه در `BAD_LINK` نبود `VALID`، **در غیر این صورت** `BROKEN` | | `ENTRIES` | تعداد کل رکوردهای فایل | | `BAD_HASH` | شماره‌های رکوردهایی که هششان نمی‌خواند، مرتب صعودی و جداشده با یک فاصله، یا `NONE` | | `BAD_LINK` | شماره‌های رکوردهایی که پیوندشان به رکورد قبلی درست نیست، مرتب صعودی و جداشده با یک فاصله، یا `NONE` | | `FIRST_BREAK` | کوچک‌ترین شماره‌ای که در `BAD_HASH` یا `BAD_LINK` آمده، یا `NONE`. این مقدار فقط کمترین شمارهٔ مشکل‌دار است و علت خرابی را مشخص نمی‌کند | + **«شمارهٔ رکورد» یعنی چه؟** هر جا در `BAD_HASH` و `BAD_LINK` و `FIRST_BREAK` از شمارهٔ رکورد حرف می‌زنیم، منظور **مقدار فیلد `INDEX` همان خط** است، نه شمارهٔ ترتیبی خط در فایل. چون خط خالی ممکن است وسط فایل بیاید، **این دو الزاماً یکی نیستند!** ## **سه حالت مرزی که باید در نظر بگیرید:** - خط‌های کاملاً خالی وسط یا انتهای فایل باید **نادیده** گرفته شوند. - ممکن است فایل بدون خط جدید در انتها تمام شود و آخرین رکورد باید همچنان خوانده شود. - ممکن است **در ابتدای خط، انتهای خط و بین قسمت‌ها** فاصله‌های اضافه باشد. اسکریپت باید همه را تحمل کند. اگر با `cut -d' '` جدا کنید می‌شکند؛ `read -r` یا `awk` بدون `-F` این حالت را خودشان مدیریت می‌کنند. |  | | :-: | | برای هر رکورد، هش بازمحاسبه و حلقه بررسی می‌شود؛ در پایان پنج مقدار خروجی از دو فهرست ساخته می‌شوند. | # **نمونه** فرض کنید فایلی با پنج رکورد داریم. چهار حالت زیر تفاوت این دو بررسی را روشن می‌کند. خروجی فایل سالم همان است که در بخش چهارم دیدید: هر دو فهرست `NONE`، `STATUS=VALID` و `FIRST_BREAK=NONE`. حالا چند نوع دستکاری روی همان فایل: **حالت اول، فقط `PAYLOAD` رکورد ۳ عوض شده و هشش به‌روز نشده:** ```text output terminal STATUS=BROKEN ENTRIES=5 BAD_HASH=3 BAD_LINK=NONE FIRST_BREAK=3 ``` > بازمحاسبهٔ هش رکورد ۳ عدد دیگری می‌دهد، پس `3` در `BAD_HASH` می‌آید. اما مقدار `HASH` نوشته‌شدهٔ رکورد ۳ دست‌نخورده مانده و رکورد ۴ هنوز به همان عدد قدیمی اشاره می‌کند، پس پیوندش معتبر است و `BAD_LINK` خالی می‌ماند. **حالت دوم، `PAYLOAD` رکورد ۳ عوض شده و هشِ خودش هم درست بازمحاسبه شده:** ```text output terminal STATUS=BROKEN ENTRIES=5 BAD_HASH=NONE BAD_LINK=4 FIRST_BREAK=4 ``` > این‌بار رکورد ۳ با هش خودش سازگار است، پس اصلاً در `BAD_HASH` نمی‌آید. ولی چون `HASH` رکورد ۳ عوض شده و `PREV_HASH` رکورد ۴ هنوز عدد قدیمی را دارد، پیوند رکورد ۴ می‌شکند. دقت کنید که رکورد گزارش‌شده `4` است، در حالی که رکوردی که واقعاً دستکاری شده `3` بوده. **حالت سوم، فقط `PREV_HASH` رکورد ۴ عوض شده:** ```text output terminal STATUS=BROKEN ENTRIES=5 BAD_HASH=4 BAD_LINK=4 FIRST_BREAK=4 ``` > اینجا رکورد `4` در **هر دو** فهرست می‌آید. دلیلش این است که `PREV_HASH` هم بخشی از ورودی فرمول هش است، پس عوض شدنش هم پیوند به رکورد قبل را می‌شکند و هم باعث می‌شود هش بازمحاسبه‌شدهٔ خود رکورد ۴ با `HASH` ذخیره‌شده‌اش نخواند. همین حالت است که در بخش سوم گفته شد یک رکورد می‌تواند در هر دو فهرست بیاید. **حالت چهارم، دو دستکاری جدا در یک فایل:** سه حالت قبلی هرکدام یک عیب داشتند. در عمل ممکن است چند جای فایل هم‌زمان خراب باشد و آن وقت هر سه فهرست با هم پر می‌شوند. فرض کنید در همان فایل پنج‌رکوردی، `PAYLOAD` رکورد ۲ عوض شده بدون به‌روز شدن هشش و جدا از آن `PREV_HASH` رکورد ۵ هم دستکاری شده: ```text output terminal STATUS=BROKEN ENTRIES=5 BAD_HASH=2 5 BAD_LINK=5 FIRST_BREAK=2 ``` > در این مثال سه نکته مهم است. اول اینکه `BAD_HASH` دو شماره دارد و باید **صعودی و با یک فاصله** جدا شوند. دوم اینکه رکورد `5` هم‌زمان در هر دو فهرست آمده، چون دستکاری `PREV_HASH` هم اتصالش را می‌شکند و هم هش خودش را. سوم اینکه `FIRST_BREAK` برابر `2` است، یعنی کوچک‌ترین شماره از **اجتماع** دو فهرست، نه کوچک‌ترین شمارهٔ `BAD_LINK`. نکتهٔ ظریف اینجاست که رکورد ۳ سالم می‌ماند: `HASH` رکورد ۲ دست‌نخورده مانده، پس پیوند رکورد ۳ به آن همچنان درست است. |  | | :-: | | نمونه‌ای از یک فایل که متن رکورد سومش عوض شده و هشش به‌روز نشده است. | # **ساب‌تسک‌های سوال** امتیاز این سؤال در قالب **ده ساب‌تسک** مستقل پخش شده و هر کدام به صورت جدا محسابه می‌شود: | **ساب‌تسک** | **درصد** | | --: | :-: | | تشخیص درست یک زنجیرهٔ سالم | ۱۰ | | گزارش تعداد ردیف‌ها | ۸ | | پیدا کردن دستکاری متن با هش خودِ ردیف | ۱۴ | | بررسی درست پیوند ردیف اول به هش صفر | ۸ | | پیدا کردن گسست پیوند بین دو ردیف | ۱۴ | | گزارش شمارهٔ اولین ردیف خراب | ۱۰ | | فهرست مرتب همهٔ ردیف‌های خراب | ۱۲ | | اعلام وضعیت خراب وقتی هر دستکاری‌ای هست | ۸ | | تاب آوردن در برابر فاصلهٔ اضافه و نبودن خط پایانی | ۸ | | مقایسهٔ کامل با مرجع روی یک فایل بزرگ | ۸ | > ترتیب این جدول **تصادفی نیست** و تقریباً همان ترتیبی است که **پیشنهاد** می‌شود در حل سوال پیش بروید. اگر فقط تشخیص زنجیرهٔ سالم و شمارش ردیف‌ها را درست کنید، تا حدود ۲۰ درصد از امتیاز را خواهد گرفت بدون اینکه سراغ پیدا کردن دستکاری بروید. # **آنچه باید آپلود کنید** فایل `solution.sh` را کامل کنید و **همین یک فایل** را بفرستید. + **توجه:** سیستم داوری کوئرا فقط `solution.sh` را برمی‌دارد و بقیهٔ فایل‌های ارسالی را دور می‌ریزد. + **توجه:** برای ساخت ورودی هش حتماً از `printf '%s'` استفاده کنید تا خط جدید اضافه‌ای وارد آن نشود. + **توجه:** سیستم داوری خروجی را بر پایهٔ کلیدها می‌خواند، ولی نام کلیدها، واژهٔ `NONE` و **مرتب بودن صعودی فهرست‌ها باید دقیق باشد.** + **توجه:** اسکریپت باید نسبت به خط‌های خالی، نبودِ خط جدید پایانی و فاصله‌های اضافه بین قسمت‌ها **مقاوم** باشد.