והפעם נדבר על שאלת 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