داستان از جایی شروع شد که تو قسمت ۲ فصل ۴ سریال Person of Interest یه معما مطرح میشه و پاسخش باعث شد که به فکر انجام این پروژه بیفتم. مطالبی که در ادامه در مورد این معما میگم به هیچ وجه اسپویل سریال نیست. اینجوری نیست که این معما با یه چیز مهم در قسمت های بعدی مرتبط باشه. توی همون قسمت در حد ۵ دقیقه تاریخ مصرف داره.
به تصویر زیر که یک صحنه از این سریاله توجه کنید :
اینجا یه شماره تلفن پیدا میکنن و زمانی که باهاش تماس می‌گیرن، می‌بینن کلا چنین شماره‌ای در شبکه وجود نداره. بعد حدس می‌زنن که این نقاطی که بین اعداد وجود داره نشان دهنده علامت ضرب باشه. اگر این ضرب رو انجام بدید نتیجه به صورت زیر میشه :
950✖641✖6701 = 4,080,573,950
با یه عدد ۱۰ رقمی روبه‌رو هستیم. بعد متوجه میشن که این عدد یک مختصات جغرافیایی رو داره نشون میده. این مختصات رو نشون میده :
latitude = 40.805
longitude = 73.950
این مختصات یه جایی توی قرقیزستانه. اما جریان این سریال توی آمریکا داره اتفاق میافته و اگر 73.950 رو به منفی 73.950 تغییر بدیم میشه یه جایی توی نیویورک.
حالا ایده‌ای که به سرم زد این بود که این کار رو برای شماره موبایل های ایران انجام بدم و ببینم چه لوکیشن هایی داخلش پیدا میشه. یعنی چی؟ مثلا شماره زیر رو در نظر بگیرید :
9123456789
صفر اولش رو در نظر نمی‌گیرم. 912 هم که ثابته و تغییر نمیکنه. برای ۷ رقم بعدش هم باید جایگشت k شی از n شی رو محاسبه کنیم که n میشه ۱۰ و k میشه ۷. تعداد جایگشت های بدون تکرار برابر است با :
604800
بدون تکرار یعنی چی؟ یعنی تو 7 رقم آخر یه شماره، از هر عدد فقط یکی وجود داره. مثلا شماره های زیر رو نداریم:
9123456111
9123456788
اگر بخوایم عدد تکراری هم داشته باشیم، میشه 10 میلیون حالت مختلف که پردازش کردنش سخت نیست ولی خب طول میکشه و من میخوام بدون تکرارش رو بررسی کنم. اگر کسی می‌خواد اون 10 میلیون حالت رو محاسبه کنه میتونه خودش دست به کد بشه و اگر کدنویسی بلد نیست و به پاسخش نیاز داره میتونه در قالب پروژه به من بگه براش انجام بدم!
اولین کاری که انجام دادم این بود که پیش شماره های اپراتور های مختلف رو پیدا کنم که از مطلبی که این سایت نوشته پیدا کردم.
پیش شماره های همراه اول :
990,991,992,993,994,911,912,913,914,915,916,917,918
پیش شماره های ایرانسل :
930,933,935,936,937,938,939,901,902,903,904,905,941,900
پیش شماره های رایتل :
920,921,922
در مجموع ۳۰ تا پیش شماره داریم. ممکنه پیش شماره های دیگه‌ای هم وجود داشته باشه ولی من فقط این پیش شماره ها رو میخوام بررسی کنم. حالا مختصات رو چه جوری از این شماره ها استخراج کنیم؟ دقیقا مثل همین کاری که تو سریال انجام شد، منم میام ۳ رقم اول رو در ۳ رقم دوم و در ۴ رقم آخر ضرب میکنم. مثلا اگر شماره زیر رو داشته باشیم :
9123456789
ضربش به صورت زیر میشه :
912✖345✖6789 = 2,136,090,960
من ضرب به شکل بالا رو برای تمام جایگشت های هر پیش شماره محاسبه کردم و نتیجه این ضرب، یک عدد 8 یا 9 یا 10 رقمی شد. از این سه حالت خارج نبود. برای هر حالت من به یک شکل مختصات رو استخراج میکنم که در ادامه توضیح میدم. لطفا شرط هایی که میذارم رو با دقت بخونید. چون این مسئله رو با شرط های مختلف میشه به شکل های مختلف بررسی کرد. من تمام شرط هایی که مد نظرمه رو توضیح میدم. پس با دقت بخونید.
اعداد 8 رقمی : مثلا فرض کنید نتیجه یه ضربی شده 21,361,909. حالا اگر بخوایم lat و long ما حداقل 2 رقم اعشار داشته باشند، مختصات ما به صورت زیر میشه :
latitude = 21.36
longitude = 19.09
شاید این سوال براتون پیش بیاد که چرا قبل از اعشار رو 2 رقم در نظر گرفتی؟ دلیلش اینه که lat تمام نقاط در ایران حدودا بین 24 تا 40 و long حدودا بین 43 تا 63 قرار داره. همونطور که می‌بینید، کلا قبل از اعشار ما دو رقم رو داریم و از اونجایی که من میخوام lat و long های داخل ایران رو پیدا کنم، کلا فرض میکنم قبل از اعشار 2 رقم رو داریم. نکته دیگه‌ای هم که وجود داره اینه که رنج lat میتونه بین منفی 90 تا 90 و رنج long میتونه بین منفی 180 تا 180 باشه. پس هر عدد سه رقمی رو هم نمی‌تونیم به عنوان lat و long در نظر بگیریم و تو ایران هم که فقط 2 رقمی داریم. پس چه کاریه؟ کلا 2 رقمی در نظر میگیرم. خلاصه اینکه قبل از اعشار رو 2 رقم و بعد از اعشار رو حداقل 2 رقم در نظر میگیرم.
اعداد 9 رقمی : فرض کنید نتیجه یه ضربی شده 213,619,096. با این شرط که lat و long حداقل 2 رقم اعشار داشته باشه، دو حالت زیر رو می‌تونیم داشته باشیم.
مختصات اول :
latitude1 = 21.36
longitude1 = 19.096
مختصات دوم :
latitude2 = 21.361
longitude2 = 90.96
اینجا هم می‌بینید دیگه؟ اگر قبل از اعشار رو 2 رقم و بعد از اعشار رو حداقل 2 رقم در نظر نگیرم، حالت های دیگه‌ای هم به وجود میاد که ما ازش صرف نظر می‌کنیم. نکته دیگه‌ای که وجود داره اینه که من فرض میکنم قراره همه ارقام این عدد مصرف بشه. یعنی چی؟ یعنی شما نمی‌تونید بگید 2 رو از ابتدای عدد نادیده میگیرم و lat و long زیر رو به دست بیارید :
latitude = 13.61
longitude = 90.96
من میخوام دقیقا مثل فیلم، همه ارقام مصرف بشه. وگرنه از این ارقام مختصات متنوعی رو میشه استخراج کرد که شرایط مسئله من رو نداشته باشه. مثلا 1 رقم اعشار داشته باشه. یا قبل از اعشار long یه عدد سه رقمی باشه.
اعداد 10 رقمی : فرض کنید نتیجه یه ضربی شده 2,136,090,960. سه حالت زیر رو می‌تونیم داشته باشیم:
مختصات اول :
latitude1 = 21.36
longitude1 = 9.0960
مختصات دوم :
latitude2 = 21.360
longitude2 = 9.0960
مختصات سوم :
latitude3 = 21.3609
longitude3 = 9.60
اینجا یه حالت خاص به وجود اومده. اگر اون 2 رقم قبل از اعشاری که انتخاب میشه مثلا 09 باشه، خب 0 قبل از 9 حساب نمیشه و اینجا عدد ما یک رقمی شد که مهم نیست. با اون شرطی که گذاشتم، خود به خود حذف میشه.
پس تا الان با الگوریتم کار آشنا شدید. مرحله بعدی چیه؟ برای تمام ۳۰ تا پیش شماره‌ای که بالاتر گفتم، به روشی که گفتم، ضرب رو انجام بدیم و بعد به روشی که گفتم مختصات رو استخراج کنیم. من تو اینترنت کمی سرچ کردم تا رنج lat و long ایران رو پیدا کنم که به این سایت رسیدم که نوشته :
Latitude from 25.2919 to 39.6482 and longitude from 44.7653 to 61.4949
تقریبا ۱.۵ میلیون نقطه توی این رنج پیدا شد. با وجود اینکه رنج خوبی رو گفته بود ولی بخش هایی از شمال غرب و جنوب شرق کشور داخل این رنج نیست. من یه مقدار رنج رو بزرگتر کردم که در نتیجه ۲ میلیون نقطه پیدا شد که اگر هیت‌مپ این نقاط رو رسم کنیم به این صورت میشه :
توی عکس بالا هر چقدر به سمت قرمز بریم یعنی تعداد lat و long های بیشتری توی اون نقاط وجود داشته. هر چقدر هم به سمت رنگ سبز بریم، یعنی تعداد lat و long های کمتری توی اون نقاط وجود داشته. اما بهتره که نقاط خارج از نقشه ایران رو ازش حذف کنم. تعداد نقاط خیلی زیاده و واقعا هم همه نقاط رو نیاز نداریم بررسی کنیم که آیا داخل ایرانه یا نه! بنابراین من به صورت دستی بخش هایی از مرکز و خارج از مرز های ایران رو حذف کردم و بقیه نقاط رو با استفاده از سرویس Reverse Geocoding نشان بررسی کردم که داخل ایرانه یا نه. سرویس های دیگه‌ای هم برای این کار وجود داره ولی تجربه ای که داشتم، سرعت API نشان بیشتر از بقیه بوده.
کار های دیگه ای هم می شد انجام داد. مثلا به کمک کتابخونه های Shapely و GeoPandas و json مرز ایران میشد کار مشابهی رو انجام داد ولی من از این روش استفاده کردم. البته این کتابخونه ها نکاتی دارن (از نظر سرعت) که الان نمیخوام در موردش بحث کنم.
نتیجه عکس زیر شد:
تصویر زیر هم هیت مپ هر کدوم از این 30 تا پیش شماره است :
حالا سوال پیش میاد که چرا هر چی به سمت جنوب ایران میریم، تعداد این نقاط بیشتر میشه؟ از شمال به جنوب مقدار latitude تغییر میکنه (کم میشه) :
گفتم که رنج latitude ایران بین حدود ۲۴ تا ۴۰ قرار داره. اگر به نحوه به دست آمدن latitude از اون نتیجه ضرب ارقام توجه کنید، می‌بینید که همیشه و در هر حالتی، حداقل ۴ رقم اول اون عدد میشه latitude. چرا؟ چون الگوریتمی که تعریف کردیم داره به این شکل عمل میکنه. به نمودار زیر توجه کنید :
این نمودار داره تعداد تکرار latitude های مختلف رو نشون میده. همونطور که می‌بینید، هر چقدر به سمت شمال میریم تعداد تکرار latitude ها داره کم میشه.
حالا اگر خودمون بخوایم چنین معمایی رو طراحی کنیم باید چیکار کنیم؟ فرض کنید میخوام با لوکیشن برج میلاد این کار رو انجام بدم. لوکیشن برج میلاد اینه :
latitude = 35.74477071243827
longitude = 51.375508002753214
اول میخواستم از lat و long فقط ۴ رقم اول (۲ رقم قبل اعشار و ۲ رقم بعد اعشار) رو انتخاب کنم. بعد توی تست ها دیدم روی بعضی لوکیشن ها جواب میده و روی بعضی جواب نمیده. برای حل مشکل اومدم به صورت زیر عمل کردم تمام حالت ها رو امتحان میکنم :
-4 رقم اول lat رو به 4 رقم اول long بجسبون و سه تا عامل ضرب رو پیدا کن
-4 رقم اول lat رو به 5 رقم اول long بجسبون و سه تا عامل ضرب رو پیدا کن
-4 رقم اول lat رو به 6 رقم اول long بجسبون و سه تا عامل ضرب رو پیدا کن
.
.
-5 رقم اول lat رو به 4 رقم اول long بجسبون و سه تا عامل ضرب رو پیدا کن
-5 رقم اول lat رو به 5 رقم اول long بجسبون و سه تا عامل ضرب رو پیدا کن
-5 رقم اول lat رو به 6 رقم اول long بجسبون و سه تا عامل ضرب رو پیدا کن
.
.
برای این لوکیشن برج میلاد که قرار دادم اعداد زیر رو پیدا کرد که هیچ کدوم شبیه شماره موبایل نیستند :
125.859.3329
859.125.3329
یا مثلا همین کار رو برای میدون ولیعصر انجام دادم و اعداد زیر رو خروجی داد :
173.249.8291
249.173.8291
498.865.8291
519.830.8291
830.519.8291
865.498.8291
180.827.2399
827.180.2399
کدش رو تو این لینک قرار دادم. توی این کد یکی باید مقدار lat و long رو تغییر بدید. همچنین میتونید رنج اعداد رو عوض کنید. من عدد اول و دوم رو فرض کردم ۳ رقمیه و عدد چهارم ۴ رقمی. مثلا میتونید رنج عدد اول رو از 900 شروع کنید که سریع تر یه چیزی شبیه شماره موبایل پیدا کنه. حتی می تونید تعداد ارقامی که در هم ضرب میشن رو تغییر بدید. مثلا 2 رقم اول در 4 رقم بعدی و در 4 رقم بعدیش ضرب بشه. من به این شکل تونستم چیزی شبیه به شماره موبایل پیدا کنم ولی برای اینکه مزاحمتی برای شخص مربوطه ایجاد نشه نخواستم شماره ای توی این پست بذارم.
