רוטר - אתגרון תיכנותי

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"אתגרון תיכנותי"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #6117	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 6117

dryice

00:22 02.06.03

אתגרון תיכנותי

עבר עריכה לאחרונה בתאריך 10.06.03 בשעה 11:38

(עקב בעיות טכניות האשכול הזה נמחק בעבר, נעשה שוב)
נתון טקסט באנגלית שסלקו ממנו את כל הרווחים,
יש לכתוב תוכנית שתחזיר את הרווחים.
למשל קלט:
whoareyou
פלט:
who are you

DRYICE
נ.ב
כמובן שיש צורך ברשימת מילים.
כמובן שלא יתכן פתרון 100%.

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

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
ננסה	יהונתן	02.06.03 00:45	1
זה לא ממש יעבוד:	dryice	02.06.03 11:22	5
התחלתי לכתוב משהו, ונתקלתי בבעיה	liranr	02.06.03 09:49	2
זאת בעיה ידועה בזיהוי תת מחרוזת במחרוזת גדולה	no1	02.06.03 10:59	3
התוכנית שלי, עושה שני דברים.	dryice	02.06.03 11:06	4
backtracking אמור להספיק	liranr	02.06.03 12:59	6
כמובן שאתה צודק	no1	02.06.03 17:09	7
יש לי רעיון לאיך אפשר לבנות תוכנה כזות	AndreyT	02.06.03 18:56	8
יש בעיות עם תוכנות כאלו לדוגמא:	Vidi	02.06.03 20:25	9
זה אכן בעיה	AndreyT	03.06.03 10:55	10
ובדיוק בשביל זה המציאו את הרווח :)	Quant86	03.06.03 15:30	11
זה מאוד פרקטי.	dryice	04.06.03 02:36	17
תגובה ל 10	Vidi	03.06.03 16:25	12
שאלה:	Dudenland	03.06.03 22:04	13
והכי חשוב... שמות?	Vidi	03.06.03 22:26	14
טוב... בעיקרון, כבר יש לי תכנית מוכנה... אבל:	Dudenland	03.06.03 23:34	15
כתוב לך שלא יתכן פתרון 100%	jossepe_4u	04.06.03 00:34	16
אני חושב שאני יעבוד עליו קצת...	Dudenland	04.06.03 13:49	18
האם אין לאף אחד תוכנית עובדת?	dryice	06.06.03 15:22	19
יש לי את הדוגמא הכי טובה למצב דומה...	Fire_Bullet	08.06.03 16:16	20
יש לך טעות בפיסוק:	Dudenland	08.06.03 18:44	21
מעבר לעובדה שהמשפטים שלך לא נכונים	dryice	08.06.03 21:11	22
טוב... אני פורש...	Dudenland	08.06.03 22:25	23
זה בלתי אפשרי!	dryice	09.06.03 12:24	24
מה פתאום?	AlexKarpman	09.06.03 21:31	25
הכוונה ל There, play proves it...	Vidi	09.06.03 22:05	26
אני כמובן לא יודע לאיית	dryice	10.06.03 11:36	27
גישה אחרת לפתרון הבעיה	dryice	10.06.03 11:47	28
משהוא שאני כתבתי	dryice	10.06.03 19:46	29

יהונתן

00:45 02.06.03

1. ננסה
בתגובה להודעה מספר 0

נתון: מערך מחרוזות מילים באנגלית - אפילו לא ממוין.
מחרוזת הקלט בלי הרווחים.
משתנים: מערך בוליאני באורך מספר המילים באנגלית- כולו true.
מונים - i j וכדו'.
מחרוזת תוצאה סופית.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

11:22 02.06.03

5. זה לא ממש יעבוד:
בתגובה להודעה מספר 1

togetridofsnow
צ"ל
to get rid of snow
ואילו אם במילון שלך תופיע המילה:
together
היא תתאים toget ותתקע, כאשר היא שכחה מהתחילית to שהתאימה
לגמריי.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

09:49 02.06.03

2. התחלתי לכתוב משהו, ונתקלתי בבעיה
בתגובה להודעה מספר 0

נגיד המשפט המקורי היה dog and cat ולאחר מחיקת הרווחים dogandcat.
התוכנה שכתבתי מזהה את המילה do ומפרידה אותה מהשאר, ואז לא מצליחה להתקדם.
לכן צריך להכניס לתוכנה איזושהיא אופציה של backtracking בשביל שאם היא
נתקעת שתחזור ותנסה שוב. אני עובד על זה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

no1

10:59 02.06.03

3. זאת בעיה ידועה בזיהוי תת מחרוזת במחרוזת גדולה
בתגובה להודעה מספר 2

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

11:06 02.06.03

4. התוכנית שלי, עושה שני דברים.
בתגובה להודעה מספר 2

1) היא מנסה להתאים את המילה הארוכה ביותר.
2) היא עושה BACKTRACKING.
שים לב שגם a וi הם מילים חוקיות.
(יתכן שbactracking זה מספיק, לא באמת בדקתי לעומק)

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

12:59 02.06.03

6. backtracking אמור להספיק
בתגובה להודעה מספר 4

למרות שלנסות להתאים את המילה הארוכה ביותר קודם יכול להפחית
בצורה משמעותית את מספר הקריאות הרקורסיביות (זה אומדן זריז שלי, לא
ממש בדקתי לעומק).
ול-no1, הבעיה שגם שאתה נתקל בצירוף the או and, אתה לא בטוח שזאת
אכן מילת קישור.
לדוגמא , אם הקלט הוא hellotherepeople (עם רווחים זה hello there people)
אז השיטה שלך תחלק את המחרוזת ל hello ול-repeople מה שיצור בעיה.

כל זה בהנחה שהבנתי מה שהתכוונת...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

no1

17:09 02.06.03

7. כמובן שאתה צודק
בתגובה להודעה מספר 6

עבר עריכה לאחרונה בתאריך 02.06.03 בשעה 17:09

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

AndreyT

18:56 02.06.03

8. יש לי רעיון לאיך אפשר לבנות תוכנה כזות
בתגובה להודעה מספר 0

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Vidi
חבר מתאריך 1.10.17
591 הודעות

20:25 02.06.03

9. יש בעיות עם תוכנות כאלו לדוגמא:
בתגובה להודעה מספר 8

אם הטקסט הוא
thisisanidealerror
אז הוא יוכל לפרש אותו כ
This is an ideal error
או כ
This is an I deal Error
לכן ישנם מלא בעיות :(

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

AndreyT

10:55 03.06.03

10. זה אכן בעיה
בתגובה להודעה מספר 9

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Quant86

15:30 03.06.03

11. ובדיוק בשביל זה המציאו את הרווח :)
בתגובה להודעה מספר 10

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

02:36 04.06.03

17. זה מאוד פרקטי.
בתגובה להודעה מספר 11

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Vidi
חבר מתאריך 1.10.17
591 הודעות

16:25 03.06.03

12. תגובה ל 10
בתגובה להודעה מספר 10

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

22:04 03.06.03

13. שאלה:
בתגובה להודעה מספר 0

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

Dudenland

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Vidi
חבר מתאריך 1.10.17
591 הודעות

22:26 03.06.03

14. והכי חשוב... שמות?
בתגובה להודעה מספר 13

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

23:34 03.06.03

15. טוב... בעיקרון, כבר יש לי תכנית מוכנה... אבל:
בתגובה להודעה מספר 0

נתקלתי בבעייה שאני לא רואה דרך לפתור אותה:
אם אני שם את המחרוזת thereplayprovesit, וכמובן שהמשפט המבוקש הוא:
the replay proves it
אז אני מקבל דווקא את המשפט:
there play proves it
וזאת משום שאני בודק לפי המילה הארוכה ביותר...
אני לא רואה דרך, אלא אם כן אני משלב באמת מידה מסויימת של "בינה מלאכותית", כמו למשל בדיקת דקדוק וכו'...
אגב, בדיקת האיות של ה-Word גם היא לא מזהה את המשפט כמשפט לא חוקי...
בכל מקרה, כשאני אומר בדיקת-דקדוק, אני מתכוון שאני צריך לסווג כבר במילון, כל מילה לתחום שלה (פעלים, שמות-עצם, תארים וכו'), ואז לפי כללי דקדוק ובעיקר לפי הגיון, לבחור את האפשרות המתאימה, כלומר להתאים למילת קישור מסויימת את המילה המתאימה לה...
זה נראה כמו עבודה של פרוייקט שלם... קצת מוגזם מדי בשביל "אתגרון"...

Dudenland

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

jossepe_4u
חבר מתאריך 18.3.02
258 הודעות

00:34 04.06.03

16. כתוב לך שלא יתכן פתרון 100%
בתגובה להודעה מספר 15

תגיש את הפתרון שלך וdryice יעבור עליו...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

13:49 04.06.03

18. אני חושב שאני יעבוד עליו קצת...
בתגובה להודעה מספר 16

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

Dudenland

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

15:22 06.06.03

19. האם אין לאף אחד תוכנית עובדת?
בתגובה להודעה מספר 0

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Fire_Bullet

16:16 08.06.03

20. יש לי את הדוגמא הכי טובה למצב דומה...
בתגובה להודעה מספר 0

לא אותו הדבר אבל משהו דומה.
פסק\י את המשפט הבא:
A woman without her man worth nothing
אם אני יגיד לך כאדם אתה תוכל לשים פסיקים בשני דרכים(ושניהם נכונים!!!)
לאחר שפיסקתם... תראו שיש אופצית פיסוק נוספת;
a woman, without her, man worth nothing
***OR***
a woman, without her man, worth nothing

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

18:44 08.06.03

21. יש לך טעות בפיסוק:
בתגובה להודעה מספר 20

a woman - without her man, worth nothing
אין לשים פסיק לאחר פתיח מסוג זה... במקום פסיק, יש לשים מקו.

Dudenland

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

21:11 08.06.03

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

אתה לחלוטין צודק.
וכבר נאמר קודם, הביאו דוגמא נפלאה:
the replay proves it
there play proves it
שניהם משפטים תקינים לחלוטין, ולא ניתן להבחין ביניהם
שלא ע"י הבנת כל הטקסט כולו, וגם אז אני יכול ליצור הקשר
בו אף אחד, לא יכול להבחין.
אבל הרצון הוא לכתוב תוכנה שתעשה ביעילות עבודה טובה, כמעט
כמו מה שעושה בן אדם שמבין את השפה.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

22:25 08.06.03

23. טוב... אני פורש...
בתגובה להודעה מספר 22

ניסיתי הכל... וזה רק הולך ומסתבך...
אני פשוט לא מצליח לתקן את משמעות המשפט, ולבטל את האפשרות: there play proves it... לטובת: the replay proves it...
יצרתי מילון קצת יותר משוכלל, כאשר כל מילה מקוטלגת גם לפי סוגה (תואר, פועל שם וכו'), אבל כל פעם יש בעייה חדשה, ואז אני מגלה שצריך להוסיף עוד התנייה, כדי להשלים עוד חוק... וזה לא נגמר !!!
יש כל-כך הרבה חוקים באנגלית... וכבר אין לי סבלנות לזה... במיוחד בזמנים כמו עכשיו... לפני בגרויות...
אולי אני אתפנה ואחזור לזה בחופש...

Dudenland

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

12:24 09.06.03

24. זה בלתי אפשרי!
בתגובה להודעה מספר 23

שני המשפטים:
the replay proves it
ו
there play proves it
הם משפטים חוקיים לחלוטין באנגלית.
תעלה לפה את מה שכתבת, ואני אעלה את מה שאני כתבתי ונשווה
מה עשינו.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

AlexKarpman

21:31 09.06.03

25. מה פתאום?
בתגובה להודעה מספר 22

בס"ד

DRYICE ו-Dudenland:
There play proves it אינו משפט תקין באנגלית.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Vidi
חבר מתאריך 1.10.17
591 הודעות

22:05 09.06.03

26. הכוונה ל There, play proves it...
בתגובה להודעה מספר 25

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

11:36 10.06.03

27. אני כמובן לא יודע לאיית
בתגובה להודעה מספר 25

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

11:47 10.06.03

28. גישה אחרת לפתרון הבעיה
בתגובה להודעה מספר 0

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

DRYICE
אני עכשיו הולך למצוא את הפתרון הישן שלי, ולהעלות אותו.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

19:46 10.06.03

29. משהוא שאני כתבתי
בתגובה להודעה מספר 0

זה נותן תוצאות סבירות, אבל הוא עובד מהר למדיי,
מצורף קובץ C, ומילון קטן.
התוכנית מקבלת קובץ מילון כפרמטר, וטקסט לפרק מקלט סטנדרטי.
DRYICE
קוד C
http://rotter.net/User_files/nor/3ee60afa6800c0e2.txt

מילון קטן:
http://rotter.net/User_files/nor/3ee60b3f697971c1.txt

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד