כבר הרבה הרבה זמן לא היה אתגר, אז בשעה טובה הגיע הזמן לאתגר חדש

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

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

שימו לב שכשמחפשים מחרוזת עם רווח בתוכה - מתעלמים ממנו. כלומר חיפוש "אניה" זהה לחיפוש "אנ יה"

בונוס
אלו לא סעיפי חובה, אבל ביצוע שלהם יקנה נקודות נוספות:

• טיפול באותיות סופיות. כלומר חיפוש "ארץ" למשל משולבת בטקסט "אבא ערד ויצחק" בצורה הזו""אבא ערד ויצחק", כי 'צ' זהה ל'ץ' . (נקודה אחת נוספת)

• טיפול בניקוד. חיפוש "שַלום" יתאים גם ל-ש עם ניקוד אחר או בלי ניקוד בכלל. (שתי נקודות נוספות)

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

קוד PHP:

 $a = "לאמה, נהרי ואהובה";
$b = "אניה";
byblicSearch($a,$b);
 /* יחזיר מערך כזה

array(1,6,9,13)

כי האות 'א' מופיעה בתו מספר 1 בטקסט (כי תוים מתחילים לספור מ-0)
האות 'נ' מופיעה בתו מספר 6 בטקסט
האות 'י' מופיעה בתו מספר 9 בטקסט
והאות 'ה' מופיעה בתו מספר 13 בטקסט

  */ 


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


הניקוד
ישנן 16 נקודות סה"כ:
6 נקודות על ביצוע המשימה
5 נקודות על יעילות (היעילות תימדד על פי זמן הריצה)
3 נקודות על בונוס (ראה סעיף בונוס)
2 נקודות על קריאות הקוד (בין היתר יש להוסיף תיעוד. לא לכתוב יותר מדי ולא לכתוב מעט מדי. מספיק תיעוד של תפקיד המשתנים ופונקציות העזר(אם יש) ותיעוד של חלקים ספציפיים בקוד שאינם אינטואיטיביים)

הפרסים
מקום ראשון: צל"ש לחודש!
מקום שני: צל"ש לשבועיים!
מקום שלישי: צל"ש לשבוע!

לוח זמנים
האתגר נפתח היום (14/6/07) ונסגר בעוד חודש (14/7/07)
יש לכם הרבה זמן, ואני מקווה שכולכם תשתתפו!

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

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


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

בהצלחה לכולם!

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

כנראה שגם באתגר הזה אני לא ישתתף, אבל רק כנראה

שאלה:

אם בחיפוש אכתוב "test" והנושא הוא "the main subject"

זה אמור לצאת:

ציטוט:

1, ... 16

?

אממ אבל המילה test לא משולבת במחרוזת בצורה נכונה. בין כל אות ששייכת לtest אמור להיות מספר קבוע של אותיות
במקרה שלך
"the main subject"
יש בין t לe רק אות אחת, בין e לs ארבע אותיות ובין s ל t יש חמש אותיות.

בכל מקרה, אם המחרוזת הייתה מתקבלת, אז המערך המוחזר היה
array(0,2,8,14)
כי האות t נמצאת בתו במקום 0, האות e בתו במקום 2, האות s בתו במקום 8 והאות t בתו במקום
14


דרך אגב, אם משהו בניסוח או בהסבר לא ברור בבקשה תגידו.

עלה לי עכשיו רעיון מעולה לראש

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

בגלל זה זה נקרא "אתגר"

בדיוק מה שבאתי לרשום..

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

שאלה מאוד מאוד חשובה!
נגיד לי לי מילה.

היי

והטקסט: "ההיי"
אז מה איך זה?

ההיי

ההיי

ההיי

איך???

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

אתה מתבלבל - הרעיון הוא שזה יפעל כמו הראשון:

ההיי

ימצא את ה-ה' הראשון, ואז את ה י' הראשון.

ההיי, ההיי : לא יהיו טובים.

ציטוט:

כאשר המחרוזת משולבת בטקסט כך שכל אות מהמחרוזת מופיעה כל מספר קבוע של אותיות בטקסט

במקרה השני ש-Radik123 הציג, יש מרחק של אפס אותיות בין כל אות של מחרוזת החיפוש. במקרה השלישי, יש מרחק של אות אחת.
מה הבעיה בזה?

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

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

מקווה שהייתי ברור.

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

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

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

איבדתי אותך.

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

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

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

השיטה הזאת למציאת האותיות - מוצאת במקביל לKEY את האותיות בטקסט.

"א"

"אראץ"

ולא:

"אראץ"

זה מה שהתכוונתי סה"כ.

אני אנסה, כנראה שאני יהיה זה עם הפיתרון הגרוע משלכם.

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

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

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

קוד PHP:

 $letters[$i]; 


אה תודה, די דומה ל c, סטרינג הוא מערך של אותיות

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

לא סטרינג, אלא מחרוזת.

[או string, כשכל המשפט באנגלית...]

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

המרחק לא חייב להיות של שתי אותיות בלבד. כל מרחק שיהיה זהה בכל האותיות של המלל יתאים.

האפשרות השניה. רווח של X קבוע

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

זה קוד PHP בילבד נכון?

אחרת זה יהיה די מצחיק להשוות מהירויות בין php לקוד מכונה למשל

באמת שלא נכעס עליך אם תכתוב את זה באסמבלי.

לבקשת ישראל אפשר גם באסמבלי

המילה לחיפוש בתוך המחרוזת, צריך למצוא כמה אפשרויות שיהיו בהם כמה רווחים בין האותיות?

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

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

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

היום אני אראה...יש לי הרבה לימודים עכשיו

האם תכניסו מחרוזות לבדיקה שאורכן 0 או 1 וכדו'? סתם ליתר ביטחון...האם תנסו לבדוק אם הפונקציה תיתן שגיאה טכנית (לדוגמא שהפונקציה נותנת שגיאה) בווריאציות שונות?

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

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

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

אז ככה:
לכל חיפוש של המחרוזת X בתוך המחרוזת Y, יוחזר אותו הדבר כמו עבור חיפוש של X שהוסרו ממנו רווחים בתוך Y

בY, יש להתחשב ברווחיםובכל התווים כמו ניקוד שאינם אותיות כאשר מחזירים את מיקום התוים, אך לא כשסופרים את האותיות על מנת להתאים את המחרוזת

אני מקווה שעכשיו זה ברור

האם כל תו יחיד של סימני הגיה\פיסוק\מה-שמו (כלומר סימנים שהם כמו חטף, קמץ, חיריק, סגול וכו') נחשב כתו שיש להתחשב בו כשמחזירים את המיקום של האות בתוך הטקסט?

כלומר האם התו הזה יכול להשפיע על מיקומה של האות בתוך הטקסט?

לדוגמא, יש לי את הטקסט:
"ֵֶַָלאמה, נהרי ואהובה"
יש בו 4 סימני הגיה אך ורק בתחילת המחרוזת.
ואת המילה שמחפשים בו:

קוד:

"א   ניהה"

[שמתי בתגיות CODE כדי שישימו לב לרווחים]

אז התוצאה שאמורים לקבל היא:

קוד:

array(5) { [0]=> int(5) [1]=> int(10) [2]=> int(13) [3]=> int(19) [4]=> int(22) } 

???

כן

זה כולל גם חיפוש של מילה בעלת 2 תווים? שיש לה 2 אותיות....

עוד שאלה שחשבתי עליה (עברתי את הזמן העריכה..):

כשאני מגיש את הקובץ עם הפונקציה byblicSearch, צריך שיהיה רק את הפונקציה הזו (על מנת שהבודק יבדוק אותה באמצעות Include)? ללא קוד HTML ואחרים?

עדיף שכן
לא הבנתי את השאלה הקודמת

השאלה הקודמת היא האם תכניסו מילה לחיפוש שאורכה יהיה 2 תוים?

לדוגמא:

קוד PHP:

 $a = "לאמה, נהרי ואהובה";
$b = "אנ";
byblicSearch($a,$b); 


אורכו של משתנה $b הוא 2 תוים...
בכל זאת השאלה היא לא משנה עכשיו...

1. איך מתבצעת השוואת זמני הריצה של האלגוריתמים? הרי:

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

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


2. מה נותן הצל"ש? כתבתי אלגוריתם מעולה אבל תהיתי פתאום מה בעצם מרוויחים מלפרסם אותו...(חוץ מביקורת חיצונית, אני יודע. אבל הוא באמת אלגוריתם עם מצב לנצח) (-:

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

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

ג. עושים את זה בשביל הכיף, תהנה

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

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

אז אתם מפרסמים את הטקסט לפני או אחרי סיום האתגר?

הטקסט מפורסם לאחר שתקופת ההגשה הסתיימה, כמובן

שימו לב - תאריך סיום האתגר נדחה בשבוע, כלומר ה-21/07/07

בדוגמא כתוב

ציטוט:

לאמה, נהרי ואהובה

עם פסיק שמפריע לרצף האותיות (יוצא 3 2 2)
צריך להתעלם מפסיקים? כי לא כתוב על זה

ובבונוס של הניקוד, לא כתבתי שום דבר בקוד שעוסק בניקוד, אז הוא מתעלם ממנו? איך ניקוד מיוצג? ואיפה אפשר ללמוד על זה?

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

ציטוט:

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

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

תודה

אני ובעיות הבנת הנקרא שלי

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

שעליהן אתם בודקים את יעילות הפונקציות

זה עדיין לא אפשרי, המחרוזות יפורסמו, אל דאגה.

יפורסמו מחר בערב

יהיה תוצאות בזמן הקרוב?

היה עיכוב מסויים

קישור