175. Solving 1,5,6,7

Expression Trees, Math Puzzles

פעם שעברה ראינו שאפשר לקמפל Expression Tree לAnonymous Delegate.

היום נראה משהו יפה שאפשר לעשות עם זה.

יש חידה מפורסמת שהולכת ככה: נתונים המספרים 1,5,6,7 (כל מספר בדיוק פעם אחת). איך אפשר להגיע למספר 21 ע”י הוספת פעולות חשבון וסוגריים בין המספרים?

חידה זו אינה דורשת ידע מתמטי לפתרון, אלא דורשת בדיקה של הרבה אפשרויות…

נראה איך אפשר לפתור אותה באמצעות Expression Trees.

ראשית נכתוב משהו כזה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static IEnumerable<Expression> GetAllExpressions(IEnumerable<double> numbers)
{
    if (numbers.Count() == 1)
    {
        yield return Expression.Constant(numbers.First());
    }
    foreach (double number in numbers)
    {
        IEnumerable<Expression> expressionsWithoutNumber =
            GetAllExpressions(numbers.Except(new[] {number}));
        foreach (Expression expression in expressionsWithoutNumber)
        {
            yield return Expression.Add(Expression.Constant(number), expression);
            yield return Expression.Subtract(Expression.Constant(number), expression);
            yield return Expression.Multiply(Expression.Constant(number), expression);
            yield return Expression.Divide(Expression.Constant(number), expression);
        }
    }
}

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

איך זה עובד?

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

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

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

(Expression.Constant מייצג איבר שהוא קבוע בExpression Tree, בניגוד לParameter שמייצג פרמטר של הExpression)

זה מאוד מזכיר את הקוד שראינו שמחשב את כל התמורות של אוסף נתון.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private static IEnumerable<Expression> GetAllExpressions(IEnumerable<double> numbers)
{
    if (numbers.Count() == 1)
    {
        yield return Expression.Constant(numbers.FirstOrDefault());
    }
    foreach (double number in numbers)
    {
        var expressionsWithoutNumber =
            GetAllExpressions(numbers.Except(new[] {number}));
        foreach (Expression expression in expressionsWithoutNumber)
        {
            yield return Expression.Add(Expression.Constant(number), expression);
            yield return Expression.Subtract(Expression.Constant(number), expression);
            yield return Expression.Multiply(Expression.Constant(number), expression);
            Func<double> denominator =
                Expression.Lambda<Func<double>>(expression).Compile();
            if (denominator() != 0)
            {
                yield return Expression.Divide(Expression.Constant(number), expression);
            }
        }
    }
}

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

כעת נוכל לפתור את החידה:

נקרא לפונקציה GetAllExpressions עם האוסף 1,5,6,7 ונבדוק מתי יוצא 21:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
IEnumerable<Expression> expressions =
    GetAllExpressions(new double[] {1, 5, 6, 7});
foreach (Expression currentExpression in expressions)
{
    Expression<Func<double>> currentLambda =
        Expression.Lambda<Func<double>>(currentExpression);
    Func<double> currentDelegate = currentLambda.Compile();
    // We check when the expression represents 21
    if (currentDelegate() == 21) 
    {
        Console.WriteLine("21 = {0}", currentExpression);
    }
}
// 21 = (6 / (1 - (5 / 7)))

יאללה, $ \displaystyle{21 = \frac{6}{1 - \frac{5}{7}} = 6\div\left(1-5\div7\right) } $. מי היה מאמין?

הערה: הריצה על הערכים כאן עובדת במקרה: היא מחפשת רק ביטויים מצורה מאוד ספציפית: $ a\#\left(b\#\left(c\#d\right)\right) $. במקום זאת, הדבר הנכון לעשות זה לרוץ על כל התת-קבוצות של האיברים שקיבלנו: על כל תת-קבוצה למצוא את כל הערכים שהיא מניבה, לעשות כנ"ל על הקבוצה המשלימה שלה, ולבצע על כל האפשרויות של שתיהן את 4 פעולות החשבון.

המשך ערב טוב

שתף