الگونَوَرد ۵: از هک شدن یک اکانت جلوگیری کنید! (حل شد توسط Iman)

اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.

دسترسی و حل سوال از منبع اصلی

پرسش: یک کلمه عبور داده شده است. یک کلمه عبور خوب است اگر که یک هکر نتواند به راحتی آن را حدس بزند. اینجا ضابطه خاصی برای یک کلمه عبور خوب داریم :

۱- طول آن باید حداقل ۶ و حداکثر ۲۰ باشد.

۲- باید شامل حداقل یک حرف بزرگ، یک حرف کوچک، یک رقم باشد.

۳- شامل هیچ سه حرف متوالی یکسان نباشد.

برنامه ای بنویسید که یک کلمه عبور را دریافت کنند و حداقل تعداد تبدیلات (درج، حذف، و جایگزینی) حروف برای تبدیل آن به یک کلمه عبور خوب را برگرداند.

توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند.

از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.

زمان بندی: ارسال پاسخ ها تا پایان روز 27 آوریل

یادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.

توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.

حل مساله

الگونورد برتر: الگونورد برتر الگونورد 4، کاربر با ای دی Iman هست.

ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. تشریح حل مساله رو خودشون بصورت کامل نوشتن.

ایمان فراحی http://professionalProgrammer.ir یک برنامه نویسی فوق العاده است و ریاضی اش هم خیلی خوبه و می تونه هم مسایل رو فرمول کنه و هم پیاده سازی کنه!

به Iman تبریک می گم و بهش می گم: عالی هستی! ادامه بده!

و حالا شرح پاسخ:

حل مسئله را با چند مثال شروع می‌کنیم تا مطمئن شویم که مسئله را درستی درک کرده ایم.

هدف پیدا کردن کمینه تغییراتی که کاربر می‌تواند، اعمال کند تا برحسب محدودیت‌های بالا یک کلمه عبور، کلمه عبور مستحکمی بشود. به جدول تهیه شده  زیر توجه کنید:

همان گونه که در جدول فوق مشاهده کردید ما با سه دسته محدودیت عمده سروکار داریم:

1-نوع حروف معتبر 2- متوالی نبودن سه حرف تکراری. 3- طول رشته ورودی

• حروف معتبر ورودی شامل سه محدودیت می باشد:

1-یک محدودیت حرف بزرگ 2- یک محدودیت حرف کوچک 3- یک محدودیت عدد؛ که مجموع  آنها سه محدودیت را به وجود می آورد.

• متوالی نبودن سه حرف تکراری که هر سه حرف تکراری یک محدودیت را به وجود می آورد.
• طول رشته ورودی که می توان آن را به سه بازه تقسیم کرد:
• بازه 0 تا 5 که شامل 6-len(n) محدودیت اضافه هست.
• بازه 6 تا 20 که محدودیت اضافه‌ای ایجاد نمی‌کند.
• بازه 20 به بالا که هر حرف اضافه یک محدودیت و تصحیح این حرف بر روی سه حالت زیر تاثیر می گذارد:
• برای یک مورد زیر رشته تکراری پیوسته که طول آن ضریب ۳ است ( از 3n منظور زیررشته‌های با حروف تکراری پیوسته به صورت "aaa" است) حذف یک حرف اضافی موجب کاهش محدودیت یک مورد از این زیر رشته تکراری می‌شود.
• برای یک مورد زیر رشته تکراری پیوسته که طول آن ضریب ۳ بعلاوه ۱ است (3n+1 به عنوان مثال "aaaa") حذف دو حرف اضافی موجب کاهش محدودیت یک مورد از این زیررشته تکراری می‌شود.
• برای یک مورد زیر رشته تکراری پیوسته که طول آن ضریب ۳ بعلاوه 2 است (3n+2 به عنوان مثال "aaaaa") حذف سه حرف اضافی موجب کاهش محدودیت یک مورد از این زیررشته تکراری می‌شود.

به عنوان مثال:

برای زیر رشته 3n حرفی پیوسته خواهیم داشت: "1aaaaaaA…2" که حذف یک حرف اضافه می‌تواند، موجب کاهش محدودیت تنها یک زیر رشته 3 حرفی تکراری شود، که این حالت می‌تواند "1aaaaaA...2" باشد.

برای زیر رشته 3n+1 حرفی پیوسته خواهیم داشت: "12aaaaaaaA...2" که حذف دو حرف اضافه می‌تواند، موجب کاهش محدودیت تنها یک زیر رشته 3 حرفی تکراری شود، که این حالت می‌تواند "12aaaaaA...2" باشد.

برای زیر رشته 3n+2 حرفی پیوسته خواهیم داشت: "123aaaaaaaaA...2" که حذف سه حرف اضافه می‌تواند، موجب کاهش محدودیت تنها یک زیر رشته 3 حرفی تکراری شود، که این حالت می‌تواند "123aaaaaA...2" باشد.

نکته: دقت شود که در مثال های بالا حداقل تعداد تغییرات باید مورد ملاک باشد.

برای روشن شدن موضوع مثال شماره 4 جدول فوق را بررسی می کنیم:

اگر داشته باشیم:

aaaabbaaabbaaa123456A

این رشته شامل 21 حرف یا کاراکتر هست، که شامل 3 محدودیت حروف تکراری (که شامل 2 توالی 3n حرفی و 1 توالی 3n+1 حرفی) و 1 محدودیت حرف حذفی است که اگر بخواهیم با حداقل تغییرات رشته فوق را معتبر کنیم، این دسته بندی این‌گونه است:

که برای حذف حرف اضافی از رشته فوق یک محدودیت از محدودیت‌های زیررشته 3 حرفی از مثال بالا کاهش می یابد، اگر برای معتبر شدن رشته حرف a  را از توالی تکراری سمت راست را حذف کنیم، خواهیم داشت:

و دو محدودیت از سه محدودیتی که داشتیم و یکی را برطرف کردیم، باقی می‌ماند. که حداقل اصلاح مورد نیاز برای اینکه کلمه عبور فوق معتبر شود، سه محدودیت می باشد.

یا در مثال aaaaaa1234567890123Ubefg با طول 24 که شامل 4 حرف اضافه، 2 محدودیت حروف تکراری (که شامل 1 توالی 3n حرفی است) که جمعا حداقل به 4 تغییر احتیاج خواهیم داشت.

یا در مثال aaaaaaaaaaaaaaaaaaaaa با طول 21 که شامل 1 حرف اضافه، 7 محدودیت حروف تکراری (که شامل 1 توالی 3n حرفی است) که جمعا حداقل به 7 تغییر احتیاج خواهیم داشت.

در نتیجه مقدار حروف اضافه که محدودیت ایجاد می کنند ثابت است، و این مقدار اضافه شده محدودیت توالی سه حرفی است، که باید در حالتی که رشته ما بیشتر از 20 حرف طول دارد، اصلاح شود.

توضیح الگوریتم

این تابع از را به سه بخش تقسیم کرده ایم:

1-حالتی که اندازه رشته ورودی ما کمتر 6 هست.

2-حالتی که اندازه رشته ورودی ما بین 6 تا 20 کاراکتر هست.

3-حالتی که رشته ما بیش از 20 کاراکتر دارد.

حالت اول و دوم بسیار ساده است.

در حالت اول کافیست مقدار حداکثر بین تعداد محدودیت های ناشی از نوع حرف یا 6-len(s) را به خروجی برگردانیم.

در حالت دوم نیز مقدار حداکثر بین محدودیت هر 3 حرف تکراری که باید اصلاح شوند یا محدودیت های نوع را به خروجی برمی گردانیم.

حالت سوم که مشکل ترین، مرحله الگوریتم هست، می بایست به ازای هر حرف اضافه یک محدودیت اضافه در نظر بگیریم، که این محدودیت اضافه می‌تواند بر روی توالی های 3n، 3n+1 و 3n+2 تاثیر بگذارد.

در خط 2 متغیرهای اصلی الگوریتم را تعریف کرده‌ایم:

• متغیر str_len جهت نگهداری اندازه رشته متنی ورودی با مقدار اولیه برابر طول رشته ورودی.
• متغیر change جهت نگهداری محدودیت تعداد کل زیررشته‌های سه حرفی تکراری پیوسته با مقدار اولیه برابر صفر.
• متغیر triple جهت نگهداری تعداد سه حرف تکراری پیوسته یک زیر رشته با مقدار اولیه برابر صفر.
• متغیر seq باقیمانده تقسیم بر 3 را نگهداری می‌کند، با مقدار اولیه برابر صفر.
• متغیر i اندیس رشته برای پیمایش با مقدار اولیه برابر صفر.
• متغیر length اندازه حروف یک زیر رشته تکراری پیمایش شده با مقدار اولیه برابر یک.
• متغیر delete تعداد حروف اضافی را نگهداری می‌کند، با مقدار اولیه برابر صفر.
• آرایه types یک آرایه با 4 عنصر هست، که عنصر اول آن را برای خروجی تابع get_missing_type بی ارزش تلقی کردیم، و عناصر آن را با یک مقدار دهی نموده ایم، که جمع سه عنصر اولیه برابر 3 محدودیت نوع ورودی است، که با یافتن هر حرفی که این محدودیت را از بین می‌رود اندیس مورد نظر را صفر می‌کنیم.

در خط 3 تابع get_missing_type را تعریف نموده‌ایم که اندیس مورد نظر هر محدودیت نوع را برای آرایه types  به ما می‌دهد.

در خط 4 یک حلقه برای پیمایش حروف رشته تعریف نموده‌ایم.

خط 5 جهت به دست آوردن طول زیررشته تکراری پیوسته تعریف شده است.

در خط 6 محدودیت نوع را چک می‌کنیم و هرجا که محدودیت بر طرف شد، پرچم 1 محدودیت نوع حرف را صفر می‌کنیم. دقت شود که وقتی حروف تکراری هست، چک کردن آخرین حرف مانند چک کردن تمام حروف تکراری ماقبل است.

در خط 7 تعداد زیر رشته‌های 3 حرفی تکراری را شمارش کرده‌ایم.

در خط 8 یک شرط گذاشته‌ایم، که اگر تعداد زیر رشته‌های 3 حرفی داشتیم. آن را به عنوان محدودیت تغییر به متغیر change اضافه کن، منتهی اگر حروف اضافی داشتیم باید تغییراتی در آن اعمال شود.

در خط 10 مقدار  باقیمانده تقسیم بر 3 را برای زیر رشته‌های پیوسته با یک حرف تکراری به دست آورده‌ایم؛ اگر این باقیمانده برابر صفر بود و حداقل یک حرف اضافی داشتیم، یک واحد از مقدار محدودیت زیررشته‌های 3 حرفی تکراری کم و یک واحد نیز از حروف اضافی موقتی کم می‌کنیم. اگر نیز باقیمانده برابر یک بود، یک واحد از مقدار محدودیت زیررشته‌های 3 حرفی تکراری کم و دو واحد نیز از حروف اضافی موقتی کم می‌کنیم و در خط 18 کد، تعداد حروف اضافی باقیمانده نیز به ازای هر سه حرف یک واحد از مقدار محدودیت زیررشته‌های 3 حرفی تکراری کم می‌کنیم.

در خط 16 مجموع محدودیت‌های نوع را به دست آورده‌ایم که حداکثر 3 می‌شود.

در خط 21 اگر رشته ورودی ما بیشتر 20 حرف داشت، تعداد حروف اضافی که ایجاد محدودیت می‌کنند بعلاوه حداکثر بین محدودیت نوع و محدودیت‌های سه حرفی اصلاح شده جواب مسئله ما است.

خط 22 اگر رشته ورودی ما بین 6 تا 20 حرف داشت، حداکثر بین محدودیت نوع و محدودیت‌های سه حرفی بدون نیاز به  اصلاح جواب مسئله ما است.

خط 22  اگر رشته ورودی ما تا 5 حرف داشت حداکثر بین محدودیت نوع و تعداد حروفی که وارد نشده است، جواب مسئله است.

یک نمونه از تحلیل الگوریتم فوق را در جدول زیر می توانید، مشاهده کنید: