כמה משולשים יש כאן?

להלן חידה שהתפרסמה בקבוצת "חידות מתמטיות" בפייסבוק:

כמה משולשים יש בציור הזה?

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

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

אנחנו ננסה לפתור את הבעייה בעזרת SQL: זו אינה בעייה ש-DBA אמור להיתקל בה בעבודתו, אבל האתגר הטכני מחייב לחשוב על מידול נכון של הבעייה (אילו טבלאות ידרשו, מה היחסים בינהם, וכיצד ימצא הפתרון לשאלה בעזרתן), להזין את הנתונים, לשלוף את המידע, להשתמש ביכולות שונות של SQL Server; ותוך כדי – לשפר את כישורי ה-SQL שלנו. בנוסף, אפרסם בהמשך פוסט עם פתרון תוך שימוש ב-Geometry Data Type.

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

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

קודם כל אצור טבלת קודקודים עבור 20 הקודקודים שבציור. טבלה זו אינה הכרחית, אבל מכיוון שאנחנו DBA-ים מסודרים ומקצועיים, ננסה לעבוד בצורה מסודרת: בהמשך ניצור טבלת קווים (או צלעות משולשים) כשכל קו מוגדר מצמד קודקודים בסדר עולה (למשל 1,2 או 6,19), הקודקודים יופיעו בהגדרות של הקווים בכל מקרה, אבל הגדרת טבלת קודקודים תאפשר לנו לוודא שלא יוזנו קווים עם קודקודים שאינם קיימים.

If            Object_ID('T_Vertices') Is Null

Create Table T_Vertices --"kodkodim"

              (Name Int,

              Constraint PK_vertices Primary Key Clustered(Name));

Go

Insert

Into   T_Vertices(Name)

Select Name

From   (Values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20)) T(Name)

Where  Not Exists (Select   *

                                    From   T_Vertices T1

                                    Where  T1.Name=T.Name);

Go

הקוד המעט מסורבל בפקודת ה-Insert נועד לוודא שלא ננסה להכניס פעמיים אותם נתונים.

כעת יש לנו טבלת קודקודים עם 20 שורות, כמספר הקודקודים בציור.

וכעת לטבלת הקווים: הטבלה אמורה לכלול צמדים של קודודים שמופיעים בציור כצלעות של משולשים, בכפוף לכללים והאילוצים הבאים:

• ניצור Foreign Keys מתאימים לטבלת הקודקודים כדי לוודא שכולם קיימים.

• כדי למנוע כפילויות נגדיר מפתח ראשי PK על שתי עמודות הקודקודים בטבלת הקווים, ונקבע שהקודקוד הראשון יהיה הקטן יותר (כדי לא להכניס גם את 1,2 וגם את 2,1), ונגדיר על כך אילוץ Check.

• בהמשך נרצה לוודא שלא נקבל משולשים "שטוחים" כמו 1-2-3, ולכן לכל קו נציין על איזה קו ראשי הוא נמצא (נניח- הקו 1,2 נמצא על 1,4; והקו 6,19 על הקו 3,19); וכך נוכל לבדוק ששלוש צלעות המשולש אינן על אותו קו.

Create Table T_Lines 

(Vertix1 Int Not Null,

              Vertix2 Int Not Null,

              VertixMn Int Not Null,

              VertixMx Int Not Null,

              Constraint PK_T_Lines Primary Key Clustered(Vertix1,Vertix2),

              Check (Vertix1<Vertix2),

              Check (VertixMn<=Vertix1),

              Check (Vertix2<=VertixMx),

              Constraint FK_T_Lines_Vertix1 Foreign Key (Vertix1) References T_Vertices(Name),

              Constraint FK_T_Lines_Vertix2 Foreign Key (Vertix2) References T_Vertices(Name),

              Constraint FK_T_Lines_VertixMn Foreign Key (VertixMn) References T_Vertices(Name),

              Constraint FK_T_Lines_VertixMx Foreign Key (VertixMx) References T_Vertices(Name),

              Index Idx_T_Lines Unique(Vertix1,Vertix2));

בטבלה 4 עמודות:  Vertix1 & Vertix2 מגדירות כל אחד מצמדי הקודקודים שיוצרים צלעות של משולשים,ו- VertixMn & VertixMx את הקודקוד המינימלי והמקסימלי בהתאמה של הקו כולו.בנוסף יש PK על צמד הקודקודים,שלושת אילוצי ה-Check נועדו לוודא שהקודקוד הראשון קטן מהשני, שהמינמלי קטן או שווה לראשון, ושהמקסימלי גדול או שווה לשני,ארבעת אילוצי ה-FK נועדו לוודא שהקודקודים קיימים,ולבסוף  אינדקס על הקודקוד המינימלי והמקסימלי.

כיצד נזין את כל הצלעות בלי להתבלבל? הרי הקו 1,4 כולל בתוכו את 6 הצמדים: 1,2 & 1,3 & 1,4 & 2,3 & 2,4 & 3,4 ; ובקווים בני 5 קודקודים המצב מסובך יותר, שלא לדבר על העבודה השחורה הכרוכה בכך..כייאה לעצלנים מדופלמים, נעשה לעצמנו חיים קלים וניצור פרוצדורה שתקבל משתנה טבלה עם כל הקודקודים לאורך הקו, תיצור מהם את כל הצלעות האפשריות, ותכניס לתוך הטבלה הנ"ל תוך שהיא מוודאת שלא נוצרות כפילויות.

תחילה ניצור Type מתאים עבור משתנה הטבלה:

If            Not Exists (Select * From sys.types Where name='TypeVertices')

Create Type TypeVertices

              As Table(Name Int);

וכעת הפרוצדורה שמקבלת כפרמטר את ה-Type הנ"ל:

Create Or Alter Procedure P_Lines

              @T TypeVertices ReadOnly

              As

Declare       @Mn Int,

              @Mx Int;

Select @Mn=Min(Name),

              @Mx=Max(Name)

From   @T;

Insert

Into   T_Lines(Vertix1,Vertix2,VertixMn,VertixMx)

Select T1.Name,

              T2.Name,

              @Mn,

              @Mx

From   @T T1

Inner Join @T T2

              On T1.Name<T2.Name

Where  Not Exists (Select   *

                                    From   T_Lines L

                                    Where  L.Vertix1=T1.Name

                                                  And L.Vertix2=T2.Name);

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

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

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

Declare @T As TypeVertices;

Insert Into   @T Values(1),(2),(3),(4);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(1),(5),(6),(7),(8);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(1),(9),(10),(12);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(1),(13),(14),(16),(17);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(1),(18),(19),(20);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(2),(5),(10),(15),(17);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(3),(5),(9);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(3),(6),(10),(14),(19);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(3),(7),(11),(12);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(4),(8),(12),(17),(20);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(8),(11),(10),(13),(18);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(9),(13),(19);

Exec P_Lines @T;

Go

Declare @T As TypeVertices;

Insert Into   @T Values(12),(15),(16),(19);

Exec P_Lines @T;

Go

כל הכבוד לנו: עד כה הגדרנו את שתי הטבלאות ואיכלסנו (או "פיבלשנו") אותן בנתונים.

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

הדרך הראשונה היא ליצור שלשות של צלעות,

לבדוק שהן מחוברות (כלומר- שהקודקוד של האחת נמצא באחרת), וכדי למנוע כפילויות – משולש יוגדר בסדר עולה של קודקודיו (1,2,5 אבל לא 5,1,2),

וכמובן – ששלוש הצלעות אינן על אותו קו:

Select L1.Vertix1,L2.Vertix1,L3.Vertix2

From   T_Lines L1

Inner Join T_Lines L2

              On L1.Vertix2=L2.Vertix1 And L1.VertixMn<>L2.VertixMn

Inner Join T_Lines L3

              On L2.Vertix2=L3.Vertix2

              And L3.Vertix1=L1.Vertix1;

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

הדרך השנייה היא ליצור שלשות של קודקודים (ולא של צלעות כנ"ל!) בסדר עולה,

לוודא שהם מחוברים בצלעות,

ושהן אינן על אותו קו:

Select V1.Name,V2.Name,V3.Name

From   T_Vertices V1

Inner Join T_Vertices V2

              On V1.Name<V2.Name

Inner Join T_Vertices V3

              On V2.Name<V3.Name

Cross Apply (Select  L1.VertixMn

                      From   T_Lines L1

                      Where  L1.Vertix1=V1.Name And L1.Vertix2=V2.Name) L1

Cross Apply (Select  L2.VertixMn

                      From   T_Lines L2

                      Where  L2.Vertix1=V2.Name And L2.Vertix2=V3.Name) L2

Cross Apply (Select  L3.VertixMn

                      From   T_Lines L3

                      Where  L3.Vertix1=V1.Name And L3.Vertix2=V3.Name) L3

Where         L1.VertixMn<>L2.VertixMn;

פסוקיות ה-From & Inner Join יוצרות את השלשות,פסוקיות ה-Cross Join מוודאות שיש לכל צמד מהשלוש צלע מתאימה,וה-Where מוודא שלפחות שתי הצלעות הראשונות שונות.

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

נעיין ב-Execution Plans:

משולשי האזהרה הצהובים ליד חלק מפעולות ה-Seek & Scan מלמדות שאין לטבלת T_Lines סטטיסטיקה מתאימה, מה שעלול לגרום לבחירת תוכנית לא אופטימלית.את זה נפתור בעזרת הפקודה הבאה:

Update Statistics T_Lines;

וכעת נקבל תוכנית המתבססת על סטטיסטיקה מעודכנת.

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