ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
תחרות התכנות של גוגל 
 
 לגרום למחשב לעשות את מה שאתם רוצים - ומהר    צילום: GettyImages    
לפרק את הבייט |
 

גם אתם לא שמעתם בזמן על Google Code Jam? עידו גנדל עם כל המידע והרשמים מסיבוב המוקדמות של תחרות התכנות הפתוחה, העולמית והמגניבה

 
 
 
 
 
 
 
 
 
 
 
אם אתם חולמים לעבוד כמתכנתים בגוגל ועוד לא שמעתם על Google Code Jam, תצטרכו לדחות את הגשמת החלום בעוד שנה לפחות. ה-Code Jam, שמסיבות לא ברורות זכתה לפרסום אפסי ממש במקומותינו, היא תחרות תכנות עולמית ושנתית של גוגל, שהחלה בשנת 2003 וכוללת לא רק פרסים אלא גם רמיזות סמויות באשר לאפשרויות עבודה. השנה, ההרשמה לתחרות כבר נסגרה וגם שלב המוקדמות הסתיים, אך עדיין ניתן להשתתף כצופים ובעיקר להתחיל להתאמן לקראת הפעם הבאה.
 

איך זה עובד

לקפוץ למים של התכנות. הכישורים בסיסיים, אבל תצטרכו להזהר ממלכודות
 לקפוץ למים של התכנות. הכישורים בסיסיים, אבל תצטרכו להזהר ממלכודות 
 צילום: GettyImages 
 
כל תחרות מורכבת ממספר שלבים, שכולם (פרט לגמר) מתקיימים אונליין ודורשים מהמשתתפים לפתור בעיות תכנות קשות יותר ויותר בזמן מוגבל. הבעיות מוצגות באתר התחרות בשפה יומיומית וברורה, כולל קלט ופלט לדוגמה, והמתכנת נדרש לכתוב תוכנה לפתרון בכל שפת תכנות שמתחשק, כל עוד הכלים בהם הוא משתמש זמינים להורדה חינם. לכל בעיה מצורפים שני קובצי קלט, אחד קטן ואחד גדול, ומרגע שמורידים אותם יש ארבע או שמונה דקות, בהתאמה, להעלות בחזרה את קובץ הפלט. הניקוד מחושב לפי זריזות ההגשה (מרגע התחלת אותו שלב בתחרות) ומספר הקבצים שהמשתתף הגיש עד שהגיע לפתרון הנכון. יש להעלות גם את קוד התוכנית, שנבדק מן הסתם בשלבים המכריעים כדי להבטיח שאיש אינו מנסה לתחמן את המערכת.

כישורי התכנות הנדרשים, מבחינה טכנית, בסיסיים למדי וסביר להניח שכל תלמיד מתקדם במגמת מחשבים מצויד בהם: פעולות לוגיות, מניפולציה של מערכים ומחרוזות, מבני נתונים פשוטים ורקורסיה. עם זאת, חייבים להיות זריזים ובעיקר לחשוב נכון. כל בעיה דורשת יצירתיות מסוימת לפתרון, ובחלקן (כפי שנראה בהמשך) הפתרון הטריוויאלי לכאורה הוא לא פחות ממלכודת.
 
 

מילים חייזריות ואגני ניקוז

שלב המוקדמות של 2009 נערך בשני בספטמבר ונמשך עשרים ושש שעות – שתיים מתוכן הארכת זמן בשל תקלה טכנית. בתום השלב, אותו עברו 7830 מתכנתים מתוך כ-9700 שהגישו תשובות כלשהן, שלוש הבעיות שנכללו בו נשארו זמינות (כולל מנגנון הבדיקה האוטומטית של התשובות) וכן אפשר למצוא שם הצעות לפתרון מטעם מארגני התחרות. אם אתם מעוניינים לנסות את כוחכם, עשו זאת לפני שתקראו את המשך הכתבה מכיוון שאנו עוברים כעת לדיון בבעיות – ובפתרונותיהן.
 
לזהות את שפת החייזרים
 לזהות את שפת החייזרים 
 צילום: GettyImages 
 
הבעיה הראשונה ("Alien Language") היתה קלה: קובץ הקלט כולל "מילון", אוסף מילים באורך שווה (לדוגמה "ACB", "DBB" ו-"CBA"), ואחריו רשימה של תבניות מילים, שבהן חלק מהאותיות – או כולן – הוחלפו בסוגריים ובתוכם מספר אותיות חלופיות ("A(CB)B") המשימה היא למצוא כמה מילים מתוך המילון יכולות להתאים לכל אחת מהתבניות. בדוגמה שלנו, התבנית יכולה לייצג שתי מילים שונות: ABB או ACB. רק הראשונה נמצאת במילון, ולכן התשובה תהיה 1. כדי לפתור את הבעיה, כל שצריך לעשות הוא לפרק את התבנית למרכיביה ("A", "CB" ו-"B") ואז לבדוק, עבור כל אות במילה, אם היא נמצאת בתוך המחרוזת המקבילה בתבנית. אם כולן נמצאות, יש התאמה.

הבעיה השניה היתה מורכבת יותר, גם באופן הצגתה וגם בפתרונה. הקלט היה מערך דו-ממדי שייצג פני קרקע ב"גבהים" שונים, כאשר מי הגשמים מתנקזים מכל תא במערך אל התא הנמוך ביותר מבין הצמודים אליו, או – אם הוא עצמו הנמוך ביותר – נשארים בו. במקרה של שוויון בין תאים סמוכים, נקבע "סדר עדיפות" בהתאם לכיוון – צפון, מערב, מזרח או דרום. הגדרות אלה יוצרות "אגני ניקוז" על פני המערך, מעין גושים נפרדים של תאים שמתנקזים כולם לאותו המקום. המשימה היתה לזהות את הגושים הללו ולסמן אותם באותיות ה-ABC בסדר עולה משמאל לימין.

לב הפתרון הוא בפונקציה שמזהה, בהינתן התנאים שהוגדרו, לאיזה תא מתנקז תא נתון. ניתן כמובן לפתור זאת בצורה גנרית באמצעות מיון-בתוך-מיון של גובה ושל כיוון, אך למעשה, עבור המקרה הספציפי, גם ארבע התניות if בסדר הנכון יספיקו. הפתרון שהוצע באתר לבעיה היה למצוא, עבור כל תא במערך ובאמצעות שימוש חוזר בפונקציה הנ"ל, את התא הסופי אליו הוא מתנקז ולאחר מכן להקצות לאותם אגני ניקוז סופיים אותיות משמאל לימין.
 

ברוכים הבאים... למלכודת!

הבעיה השלישית נראתה, במבט ראשון, כמו תרגיל פשוט ברקורסיה. בהינתן מחרוזת כלשהי של אותיות, על התוכנה לאתר כמה פעמים אפשר לקרוא בה את המחרוזת "welcome to code jam" ברווחים שאינם בהכרח סדירים. לדוגמה, במילה "נענע" אפשר לקרוא את המחרוזת "נע" שלוש פעמים – ה-נ' הראשונה עם ה-ע' הראשונה, ה-נ' הראשונה עם ה-ע' השניה וה-נ' השניה עם ה-ע' השניה. מתכנתים שתאוות הבצע דרבנה אותם לכתוב כמה שיותר מהר פשוט כתבו פונקציה רקורסיבית שעוברת על המחרוזת ומחפשת את האות הראשונה של מחרוזת המטרה. בכל פעם שזו נמצאה, הפונקציה קראה לעותק של עצמה עם המשך המחרוזת ועם האות הבאה של מחרוזת המטרה. אם אות המטרה האחרונה אותרה, מוסיפים 1 למונה. למען האמת, שיטה זו מזכירה קצת את הדרך לאיתור התאמות בגימטריה שהצגנו כאן בעבר.
 
44% נפלו במלכודת וגילו זאת מאוחר מדי
 44% נפלו במלכודת וגילו זאת מאוחר מדי 
 צילום: GettyImages 
 
פונקציה זו היא לא רק קלה לכתיבה, היא גם פותרת במהירות את קובץ הקלט הקטן – שנכתב, מן הסתם, מראש בצורה שתיפתר בקלות כדי למנוע חשד. הקובץ הגדול, לעומת זאת, כלל הפתעה לא נעימה. במחרוזת המטרה יש 20 אותיות (כולל רווחים). נניח שמתקבלת מחרוזת בת 100 אותיות, שכל חמש אותיות עוקבות בה הן זהות ויוצרות, ביחד, את מחרוזת המטרה ("wwwwweeeeelllll..."). מספר הפעמים שהפונקציה הרקורסיבית תצטרך לרוץ כדי לתת תשובה הוא חמש בחזקת 20 – ובעברית, 95,367,431,640,625. הרבה מעבר למה שאפשר להספיק בשמונה דקות. הסטטיסטיקה מוכיחה שכמעט חצי מהמשתתפים (44%, לעומת 16%-12% בבעיות האחרות) נפלו במלכודת – וכמובן, מרגע שהבינו את הטעות, מה שנשאר משמונה הדקות לא הספיק כדי לשכתב את התוכנה בהתאם.

בתור התחלה, רצוי לא להתייחס לכל אות בנפרד, אלא לחפש קבוצות של אותיות – לדוגמה, כל ה-w מתחילת המחרוזת ועד ה-e הראשון. מכפילים את מספר האותיות בכל קבוצה שמאותרת ומגיעים לאותה תוצאה במהירות מדהימה יחסית – בדוגמה שלנו, תוך 20 ריצות בלבד. כמובן שאפשר "לתפור" קלט שיהווה בעיה גם לאלגוריתם כזה ("wewewewewelclclclclc..."), ולכן מומלץ להשתמש בפתרון חכם עוד יותר, ללא כל רקורסיה, אותו אפשר לראות בדף הפתרון הרשמי.
 

איך להתכונן לתחרות

להכין לעצמכם מראש פונקציות וחלקי קוד
 להכין לעצמכם מראש פונקציות וחלקי קוד 
 צילום: GettyImages 
 
הבעיות נראו לכם קלות? אתם מוזמנים להתחיל להתכונן לתחרות הבאה. מעבר לאימון שניתן לבצע באתר התחרות (וכמובן בכל אתר אחר בו יש חידות למתכנתים), ישנם כמה טיפים שעשויים להועיל – אם לא במוקדמות, אז בוודאי בשלבים המאוחרים יותר. ראשית, חשוב להכין מראש את פרוצדורות הקלט והפלט, שמנתחות או מרכיבות את המחרוזות שבקבצים. אלו הן מטלות שכל מתכנת מנוסה יבצע תוך דקות, אך בשלבים המתקדמים כל דקה חשובה וחבל לבזבז זמן על דברים שכאלה. כמו כן, כדאי להכין פונקציות גנריות למשימות נפוצות כגון מיון של מערך, חלוקה של מחרוזת לפי "מפרידים" מוגדרים מראש (כגון פסיקים או רווחים), חיפוש בעץ בינארי וכן הלאה. גם כאן, אם אינכם יכולים לתכנת דברים כאלה מתוך שינה, אולי התחרות אינה בשבילכם – אבל בשביל מה לבזבז עליהם זמן ולהסתכן בשגיאת הקלדה מטופשת שתדפוק את כל העסק? עוד דבר שכדאי לעבוד עליו הוא הבנת הנקרא. הבעיות מוצגות באנגלית ברורה, ועם זאת כל מילה בהן חשובה. פספוס של משפט מסוים או רמז עלולים לחרב את התוכנה שלכם. בהצלחה!
 

ימים קשים לדלפי

נעבור לנושא אחר וכאוב. לאחרונה, במקביל ליציאתה לשוק של דלפי 2010 המגניבה ברמות, נעלם הקישור להורדה של טורבו דלפי 2006 החינמית. פניות נרגשות לחברה באימייל ובפורומים העלו, בינתיים, חרס: זו לא תקלה אלא החלטה. ברור, אם כך, שאין טעם להמשיך את פרויקט Byteroids במתכונתו הנוכחית. כעת נבדקת האפשרות להגר ל-Lazarus. כשפרויקט זה יסתיים (כך או אחרת) נעבור למשחק שקיבל את מירב הקולות בסקר שנערך לפני שבועיים - Lemmings.
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by