task

Write a program that takes four digits, either from user input or by random generation, and computes arithmetic expressions following the rules of the 24 game.

Show examples of solutions generated by the program.



Related task

   Arithmetic Evaluator


using System;
using System.Collections.Generic;
using static System.Linq.Enumerable;
 
public static class Solve24Game
{
    public static void Main2() {
        var testCases = new [] {
            new [] { 1,1,2,7 },
            new [] { 1,2,3,4 },
            new [] { 1,2,4,5 },
            new [] { 1,2,7,7 },
            new [] { 1,4,5,6 },
            new [] { 3,3,8,8 },
            new [] { 4,4,5,9 },
            new [] { 5,5,5,5 },
            new [] { 5,6,7,8 },
            new [] { 6,6,6,6 },
            new [] { 6,7,8,9 },
        };
        foreach (var t in testCases) Test(24, t);
        Test(100, 9,9,9,9,9,9);
 
        static void Test(int target, params int[] numbers) {
            foreach (var eq in GenerateEquations(target, numbers)) Console.WriteLine(eq);
            Console.WriteLine();
        }
    }
 
    static readonly char[] ops = { '*', '/', '+', '-' };
    public static IEnumerable<string> GenerateEquations(int target, params int[] numbers) {
        var operators = Repeat(ops, numbers.Length - 1).CartesianProduct().Select(e => e.ToArray()).ToList();
        return (
            from pattern in Patterns(numbers.Length)
            let expression = CreateExpression(pattern)
            from ops in operators
            where expression.WithOperators(ops).HasPreferredTree()
            from permutation in Permutations(numbers)
            let expr = expression.WithValues(permutation)
            where expr.Value == target && expr.HasPreferredValues()
            select $"{expr.ToString()} = {target}")
            .Distinct()
            .DefaultIfEmpty($"Cannot make {target} with {string.Join(", ", numbers)}");
    }
 
    ///<summary>Generates postfix expression trees where 1's represent operators and 0's represent numbers.</summary>
    static IEnumerable<int> Patterns(int length) {
        if (length == 1) yield return 0; //0
        if (length == 2) yield return 1; //001
        if (length < 3) yield break;
        //Of each tree, the first 2 bits must always be 0 and the last bit must be 1. Generate the bits in between.
        length -= 2;
        int len = length * 2 + 3;
        foreach (int permutation in BinaryPatterns(length, length * 2)) {
            (int p, int l) = ((permutation << 1) + 1, len);
            if (IsValidPattern(ref p, ref l)) yield return (permutation << 1) + 1;
        }
    }
 
    ///<summary>Generates all numbers with the given number of 1's and total length.</summary>
    static IEnumerable<int> BinaryPatterns(int ones, int length) {
        int initial = (1 << ones) - 1;
        int blockMask = (1 << length) - 1;
        for (int v = initial; v >= initial; ) {
            yield return v;
            int w = (v | (v - 1)) + 1;
            w |= (((w & -w) / (v & -v)) >> 1) - 1;
            v = w & blockMask;
        }
    }
 
    static bool IsValidPattern(ref int pattern, ref int len) {
        bool isNumber = (pattern & 1) == 0;
        pattern >>= 1;
        len--;
        if (isNumber) return true;
        IsValidPattern(ref pattern, ref len);
        IsValidPattern(ref pattern, ref len);
        return len == 0;
    }
 
    static Expr CreateExpression(int pattern) {
        return Create();
 
        Expr Create() {
            bool isNumber = (pattern & 1) == 0;
            pattern >>= 1;
            if (isNumber) return new Const(0);
            Expr right = Create();
            Expr left = Create();
            return new Binary('*', left, right);
        }
    }
 
    static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Empty<T>() };
        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
                from acc in accumulator
                from item in sequence
                select acc.Concat(new [] { item }));
    }
 
    private static List<int> helper = new List<int>();
    public static IEnumerable<T[]> Permutations<T>(params T[] input) {
        if (input == null || input.Length == 0) yield break;
        helper.Clear();
        for (int i = 0; i < input.Length; i++) helper.Add(i);
        while (true) {
            yield return input;
            int cursor = helper.Count - 2;
            while (cursor >= 0 && helper[cursor] > helper[cursor + 1]) cursor--;
            if (cursor < 0) break;
            int i = helper.Count - 1;
            while (i > cursor && helper[i] < helper[cursor]) i--;
            (helper[cursor], helper[i]) = (helper[i], helper[cursor]);
            (input[cursor], input[i]) = (input[i], input[cursor]);
            int firstIndex = cursor + 1;
            for (int lastIndex = helper.Count - 1; lastIndex > firstIndex; ++firstIndex, --lastIndex) {
                (helper[firstIndex], helper[lastIndex]) = (helper[lastIndex], helper[firstIndex]);
                (input[firstIndex], input[lastIndex]) = (input[lastIndex], input[firstIndex]);
            }
        }
    }
 
    static Expr WithOperators(this Expr expr, char[] operators) {
        int i = 0;
        SetOperators(expr, operators, ref i);
        return expr;
 
        static void SetOperators(Expr expr, char[] operators, ref int i) {
            if (expr is Binary b) {
                b.Symbol = operators[i++];
                SetOperators(b.Right, operators, ref i);
                SetOperators(b.Left, operators, ref i);
            }
        }
    }
 
    static Expr WithValues(this Expr expr, int[] values) {
        int i = 0;
        SetValues(expr, values, ref i);
        return expr;
 
        static void SetValues(Expr expr, int[] values, ref int i) {
            if (expr is Binary b) {
                SetValues(b.Left, values, ref i);
                SetValues(b.Right, values, ref i);
            } else {
                expr.Value = values[i++];
            }
        }
    }
 
    static bool HasPreferredTree(this Expr expr) => expr switch {
        Const _ => true,
 
        // a / b * c => a * c / b
        ((_, '/' ,_), '*', _) => false,
        // c + a * b => a * b + c
        (var l, '+', (_, '*' ,_) r) when l.Depth < r.Depth => false,
        // c + a / b => a / b + c
        (var l, '+', (_, '/' ,_) r) when l.Depth < r.Depth => false,
        // a * (b + c) => (b + c) * a
        (var l, '*', (_, '+' ,_) r) when l.Depth < r.Depth => false,
        // a * (b - c) => (b - c) * a
        (var l, '*', (_, '-' ,_) r) when l.Depth < r.Depth => false,
        // (a +- b) + (c */ d) => ((c */ d) + a) +- b
        ((_, var p, _), '+', (_, var q, _)) when "+-".Contains(p) && "*/".Contains(q) => false,
        // a + (b + c) => (a + b) + c
        (var l, '+', (_, '+' ,_) r) => false,
        // a + (b - c) => (a + b) - c
        (var l, '+', (_, '-' ,_) r) => false,
        // a - (b + c) => (a - b) + c
        (_, '-', (_, '+', _)) => false,
        // a * (b * c) => (a * b) * c
        (var l, '*', (_, '*' ,_) r) => false,
        // a * (b / c) => (a * b) / c
        (var l, '*', (_, '/' ,_) r) => false,
        // a / (b / c) => (a * c) / b
        (var l, '/', (_, '/' ,_) r) => false,
        // a - (b - c) * d => (c - b) * d + a
        (_, '-', ((_, '-' ,_), '*', _)) => false,
        // a - (b - c) / d => (c - b) / d + a
        (_, '-', ((_, '-' ,_), '/', _)) => false,
        // a - (b - c) => a + c - b
        (_, '-', (_, '-', _)) => false,
        // (a - b) + c => (a + c) - b
        ((_, '-', var b), '+', var c) => false,
 
        (var l, _, var r) => l.HasPreferredTree() && r.HasPreferredTree()
    };
 
    static bool HasPreferredValues(this Expr expr) => expr switch {
        Const _ => true,
 
        // -a + b => b - a
        (var l, '+', var r) when l.Value < 0 && r.Value >= 0 => false,
        // b * a => a * b
        (var l, '*', var r) when l.Depth == r.Depth && l.Value > r.Value => false,
        // b + a => a + b
        (var l, '+', var r) when l.Depth == r.Depth && l.Value > r.Value => false,
        // (b o c) * (a o d) => (a o d) * (b o c)
        ((var a, _, _) l, '*', (var c, _, _) r) when l.Value == r.Value && l.Depth == r.Depth && a.Value < c.Value => false,
        // (b o c) + (a o d) => (a o d) + (b o c)
        ((var a, var p, _) l, '+', (var c, var q, _) r) when l.Value == r.Value && l.Depth == r.Depth && a.Value < c.Value => false,
        // (a * c) * b => (a * b) * c
        ((_, '*', var c), '*', var b) when b.Value < c.Value => false,
        // (a + c) + b => (a + b) + c
        ((_, '+', var c), '+', var b) when b.Value < c.Value => false,
        // (a - b) - c => (a - c) - b
        ((_, '-', var b), '-', var c) when b.Value < c.Value => false,
        // a / 1 => a * 1
        (_, '/', var b) when b.Value == 1 => false,
        // a * b / b => a + b - b
        ((_, '*', var b), '/', var c) when b.Value == c.Value => false,
        // a * 1 * 1 => a + 1 - 1
        ((_, '*', var b), '*', var c) when b.Value == 1 && c.Value == 1 => false,
 
        (var l, _, var r) => l.HasPreferredValues() && r.HasPreferredValues()
    };
 
    private struct Fraction : IEquatable<Fraction>, IComparable<Fraction>
    {
        public readonly int Numerator, Denominator;
 
        public Fraction(int numerator, int denominator)
            => (Numerator, Denominator) = (numerator, denominator) switch
        {
            (_, 0) => (Math.Sign(numerator), 0),
            (0, _) => (0, 1),
            (_, var d) when d < 0 => (-numerator, -denominator),
            _ => (numerator, denominator)
        };
 
        public static implicit operator Fraction(int i) => new Fraction(i, 1);
        public static Fraction operator +(Fraction a, Fraction b) =>
            new Fraction(a.Numerator * b.Denominator + a.Denominator * b.Numerator, a.Denominator * b.Denominator);
        public static Fraction operator -(Fraction a, Fraction b) =>
            new Fraction(a.Numerator * b.Denominator + a.Denominator * -b.Numerator, a.Denominator * b.Denominator);
        public static Fraction operator *(Fraction a, Fraction b) =>
            new Fraction(a.Numerator * b.Numerator, a.Denominator * b.Denominator);
        public static Fraction operator /(Fraction a, Fraction b) =>
            new Fraction(a.Numerator * b.Denominator, a.Denominator * b.Numerator);
 
        public static bool operator ==(Fraction a, Fraction b) => a.CompareTo(b) == 0;
        public static bool operator !=(Fraction a, Fraction b) => a.CompareTo(b) != 0;
        public static bool operator  <(Fraction a, Fraction b) => a.CompareTo(b)  < 0;
        public static bool operator  >(Fraction a, Fraction b) => a.CompareTo(b)  > 0;
        public static bool operator <=(Fraction a, Fraction b) => a.CompareTo(b) <= 0;
        public static bool operator >=(Fraction a, Fraction b) => a.CompareTo(b) >= 0;
 
        public bool Equals(Fraction other) => Numerator == other.Numerator && Denominator == other.Denominator;
        public override string ToString() => Denominator == 1 ? Numerator.ToString() : $"[{Numerator}/{Denominator}]";
 
        public int CompareTo(Fraction other) => (Numerator, Denominator, other.Numerator, other.Denominator) switch {
            var (    n1, d1,     n2, d2) when n1 == n2 && d1 == d2 => 0,
                (     0,  0,      _,  _) => (-1),
                (     _,  _,      0,  0) => 1,
            var (    n1, d1,     n2, d2) when d1 == d2 => n1.CompareTo(n2),
                (var n1,  0,      _,  _) => Math.Sign(n1),
                (     _,  _, var n2,  0) => Math.Sign(n2),
            var (    n1, d1,     n2, d2) => (n1 * d2).CompareTo(n2 * d1)
        };
    }
 
    private abstract class Expr
    {
        protected Expr(char symbol) => Symbol = symbol;
        public char Symbol { get; set; }
        public abstract Fraction Value { get; set; }
        public abstract int Depth { get; }
        public abstract void Deconstruct(out Expr left, out char symbol, out Expr right);
    }
 
    private sealed class Const : Expr
    {
        public Const(Fraction value) : base('c') => Value = value;
        public override Fraction Value { get; set; }
        public override int Depth => 0;
        public override void Deconstruct(out Expr left, out char symbol, out Expr right) => (left, symbol, right) = (this, Symbol, this);
        public override string ToString() => Value.ToString();
    }
 
    private sealed class Binary : Expr
    {
        public Binary(char symbol, Expr left, Expr right) : base(symbol) => (Left, Right) = (left, right);
        public Expr Left { get; }
        public Expr Right { get; }
        public override int Depth => Math.Max(Left.Depth, Right.Depth) + 1;
        public override void Deconstruct(out Expr left, out char symbol, out Expr right) => (left, symbol, right) = (Left, Symbol, Right);
 
        public override Fraction Value {
            get => Symbol switch {
                '*' => Left.Value * Right.Value,
                '/' => Left.Value / Right.Value,
                '+' => Left.Value + Right.Value,
                '-' => Left.Value - Right.Value,
                _ => throw new InvalidOperationException() };
            set {}
        }
 
        public override string ToString() => Symbol switch {
            '*' => ToString("+-".Contains(Left.Symbol), "+-".Contains(Right.Symbol)),
            '/' => ToString("+-".Contains(Left.Symbol), "*/+-".Contains(Right.Symbol)),
            '+' => ToString(false, false),
            '-' => ToString(false, "+-".Contains(Right.Symbol)),
            _ => $"[{Value}]"
        };
 
        private string ToString(bool wrapLeft, bool wrapRight) =>
            $"{(wrapLeft ? $"({Left})" : $"{Left}")} {Symbol} {(wrapRight ? $"({Right})" : $"{Right}")}";
    }
}