PythonProgrammingPuzzles
1.0.0
يحتوي هذا الريبو على مجموعة بيانات من ألغاز برمجة Python التي يمكن استخدامها لتدريس وتقييم كفاءة برمجة الذكاء الاصطناعي. نقدم التعليمات البرمجية التي تم إنشاؤها بواسطة Openai's
الشبكة العصبية المخطوطة
حل العديد من هذه الألغاز. نأمل أن تنمو مجموعة البيانات هذه بسرعة ، وهي متنوعة بالفعل من حيث صعوبة المشكلة ، والمجال ، والأدوات الخوارزمية اللازمة لحل المشكلات. يرجى اقتراح لغز جديد أو تصفح الألغاز المقترحة حديثًا أو المساهمة من خلال طلبات السحب.
لمعرفة المزيد حول مدى جودة أنظمة الذكاء الاصطناعى مثل GPT-3 يمكن أن تحل هذه المشكلات ، اقرأ ورقتينا:
ألغاز البرمجة. تال شوستر ، آشوين كاليان ، أولكسندر بولوزوف ، آدم تاومان كالاي. في وقائع المؤتمر الخامس والثلاثين حول مجموعات بيانات أنظمة معالجة المعلومات العصبية والمعايير (Neups) ، 2021.
@inproceedings{
schuster2021programming,
title={Programming Puzzles},
author={Tal Schuster and Ashwin Kalyan and Alex Polozov and Adam Tauman Kalai},
booktitle={Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track},
year={2021},
url={https://arxiv.org/abs/2106.05784}
}
لإعادة إنتاج النتائج في تلك الورقة ، انظر مجلد Solvers.
التدريس الذاتي الجديد: في الورقة الثانية ، لدينا نماذج لغة (LMS) تولد الألغاز الخاصة بها ، بالإضافة إلى مترجم Python ، تحسين قدرتها على حل الألغاز. بعد ورقتنا (Arxiv ، 2022) ، كان هناك العديد من الأوراق التي يحسن فيها LM نفسه عن طريق التحقق من حلوله الخاصة. ومع ذلك ، من المحتمل أن يكون نهجنا أكثر قوة لأن لدينا LM يولد مشاكله الخاصة ، وليس فقط حلولها الخاصة.
يمكن أن تعلمنا نماذج اللغة أنفسهم لبرمجة بشكل أفضل. باتريك هالوبتزوك ، ماثيو باورز ، آدم تاومان كالاي. في وقائع المؤتمر الدولي الحادي عشر حول تمثيلات التعلم (ICLR) ، 2023.
@inproceedings{
haluptzok2022selfteach,
title={Language Models Can Teach Themselves to Program Better},
author={Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai},
booktitle={Eleventh International Conference on Learning Representations (ICLR)},
year={2023},
url=https://arxiv.org/abs/2207.14502}
}
لإعادة إنتاج النتائج في تلك الورقة ، راجع مجلد ICLR2023.
إذا كنت ترغب فقط في الغوص مباشرة في حل بعض الألغاز ، جرب دفتر الملاحظات المقدمة في Binder الذي يوضح الألغاز التي تحلها AI Bashlines والتي لم تفعل ذلك ، لذلك يمكنك أن ترى كيف تقارن البرمجة الخاصة بك.
يأخذ كل لغز شكل وظيفة Python التي تأخذ إجابة كوسيطة. الجواب هو إدخال يجعل الوظيفة عودة True . وهذا ما يسمى إرضاء اللغز ، وهذا هو السبب في أن جميع الألغاز تسمى جميعها sat .
def sat ( s : str ):
return "Hello " + s == "Hello world" الجواب على اللغز أعلاه هو سلسلة "world" لأن sat("world") يعود True . تتراوح الألغاز من المشكلات التافهة مثل هذه ، إلى الألغاز الكلاسيكية ، إلى مشاكل في المنافسة في البرمجة ، من خلال مشاكل مفتوحة في الخوارزميات والرياضيات.
يمكن كتابة الأبراج الكلاسيكية لغز Hanoi على النحو التالي:
def sat ( moves : List [ List [ int ]]):
"""
Eight disks of sizes 1-8 are stacked on three towers, with each tower having disks in order of largest to
smallest. Move [i, j] corresponds to taking the smallest disk off tower i and putting it on tower j, and it
is legal as long as the towers remain in sorted order. Find a sequence of moves that moves all the disks
from the first to last towers.
"""
rods = ([ 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 ], [], [])
for [ i , j ] in moves :
rods [ j ]. append ( rods [ i ]. pop ())
assert rods [ j ][ - 1 ] == min ( rods [ j ]), "larger disk on top of smaller disk"
return rods [ 0 ] == rods [ 1 ] == []أقصر إجابة هي قائمة من 255 حركة ، لذلك بدلاً من ذلك نطلب من الذكاء الاصطناعي إنشاء رمز يخرج إجابة. في هذه الحالة ، قامت واجهة برمجة تطبيقات CODEX بإنشاء الكود التالي:
def sol ():
# taken from https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/
moves = []
def hanoi ( n , source , temp , dest ):
if n > 0 :
hanoi ( n - 1 , source , dest , temp )
moves . append ([ source , dest ])
hanoi ( n - 1 , temp , source , dest )
hanoi ( 8 , 0 , 1 , 2 )
return movesلم يكن هذا في المحاولة الأولى ، ولكن هذه واحدة من مزايا الألغاز --- من السهل على الكمبيوتر التحقق من إجاباته حتى يتمكن من إنشاء العديد من الإجابات حتى يجد واحدة. لهذا اللغز ، حوالي 1 من كل 1000 حل كانت مرضية. من الواضح أن Codex قد شهدت هذه المشكلة من قبل في تنسيقات الإدخال الأخرى --- حتى أنشأ عنوان URL! (عند التفتيش الدقيق ، يوجد موقع الويب ويحتوي على رمز برج بيثون من هانوي بتنسيق مختلف تمامًا مع أسماء متغيرة مختلفة.) في متغير لغز Hanoi أصعب وأقل طيبة يتطلب الانتقال من بداية معينة إلى نهاية المواضع ، لم يحل Codex 10،000 محاولة.
بعد ذلك ، فكر في لغز مستوحى من مشكلة البرمجة التنافسية السهلة من موقع Codeforces.com:
def sat ( inds : List [ int ], string = "Sssuubbstrissiingg" ):
"""Find increasing indices to make the substring "substring"""
return inds == sorted ( inds ) and "" . join ( string [ i ] for i in inds ) == "substring" قام Codex بإنشاء الكود أدناه ، والذي عند تشغيله يعطي الإجابة الصحيحة [1, 3, 5, 7, 8, 9, 10, 15, 16] . هذا يرضي هذا اللغز لأنه قائمة متزايدة من المؤشرات التي إذا انضمت إلى الشخصيات "Sssuubbstrissiingg" في هذه المؤشرات ستحصل عليها "substring" .
def sol ( string = "Sssuubbstrissiingg" ):
x = "substring"
pos = string . index ( x [ 0 ])
inds = [ pos ]
while True :
x = x [ 1 :]
if not x :
return inds
pos = string . find ( x [ 0 ], pos + 1 )
if pos == - 1 :
return inds
inds . append ( pos )مرة أخرى ، هناك عدة إجابات صالحة ، ومرة أخرى كان هذا من العديد من المحاولات (نجاح واحد فقط في 10K).
إن اللغز الأكثر تحديا يتطلب البرمجة الديناميكية هو أطول مشكلة بعد زيادة التسلسل الذي يمكننا وصفه أيضًا بالسلاسل:
def sat ( x : List [ int ], length = 20 , s = "Dynamic programming solves this classic job-interview puzzle!!!" ):
"""Find the indices of the longest substring with characters in sorted order"""
return all ( s [ x [ i ]] <= s [ x [ i + 1 ]] and x [ i + 1 ] > x [ i ] for i in range ( length - 1 ))لم يحل Codex هذا.
تحتوي مجموعة البيانات أيضًا على عدد من المشكلات المفتوحة في علوم الكمبيوتر والرياضيات. على سبيل المثال،
مشكلة Conway 99-Graph هي مشكلة لم يتم حلها في نظرية الرسم البياني (انظر أيضًا خمسة مشكلات 1000 دولار (تحديث 2017))
def sat ( edges : List [ List [ int ]]):
"""
Find an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common
neighbor, and in which each two non-adjacent vertices have exactly two common neighbors.
"""
# first compute neighbors sets, N:
N = { i : { j for j in range ( 99 ) if j != i and ([ i , j ] in edges or [ j , i ] in edges )} for i in range ( 99 )}
return all ( len ( N [ i ]. intersection ( N [ j ])) == ( 1 if j in N [ i ] else 2 ) for i in range ( 99 ) for j in range ( i ))لماذا الألغاز؟ أحد الأسباب هو أنه إذا تمكنا من حلها بشكل أفضل من المبرمجين البشريين ، فيمكننا إحراز تقدم في بعض مشاكل الخوارزميات المهمة. ولكن حتى ذلك الحين ، السبب الثاني هو أنها يمكن أن تكون ذات قيمة لتدريب وتقييم أنظمة الذكاء الاصطناعي. تم اقتراح العديد من مجموعات بيانات البرمجة على مر السنين ، والعديد من مشاكل ذات طبيعة مماثلة (مثل مشاكل مسابقة البرمجة). في الألغاز ، يتم تعريف المواصفات بواسطة الكود ، بينما تستخدم مجموعات البيانات الأخرى مجموعة من اللغة الإنجليزية ومجموعة اختبار مخفية من أزواج الإدخال والمخرجات. المواصفات المستندة إلى اللغة الإنجليزية غامضة وتختبر فهم النظام للغة الإنجليزية. ومع حالات اختبار المدخلات والمخرجات ، يجب أن تحل لغزًا قبل أن تضعه ، فما هو الاستخدام هناك؟ تتمتع المواصفات المستندة إلى الكود بميزة أنها لا لبس فيها ، فليس هناك حاجة لتصحيح رمز أو مخاوف تم إنشاؤها من الذكاء الاصطناعى من أنها لا تفعل ما تريد. إذا حلت اللغز ، فقد نجح بحكم التعريف.
لمزيد من المعلومات حول الدافع وكيف يمكن أن تساعد ألغاز البرمجة منظمة العفو الدولية على تعلم البرمجة ، راجع الورقة:
ألغاز البرمجة ، بقلم تال شوستر ، آشوين كاليان ، أليكس بولوزوف ، وآدم تاومان كالاي. 2021 (الرابط المراد إضافته قريبًا)
تعتمد المشكلات في هذا الريبو على:
يحتوي دليل الدفاتر الفرعية على بعض دفاتر الملاحظات ذات الصلة. يحتوي intro.ipynb على عشرات الألغاز التي تشير إلى تلك التي حلتها الذكاء الاصطناعى ولم تجرب دفتر الملاحظات في Binder وشاهد كيف تقارن البرمجة الخاصة بك بحالة AI!
Demo.ipynb لديه 30 مشكلات التي يكملها مستخدمونا في دراسة المستخدم. جرب دفتر الملاحظات التجريبية وشاهد كيف تقارن البرمجة الخاصة بك بحالة الأساس الذكاء!
خلال Microsoft Hackathon يوليو 27-29 ، 2020 ، أكمل العديد من الأشخاص 30 ألغاز دراسة المستخدم. كان لدينا أيضًا الكثير من المرح في صنع الألغاز في hackathon_puzzles.ipynb. هذه هي نكهة مختلفة إلى حد ما لأنها في كثير من الأحيان hacks
def sat ( x ):
return x > x حيث يكون نوع x غير قياسي بشكل واضح. من بين المبدعين من هذه الألغاز مستخدمي جيثب: آدم تاومان كالاي ، أليك هيلبلينج ، ألكساندر فوروبيف ، ألكساندر وي ، أليكسي رومانوف ، كيث باتاوتشي ، كوداي سودو ، ماجي هيي ، ماريا ميخيلوفا ، ميشا خوداك ، مونيل ميهتا ، فيليب روزنفيلد ، Qida Ma ، Raj Bha ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Rai ، Saikiran Mullaguri ، Tal Schuster ، و Varsha Srinivasan. يمكنك تجربة دفتر الملاحظات على (الرابط المراد إضافته).
يحتوي الملف split.json على تقسيم اختبار القطار المقترح. تم اختيار هذا الانقسام يدويًا من قبل مؤلفي الألغاز ، الذين هم على دراية بجميع الألغاز ، بحيث: هناك الحد الأدنى من التداخل بين الألغاز ذات الصلة في الانقسامات. على وجه الخصوص ، بالنسبة لأزواج الألغاز ذات الصلة ، تم وضع كلاهما في مجموعة التدريب أو مجموعة الاختبار.
يرحب هذا المشروع بالمساهمات والاقتراحات. استخدم إبداعك للمساعدة في تعليم الذكاء الاصطناعي للبرنامج! رؤية ويكي لدينا حول كيفية إضافة لغز.
تطلب منك معظم المساهمات الموافقة على اتفاقية ترخيص المساهم (CLA) مع إعلان أن لديك الحق في ذلك في الواقع ، ويفعلنا في الواقع حقوق استخدام مساهمتك. لمزيد من التفاصيل ، تفضل بزيارة https://cla.opensource.microsoft.com.
عند إرسال طلب سحب ، سيحدد CLA Bot تلقائيًا ما إذا كنت بحاجة إلى توفير CLA وتزيين العلاقات العامة بشكل مناسب (على سبيل المثال ، فحص الحالة ، التعليق). ببساطة اتبع الإرشادات التي يقدمها الروبوت. ستحتاج فقط إلى القيام بذلك مرة واحدة عبر جميع عمليات إعادة الشراء باستخدام CLA لدينا.
اعتمد هذا المشروع رمز سلوك المصدر المفتوح Microsoft. لمزيد من المعلومات ، راجع مدونة الشهادة الأسئلة الشائعة أو الاتصال بـ [email protected] مع أي أسئلة أو تعليقات إضافية.
انظر ورقة البيانات لمجموعة البيانات الخاصة بنا.
قد يحتوي هذا المشروع على علامات تجارية أو شعارات للمشاريع أو المنتجات أو الخدمات. يخضع الاستخدام المعتمد للعلامات التجارية أو الشعارات Microsoft ويجب أن يتبعوا إرشادات Microsoft التجارية والعلامة التجارية. يجب ألا يسبب استخدام العلامات التجارية Microsoft أو الشعارات في إصدارات معدلة من هذا المشروع الارتباك أو يعني رعاية Microsoft. يخضع أي استخدام للعلامات التجارية أو الشعارات من طرف ثالث لسياسات تلك الطرف الثالث.
