فهرست مطالب

مقدمه🔗

بیایید تا از دانسته‌هایمان از دستورات خط فرمان استفاده کنیم و برنامه ننویسیم!

در سال ۱۹۸۴ برایان کرنیگان دانشمند علوم کامپیوتر و نویسنده‌ی محبوب من همراه با Rob Pike کتابی تحت عنوان Unix programming environment نوشتند. جمله‌ای از آن کتاب در خاطرم مانده و آن را با ترجمه‌ای آزاد نقل می‌کنم. گفته بودند: «تا می‌توانید سعی کنید از ابزارهای یونیکس استفاده کنید و برنامه‌ی مستقل ننویسید مگر اینکه مجبور باشید.» نام کتاب نیز واضح بیان می‌کند که محیط یونیکس (و سیستم‌های شبه یونیکس مثل لینوکس)، محیط برنامه‌نویسی است.

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

مساله‌ای برای حل شدن توسط ابزارهای خط فرمان🔗

عدد ۱۰۰۰ رقمی زیر را در نظر بگیرید:

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

می‌خواهیم ترکیب ۱۳ عدد پشت سر هم را پیدا کنیم که حاصلضرب این اعداد در هم از حاصلضرب تمامی توالی‌های ۱۳ رقمی دیگر بزرگتر باشد. برای مثال بزرگترین حاصلضرب ۴ عدد متوالی این لیست به صورت زیر است:

9 × 9 × 8 × 9 = 5832

یعنی هیچ دنباله ۴ عددی دیگری در لیست وجود ندارد که حاصلضرب آنها بیشتر از ۵۸۳۲ شود و ارقام این دنباله 9989 است.

حل مساله🔗

نیاز به هیچ زبان برنامه نویسی‌ای نیست، فقط باید بتوانیم از ابزارهای موجود در سیستم‌های شبه یونیکس به خوبی استفاده کنیم.

ابتدا عدد بالا را در یک فایل مثلا به نام b کپی کنید. توجه کنید که محتوای کادر بالا یک عدد و یک خط نیست بلکه ۲۰ عدد و ۲۰ خط است.

تبدیل محتوای فایل ورودی به یک عدد🔗

با استفاده از دستور tr کاراکترهای \n که به معنای New line یا معادل دگمه‌ی Enter هستند را از رشته‌ی ورودی پاک می‌کنیم تا بجای ۲۰ خط یک خط داشته باشیم:

$ cat b | tr -d "\n"

نتیجه در خروجی استاندارد که در این جا همان ترمینال است نوشته می‌شود. بنابر این باز می‌توانیم آن را توسط | به برنامه‌ی دیگری ارسال کنیم.

پیدا کردن ترکیب‌های ۱۳ رقمی🔗

در مرحله بعد نیاز داریم که کلیه ترکیب‌های ۱۳ رقمی این عدد را پیدا کنیم.

یک پنجره را تصور کنید که در آن ۱۳ رقم جا می‌شود. این پنجره را در ابتدای عدد فوق قرار می‌دهیم. بدیهی است که فقط ۱۳ رقم اول را می‌توانیم ببینیم. این عدد اولین ترکیب ماست. حالا این پنجره را یک رقم به سمت راست حرکت می‌دهیم. عدد دیده شده دومین ترکیب ماست. این کار را تا آنجایی ادامه می‌دهیم که عدد قرار گرفته در داخل پنجره کمتر از ۱۳ رقم داشته باشد. یعنی در واقع به ۱۲ رقم انتهایی عدد ۱۰۰۰ رقمی رسیده باشیم.

کد زیر به زبان awk این مفهوم را پیاده‌سازی می‌کند. این کد را در فایلی به نام b.awk ذخیره می‌کنیم:

#!/usr/bin/env awk -f
NR == 1 { 
    for (i=1;i<=length($0);i++) {
        s = substr($0, i, 13);
        if (length(s) != 13)
            break;
        print s;
    }
}

برای تست برنامه در خط فرمان، دستور زیر را اجرا می‌کنیم. برای بررسی صحت عملکرد، خروجی را در فایلی به نام awk.result ذخیره می‌کنیم:

$ cat b | tr -d "\n" | awk -f b.awk >awk.result
$ head -n 14 awk.result
7316717653133
3167176531330
1671765313306
6717653133062
7176531330624
1765313306249
7653133062491
6531330624919
5313306249192
3133062491922
1330624919225
3306249192251
3062491922511
0624919225119
$ tail -n 14 awk.result
8360082325753
3600823257530
6008232575304
0082325753042
0823257530420
8232575304207
2325753042075
3257530420752
2575304207529
5753042075296
7530420752963
5304207529634
3042075296345
0420752963450

تعداد ترکیبات بسیار زیاد است بنابر این در کد بالا فقط ۱۴ ترکیبِ ۱۳ رقمی ابتدایی و انتهایی را نمایش داده‌ایم. به نظر می‌رسد برنامه awk ترکیبات ۱۳ رقمی را به درستی پیدا می‌کند. مخصوصا به آخرین ترکیب نگاه کنید.

گذاشتن علامت ضرب بین ترکیب‌ها🔗

در این مرحله نیاز داریم تا شکل ترکیب‌ها را عوض کنیم و میان هر عدد یک علامت ضرب * بگذاریم تا کار برای محاسبات بعدی آماده شود. این کار را با sed انجام می‌دهیم. کل مراحل بالا تا اینجا در دستور خط فرمان زیر نمایش داده شده است. در این جا تعداد خروجی‌ها را به ۱۰ خط محدود می‌کنیم تا فضای زیادی اشغال نشود:

$ cat b | tr -d "\n" | awk -f b.awk | sed 's/\(.\)/\1\*/g;s/\*$//' | head
7*3*1*6*7*1*7*6*5*3*1*3*3
3*1*6*7*1*7*6*5*3*1*3*3*0
1*6*7*1*7*6*5*3*1*3*3*0*6
6*7*1*7*6*5*3*1*3*3*0*6*2
7*1*7*6*5*3*1*3*3*0*6*2*4
1*7*6*5*3*1*3*3*0*6*2*4*9
7*6*5*3*1*3*3*0*6*2*4*9*1
6*5*3*1*3*3*0*6*2*4*9*1*9
5*3*1*3*3*0*6*2*4*9*1*9*2
3*1*3*3*0*6*2*4*9*1*9*2*2

محاسبه‌ی حاصلضرب ترکیب‌ها🔗

خب! حالا باید جلوی هر خط یک = گذاشت و نتیجه‌ی حاصلضرب را جلوی آن نوشت. ساختار کنترلی while اینجا به کمک ما می‌آید:

$ cat b | tr -d "\n" | awk -f b.awk | sed 's/\(.\)/\1\*/g;s/\*$//' | while read line; do echo $line"="$[line]; done | head -n20
7*3*1*6*7*1*7*6*5*3*1*3*3=5000940
3*1*6*7*1*7*6*5*3*1*3*3*0=0
1*6*7*1*7*6*5*3*1*3*3*0*6=0
6*7*1*7*6*5*3*1*3*3*0*6*2=0
7*1*7*6*5*3*1*3*3*0*6*2*4=0
1*7*6*5*3*1*3*3*0*6*2*4*9=0
7*6*5*3*1*3*3*0*6*2*4*9*1=0
6*5*3*1*3*3*0*6*2*4*9*1*9=0
5*3*1*3*3*0*6*2*4*9*1*9*2=0
3*1*3*3*0*6*2*4*9*1*9*2*2=0
1*3*3*0*6*2*4*9*1*9*2*2*5=0
3*3*0*6*2*4*9*1*9*2*2*5*1=0
3*0*6*2*4*9*1*9*2*2*5*1*1=0
0*6*2*4*9*1*9*2*2*5*1*1*9=0
6*2*4*9*1*9*2*2*5*1*1*9*6=4199040
2*4*9*1*9*2*2*5*1*1*9*6*7=4898880
4*9*1*9*2*2*5*1*1*9*6*7*4=9797760
9*1*9*2*2*5*1*1*9*6*7*4*4=9797760
1*9*2*2*5*1*1*9*6*7*4*4*2=2177280
9*2*2*5*1*1*9*6*7*4*4*2*6=13063680

تعداد ترکیب‌ها بالاست بنابر این برای تست فقط ۲۰ مورد اول خروجی را نمایش داده‌ایم.

سورت کردن نتیجه‌ی حاصلضرب‌ها و پایان🔗

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

$ cat b | tr -d "\n" | awk -f b.awk | sed 's/\(.\)/\1\*/g;s/\*$//' | while read line; do echo $line"="$[line]; done | sort -t"=" -k2,2nr | head
5*5*7*6*6*8*9*6*6*4*8*9*5=23514624000
3*5*5*7*6*6*8*9*6*6*4*8*9=14108774400
9*7*5*3*6*9*7*8*1*7*9*7*7=8821658160
7*5*3*6*9*7*8*1*7*9*7*7*8=7841473920
4*3*5*5*7*6*6*8*9*6*6*4*8=6270566400
3*6*9*7*8*1*7*9*7*7*8*4*6=5377010688
5*3*6*9*7*8*1*7*9*7*7*8*4=4480842240
3*9*7*5*3*6*9*7*8*1*7*9*7=3780710640
4*7*6*5*4*5*6*8*2*8*4*8*9=3715891200
9*4*7*6*5*4*5*6*8*2*8*4*8=3715891200

مساله حل شد. بزرگترین حاصلضرب ۱۳ عدد متوالی برابر است با 23514624000 و حاصل از توالی [5576689664895] است. بخشی از این عدد در انتهای خط چهارم و بخشی دیگر از آن در ابتدای خط پنجم فایل b که همان عدد ۱۰۰۰ رقمیست قرار گرفته است.

ملاحظه می فرمایید که تنها با استفاده از خط فرمان و دستورات cat‍ و tr و awk و sed و sort و head و ساختار کنترلی while توانستیم این مساله را بدون نیاز به صرف وقت برای برنامه نویسی و تست برنامه حل کنیم.

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

شاد باشید.