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

aaaabbccc

אז אנחנו מחליפים את רצף ה a-ים ב a4, את רצף ה b-ים ב b2 ואת רצף ה c-ים ב c3 ומקבלים:

a4b2c3

אם התוצאה ארוכה יותר מהמחרוזת המקורית יש להחזיר את המחרוזת המקורית, ואם התוצאה קצרה יותר יש להחזיר את התוצאה המכווצת.

1. פיתרון

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

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

import re

def compress(original):
    compressed =  re.sub(
            r'(\w)\1*',
            lambda m: m[0][0] + str(len(m[0])),
            original)
    return compressed if len(compressed) < len(original) else original

def test_compress():
    assert compress("a")       == "a"
    assert compress("aaa")     == "a3"
    assert compress("aaabbb")  == "a3b3"
    assert compress("aaabccc") == "a3b1c3"