Browsed by
קטגוריה: Algorithmic

Look and Say

Look and Say

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

באחת החידות מופיעה הסדרה הבאה:

a = [1, 11, 21, 1211, 111221

והחידה היא:

len(a[30]) = ?

המטרה היא כמובן למצוא את החוקיות של הסדרה, ואז למצוא את אורך האיבר ה- 30.

פתרון

הסדרה נקראת "Look and Say". בכל איבר בסדרה (מלבד הראשון) מקריאים (ורושמים) את מספר הספרות שמתארות את האיבר הקודם. כלומר, אם התחלנו ב- 1, אז האיבר שני יתאר פעם אחת 1 – 11. האיבר השלישי יתאר פעמיים 1 – 21. האיבר הרביעי יתאר פעם אחת 2 ופעם אחת 1 – 1211, וכן הלאה.

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

קוד

נתחיל מפתרון נאיבי:

first = '1'
second = ''
for i in range(0, 30):
    j = 0
    k = 0
    while j < len(first):
        while k < len(first) and first[k] == first[j]:
            k += 1
        second += str(k-j) + first[j]
        j = k
    print second
    first = second
    second = ''
print "Final answer:", len(first)

ההתייחסות לכל איבר בסדרה היא כ- string ולא כמספר. בכל איטרציה רצים על התוים משמאל לימין וסופרים את מספר הפעמים בהם תו מסויים מופיע ברצף.

ב- Python יש כלי שיכול לפשט משמעותית את הקוד הנ"ל. נשתמש בספריית re (המשמשת ל- regular expressions) כדי למצוא אורך של תו בכל הופעה שלו. לדוגמא:

re.findall("(\\d)(\\1*)", "111221")

נקבל כתשובה:

[('1', '11'), ('2', '2'), ('1', ")]

קיבלנו מערך של צמדים (tuples) – באיבר הראשון יש את התו של הרצף הנוכחי, ואחריו את שארית הרצף. אם נעבור על המערך ומכל צמד ניקח את אורך האיבר שני (פלוס 1) ונצמיד אותו לאיבר הראשון (שהוא התו הנוכחי של הרצף) נקבל את התוצאה הרצויה – האיבר הבא בסדרה. לדוגמא במערך הנ"ל: האורך של '11' + 1, עם התו '1' => 31. האורך של '2' + 1, עם התו '2' => 22. האורך של " + 1, עם התו '1' => 11. ולסיכום: 312211.

ובקוד:

"".join([str(len(i+j))+i for i,j in re.findall(r"(\d)(\1*)", 111221)])

זה נותן לנו את האפשרות להזין איבר ולקבל את האיבר הבא. עכשיו נעשה את זה עבור האיבר ה- 30:

import re
 
current = "1" #start from '1'
for n in range(30):
    current = "".join([str(len(j) + 1)+i for i, j in re.findall(r"(\d)(\1*)", current)])
 
print "Final answer:", len(current)

התשובה, אגב, היא 5808.

Get Alive

Get Alive

lenna

זו Lenna. כל מאמר שעוסק ב- image proccessing משתמש בתמונה הזו להדגמה (למה? תקראו בלינק).

אני רוצה להראות עליה איך יוצרים מתמונה רגילה, animated gif:

fadeinlenna

תאוריה

בתור התחלה, צריך ליצור תמונת בסיס ממנה ניצור את הפריימים שיהיו ב- gif הסופי:

  • נמיר את התמונה המקורית ל- grayscale (שחור-לבן).
  • נפעיל על התמונה פילטר של ״זיהוי קצוות״ (edge detection). ישנם מספר פילטרים שעושים את זה, כמו sobel או canny. הרעיון הוא, שהם מדגישים את השינויים הבולטים בין הפיקסלים בתמונה. בצורה כזו נקבל מעין "sketch" של התמונה.
  • התוצר של edge detection יהיה לבן על רקע שחור, לכן נעשה inversion (היפוך צבעים) – ונקבל את תמונת הבסיס.

תכלס

בשביל המימוש נשתמש בספריית Pillow, שהיא fork מתוך PIL הותיקה – ספריית python לעיבוד תמונה.

נפתח טרמינל python, ונתחיל עם הפקודות הבאות:

>>> from PIL import Image
>>> im = Image.open("Lenna.png")

נשנה את התמונה ל- grayscale, כלומר שרק חלק ה- Luminance יישאר:

>>> im = im.convert("L")
>>> im.show()

וזו התוצאה:

screen-shot-2016-11-30-at-15-03-24

נפעיל את ה- edge detection המובנה של PIL:

>>> from PIL import ImageFilter
>>> im = im.filter(ImageFilter.FIND_EDGES)
>>> im.show()

ונקבל:

screen-shot-2016-11-30-at-15-06-36

מה שנשאר זה רק לעשות invert, כלומר להפוך את הצבעים:

>>> from PIL import ImageOps
>>> im = ImageOps.invert(im)
>>> im.show()

זו התמונה הסופית איתה נעבוד:

screen-shot-2016-11-30-at-15-07-24

סקריפט

נרכז את כל הקוד הנ״ל לסקריפט הזה:

import sys, os, shutil
import numpy as np
from PIL import Image, ImageFilter, ImageOps
 
if len(sys.argv) > 1:
    imageFileName = sys.argv[1]
else:
    print "arg not found."
    sys.exit()
# load image
original = Image.open(imageFileName)
# convert to grayscale -> find edges -> invert
edges = ImageOps.invert(original.convert("L").filter(ImageFilter.FIND_EDGES))

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

def changeColors(image, bgColor, threshold):
    # Because we want to support in colorful gifs - to allow rgb bgColor -
    # we covert the image back to rgb
    image = image.convert("RGB")
    # We use numpy to work with the image data array directly
    data = np.array(image)
    # Get the three channels of the image to compare to
    red, green, blue = data[:,:,0], data[:,:,1], data[:,:,2]
    # Create mask to check if all channels (that probably all the same)
    # are bigger than threshold
    bgMask = (red > threshold) & (green > threshold) & (blue > threshold)
    # Replace all pixels that fit for the criteria with the bg color
    data[:,:,:3][bgMask] = bgColor
    # create back image from data array
    return Image.fromarray(data)

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

folderName = "gifTemp"
filePath = "{0}/{1}.png"
for threshold in range(0, 255, 25):
    changeColors(image.copy(), bgColor, threshold).save(filePath.format(folderName, index))
    index += 1

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

בעיקרון, יש דרך ליצור מתוך python קבצי animated gif. לדוגמא images2gif. אבל בכל האפשרויות שניסיתי, לא הייתי מרוצה – מבחינת איכות ונפח הקובץ של התוצאה.

לכן בחרתי להשתמש בכלים חיצוניים ffmpeg ו- gifsicle. הם open source, וקיימים בדר״כ בסביבות פיתוח (לפחות ffmpeg).

נוסיף לסקריפט שלנו שתי פקודות:

os.system("ffmpeg -i " + folderName + "/%01d.png gifResults/fadeIn.gif")

הפקודה הזו מריצה את ffmpeg שלוקח את כל קבצי png שקיימים בתיקייה ומתחילים במספר – לפי הסדר – ויוצר מהם gif בשם fadeIn.

עכשיו הבעיה היא התזמון. אנחנו רוצים שכל הפריימים יהיו אותו זמן, חוץ מהאחרון – שם אנחנו רוצים להתעכב קצת, שנוכל לשים לב לתמונה הסופית. בשביל זה נריץ את gifsicle:

os.system("gifsicle -b gifResults/fadeIn.gif -d10 '#0--2' -d75 '#-1'")

פריים "-1" – כלומר הפריים האחרון מהסוף יהיה 0.75 שנייה (שנייה שלמה זה 100), וכל שאר הפריימים יהיו עשירית שנייה.

אפשר למצוא את הסקריפט המלא כאן.

 

חידת הרכבת

חידת הרכבת

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

train

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

class Node:
    def __init__(self):
        self.paths = []

כל node מצביע על רשימת nodes אחרת – או על אף node במקרה של האחרון (וזה יהיה תנאי העצירה).

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

a = Node()
b = Node()
c = Node()
d = Node()
e = Node()
f = Node()
 
a.paths = [b]
b.paths = [c, c, c, d]
c.paths = [d, e]
d.paths = [e, e, e]
e.paths = [f]

נעבור רקורסיבית על העץ-

def iterate (node):
    counter = 0
    if node.paths == []:
        return 1
    for p in node.paths:
        counter = counter + iterate(p)
    return counter

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

ways = iterate(a)
 
print "ways: " + str(ways)

לא אגלה את התוצאה, מוזמנים להריץ את הסקריפט 🙂

——————————–

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

כדי לפתור את זה, נשנה גישה. נתאר את הגרף בעזרת מטריצה-

A B C D E F
A 1
B 1 3 1
C 3 1 1
D 1 1 3
E 1 3 1
F 1

ניצור מערך דו-מימדי עם הנתונים האלו:

a = [0, 1, 0, 0, 0, 0]
b = [1, 0, 3, 1, 0, 0]
c = [0, 3, 0, 1, 1, 0]
d = [0, 1, 1, 0, 3, 0]
e = [0, 0, 1, 3, 0, 1]
f = [0, 0, 0, 0, 1, 0]
 
mat = [a, b, c, d, e, f]

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

לכן נתרגם את המטריצה הזו לתת רשימות:

def createLists(m):
    newMat = []
    for line in m:
        newLine = []
        for cell in line:
            newCell = []
            for i in range(cell):
                newCell.append(i)
            newLine.append(newCell)
        newMat.append(newLine)
    return newMat

בצורה כזו נתרגם כל מספר לרשימה, כלומר 0 יהיה [], ו- 3 יהיה [0, 1 ,2].

נפעיל על המטריצה את הפונקציה הזו:

def iterateMat(m, index):
    if index == 5:
        return 1
    counter = 0
    line = m[index]
    for i in range(len(line)):
        if len(line[i]) > 0:
            for cell in line[i]:
                #deep copying
                newMat = copy.deepcopy(m)
 
                newMat[index][i].remove(cell)
                newMat[i][index].remove(cell)
                counter += iterateMat(newMat, i)
 
    return counter

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

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

mat = createLists([a, b, c, d, e, f])
ways = iterateMat(mat, 0)
 
print "ways: " + str(ways)

אגב, התשובה היא 640.