והפעם נדבר על שאלת 420. LeetCode - Strong Password Checker הבאה:
סיסמה חזקה, נחשבת לסיסמה חזקה כאשר היא עונה על התנאים הבאים:
1 - אורך הסיסמה הוא בין 6 לבין 20 תווים, לא יותר ולא פחות.
2 - הסיסמה חייבת להכיל לפחות: אות 1 קטנה (abc-z) + אות 1 גדולה (ABC-Z) + מספר 1 כלשהו (123-0).
3 - אסור שהסיסמה תכיל 3 תווים רצופים כלשהם. לדוגמה אסור שהסיסמה תהיה 123AAA4 כי האות A חוזרת על עצמה ברציפות 3 פעמים. כן מותר שהסיסמה תהיה 123Aaa4, או 12A3AA4 כי שום אות לא חוזרת על עצמה ברציפות 3 פעמים.
כל סיסמה שאינה סיסמה חזקה, ניתן לבצע עליה 3 פעולות כדי להפוך אותה לחזקה. ניתן להוסיף לה אותיות, ניתן להסיר ממנה אותיות, וניתן להחליף בה אותיות. דהיינו, ניתן לבצע פעולת הוספה / מחיקה / החלפה.
עכשיו השאלה היא כזאת, נותנים לנו סיסמה כלשהי, ואנחנו צריכים לומר, מהו המספר המינימאלי ההכרחי של פעולות שחייבים לעשות, כדי להפוך את הסיסמה לחזקה.
לדוגמה, אם הסיסמה היא A12345, אז אנחנו צריכים לעשות לפחות פעולה 1 שתגרום לכך שהסיסמה תכיל גם אות קטנה כלשהי. אם הסיסמה היא נניח 1Aa2, עלינו לבצע 2 פעולות כדי לגרום לסיסמה להיות באורך של 6 תווים.
נתון נוסף שנותנים לנו הוא, שסיסמה יכולה להיות בין אורך של 1 לאורך של 50. וגם סיסמה יכולה יכולה להכיל נקודה "." או סימן קריאה "!" כתווים חוקיים.
אז שוב השאלה היא: אנחנו מקבלים סיסמה, ועלינו לומר מהו מינימום הפעולות ההכרחי, כדי לגרום לסיסמה להיות נחשבת לסיסמה חזקה, ע"פ ההגדרות שהגדרנו לעיל. אם אין צורך לעשות פעולות כלשהן, אז נחזיר 0.
אחדד ואומר, כי בעיקרון השאלה מנוסחת בצורה פחות ברורה ממה שהצגתי לעיל, אבל כאן העדפתי לחסוך את המאמץ של הבנת השאלה ולנסות להתמקד במאמץ של מציאת התשובה.
אז איך ניגשים לפתור את זה?
אז כמובן שעלינו לנסות לחלק את התהליך לחלקים כמה שיותר קטנים. ועלינו לנסות לשחק קצת עם כל מיני אפשרויות בצורה "ידנית", לפני שאנחנו מנסים למצוא את החוקיות של התהליך ולבנות ממנו נוסחה.
דהיינו, קודם כל ננסה להריץ "ידנית" כל מיני סימולציות, של המקרים הפשוטים ביותר, אחר כך של מקרים יותר מורכבים. אחר כך ננסה למצוא חוקיות כלשהי ובהתאם לכך, ננסה לבנות נוסחה כלשהי לפתור את השאלה.
אז בשלב הראשון, ננסה לחלק לחלקים קטנים. נתנו לנו 3 חוקים שמגדירים מהי סיסמה חזקה. עלינו לנסות להבין האם אנחנו יודעים לפתור את השאלה, בהינתן רק חוק 1. דהיינו, במקום לנסות להבין איך לפתור את השאלה כשיש 3 חוקים, נשאל את עצמנו את השאלה הבאה:
נניח שנותנים לנו סיסמה, ויש לנו רק חוק 1 שאומר, שהסיסמה צריכה להיות בין 6 לבין 20 תווים. האם היינו יודעים כמה מינימום פעולות אנחנו צריכים לבצע כדי להפוך את הסיסמה לתקינה? וכאן אפשרי להניח שרוב האנשים יגידו שכן. כי אם אורך הסיסמה קטן מ 6 תווים, אז צריך להוסיף תווים. ואם אורך הסיסמה גדול מ 20 תווים, אז צריכים למחוק תווים.
אבל מאחר שחשוב לנו ללמוד לחלק לחלקים, אז אומר בצורה ברורה, כי מצד האמת, אפשרי לנסח את השאלה בצורה עוד יותר פשוטה. דהיינו: התנאי של אורך סיסמה חייב להיות בין 6 לבין 20, הוא תנאי מורכב ולא תנאי פשוט. התנאי היותר פשוט, הוא, אורך הסיסמה חייב להיות לפחות 6 תווים בלי מגבלה על אורך מקסימאלי.
ולכן המקרה היותר פשוט שעלינו לראות שאנחנו יודעים למצוא לו פתרון, הוא, מה קורה אם יש רק חוק 1 שאומר, שסיסמה צריכה להיות לפחות 6 תווים. האם היינו יודעים לפתור את המקרה הזה?
וגם כאן אפשרי להתחיל מצורת שאלה עוד יותר פשוטה: נניח סיסמה חייבת להכיל לפחות תו 1 בלבד. האם היינו יודעים איך לפתור שאלה כזו? זה המקרה הפשוט ביותר שעלינו לנסות להתחיל לפתור ממנו.
ומאחר שמטרת המאמר היא לא ללמד את הפתרון של השאלה, אלא כן ללמד איך אפשרי למצוא את הפתרון לשאלה. ומאחר שכדי למצוא את הפתרון לשאלה, צריכים ללמוד לחלק לחלקים הכי קטנים שיש, לכן אני אציג כאן רצף של שאלות, מהקל אל הכבד, איך אמורים לגשת לנתח את השאלה הזאת:
האם אני יודע לפתור את השאלה במקרה שיש רק חוק 1 שאומר ש:
הסיסמה צריכה להיות באורך של לפחות תו 1
הסיסמה צריכה להיות באורך של לפחות 2 תווים
הסיסמה צריכה להיות באורך של לפחות 3 תווים
הסיסמה צריכה להיות באורך של לפחות X תווים
אם כן, אז האם אני יודע לפתור את השאלה במידה ו:
הסיסמה צריכה להיות באורך של לפחות 6 תווים
ועד כאן אני מניח שהתשובה ברורה, והיא שעלינו לבדוק את אורך הסיסמה (=N) ואם אורך הסיסמה קטן מ X (אורך מינימאלי) תווים, הרי שזה אומר שעלינו להוסיף X-N תווים, כדי שהסיסמה תהיה תקינה. לדוגמה אם אורך הסיסמה הוא 3 דהיינו, אורך שקטן מ X=6, אז 6-3 = 3 ולכן נצטרך להוסיף 3 תווים כדי לגרום לסיסמה להיות תקינה. דהיינו, נצטרך לעשות 3 פעולות של הוספה כדי לגרום לסיסמה להיות תקינה כסיסמה חזקה.
ועכשיו ננסה להבין, האם אני יודע למצוא תשובה לשאלה, אם יש רק חוק 1 שאומר ש:
הסיסמה צריכה להיות באורך של לא יותר מ תו 1
הסיסמה צריכה להיות באורך של לא יותר מ 2 תווים
הסיסמה צריכה להיות באורך של לא יותר מ 3 תווים
הסיסמה צריכה להיות באורך של לא יותר מ X תווים
אם כן, אז האם אני יודע לפתור את השאלה במידה ו:
הסיסמה צריכה להיות באורך של לא יותר מ 20 תווים
וגם עד כאן אני מניח שהתשובה ברורה, והיא שעלינו לבדוק את אורך הסיסמה (=N) ואם אורך הסיסמה גדול מ X (אורך מקסימאלי) תווים, הרי שזה אומר שעלינו למחוק N-X תווים, כדי שהסיסמה תהיה תקינה. לדוגמה אם אורך הסיסמה הוא 33 דהיינו, אורך שגדול מ X=20, אז 33-20 = 13 ולכן נצטרך למחוק 13 תווים כדי לגרום לסיסמה להיות תקינה. דהיינו, נצטרך לעשות 13 פעולות של מחיקה כדי לגרום לסיסמה להיות תקינה כסיסמה חזקה.
ועכשיו נשאל, האם אני יודע לפתור את השאלה במידה ויש חוק 1 שאומר, שהסיסמה אסור לה להיות פחות מ X (אורך מינימאלי) תווים ולא יותר מ Y (אורך מקסימאלי) תווים?
וגם כאן אפשרי להניח התשובה היא שכן, אם יש פחות מ X(אורך מינימאלי), אז צריך להוסיף תווים. ואם יש יותר מ Y (אורך מקסימאלי) תווים, אז צריכים למחוק אותיות, כדי לגרום לסיסמה להיות תקינה.
ועד כאן בעצם היתה דוגמה לאיך לחלק לחלקים קטנים.
עכשיו נעבור לחוק מספר 2 שאומר שהסיסמה צריכה להכיל לפחות אות 1 קטנה + אות 1 גדולה + מספר 1. וננסה להבין איך אפשרי לחלק את זה לחלקים קטנים.
אז נשאל, האם אני יודע לפתור את השאלה במידה ויש רק חוק 1 שאומר שהסיסמה צריכה להכיל אות 1 קטנה. בלי להתייחס לאות גדולה או מספר.
ונחלק לחלק יותר קטן, איך נפתור את השאלה, במידה ויש חוק שאומר שהסיסמה צריכה להכיל את האות a הקטנה.
דהיינו, לא נשאל על חוק שאומר שהסיסמה צריכה להכיל אות אחת קטנה כלשהי, אלא כן נשאל על מקרה יותר פשוט, שהסיסמה צריכה להכיל אות אחת ספציפית, כי זה מקרה שיותר קל לפתור.
כי יותר קל לדעת אם הסיסמה מכילה אות 1 ספציפית, מאשר לדעת אם הסיסמה מכילה אות 1 קטנה כלשהי. וגם יותר קל להבין שצריכים להוסיף אות 1 ספציפית אם היא חסרה, מאשר לחשוב איזו אות קטנה עלינו להוסיף, במידה ואין שום אות קטנה כלשהי.
ולכן נשאל מה אם:
הסיסמה צריכה להכיל את האות a
הסיסמה צריכה להכיל את האות b
הסיסמה צריכה להכיל אות ספציפית כלשהי
ואם יש לנו תשובה, אז נשאל, מה אם:
הסיסמה צריכה להכיל אות אחת קטנה כלשהי?
והתשובה לכך היא, שעלינו לבדוק האם הסיסמה מכילה אות 1 קטנה כלשהי. ואם לא, אז עלינו להוסיף אות 1 קטנה כלשהי, או עלינו להחליף אות אחת קיימת, לאות 1 קטנה כלשהי.
דהיינו, במקרה כזה לדוגמה A123456, עלינו או להוסיף אות אחת לדוגמה a קטנה aA123456 או להחליף לאות 1 קטנה לדוגמה כך Aa23456 ובשני המקרים הסיסמה תהיה תקינה.
דהיינו, אם חסרה לנו אות 1 קטנה, אז עלינו לבצע פעולה 1 של הוספה של אות קטנה או פעולה 1 של החלפה של אות כלשהי, לאות קטנה, כדי שהסיסמה תהיה חוקית.
ומה אם הסיסמה צריכה להכיל אות 1 גדולה? ומה אם הסיסמה צריכה להכיל ספרה אחת כלשהי? אז אם יש לנו תשובה גם לזה, אז נשאל מה אם:
הסיסמה צריכה להכיל את האות a הקטנה ואת האות A הגדולה?
ואם הסיסמה צריכה להכיל אות 1 קטנה כלשהי ואות אחת גדולה כלשהי?
ואם הסיסמה צריכה להכיל אות אחת קטנה כלשהי אות אחת גדולה כלשהי וספרה אחת כלשהי?
וכאן דילגתי קצת על חלקים ועל שאלות יותר קטנות, אבל כמובן שהיה אפשרי לחלק את זה למקרים יותר קטנים.
אז מי שיתבונן יראה, כי חוק מספר 2 שאומר שהסיסמה צריכה להכיל אות 1 קטנה גדולה וספרה, בעצם אומר ש:
עלינו לבדוק האם חסרה אות קטנה / גדולה / מספר, ואז עלינו להוסיף או להחליף אותיות בהתאם לצורך שלנו. לדוגמה 123456 יכול להפוך להיות 123456Aa או יכול להיות 12345Aa או יכול להיות 1234Aa וכולי.
ועכשיו נעבור לחוק מספר 3 שאומר, שסיסמה לא יכולה להכיל 3 תווים או יותר רצופים. ונשאל, האם נדע לפתור מקרה לדוגמה שאסור שיהיה תו ספציפי רצוף, לדוגמה AAA?
והתשובה היא, שאם לדוגמה יש לנו AAA עלינו או למחוק A אחד וישאר רק AA או להחליף תו אחד לדוגמה A1A או 1AA או AA1 ועכשיו הסיסמה תהיה תקינה. או להוסיף תו אחד לדוגמה A1AA או AA1A, שגם כך הסיסמה הופכת להיות תקינה.
ואם יש לנו 4 תווים רצופים, לדוגמה AAAA עלינו או למחוק 2 תווים ונקבל AA. או להוסיף תו אחד לדוגמה AA1AA או להחליף תו אחד לדוגמה A1AA או AA1A ואז הסיסמה תהיה תקינה.
ואם יש לנו 5 תווים רצופים, לדוגמה AAAAA עלינו או למחוק 3 תווים, ונקבל AA או להוסיף 2 תווים לדוגמה AA1AA2A או להחליף תו אחד דהיינו, AA1AA וככה הסיסמה תהיה תקינה.
ואם יש לנו 6 תווים רצופים, לדוגמה AAAAAA אז עלינו או למחוק 4 או להוסיף 2 ל AA1AA2AA או להחליף 2 כך AA2AA1 וכיו"ב.
ואם יש לנו 7 לדוגמה AAAAAAA אז עלינו או למחוק 5 או להוסיף 3 כך: AA2AA3AA1A או להחליף 2 כך: AA1AA2A.
ואם יש לנו 8 לדוגמה AAAAAAAA אז עלינו או למחוק 6 או להוסיף 3 כך: AA2AA3AA1AA או להחליף 2 כך: AA1AA2AA
וכך עלינו להמשיך ולבדוק ידנית עוד מקרים, מבחינתי עד 20 תווים רצופים, שזה המספר המקסימאלי של התווים שהסיסמה יכולה להכיל.
ועכשיו עלינו לבצע עוד סוג של בדיקות ידניות, ולחלק לחלקים בצורה הבאה:
נניח שהיתה רק פעולה אחת אפשרית, פעולה של מחיקה בלבד. האם היינו יודעים לפתור את כל המצבים? האם היינו יכולים לפתור פעולות של סיסמה קצרה? תשובה: לא. האם היינו יודעים לפתור מצב של סיסמה ארוכה: כן. האם היינו יודעים לפתור מצב של תווים חסרים? תשובה: לא. האם היינו יודעים לפתור מצב של תווים רצופים? תשובה: כן.
ואם היתה רק פעולה אחת אפשרית של הוספה? אז היינו יכולים לפתור מצב של סיסמה קצרה, לא היינו יכולים לפתור מצב של סיסמה ארוכה מידי. כן היינו יכולים לפתור מצב של תווים חסרים או רצופים.
ואם היתה רק פעולה אחת אפשרית של החלפה? אז לא היינו יכולים לפתור בעיה של אורך. אבל כן היינו יכולים לפתור בעיה של תווים חסרים או רצופים.
ואם היו רק 2 פעולות של מחיקה והוספה? אז היינו יכולים לפתור את כל המצבים. ואם היו רק 2 פעולות של מחיקה והחלפה? לא היינו יכולים לפתור מצב של סיסמה קצרה מידי.
או במילים אחרות ננסה לבדוק את כל החוקים ואת כל המצבים, במקרה שיש רק פעולה אחת אפשרית של הוספה או מחיקה או החלפה. ובמקרה שיש רק 2 פעולות אפשריות, של הוספה + מחיקה או הוספה + החלפה או מחיקה + החלפה בלבד. וכמובן גם במקרה שיש 3 פעולות אפשריות, של מחיקה או הוספה או החלפה.
אז מה בעצם עשינו עד כה?
עד כה שיחקנו ידנית עם כל מיני מקרים שונים, וניסינו לחלק את התהליך לחלקים ולמקרים פשוטים. מה לא ניסינו לעשות, לא ניסינו למצוא חוקיות, לא ניסינו למצוא נוסחה.
או במילים אחרות, קודם כל צריכים לנסות לראות אם יודעים לפתור את השאלה, במקרה הפשוט ביותר, בלי שום חוקיות, בלי שום נוסחה, בלי שום מורכבות.
רק אחרי שאנחנו מסוגלים לפתור את השאלה ידנית, בלי חוקיות, בלי נוסחה בלי כלום, במקרה הכי פשוט. עכשיו ננסה לפתור את השאלה בצורה קצת יותר מורכבת.
אז האם אנחנו נדע לפתור את השאלה במידה ויש לנו 2 חוקים שהם:
1 - האורך חייב להיות בין X לבין Y
2 - הסיסמה חייבת להכיל אות קטנה / גדולה / מספר
במידה ואלו 2 החוקים שנותנים לנו, האם נדע לפתור את השאלה?
ומה אם היו לנו את 2 החוקים הבאים:
1 - האורך חייב להיות בין X לבין Y
2 - אסור שתו יחזור על עצמו 3 פעמים או יותר
ומה אם היו לנו את 2 החוקים הבאים:
1 - הסיסמה חייבת להכיל אות קטנה / גדולה / מספר
2 - אסור שתו יחזור על עצמו 3 פעמים או יותר
ומה אם היו לנו את 3 החוקים המלאים:
1 - האורך חייב להיות בין X לבין Y
2 - הסיסמה חייבת להכיל אות קטנה / גדולה / מספר
3 - אסור שתו יחזור על עצמו 3 פעמים או יותר
עכשיו כמובן שהעלילה מתחילה להסתבך... איך ניגשים לזה? איך פותרים את זה?
כמובן, ש... איך פותרים את זה ידנית. בלי נוסחאות ובלי סיבוכים, ננסה קודם כל להבין איך פותרים את זה ידנית.
האם קודם מתחילים מחוק מספר 1 או 2 או 3? מה קדם למה?
אז לשם כך ננסה שוב להתחיל הכל מהתחלה, וננסה להבין האם בכל האפשרויות יש משהו שהוא בטוח נכון.
אז נחזור לחוק של האורך, אם נתבונן עליו נראה שיש בו משהו שהוא בטוח נכון.
אם האורך צריך להיות 6, אז בטוח נכון שאם יש פחות מ 6 תווים, אז בטוח נכון שעלינו לבצע 6-N פעולות של הוספה. לדוגמה, אם יש לנו 3 תווים, אז בוודאות של מאה אחוז, שעלינו לבצע 3 פעולות של הוספה כדי שהסיסמה תהיה באורך של 6.
דהיינו, יש לנו וודאות של מאה אחוז
1 - גם לגבי כמות הפעולות שאנחנו צריכים לבצע, כי אנחנו בוודאות צריכים לבצע 3 פעולות.
2 - וגם יש לנו וודאות של מאה אחוז, לגבי סוג הפעולות שאנחנו צריכים לבצע, כי אנחנו צריכים לבצע בוודאות פעולות של הוספה ולא של מחיקה או של החלפה.
ואם הסיסמה ארוכה מ 20 לדוגמה היא באורך של 5, אז יש לנו וודאות של מאה אחוז שאנחנו צריכים לבצע 5 פעולות מסוג פעולה של מחיקה.
דהיינו, בדיקת החוק של האורך, נותן לנו וודאות גם לגבי כמות הפעולות שצריכים לבצע וגם לגבי סוג הפעולות שצריכים לבצע, כדי להתאים את הסיסמה לחוק של האורך.
עכשיו נבדוק את החוק של האותיות הנדרשות, אם נסתכל נראה כי נניח שאנחנו צריכים שתהיה אות אחת קטנה, הרי שאם אין אות אחת קטנה, הרי שיש לנו וודאות של מאה אחוז לגבי כמות הפעולות שעלינו לבצע, דהיינו, שעלינו לבצע פעולה 1 כלשהי. אבל יש לנו ספק לגבי סוג הפעולה שעלינו לבצע, כי אולי נצטרך לעשות הוספה של אות 1 או החלפה של אות 1.
ואם חסר לנו אות גדולה + מספר, הרי שבוודאות עלינו לבצע 2 פעולות. אבל הן יכולות להיות או 2 פעולות הוספה או 2 פעולות החלפה או 1 פעולה הוספה + 1 פעולת החלפה וכולי.
במילים אחרות, החוק השני של תווים הכרחיים, נותן לנו וודאות לגבי כמות פעולות שצריכים לבצע, אבל משאיר לנו ספק לגבי סוג הפעולות שצריכים לבצע.
ועכשיו נעבור לחוק 3 שאסור שיהיו 3 תווים רצופים. ואם נחקור אותו נראה, כי הוא משאיר לנו ספק, גם לגבי כמות הפעולות וגם לגבי סוג הפעולות.
לדוגמה במקרה של 8 תווים רצופים לדוגמה כך: AAAAAAAA, אז הרי שעלינו
או לבצע 6 פעולות של מחיקה
או לבצע 3 פעולות של הוספה
או לבצע 2 פעולות של החלפה
דהיינו, יש לנו וודאות כלשהי, אבל הכי פחות וודאות. גם לגבי כמות הפעולות וגם לגבי סוג הפעולות.
במילים אחרות אנחנו מבינים, שהחוק של האורך התקין, מספק לנו הכי הרבה וודאות. אחר כך יש לנו את החוק של התווים ההכרחיים, אחר כך החוק של האותיות הרצופות, שמספק לנו הכי פחות וודאות והכי הרבה ספקות ואפשרויות.
אז מה בעצם זה אומר לנו?
אז זה בעצם אומר לנו שכאשר אנחנו מקבלים שאלה כזאת, עלינו כמובן לנסות להתחיל מהחלק הכי קטן שבטוח נכון. דהיינו, כאשר נקבל סיסמה ונצטרך לבדוק אותה אל מול 3 החוקים הנ"ל, קודם כל נעדיף לבדוק את החוק של האורך, שהוא מספק לנו וודאות של מאה אחוז, גם לגבי כמות הפעולות וגם לגבי סוג הפעולות. אחר כך נבדוק את החוק של התווים ההכרחיים, שמספק לנו וודאות לגבי כמות ופחות לגבי סוג. ורק אחר כך נבדוק את החוק של התווים הרצופים, שמספק לנו הכי פחות וודאות לגבי כמות או סוג הפעולות שעלינו לבצע.
מהי החוקיות של הפעולות עצמן? מה היחס ביניהן?
ואם נעמיק עוד קצת לגבי הפעולות האפשריות לתקן סיסמה, וננסה לשאול את עצמנו, אם יכולנו לבחור פעולה אחת או 2 פעולות בלבד, מה היינו בוחרים? האם יש פעולה שעדיפה על פעולות אחרות? אם נחקור את הנושא נראה ש:
בשביל סיסמה שתהיה באורך לפחות 6, חייבים פעולה של הוספה ואך ורק פעולה של הוספה.
בשביל סיסמה שתהיה לא יותר מאורך של 20, חייבים פעולה של מחיקה ואך ורק פעולה של מחיקה.
בשביל שהסיסמה תהיה עם תווים הכרחיים, צריך פעולה של הוספה או של החלפה. כאשר אין יתרון לפעולה של החלפה או של הוספה. אם נבצע הוספה או החלפה של תווים, הרי שנבצע מספר זהה של פעולות. דהיינו, אם נבחר לתקן את הסיסמה באמצעות הוספה או החלפה, נבצע כמות זהה של פעולות.
דהיינו, עד כה אנחנו רואים שבמובן מסוים, עדיף לנו שתהיה לנו אפשרות של הוספה, כי היא פותרת מצבים של סיסמה קצרה ושל תווים חסרים. כי מחיקה, לא פותרת את התווים החסרים.
ואם נחקור את החוק של התווים הרצופים, אז נראה שאפשרי לתקן בהתאם לחוק באמצעות מחיקה או הוספה או החלפה. כאשר מחיקה היא בדרך כלל דורשת הכי הרבה פעולות. אחר כך פעולה של הוספה שדורשת פחות פעולות. ואחר כך פעולה של החלפה, שדורשת הכי פחות פעולות.
דהיינו, תווים רצופים, בברירת המחדל, נעדיף לפתור אותו עם פעולת החלפה, שדורשת הכי פחות פעולות.
או במילים אחרות, אם נוכל לבחור לפתור בעיה של חוק 2 של תווים חסרים, באמצעות הוספה או החלפה, אז עלינו להעדיף את הפעולה של ההחלפה. כי היא יודעת לתקן גם ביחס לחוק 3, שהחלפה פותרת בו את הבעיה בדרך הקצרה ביותר.
דהיינו, החוק של התווים הרצופים, הכי טוב לפתור אותו באמצעות החלפה. כי זה דורש הכי פחות פעולות. ולכן ננסה בברירת המחדל בלפתור את חוק 2 של תווים חסרים, ננסה להעדיף פעולה של החלפה על פני פעולה של הוספה. כי פעולה של החלפה, היא יותר יעילה עבור חוק 3 מאשר פעולה של הוספה או פעולה של מחיקה.
אז לכאורה פתרנו את השאלה. כי בעצם עלינו קודם כל לבדוק את האורך של הסיסמה. אחר כך לבדוק תווים חסרים ואחר כך לבדוק תווים רצופים. לדוגמה:
נניח שהסיסמה היא AAA אז:
מהחוק של האורך אנחנו יודעים בוודאות שאנחנו צריכים לבצע 3 פעולות של הוספה.
מהחוק של התווים החסרים, אנחנו יודעים בוודאות שאנחנו צריכים לבצע 2 פעולות של הוספה או של החלפה.
ומהחוק של התווים הרצופים, אנחנו יודעים בוודאות שאנחנו צריכים לבצע פעולה 1 של החלפה / הסרה / מחיקה.
ומאחר שבטוח נכון שאנחנו צריכים לבצע 3 פעולות של הוספה, בגלל חוק האורך, הרי שבעצם ב 3 פעולות של הוספה, נוכל גם להתאים את הסיסמה לחוק של התווים החסרים וגם של התווים הרצופים. לדוגמה כך: AaAA12.
דהיינו, ב 3 פעולות של הוספה, גם תיקנו את הסיסמה לאורך של 6 גם הוספנו אות קטנה ומספר, וגם ביטלנו את ה 3 אותיות הרצופות.
במילים אחרות, מצב של AAA נפתור אותו ב 3 פעולות.
ואם יש לנו סיסמה באורך של 25 אותיות, לדוגמה ABABABAAAAABABABABAB12345.
אז בוודאות שאנחנו צריכים לעשות 5 פעולות מחיקה בגלל האורך.
+ פעולת החלפה או הוספה 1 של אות קטנה.
+ בגלל שיש בתוך הסיסמה 5 אותיות רצופות של AAAAA אז אנחנו צריכים לעשות או 5 פעולות מחיקה או 2 פעולות הוספה או 1 פעולת החלפה.
ולכן, נעשה 5 פעולות מחיקה להתאים את האורך
+ פעולה 1 של החלפה, כדי להוסיף אות קטנה ולא פעולה של הוספה, כדי לא לפגוע באורך
+ ב 5 הפעולות מחיקה הקודמות, נוכל למחוק את כל רצף האותיות הנ"ל.
דהיינו, סה"כ נצטרך 6 פעולות בלבד. 5 של מחיקה + 1 של החלפה.
אז מהי מהות הפתרון עד כה?
במילים אחרות, ניקח את הפעולות שהן בטוח נכונות, דהיינו, שבטוח צריך לבצע אותן ובאמצעותן נפתור את כל שאר הפעולות שאולי צריך לבצע.
דהיינו, אם חובה לבצע פעולות מחיקה בגלל האורך, נוכל באמצעותן למחוק אותיות רצופות.
אם חובה לבצע פעולות הוספה בגלל האורך, נוכל באמצעות פעולות ההוספה לתקן בהתאם לתווים חסרים או רצופים.
כאשר אם ואחרי שהאורך תקין, תמיד נעדיף לבצע רק פעולות של החלפה.
כי מצד החוק של תווים חסרים, פעולת החלפה יעילה בוודאות כמו פעולת הוספה. והחלפה, לא יכולה להרוס את האורך של הסיסמה. ומצד החוק של תווים רצופים, בכל מקרה עדיף החלפה, כי זאת הפעולה הכי יעילה.
ולכן קודם כל נבדוק את האורך, ואז נשתמש בפעולת ההוספה כדי לפתור את 2 החוקים הנוספים של להוסיף אותיות חסרות או כדי לנטרל אותיות רצופות.
ונשתמש בפעולת המחיקה, כדי לתקן את האורך וגם כדי לפתור אותיות רצופות. ומכאן ואילך, נספור רק פעולות של החלפה בלבד. כדי שלא בטעות נשבש את האורך של הסיסמה וגם כי החלפה יותר יעילה עבור התיקון של אותיות...
A password is considered strong if the below conditions are all met:
It has at least 6 characters and at most 20 characters.
It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
It does not contain three repeating characters in a row (i.e: "Baaabb0" is weak, but "Baaba0" is strong).
Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
In one step, you can:
Insert one character to password
Delete one character from password, or
Replace one character of password with another character.
Example 1:
Input: password = "a"
Output: 5
Example 2:
Input: password = "aA1"
Output: 3
Example 3:
Input: password = "1337C0d3"
Output: 0
Constraints:
1 <= password.length <= 50
password consists of letters, digits, dot '. ' or exclamation mark '! '.
אז קודם כל נסביר את השאלה שהולכת כך:It has at least 6 characters and at most 20 characters.
It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
It does not contain three repeating characters in a row (i.e: "Baaabb0" is weak, but "Baaba0" is strong).
Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
In one step, you can:
Insert one character to password
Delete one character from password, or
Replace one character of password with another character.
Example 1:
Input: password = "a"
Output: 5
Example 2:
Input: password = "aA1"
Output: 3
Example 3:
Input: password = "1337C0d3"
Output: 0
Constraints:
1 <= password.length <= 50
password consists of letters, digits, dot '. ' or exclamation mark '! '.
סיסמה חזקה, נחשבת לסיסמה חזקה כאשר היא עונה על התנאים הבאים:
1 - אורך הסיסמה הוא בין 6 לבין 20 תווים, לא יותר ולא פחות.
2 - הסיסמה חייבת להכיל לפחות: אות 1 קטנה (abc-z) + אות 1 גדולה (ABC-Z) + מספר 1 כלשהו (123-0).
3 - אסור שהסיסמה תכיל 3 תווים רצופים כלשהם. לדוגמה אסור שהסיסמה תהיה 123AAA4 כי האות A חוזרת על עצמה ברציפות 3 פעמים. כן מותר שהסיסמה תהיה 123Aaa4, או 12A3AA4 כי שום אות לא חוזרת על עצמה ברציפות 3 פעמים.
כל סיסמה שאינה סיסמה חזקה, ניתן לבצע עליה 3 פעולות כדי להפוך אותה לחזקה. ניתן להוסיף לה אותיות, ניתן להסיר ממנה אותיות, וניתן להחליף בה אותיות. דהיינו, ניתן לבצע פעולת הוספה / מחיקה / החלפה.
עכשיו השאלה היא כזאת, נותנים לנו סיסמה כלשהי, ואנחנו צריכים לומר, מהו המספר המינימאלי ההכרחי של פעולות שחייבים לעשות, כדי להפוך את הסיסמה לחזקה.
לדוגמה, אם הסיסמה היא A12345, אז אנחנו צריכים לעשות לפחות פעולה 1 שתגרום לכך שהסיסמה תכיל גם אות קטנה כלשהי. אם הסיסמה היא נניח 1Aa2, עלינו לבצע 2 פעולות כדי לגרום לסיסמה להיות באורך של 6 תווים.
נתון נוסף שנותנים לנו הוא, שסיסמה יכולה להיות בין אורך של 1 לאורך של 50. וגם סיסמה יכולה יכולה להכיל נקודה "." או סימן קריאה "!" כתווים חוקיים.
אז שוב השאלה היא: אנחנו מקבלים סיסמה, ועלינו לומר מהו מינימום הפעולות ההכרחי, כדי לגרום לסיסמה להיות נחשבת לסיסמה חזקה, ע"פ ההגדרות שהגדרנו לעיל. אם אין צורך לעשות פעולות כלשהן, אז נחזיר 0.
אחדד ואומר, כי בעיקרון השאלה מנוסחת בצורה פחות ברורה ממה שהצגתי לעיל, אבל כאן העדפתי לחסוך את המאמץ של הבנת השאלה ולנסות להתמקד במאמץ של מציאת התשובה.
אז איך ניגשים לפתור את זה?
אז כמובן שעלינו לנסות לחלק את התהליך לחלקים כמה שיותר קטנים. ועלינו לנסות לשחק קצת עם כל מיני אפשרויות בצורה "ידנית", לפני שאנחנו מנסים למצוא את החוקיות של התהליך ולבנות ממנו נוסחה.
דהיינו, קודם כל ננסה להריץ "ידנית" כל מיני סימולציות, של המקרים הפשוטים ביותר, אחר כך של מקרים יותר מורכבים. אחר כך ננסה למצוא חוקיות כלשהי ובהתאם לכך, ננסה לבנות נוסחה כלשהי לפתור את השאלה.
אז בשלב הראשון, ננסה לחלק לחלקים קטנים. נתנו לנו 3 חוקים שמגדירים מהי סיסמה חזקה. עלינו לנסות להבין האם אנחנו יודעים לפתור את השאלה, בהינתן רק חוק 1. דהיינו, במקום לנסות להבין איך לפתור את השאלה כשיש 3 חוקים, נשאל את עצמנו את השאלה הבאה:
נניח שנותנים לנו סיסמה, ויש לנו רק חוק 1 שאומר, שהסיסמה צריכה להיות בין 6 לבין 20 תווים. האם היינו יודעים כמה מינימום פעולות אנחנו צריכים לבצע כדי להפוך את הסיסמה לתקינה? וכאן אפשרי להניח שרוב האנשים יגידו שכן. כי אם אורך הסיסמה קטן מ 6 תווים, אז צריך להוסיף תווים. ואם אורך הסיסמה גדול מ 20 תווים, אז צריכים למחוק תווים.
אבל מאחר שחשוב לנו ללמוד לחלק לחלקים, אז אומר בצורה ברורה, כי מצד האמת, אפשרי לנסח את השאלה בצורה עוד יותר פשוטה. דהיינו: התנאי של אורך סיסמה חייב להיות בין 6 לבין 20, הוא תנאי מורכב ולא תנאי פשוט. התנאי היותר פשוט, הוא, אורך הסיסמה חייב להיות לפחות 6 תווים בלי מגבלה על אורך מקסימאלי.
ולכן המקרה היותר פשוט שעלינו לראות שאנחנו יודעים למצוא לו פתרון, הוא, מה קורה אם יש רק חוק 1 שאומר, שסיסמה צריכה להיות לפחות 6 תווים. האם היינו יודעים לפתור את המקרה הזה?
וגם כאן אפשרי להתחיל מצורת שאלה עוד יותר פשוטה: נניח סיסמה חייבת להכיל לפחות תו 1 בלבד. האם היינו יודעים איך לפתור שאלה כזו? זה המקרה הפשוט ביותר שעלינו לנסות להתחיל לפתור ממנו.
ומאחר שמטרת המאמר היא לא ללמד את הפתרון של השאלה, אלא כן ללמד איך אפשרי למצוא את הפתרון לשאלה. ומאחר שכדי למצוא את הפתרון לשאלה, צריכים ללמוד לחלק לחלקים הכי קטנים שיש, לכן אני אציג כאן רצף של שאלות, מהקל אל הכבד, איך אמורים לגשת לנתח את השאלה הזאת:
האם אני יודע לפתור את השאלה במקרה שיש רק חוק 1 שאומר ש:
הסיסמה צריכה להיות באורך של לפחות תו 1
הסיסמה צריכה להיות באורך של לפחות 2 תווים
הסיסמה צריכה להיות באורך של לפחות 3 תווים
הסיסמה צריכה להיות באורך של לפחות X תווים
אם כן, אז האם אני יודע לפתור את השאלה במידה ו:
הסיסמה צריכה להיות באורך של לפחות 6 תווים
ועד כאן אני מניח שהתשובה ברורה, והיא שעלינו לבדוק את אורך הסיסמה (=N) ואם אורך הסיסמה קטן מ X (אורך מינימאלי) תווים, הרי שזה אומר שעלינו להוסיף X-N תווים, כדי שהסיסמה תהיה תקינה. לדוגמה אם אורך הסיסמה הוא 3 דהיינו, אורך שקטן מ X=6, אז 6-3 = 3 ולכן נצטרך להוסיף 3 תווים כדי לגרום לסיסמה להיות תקינה. דהיינו, נצטרך לעשות 3 פעולות של הוספה כדי לגרום לסיסמה להיות תקינה כסיסמה חזקה.
ועכשיו ננסה להבין, האם אני יודע למצוא תשובה לשאלה, אם יש רק חוק 1 שאומר ש:
הסיסמה צריכה להיות באורך של לא יותר מ תו 1
הסיסמה צריכה להיות באורך של לא יותר מ 2 תווים
הסיסמה צריכה להיות באורך של לא יותר מ 3 תווים
הסיסמה צריכה להיות באורך של לא יותר מ X תווים
אם כן, אז האם אני יודע לפתור את השאלה במידה ו:
הסיסמה צריכה להיות באורך של לא יותר מ 20 תווים
וגם עד כאן אני מניח שהתשובה ברורה, והיא שעלינו לבדוק את אורך הסיסמה (=N) ואם אורך הסיסמה גדול מ X (אורך מקסימאלי) תווים, הרי שזה אומר שעלינו למחוק N-X תווים, כדי שהסיסמה תהיה תקינה. לדוגמה אם אורך הסיסמה הוא 33 דהיינו, אורך שגדול מ X=20, אז 33-20 = 13 ולכן נצטרך למחוק 13 תווים כדי לגרום לסיסמה להיות תקינה. דהיינו, נצטרך לעשות 13 פעולות של מחיקה כדי לגרום לסיסמה להיות תקינה כסיסמה חזקה.
ועכשיו נשאל, האם אני יודע לפתור את השאלה במידה ויש חוק 1 שאומר, שהסיסמה אסור לה להיות פחות מ X (אורך מינימאלי) תווים ולא יותר מ Y (אורך מקסימאלי) תווים?
וגם כאן אפשרי להניח התשובה היא שכן, אם יש פחות מ X(אורך מינימאלי), אז צריך להוסיף תווים. ואם יש יותר מ Y (אורך מקסימאלי) תווים, אז צריכים למחוק אותיות, כדי לגרום לסיסמה להיות תקינה.
ועד כאן בעצם היתה דוגמה לאיך לחלק לחלקים קטנים.
עכשיו נעבור לחוק מספר 2 שאומר שהסיסמה צריכה להכיל לפחות אות 1 קטנה + אות 1 גדולה + מספר 1. וננסה להבין איך אפשרי לחלק את זה לחלקים קטנים.
אז נשאל, האם אני יודע לפתור את השאלה במידה ויש רק חוק 1 שאומר שהסיסמה צריכה להכיל אות 1 קטנה. בלי להתייחס לאות גדולה או מספר.
ונחלק לחלק יותר קטן, איך נפתור את השאלה, במידה ויש חוק שאומר שהסיסמה צריכה להכיל את האות a הקטנה.
דהיינו, לא נשאל על חוק שאומר שהסיסמה צריכה להכיל אות אחת קטנה כלשהי, אלא כן נשאל על מקרה יותר פשוט, שהסיסמה צריכה להכיל אות אחת ספציפית, כי זה מקרה שיותר קל לפתור.
כי יותר קל לדעת אם הסיסמה מכילה אות 1 ספציפית, מאשר לדעת אם הסיסמה מכילה אות 1 קטנה כלשהי. וגם יותר קל להבין שצריכים להוסיף אות 1 ספציפית אם היא חסרה, מאשר לחשוב איזו אות קטנה עלינו להוסיף, במידה ואין שום אות קטנה כלשהי.
ולכן נשאל מה אם:
הסיסמה צריכה להכיל את האות a
הסיסמה צריכה להכיל את האות b
הסיסמה צריכה להכיל אות ספציפית כלשהי
ואם יש לנו תשובה, אז נשאל, מה אם:
הסיסמה צריכה להכיל אות אחת קטנה כלשהי?
והתשובה לכך היא, שעלינו לבדוק האם הסיסמה מכילה אות 1 קטנה כלשהי. ואם לא, אז עלינו להוסיף אות 1 קטנה כלשהי, או עלינו להחליף אות אחת קיימת, לאות 1 קטנה כלשהי.
דהיינו, במקרה כזה לדוגמה A123456, עלינו או להוסיף אות אחת לדוגמה a קטנה aA123456 או להחליף לאות 1 קטנה לדוגמה כך Aa23456 ובשני המקרים הסיסמה תהיה תקינה.
דהיינו, אם חסרה לנו אות 1 קטנה, אז עלינו לבצע פעולה 1 של הוספה של אות קטנה או פעולה 1 של החלפה של אות כלשהי, לאות קטנה, כדי שהסיסמה תהיה חוקית.
ומה אם הסיסמה צריכה להכיל אות 1 גדולה? ומה אם הסיסמה צריכה להכיל ספרה אחת כלשהי? אז אם יש לנו תשובה גם לזה, אז נשאל מה אם:
הסיסמה צריכה להכיל את האות a הקטנה ואת האות A הגדולה?
ואם הסיסמה צריכה להכיל אות 1 קטנה כלשהי ואות אחת גדולה כלשהי?
ואם הסיסמה צריכה להכיל אות אחת קטנה כלשהי אות אחת גדולה כלשהי וספרה אחת כלשהי?
וכאן דילגתי קצת על חלקים ועל שאלות יותר קטנות, אבל כמובן שהיה אפשרי לחלק את זה למקרים יותר קטנים.
אז מי שיתבונן יראה, כי חוק מספר 2 שאומר שהסיסמה צריכה להכיל אות 1 קטנה גדולה וספרה, בעצם אומר ש:
עלינו לבדוק האם חסרה אות קטנה / גדולה / מספר, ואז עלינו להוסיף או להחליף אותיות בהתאם לצורך שלנו. לדוגמה 123456 יכול להפוך להיות 123456Aa או יכול להיות 12345Aa או יכול להיות 1234Aa וכולי.
ועכשיו נעבור לחוק מספר 3 שאומר, שסיסמה לא יכולה להכיל 3 תווים או יותר רצופים. ונשאל, האם נדע לפתור מקרה לדוגמה שאסור שיהיה תו ספציפי רצוף, לדוגמה AAA?
והתשובה היא, שאם לדוגמה יש לנו AAA עלינו או למחוק A אחד וישאר רק AA או להחליף תו אחד לדוגמה A1A או 1AA או AA1 ועכשיו הסיסמה תהיה תקינה. או להוסיף תו אחד לדוגמה A1AA או AA1A, שגם כך הסיסמה הופכת להיות תקינה.
ואם יש לנו 4 תווים רצופים, לדוגמה AAAA עלינו או למחוק 2 תווים ונקבל AA. או להוסיף תו אחד לדוגמה AA1AA או להחליף תו אחד לדוגמה A1AA או AA1A ואז הסיסמה תהיה תקינה.
ואם יש לנו 5 תווים רצופים, לדוגמה AAAAA עלינו או למחוק 3 תווים, ונקבל AA או להוסיף 2 תווים לדוגמה AA1AA2A או להחליף תו אחד דהיינו, AA1AA וככה הסיסמה תהיה תקינה.
ואם יש לנו 6 תווים רצופים, לדוגמה AAAAAA אז עלינו או למחוק 4 או להוסיף 2 ל AA1AA2AA או להחליף 2 כך AA2AA1 וכיו"ב.
ואם יש לנו 7 לדוגמה AAAAAAA אז עלינו או למחוק 5 או להוסיף 3 כך: AA2AA3AA1A או להחליף 2 כך: AA1AA2A.
ואם יש לנו 8 לדוגמה AAAAAAAA אז עלינו או למחוק 6 או להוסיף 3 כך: AA2AA3AA1AA או להחליף 2 כך: AA1AA2AA
וכך עלינו להמשיך ולבדוק ידנית עוד מקרים, מבחינתי עד 20 תווים רצופים, שזה המספר המקסימאלי של התווים שהסיסמה יכולה להכיל.
ועכשיו עלינו לבצע עוד סוג של בדיקות ידניות, ולחלק לחלקים בצורה הבאה:
נניח שהיתה רק פעולה אחת אפשרית, פעולה של מחיקה בלבד. האם היינו יודעים לפתור את כל המצבים? האם היינו יכולים לפתור פעולות של סיסמה קצרה? תשובה: לא. האם היינו יודעים לפתור מצב של סיסמה ארוכה: כן. האם היינו יודעים לפתור מצב של תווים חסרים? תשובה: לא. האם היינו יודעים לפתור מצב של תווים רצופים? תשובה: כן.
ואם היתה רק פעולה אחת אפשרית של הוספה? אז היינו יכולים לפתור מצב של סיסמה קצרה, לא היינו יכולים לפתור מצב של סיסמה ארוכה מידי. כן היינו יכולים לפתור מצב של תווים חסרים או רצופים.
ואם היתה רק פעולה אחת אפשרית של החלפה? אז לא היינו יכולים לפתור בעיה של אורך. אבל כן היינו יכולים לפתור בעיה של תווים חסרים או רצופים.
ואם היו רק 2 פעולות של מחיקה והוספה? אז היינו יכולים לפתור את כל המצבים. ואם היו רק 2 פעולות של מחיקה והחלפה? לא היינו יכולים לפתור מצב של סיסמה קצרה מידי.
או במילים אחרות ננסה לבדוק את כל החוקים ואת כל המצבים, במקרה שיש רק פעולה אחת אפשרית של הוספה או מחיקה או החלפה. ובמקרה שיש רק 2 פעולות אפשריות, של הוספה + מחיקה או הוספה + החלפה או מחיקה + החלפה בלבד. וכמובן גם במקרה שיש 3 פעולות אפשריות, של מחיקה או הוספה או החלפה.
אז מה בעצם עשינו עד כה?
עד כה שיחקנו ידנית עם כל מיני מקרים שונים, וניסינו לחלק את התהליך לחלקים ולמקרים פשוטים. מה לא ניסינו לעשות, לא ניסינו למצוא חוקיות, לא ניסינו למצוא נוסחה.
או במילים אחרות, קודם כל צריכים לנסות לראות אם יודעים לפתור את השאלה, במקרה הפשוט ביותר, בלי שום חוקיות, בלי שום נוסחה, בלי שום מורכבות.
רק אחרי שאנחנו מסוגלים לפתור את השאלה ידנית, בלי חוקיות, בלי נוסחה בלי כלום, במקרה הכי פשוט. עכשיו ננסה לפתור את השאלה בצורה קצת יותר מורכבת.
אז האם אנחנו נדע לפתור את השאלה במידה ויש לנו 2 חוקים שהם:
1 - האורך חייב להיות בין X לבין Y
2 - הסיסמה חייבת להכיל אות קטנה / גדולה / מספר
במידה ואלו 2 החוקים שנותנים לנו, האם נדע לפתור את השאלה?
ומה אם היו לנו את 2 החוקים הבאים:
1 - האורך חייב להיות בין X לבין Y
2 - אסור שתו יחזור על עצמו 3 פעמים או יותר
ומה אם היו לנו את 2 החוקים הבאים:
1 - הסיסמה חייבת להכיל אות קטנה / גדולה / מספר
2 - אסור שתו יחזור על עצמו 3 פעמים או יותר
ומה אם היו לנו את 3 החוקים המלאים:
1 - האורך חייב להיות בין X לבין Y
2 - הסיסמה חייבת להכיל אות קטנה / גדולה / מספר
3 - אסור שתו יחזור על עצמו 3 פעמים או יותר
עכשיו כמובן שהעלילה מתחילה להסתבך... איך ניגשים לזה? איך פותרים את זה?
כמובן, ש... איך פותרים את זה ידנית. בלי נוסחאות ובלי סיבוכים, ננסה קודם כל להבין איך פותרים את זה ידנית.
האם קודם מתחילים מחוק מספר 1 או 2 או 3? מה קדם למה?
אז לשם כך ננסה שוב להתחיל הכל מהתחלה, וננסה להבין האם בכל האפשרויות יש משהו שהוא בטוח נכון.
אז נחזור לחוק של האורך, אם נתבונן עליו נראה שיש בו משהו שהוא בטוח נכון.
אם האורך צריך להיות 6, אז בטוח נכון שאם יש פחות מ 6 תווים, אז בטוח נכון שעלינו לבצע 6-N פעולות של הוספה. לדוגמה, אם יש לנו 3 תווים, אז בוודאות של מאה אחוז, שעלינו לבצע 3 פעולות של הוספה כדי שהסיסמה תהיה באורך של 6.
דהיינו, יש לנו וודאות של מאה אחוז
1 - גם לגבי כמות הפעולות שאנחנו צריכים לבצע, כי אנחנו בוודאות צריכים לבצע 3 פעולות.
2 - וגם יש לנו וודאות של מאה אחוז, לגבי סוג הפעולות שאנחנו צריכים לבצע, כי אנחנו צריכים לבצע בוודאות פעולות של הוספה ולא של מחיקה או של החלפה.
ואם הסיסמה ארוכה מ 20 לדוגמה היא באורך של 5, אז יש לנו וודאות של מאה אחוז שאנחנו צריכים לבצע 5 פעולות מסוג פעולה של מחיקה.
דהיינו, בדיקת החוק של האורך, נותן לנו וודאות גם לגבי כמות הפעולות שצריכים לבצע וגם לגבי סוג הפעולות שצריכים לבצע, כדי להתאים את הסיסמה לחוק של האורך.
עכשיו נבדוק את החוק של האותיות הנדרשות, אם נסתכל נראה כי נניח שאנחנו צריכים שתהיה אות אחת קטנה, הרי שאם אין אות אחת קטנה, הרי שיש לנו וודאות של מאה אחוז לגבי כמות הפעולות שעלינו לבצע, דהיינו, שעלינו לבצע פעולה 1 כלשהי. אבל יש לנו ספק לגבי סוג הפעולה שעלינו לבצע, כי אולי נצטרך לעשות הוספה של אות 1 או החלפה של אות 1.
ואם חסר לנו אות גדולה + מספר, הרי שבוודאות עלינו לבצע 2 פעולות. אבל הן יכולות להיות או 2 פעולות הוספה או 2 פעולות החלפה או 1 פעולה הוספה + 1 פעולת החלפה וכולי.
במילים אחרות, החוק השני של תווים הכרחיים, נותן לנו וודאות לגבי כמות פעולות שצריכים לבצע, אבל משאיר לנו ספק לגבי סוג הפעולות שצריכים לבצע.
ועכשיו נעבור לחוק 3 שאסור שיהיו 3 תווים רצופים. ואם נחקור אותו נראה, כי הוא משאיר לנו ספק, גם לגבי כמות הפעולות וגם לגבי סוג הפעולות.
לדוגמה במקרה של 8 תווים רצופים לדוגמה כך: AAAAAAAA, אז הרי שעלינו
או לבצע 6 פעולות של מחיקה
או לבצע 3 פעולות של הוספה
או לבצע 2 פעולות של החלפה
דהיינו, יש לנו וודאות כלשהי, אבל הכי פחות וודאות. גם לגבי כמות הפעולות וגם לגבי סוג הפעולות.
במילים אחרות אנחנו מבינים, שהחוק של האורך התקין, מספק לנו הכי הרבה וודאות. אחר כך יש לנו את החוק של התווים ההכרחיים, אחר כך החוק של האותיות הרצופות, שמספק לנו הכי פחות וודאות והכי הרבה ספקות ואפשרויות.
אז מה בעצם זה אומר לנו?
אז זה בעצם אומר לנו שכאשר אנחנו מקבלים שאלה כזאת, עלינו כמובן לנסות להתחיל מהחלק הכי קטן שבטוח נכון. דהיינו, כאשר נקבל סיסמה ונצטרך לבדוק אותה אל מול 3 החוקים הנ"ל, קודם כל נעדיף לבדוק את החוק של האורך, שהוא מספק לנו וודאות של מאה אחוז, גם לגבי כמות הפעולות וגם לגבי סוג הפעולות. אחר כך נבדוק את החוק של התווים ההכרחיים, שמספק לנו וודאות לגבי כמות ופחות לגבי סוג. ורק אחר כך נבדוק את החוק של התווים הרצופים, שמספק לנו הכי פחות וודאות לגבי כמות או סוג הפעולות שעלינו לבצע.
מהי החוקיות של הפעולות עצמן? מה היחס ביניהן?
ואם נעמיק עוד קצת לגבי הפעולות האפשריות לתקן סיסמה, וננסה לשאול את עצמנו, אם יכולנו לבחור פעולה אחת או 2 פעולות בלבד, מה היינו בוחרים? האם יש פעולה שעדיפה על פעולות אחרות? אם נחקור את הנושא נראה ש:
בשביל סיסמה שתהיה באורך לפחות 6, חייבים פעולה של הוספה ואך ורק פעולה של הוספה.
בשביל סיסמה שתהיה לא יותר מאורך של 20, חייבים פעולה של מחיקה ואך ורק פעולה של מחיקה.
בשביל שהסיסמה תהיה עם תווים הכרחיים, צריך פעולה של הוספה או של החלפה. כאשר אין יתרון לפעולה של החלפה או של הוספה. אם נבצע הוספה או החלפה של תווים, הרי שנבצע מספר זהה של פעולות. דהיינו, אם נבחר לתקן את הסיסמה באמצעות הוספה או החלפה, נבצע כמות זהה של פעולות.
דהיינו, עד כה אנחנו רואים שבמובן מסוים, עדיף לנו שתהיה לנו אפשרות של הוספה, כי היא פותרת מצבים של סיסמה קצרה ושל תווים חסרים. כי מחיקה, לא פותרת את התווים החסרים.
ואם נחקור את החוק של התווים הרצופים, אז נראה שאפשרי לתקן בהתאם לחוק באמצעות מחיקה או הוספה או החלפה. כאשר מחיקה היא בדרך כלל דורשת הכי הרבה פעולות. אחר כך פעולה של הוספה שדורשת פחות פעולות. ואחר כך פעולה של החלפה, שדורשת הכי פחות פעולות.
דהיינו, תווים רצופים, בברירת המחדל, נעדיף לפתור אותו עם פעולת החלפה, שדורשת הכי פחות פעולות.
או במילים אחרות, אם נוכל לבחור לפתור בעיה של חוק 2 של תווים חסרים, באמצעות הוספה או החלפה, אז עלינו להעדיף את הפעולה של ההחלפה. כי היא יודעת לתקן גם ביחס לחוק 3, שהחלפה פותרת בו את הבעיה בדרך הקצרה ביותר.
דהיינו, החוק של התווים הרצופים, הכי טוב לפתור אותו באמצעות החלפה. כי זה דורש הכי פחות פעולות. ולכן ננסה בברירת המחדל בלפתור את חוק 2 של תווים חסרים, ננסה להעדיף פעולה של החלפה על פני פעולה של הוספה. כי פעולה של החלפה, היא יותר יעילה עבור חוק 3 מאשר פעולה של הוספה או פעולה של מחיקה.
אז לכאורה פתרנו את השאלה. כי בעצם עלינו קודם כל לבדוק את האורך של הסיסמה. אחר כך לבדוק תווים חסרים ואחר כך לבדוק תווים רצופים. לדוגמה:
נניח שהסיסמה היא AAA אז:
מהחוק של האורך אנחנו יודעים בוודאות שאנחנו צריכים לבצע 3 פעולות של הוספה.
מהחוק של התווים החסרים, אנחנו יודעים בוודאות שאנחנו צריכים לבצע 2 פעולות של הוספה או של החלפה.
ומהחוק של התווים הרצופים, אנחנו יודעים בוודאות שאנחנו צריכים לבצע פעולה 1 של החלפה / הסרה / מחיקה.
ומאחר שבטוח נכון שאנחנו צריכים לבצע 3 פעולות של הוספה, בגלל חוק האורך, הרי שבעצם ב 3 פעולות של הוספה, נוכל גם להתאים את הסיסמה לחוק של התווים החסרים וגם של התווים הרצופים. לדוגמה כך: AaAA12.
דהיינו, ב 3 פעולות של הוספה, גם תיקנו את הסיסמה לאורך של 6 גם הוספנו אות קטנה ומספר, וגם ביטלנו את ה 3 אותיות הרצופות.
במילים אחרות, מצב של AAA נפתור אותו ב 3 פעולות.
ואם יש לנו סיסמה באורך של 25 אותיות, לדוגמה ABABABAAAAABABABABAB12345.
אז בוודאות שאנחנו צריכים לעשות 5 פעולות מחיקה בגלל האורך.
+ פעולת החלפה או הוספה 1 של אות קטנה.
+ בגלל שיש בתוך הסיסמה 5 אותיות רצופות של AAAAA אז אנחנו צריכים לעשות או 5 פעולות מחיקה או 2 פעולות הוספה או 1 פעולת החלפה.
ולכן, נעשה 5 פעולות מחיקה להתאים את האורך
+ פעולה 1 של החלפה, כדי להוסיף אות קטנה ולא פעולה של הוספה, כדי לא לפגוע באורך
+ ב 5 הפעולות מחיקה הקודמות, נוכל למחוק את כל רצף האותיות הנ"ל.
דהיינו, סה"כ נצטרך 6 פעולות בלבד. 5 של מחיקה + 1 של החלפה.
אז מהי מהות הפתרון עד כה?
במילים אחרות, ניקח את הפעולות שהן בטוח נכונות, דהיינו, שבטוח צריך לבצע אותן ובאמצעותן נפתור את כל שאר הפעולות שאולי צריך לבצע.
דהיינו, אם חובה לבצע פעולות מחיקה בגלל האורך, נוכל באמצעותן למחוק אותיות רצופות.
אם חובה לבצע פעולות הוספה בגלל האורך, נוכל באמצעות פעולות ההוספה לתקן בהתאם לתווים חסרים או רצופים.
כאשר אם ואחרי שהאורך תקין, תמיד נעדיף לבצע רק פעולות של החלפה.
כי מצד החוק של תווים חסרים, פעולת החלפה יעילה בוודאות כמו פעולת הוספה. והחלפה, לא יכולה להרוס את האורך של הסיסמה. ומצד החוק של תווים רצופים, בכל מקרה עדיף החלפה, כי זאת הפעולה הכי יעילה.
ולכן קודם כל נבדוק את האורך, ואז נשתמש בפעולת ההוספה כדי לפתור את 2 החוקים הנוספים של להוסיף אותיות חסרות או כדי לנטרל אותיות רצופות.
ונשתמש בפעולת המחיקה, כדי לתקן את האורך וגם כדי לפתור אותיות רצופות. ומכאן ואילך, נספור רק פעולות של החלפה בלבד. כדי שלא בטעות נשבש את האורך של הסיסמה וגם כי החלפה יותר יעילה עבור התיקון של אותיות...
050-3331-331