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

1. מה צריך לעשות

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

לכן בחשבון המוזר של החבר התרגיל הבא ייתן את התוצאה 8:

2 + 2 * 2

איך זה עובד? קודם מחברים את ה 2 + 2 כדי לקבל 4, ואז את התוצאה כופלים ב-2 ומקבלים שמונה. התרגיל הבא עם סוגריים נותן 51:

1 + (2 * 3) + (4 * (5 + 6))

נתחיל עם הסוגריים הפנימיים בצד ימין, כלומר נחבר 5 ו-6 כדי לקבל 11, אותו נכפול ב-4 כדי לקבל 44, לזה נחבר את תוצאת הסוגריים הבאים (6) ואת 1, סך הכל 44 ועוד 7 שווה 51.

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

2. הגישה היוניקסאית: אפשר לכתוב מחשבון עם Bison ו Flex

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

https://github.com/meyerd/flex-bison-example

אני מתחיל עם הקובץ calc.l שהוא הקלט ל flex, כלומר זה הקובץ שמגדיר איזה טוקנים אני הולך לראות:

%option noyywrap

%{
#include <stdio.h>

#define YY_DECL int yylex()

#include "calc.tab.h"

%}

%%

[ \t]   ; // ignore all whitespace
[0-9]+      {yylval.ival = atoi(yytext);
\n      {return T_NEWLINE;}
"+"     {return T_PLUS;}
"*"     {return T_MULTIPLY;}
"("     {return T_LEFT;}
")"     {return T_RIGHT;}
"exit"      {return T_QUIT;}
"quit"      {return T_QUIT;}

%%

החלק החשוב בקובץ הוא הסוף שלו: אני מגדיר שמספרים יעדכנו משתנה (שמוגדר בקובץ השני) להכיל את הערך המספרי שלהם; פעולות הפלוס והכפול ייקראו T_PLUS ו T_MULTIPLY ונתתי גם שמות לפעולות הסוגריים, ירידת שורה ולמילים exit ו quit.

הקובץ השני בדוגמה וגם הארוך יותר הוא calc.y. רוב הקוד הוא Boilerplate והתוכן המלא נראה כך:

%{

#include <stdio.h>
#include <stdlib.h>

extern int yylex();
extern int yyparse();
extern FILE* yyin;

void yyerror(const char* s);
%}

%union {
  unsigned long ival;
}

%token<ival> T_INT
%token T_PLUS T_MULTIPLY T_LEFT T_RIGHT
%token T_NEWLINE T_QUIT
%left T_MULTIPLY
%left T_PLUS

%type<ival> expression

%start calculation

%%

calculation:
       | calculation line
;

line: T_NEWLINE
    | expression T_NEWLINE { printf("%ld\n", $1); }
    | T_QUIT T_NEWLINE { exit(0); }
;

expression: T_INT               { $$ = $1; }
      | expression T_PLUS expression    { $$ = $1 + $3; }
      | expression T_MULTIPLY expression    { $$ = $1 * $3; }
      | T_LEFT expression T_RIGHT       { $$ = $2; }
;

%%

int main() {
    yyin = stdin;

    do {
        yyparse();
    } while(!feof(yyin));

    return 0;
}

void yyerror(const char* s) {
    fprintf(stderr, "Parse error: %s\n", s);
    exit(1);
}

החלק החשוב בקובץ זה הוא השורות שמתחילות ב %left. שורות אלה קובעות את סדר הפעולות כאשר מה שמופיע נמוך יותר בקובץ הוא בעל קדימות גבוהה יותר. בדוגמה שלנו השורות:

%left T_MULTIPLY
%left T_PLUS

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

expression: T_INT               { $$ = $1; }
      | expression T_PLUS expression    { $$ = $1 + $3; }
      | expression T_MULTIPLY expression    { $$ = $1 * $3; }
      | T_LEFT expression T_RIGHT       { $$ = $2; }
;

והוא די מסביר את עצמו.

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

$ bison -t -v -d calc.y
$ flex calc.l
$ gcc -o calc calc.tab.c lex.yy.c

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

./calc < ../input/day18.txt

3. הגישה הרגולארית: אפשר להחליף ביטוי רגולארי בתוצאה של פונקציה

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

במקרה של המחשבון ההפוך יש לנו 3 אופרטורים עם סדר קדימויות לקחת בחשבון:

1. סוגריים, אותם צריך לפתור לפני הכל

2. חיבור, אותו צריך לפתור כשאין יותר סוגריים

3. כפל, אותו נפתור כשסיימנו את כל תרגילי החיבור

לכן אני יכול לכתוב פונקציה שתעבוד כך:

1. אם יש סוגריים בביטוי, היא תיקח את הסוגריים הפנימיים ביותר ותנסה לפתור אותם

2. אם יש פלוס בביטוי היא תחפש את שני המספרים שסביבו ותחליף את כל השלישיה בתוצאת החיבור (אנחנו יודעים שזה מספרים, כי אם היו סוגריים מסביב לפלוס היינו נכנסים פנימה לפתור אותם לפי סעיף 1)

3. אם יש כפל בביטוי היא תחפש את שני המספרים שסביבו ותחליף את כל השלישייה במכפלה.

זאת הדרך בה אני פתרתי את התרגיל במקור וקוד הפונקציה בשפת Elixir נראה כך:

  def solve_part2(expr) do
    cond do
      String.contains?(expr, "(") ->
        Regex.replace(~r/\(([^()]+)\)/, expr, fn _, expr -> solve_part2(expr) end)
        |> solve_part2

      String.contains?(expr, "+") ->
        Regex.replace(~r/(\d+) \+ (\d+)/, expr, fn
          _, op1, op2 -> Integer.to_string(String.to_integer(op1) + String.to_integer(op2))
        end)
        |> solve_part2

      String.contains?(expr, "*") ->
        Regex.replace(~r/(\d+) \* (\d+)/, expr, fn
          _, op1, op2 -> Integer.to_string(String.to_integer(op1) * String.to_integer(op2))
        end)
        |> solve_part2

        true -> expr
    end
  end

4. הגישה מונחית העצמים: אפשר לשנות את משמעות האופרטורים של השפה

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

class Integer
  alias_method :real_plus, :+
  alias_method :real_mul, :*

  def -(other)
    self.real_mul(other)
  end

  def *(other)
    self.real_plus(other)
  end

end

def solve(expr)
  puts(eval(expr.gsub("*", "-").gsub("+", "*")))
end

solve("2 + 2 * 2")
solve("1 + (2 * 3) + (4 * (5 + 6))")

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