הבלוג של גרי רשף

11/10/2011

משחק החיים

Filed under: Uncategorized — גרי רשף @ 21:28

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

clip_image002

If Object_ID('T_Hayim') Is Not Null Drop Table T_Hayim;
Go

Create Table T_Hayim(X Int,
                    Y Int,
                    Constraint PK_T_Hayim Primary Key Clustered(X,Y));
Go

Insert
Into T_Hayim
Values (2,1),(2,2),(2,3);
Go

Select *
From   T_Hayim;
Go

clip_image004

כדי לחשב את מצב הלוח בשלב הבא נצטרך להתייחס ללוח הנ"ל עם השורות והעמודות מסביב ששלולות להיות מושפעות מהתאים "החיים" (כלומר- עם עמודות X-0,X=4 ושורות Y=0,Y=4),

ולבדוק בכל תא כמה תאים "חיים" סביבו.

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

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

התא מעל הוא ה-Lag לפי X, התא משמאל הוא ה-Lag לפי Y, התאים מימין ומשמאל הם ה-Lead-ים בהתאם.

התא משמאל למעלה (באלכסון) הוא ה-Lag לפי Y-X (כלומר- לאורך האלכסונים היורדים משמאל לימין הערך Y-X קבוע לכל אלכסון),

התא משמאל למטה (באלכסון) הוא ה-Lag לפי Y+X (כלומר- לאורך האלכסונים העולים משמאל לימין הערך Y+X קבוע לכל אלכסון),

והתאים מימין למעלה ומימין למטה הם ה-Lead-ים בהתאם.

בהזדמנות חגיגית זו נשתמש גם בפונקצית התנאי המיידית IIF שמהווה חלופה נוחהל-Case When במקרים פשוטים בהם יש שתי אופציות:

With T As
(Select Min(X) Mnx,
        Max(X) Mxx,
        Min(Y) Mny,
        Max(Y) Mxy
From    T_Hayim),
Nm As
(Select Iif(Mnx<Mny,Mnx-1,Mny-1) N
From    T
Union All
Select  N+1 N
From    Nm
Cross Join T
Where   N<Iif(Mxx>Mxy,Mxx+1,Mxy+1)),
T1 As
(Select Nmx.N [X],
        Nmy.N [Y],
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N-Nmx.N Order By Nmx.N) As SmallInt) A1,
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmx.N Order By Nmy.N) As SmallInt) A2,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N+Nmx.N Order By
        Nmx.N) As SmallInt) A3,
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N Order By Nmx.N) As SmallInt) A4,
        Iif(Th.X Is Null,0,1) A5,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N Order By Nmx.N) As SmallInt) A6,
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N+Nmx.N Order By Nmx.N) As SmallInt) A7,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmx.N Order By Nmy.N) As SmallInt) A8,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N-Nmx.N Order By Nmy.N) As SmallInt) A9
From    T
Inner Join Nm Nmx
        On Nmx.N Between T.Mnx-1 And T.Mxx+1
Inner Join Nm Nmy
        On Nmy.N Between T.Mny-1 And T.Mxy+1
Left Join T_Hayim Th
        On Nmx.N=Th.X
        And Nmy.N=Th.Y)
Select  *,
        Case A1+A2+A3+A4+A6+A7+A8+A9
            When 0 Then 0
            When 1 Then 0
            When 2 Then A5
            When 3 Then 1
            When 4 Then 0
            When 5 Then 0
            When 6 Then 0
            When 7 Then 0
            When 8 Then 0
            End NewA5
From    T1
Order By X,
        Y;

clip_image006

לצורך הנוחות אני אמספר את התאים סביב כל תא כך:

clip_image008

כלומר- אם אנחנו מסתכלים מנקודת מבטו של תא X=1, Y=1 אזי תאים 1,2,3,4,7 הם מחוץ לתחום ולכן ערכם 0,

בתאים 6,8 הערך הוא 0 (תא 6 X=3,Y=2, תא 8 X=2,Y=3),

ובתא 9 הערך הוא 1 (תא 9 X=3,Y=3).

בפלט של השאילתה- A1..A9 מציינים את "השכנים" של כל תא, כאשר A5 שבמרכז הוא התא עצמו.

הערה טכנית- טבלת המספרים כוללת את כל המספרים מהמינימום מבין ערכי X ו-Y (פחות 1),

ועד למקסימום מבין ערכי X ו-Y (ועוד 1).

העמודה השמאלית NewA5 מציגה את ערכו המחושב של התא בשלב הבא.

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

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

לפיכך אין ברירה אלא להשתמש בלולאה.

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

If Object_ID('T_Hayim') Is Not Null Drop Table T_Hayim;
Go

Create Table T_Hayim(Shlav Int,
                    X Int,
                    Y Int,
                    Constraint PK_T_Hayim Primary Key Clustered(Shlav,X,Y));
Go

Insert
Into T_Hayim
Values (1,2,1),(1,2,2),(1,2,3);
Go

Select  *
From    T_Hayim;
Go

clip_image010

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

Declare @Shlav Int=2,
               @I Int=1;

While @I<=@Shlav
Begin

Select  *
From    (Select X,Y,Iif(X Is Null,0,1) XY From T_Hayim Where Shlav=@I) Th
Pivot   (Max(XY) For Y In ([0],[1],[2],[3],[4])) P;

Delete
From    T_Hayim
Where   Shlav=@I+1;
With T As
(Select Min(X) Mnx,
        Max(X) Mxx,
        Min(Y) Mny,
        Max(Y) Mxy
From    T_Hayim
Where   Shlav=@I),
Nm As
(Select Iif(Mnx<Mny,Mnx-1,Mny-1) N
From    T
Union All
Select  N+1 N
From    Nm
Cross Join T
Where   N<Iif(Mxx>Mxy,Mxx+1,Mxy+1)),
T1 As
(Select Nmx.N [X],
        Nmy.N [Y],
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N-Nmx.N Order By Nmx.N) As SmallInt) A1,
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmx.N Order By Nmy.N) As SmallInt) A2,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N+Nmx.N Order By Nmx.N) As SmallInt) A3,
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N Order By Nmx.N) As SmallInt) A4,
        Iif(Th.X Is Null,0,1) A5,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N Order By Nmx.N) As SmallInt) A6,
        Cast(Lag(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N+Nmx.N Order By Nmx.N) As SmallInt) A7,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmx.N Order By Nmy.N) As SmallInt) A8,
        Cast(Lead(Iif(Th.X Is Null,0,1),1,0) Over(Partition By Nmy.N-Nmx.N Order By Nmy.N) As SmallInt) A9
From    T
Inner Join Nm Nmx
        On Nmx.N Between T.Mnx-1 And T.Mxx+1
Inner Join Nm Nmy
        On Nmy.N Between T.Mny-1 And T.Mxy+1
Left Join T_Hayim Th
        On Nmx.N=Th.X
        And Nmy.N=Th.Y
        And Shlav=@I), --Where-הפילטור צריך להתבצע כאן ולא ב
T2 As
(Select *,
        Case A1+A2+A3+A4+A6+A7+A8+A9
            When 0 Then 0
            When 1 Then 0
            When 2 Then A5
            When 3 Then 1
            When 4 Then 0
            When 5 Then 0
            When 6 Then 0
            When 7 Then 0
            When 8 Then 0
            End NewA5
From    T1)
Insert
Into    T_Hayim(Shlav,X,Y)
Select  @I+1 Shlav,
        X,
        Y
From    T2
Where   NewA5=1
Order By X,
        Y;

Set @I+=1; --ככה מוסיפים 1

End

Select  *
From    (Select X,Y,Iif(X Is Null,0,1) XY From T_Hayim Where Shlav=@I) Th
Pivot   (Max(XY) For Y In ([0],[1],[2],[3],[4])) P;

clip_image012

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

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: