24 game/Solve: Difference between revisions

=={{header|C sharp}}==

Generate binary trees -> generate permutations -> create expression -> evaluate expression<br/>

This works with other targets and more numbers but it will of course become slower.<br/>

Redundant expressions are filtered out (based on https://www.4nums.com/theory/) but I'm not sure I caught them all.

{{works with|C sharp|8}}

<lang csharp>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}")}";

}

}</lang>

{{out}}

<pre>

(1 + 2) * (1 + 7) = 24

(1 + 3) * (2 + 4) = 24

1 * 2 * 3 * 4 = 24

(1 + 2 + 3) * 4 = 24

(5 - 1) * (2 + 4) = 24

(2 + 5 - 1) * 4 = 24

(7 * 7 - 1) / 2 = 24

4 / (1 - 5 / 6) = 24

6 / (5 / 4 - 1) = 24

8 / (3 - 8 / 3) = 24

Cannot make 24 with 4, 4, 5, 9

5 * 5 - 5 / 5 = 24

(8 - 6) * (5 + 7) = 24

6 * 8 / (7 - 5) = 24

(5 + 7 - 8) * 6 = 24

6 + 6 + 6 + 6 = 24

6 * 6 - 6 - 6 = 24

6 * 8 / (9 - 7) = 24

(9 / 9 + 9) * (9 / 9 + 9) = 100</pre>