תרגילים

הגדרה

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

נמנה כמה תכונות נפוצות של פונקציות גיבוב:

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

מימוש בסיסי

בתרגיל זה נממש גרסה פשוטה של פונקציית גיבוב (hash function).
פונקציית הגיבוב שלנו תקבל מחרוזת ותחזיר תמיד פלט באורך זהה.

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

פונקציית הגיבוב שלנו תעבוד כך:

1. נאתחל משתנה עזר בשם hash כך שערכו יהיה 1.
2. עבור כל אות במחרוזת:
1. נחשב את ord(letter) ונכפיל במשתנה העזר hash.
2. נכפיל את הערך שקיבלנו במיקום של האות הבאה במחרוזת.
3. לתוצאה הזו נבצע מודולו 397,643, ונשמור על hash.
3. כדי שהפלט תמיד יהיה באורך זהה, נשתמש במודולו 100,297 על התוצאה (חשבו: איך מודולו גורם לזה לקרות?)

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

דוגמה:

myhash('aba')
62242

החישוב התבצע כך:

temp_hash = 1
temp_hash = (temp_hash * ord('a') * 1) % 397643 # temp_hash = (1 * 97 * 1) % 397643 = 97

שימו לב שכאן הכפלנו ב־1, כיוון שמיקום האות הוא 0 ואנו מכפילים באינדקס האות הבאה.

temp_hash = (temp_hash * ord('b') * 2) % 397643 # temp_hash = (97 * 98 * 2) % 397643 = 19012 temp_hash = (temp_hash * ord('a') * 3) % 397643 # temp_hash = (19012 * 97 * 3) % 397643 = 363133 return temp_hash % 100297 # temp_hash = 363133 % 100297 = 62242

ממשו את פונקציית הגיבוב.
כדי לבדוק את עצמכם ודאו שקיבלתם את הערכים הבאים עבור המחרוזות הבאות:

• myhash('python course')
  75273
• myhash('hashing is sababa')
  38166
• myhash('i calculate hashes for fun')
  68720

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

איקס־עיגול

נזכיר את החוקים של המשחק המוכר איקס־עיגול:

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

מימוש המשחק</p>

ייצוג הלוח

את הלוח נייצג באמצעות רשימה של רשימות.
כל רשימה תייצג שורה בלוח שלנו: הרשימה במיקום 0 תייצג את השורה הראשונה בלוח, הרשימה בשורה 1 את השורה השנייה וכך הלאה.
הרשימות המייצגות את השורות יהיו רשימות של תווים, כאשר בכל תא יהיה אחד מבין התווים האפשריים – 'O', 'X' או '-'

לדוגמה, כך נראה לוח ריק:

[['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']]

נוח לדמיין את הרשימה הזו כתובה במאונך:

[ ['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-'] ]

כעת נראה איך נראה הלוח כאשר יש 'X'־ים באלכסון:

[ ['X', '-', '-'], ['-', 'X', '-'], ['-', '-', 'X'] ]

וללא ההדפסה לאורך:

[['X', '-', '-'], ['-', 'X', '-'], ['-', '-', 'X']]

תחילה נממש פונקציה המקבלת את הלוח ובודקת אם יש מנצח כלשהו (X או O), ומחזירה את האות של המנצח ('X' או 'O') אם יש מנצח, או '' (מחרוזת ריקה) אחרת.

חִשבו אילו בדיקות נידרש לבצע כדי למצוא אם יש בלוח מצב של ניצחון. ממשו את הפונקציה check_board(board) כך שתשתמש בכמה שיותר פונקציות עזר.

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

• ניצחון באלכסון הראשי (שמאל למעלה–ימין למטה).
• ניצחון באלכסון המשני (ימין למעלה–שמאל למטה).
• ניצחון בכל אחד מהטורים.
• ניצחון בכל אחת מהשורות.
• לוח מלא ללא ניצחון.
• לוח לא מלא ללא ניצחון (במקומות לא מסומנים יופיע הסימן '-').

בסך הכול תצטרכו לכתוב 10 בדיקות. בכל בדיקה הפעילו את הפונקציה שלכם check_board(board) על לוח כפי שמתואר ובדקו אם הפלט שמוחזר תואם לפלט שציפיתם לקבל.

פונקציות לבדיקת תקינות קלט</p>

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

1 2

נמקם את האות המתאימה לשחקן, נניח X, בשורה 1 ובעמודה 2, כך:

[['-', '-', '-'], ['-', '-', 'X'], ['-', '-', '-']]

זכרו כי הספירה מתחילה מ־0, ולכן מדובר בשורה האמצעית ובעמודה הימנית.

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

• מספר השורה הוא בין 0 ל־2.
• מספר העמודה הוא בין 0 ל־2.
• המקום המבוקש לא תפוס על ידי אות כלשהי (כלומר יש בו '-').

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

רמז: השתמשו בלולאת while

לוח לדוגמה:

board = [['-', '-', '-'], ['-', 'O', 'X'], ['-', '-', '-']]

הזנה חוקית:

make_turn('X', board)

Player 'X' Please choose cell: 0 2 [['-', '-', 'X'], ['-', 'O', 'X'], ['-', '-', '-']]

הזנה לא חוקית:

Player 'X' Please choose cell: 5 -2 Invalid line chosen (5) Invalid column chosen (-2) [['-', '-', '-'], ['-', 'O', 'X'], ['-', '-', '-']]

Player 'X' Please choose cell: 1 2 Cell (1,2) is taken, use other. [['-', '-', '-'], ['-', 'O', 'X'], ['-', '-', '-']]

Player 'X' Please choose cell: 2 -2 Invalid column chosen (-2) [['-', '-', '-'], ['-', 'O', 'X'], ['-', '-', '-']]

Player 'X' Please choose cell: 1 1 Cell (1,1) is taken, use other. [['-', '-', '-'], ['-', 'O', 'X'], ['-', '-', '-']]

שימו לב שלאחר כל פעולה אנו מדפיסים את הלוח, בין אם הצליחה ובין אם לאו.

בונוס: ממשו פונקציה שמדפיסה את הלוח לאורך.

print_board(board)

[ ['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-'] ]

מימוש המשחק

כאמור המשחק ממשיך כל עוד אין מנצח ונותר מקום פנוי בלוח.
נשים לב כי מספר המהלכים החוקיים יכול להיות לכל היותר כגודל הלוח.
כלומר – אם לא הוכרז מנצח במהלך המשחק, המשחק ייגמר לאחר 9 מהלכים עבור לוח בגודל $3\times3$.
נספור כמה מהלכים חוקיים יש במשחק. עבור מספרי מהלך זוגיים (0, 2, 4, ...) ישחק השחקן O, ועבור מספרי מהלך אי־זוגיים ישחק השחקן X.
נתאר את מהלך המשחק בפסאודו־קוד:

1. אתחל את מונה המהלכים ל־0.
2. כל עוד אין מנצח וגם הלוח לא מלא:
   • אם מספר המהלך זוגי – בצע מהלך שחקן O.
   • אם מספר המהלך אי־זוגי – בצע מהלך שחקן X.
3. הגדל את מונה המהלכים ב־1.
4. אם יש ניצחון – הכרז על המנצח, אחרת הכרז תיקו.

ממשו את המשחק על פי הפונקציות שיצרתם ועל פי תיאור מהלך המשחק.

כעת שחקו עם בני משפחה וחברים ;)

בנק 2.0

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

מנגנון הסיסמאות ינוהל כך:

1. הבנק ינהל קובץ סיסמאות שייקרא bank_passwd.txt.
2. כאשר משתמש יפתח חשבון בנק, הוא יכניס את הסיסמה שהוא מעוניין שתשמש אותו בהתחברות הבאה.
3. נחשב את ה־hash של הסיסמה הזו באמצעות פונקציית ה־hash שכתבנו בתחילת מחברת זו.
4. הבנק ישמור את שם המשתמש ותוצאת ה־hash בקובץ הסיסמאות בצורה קבועה מראש.

כל סיסמה של משתמש תישמר בקובץ בצורה: username:62242,
כאשר username הוא שם המשתמש שנרשם בפתיחת החשבון, ו־62242 הוא תוצאת ה־hash עבור הסיסמה שבחר.

פתיחת חשבון בנק

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

דוגמאות

תוכן קובץ הסיסמאות (לצורך הדוגמה):

FreddieMercury:56443
BBKing:33471
DonaldDuck:17743

register_to_bank('FreddieMercury', 'ILoveQueen')
An account with name "FreddieMercury" already exists.
Account was not created.

register_to_bank('Simba', 'ILoveNala')
Account with name "Simba" was created and added to the bank.

תוכן קובץ הסיסמאות כעת:

FreddieMercury:56443
BBKing:19463
DonaldDuck:17743
Simba:6362

תרגיל

ממשו את פונקציית הרישום.

רמזים:

• קראו את המידע מהקובץ לתוך רשימה, זכרו שכל שורה היא מחרוזת וניתן להפעיל עליה פעולות של מחרוזות כדי לחלץ את שם המשתמש.
• כאשר פותחים קובץ במצב הוספה, ניתן להוסיף אליו נתונים מבלי למחוק את הקיימים. קראו על פונקציית open וחפשו כיצד עושים זאת.

מערכת הזדהות

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

מערכת ההזדהות תעבוד כך:

• הלקוח יזין שם משתמש וסיסמה.
  • אם המשתמש לא קיים, נדפיס Account not registered, ונסיים.
  • אם הלקוח קיים, אך הסיסמה שהזין שגויה – יש ללקוח עוד 2 נסיונות להזין סיסמה נכונה.
• למשתמש ינתנו 3 ניסיונות בסך הכול להכניס סיסמה נכונה.
  • אם הזין סיסמה שגויה בשלושתם – הרשומה שלו תימחק מקובץ הסיסמאות, ויהיה עליו להירשם מחדש בעתיד.
  • אחרת, הזיהוי הצליח.

מערכת ההזדהות הינה פונקציה המקבלת שם משתמש וסיסמה.
היא מחזירה True אם הזיהוי הצליח, ו־False אחרת.

דוגמאות

תוכן קובץ הסיסמאות (לצורך הדוגמה):

FreddieMercury:61875
BBKing:33471
DonaldDuck:17743
Simba:6362

authenticate('FreddieMercury', 'ILoveQueen')
Wrong password (1/3). # myhash('ILoveQueen') = 99597 != 61875 (in password file)

authenticate('FreddieMercury', 'LetItBe')
Wrong password (2/3). # myhash('LetItBe') = 58060 != 61875 (in password file)

authenticate('FreddieMercury', 'HeyJude')
Wrong password (3/3). 'FreddieMercury' was removed. # myhash('HeyJude') = 8309 != 61875 (in password file)

authenticate('FreddieMercury', 'IHatePasswords!')
Account not registered. # FreddieMercury was removed in the previous example

authenticate('Simba', 'ILoveNala')
Welcome 'Simba'. # myhash('ILoveNala') = 6362 == 6362 (in password file)

תוכן קובץ הסיסמאות כעת:

BBKing:19463
DonaldDuck:17743
Simba:6362

תרגול

ממשו את מערכת ההזדהות.