24 game/Solve: Difference between revisions

{{trans|Nim}}

op[Char(‘+’)] = (x, y) -> x + y

op[Char(‘-’)] = (x, y) -> x - y

[5, 7, 9, 7],

[3, 3, 8, 8]]

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program game24Solvex64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

{{Output}}

<pre>

Note: the permute function was locally from [[Permutations#ABAP|here]]

lv_number type i,

lt_numbers type table of i.

modify iv_set index lv_perm from lv_temp_2.

modify iv_set index lv_len from lv_temp.

Sample Runs:

=={{header|Argile}}==

{{works with|Argile|1.0.0}}

print a function that given four digits argv[1] subject to the rules of \

(roperators[(rrop[rpn][2])]) (rdigits[3]);

return buffer as text

Examples:

<pre>$ arc 24_game_solve.arg -o 24_game_solve.c

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program game24Solver.s */

.include "../affichage.inc"

{{output}}

<pre>

{{works with|AutoHotkey_L}}

Output is in RPN.

InputBox, NNNN ; user input 4 digits

NNNN := RegExReplace(NNNN, "(\d)(?=\d)", "$1,") ; separate with commas for the sort command

o := A_LoopField o

return o

{{out}}for 1127:

<pre>

=={{header|BBC BASIC}}==

PROCsolve24("1234")

PROCsolve24("6789")

IF I% > 4 PRINT "No solution found"

ENDPROC

{{out}}

<pre>

Note: This a brute-force approach with time complexity <em>O(6ⁿ.n.(2n-3)!!)</em> and recursion depth <em>n</em>.<br>

typedef struct {int val, op, left, right;} Node;

return 0;

=={{header|C++}}==

This code may be extended to work with more than 4 numbers, goals other than 24, or different digit ranges. Operations have been manually determined for these parameters, with the belief they are complete.

#include <iostream>

#include <ratio>

return 0;

}

{{out}}

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}}

using System.Collections.Generic;

using static System.Linq.Enumerable;

$"{(wrapLeft ? $"({Left})" : $"{Left}")} {Symbol} {(wrapRight ? $"({Right})" : $"{Right}")}";

}

{{out}}

<pre>

=={{header|Ceylon}}==

Don't forget to import ceylon.random in your module.ceylon file.

DefaultRandom

}

expressions.each(print);

}

=={{header|Clojure}}==

(:require [clojure.math.combinatorics :as c]

[clojure.walk :as w]))

(map println)

doall

The function <code>play24</code> works by substituting the given digits and the four operations into the binary tree patterns (o (o n n) (o n n)), (o (o (o n n) n) n), and (o n (o n (o n n))).

=={{header|COBOL}}==

*> This code is dedicated to the public domain

*> This is GNUCobol 2.0

end-perform

.

{{out}}

=={{header|CoffeeScript}}==

# This program tries to find some way to turn four digits into an arithmetic

# expression that adds up to 24.

solution = solve_24_game a, b, c, d

console.log "Solution for #{[a,b,c,d]}: #{solution ? 'no solution'}"

{{out}}

<pre>

=={{header|Common Lisp}}==

(defun digits ()

digits which evaluates to 24. The first form found is returned, or

NIL if there is no solution."

{{out}}

This uses the Rational struct and permutations functions of two other Rosetta Code Tasks.

{{trans|Scala}}

std.concurrency, permutations2, arithmetic_rational;

foreach (const prob; [[6, 7, 9, 5], [3, 3, 8, 8], [1, 1, 1, 1]])

writeln(prob, ": ", solve(24, prob));

{{out}}

<pre>[6, 7, 9, 5]: (6+(9*(7-5)))

The program takes n numbers - not limited to 4 - builds the all possible legal rpn expressions according to the game rules, and evaluates them. Time saving : 4 5 + is the same as 5 4 + . Do not generate twice. Do not generate expressions like 5 6 * + which are not legal.

;; use task [[RPN_to_infix_conversion#EchoLisp]] to print results

(define (rpn->string rpn)

(writeln digits '→ target)

(try-rpn digits target))

{{out}}

=={{header|Elixir}}==

{{trans|Ruby}}

@expressions [ ["((", "", ")", "", ")", ""],

["(", "(", "", "", "))", ""],

IO.puts "found #{length(solutions)} solutions, including #{hd(solutions)}"

IO.inspect Enum.sort(solutions)

{{out}}

=={{header|ERRE}}==

ERRE hasn't an "EVAL" function so we must write an evaluation routine; this task is solved via "brute-force".

PROGRAM 24SOLVE

END PROGRAM

{{out}}

<pre>

Via brute force.

>function try24 (v) ...

$n=cols(v);

$return 0;

$endfunction

>try24([1,2,3,4]);

Solved the problem

-1+5=4

3-4=-1

=={{header|F_Sharp|F#}}==

It eliminates all duplicate solutions which result from transposing equal digits.

The basic solution is an adaption of the OCaml program.

let rec gcd x y = if x = y || x = 0 then y else if x < y then gcd y x else gcd y (x-y)

|> Seq.groupBy id

|> Seq.iter (fun x -> printfn "%s" (fst x))

{{out}}

<pre>>solve24 3 3 3 4

=={{header|Factor}}==

Factor is well-suited for this task due to its homoiconicity and because it is a reverse-Polish notation evaluator. All we're doing is grouping each permutation of digits with three selections of the possible operators into quotations (blocks of code that can be stored like sequences). Then we <code>call</code> each quotation and print out the ones that equal 24. The <code>recover</code> word is an exception handler that is used to intercept divide-by-zero errors and continue gracefully by removing those quotations from consideration.

prettyprint quotations random sequences sequences.deep ;

IN: rosetta-code.24-game

print expressions [ [ 24= ] [ 2drop ] recover ] each ;

{{out}}

<pre>

=={{header|Fortran}}==

use helpers

implicit none

end function op

contains

end subroutine nextpermutation

{{out}} (using g95):

<pre> 3 6 7 9 : 3 *(( 6 - 7 )+ 9 )

=={{header|GAP}}==

check := function(x, y, z)

local r, c, s, i, j, k, a, b, p;

# A tricky one:

Player24([3,3,8,8]);

=={{header|Go}}==

import (

}

}

{{out}}

<pre> 8 6 7 6: No solution

=={{header|Gosu}}==

uses java.lang.Integer

uses java.lang.Double

print( "No solution!" )

}

=={{header|Haskell}}==

import Data.Ratio

import Control.Monad

nub $ permutations $ map Constant r4

Example use:

(8 / (2 / (9 - 3)))</pre>

===Alternative version===

import Data.List

import Text.PrettyPrint

{{out}}

<pre>((8 / 2) * (9 - 3))

This shares code with and solves the [[24_game#Icon_and_Unicon|24 game]]. A series of pattern expressions are built up and then populated with the permutations of the selected digits. Equations are skipped if they have been seen before. The procedure 'eval' was modified to catch zero divides. The solution will find either all occurrences or just the first occurrence of a solution.

link strings # for csort, deletec, permutes

suspend 2(="(", E(), =")") | # parenthesized subexpression, or ...

tab(any(&digits)) # just a value

=={{header|J}}==

ops=: ' ',.'+-*%' {~ >,{i.each 4 4 4

cmask=: 1 + 0j1 * i.@{:@$@[ e. ]

parens=: ], 0 paren 3, 0 paren 5, 2 paren 5, [: 0 paren 7 (0 paren 3)

all=: [: parens [:,/ ops ,@,."1/ perm { [:;":each

This implementation tests all 7680 candidate sentences.

Here is an alternative version that supports multi-digit numbers. It prefers expressions without parens, but searches for ones with if needed.

perms=: [: ":"0 [: ~. i.@!@# A. ]

build=: 1 : '(#~ 24 = ".) @: u'

if. 0 = #es do. es =. ([: ,/ [: ,/ ops combp"1 2/ perms) build y end.

es -."1 ' '

{{out}}

Note that this version does not extend to different digit ranges.

public class Game24Player {

res.add(Arrays.asList((i / npow), (i % npow) / n, i % n));

}

{{out}}

=={{header|JavaScript}}==

This is a translation of the C code.

var NOVAL=9999,oper="+-*/",out;

solve24("1234");

solve24("6789");

Examples:

'''Infrastructure:'''

def permutations:

if length == 0 then []

| ($in[$i+1:] | triples) as $tail

| [$head, $in[$i], $tail]

'''Evaluation and pretty-printing of allowed expressions'''

def eval:

if type == "array" then

def pp:

'''24 Game''':

# Input: an array of 4 digits

;

{{out}}

[1,2,3,4]

That was too easy. I found 242 answers, e.g. [4 * [1 + [2 + 3]]]

[1,2,3,4,5,6]

That was too easy. I found 197926 answers, e.g. [[2 * [1 + 4]] + [3 + [5 + 6]]]

=={{header|Julia}}==

For julia version 0.5 and higher, the Combinatorics package must be installed and imported (`using Combinatorics`). Combinatorial functions like `nthperm` have been moved from Base to that package and are not available by default anymore.

length(nums) != 4 && error("Input must be a 4-element Array")

syms = [+,-,*,/]

end

return "0"

{{out}}

<pre>julia> for i in 1:10

=={{header|Kotlin}}==

{{trans|C}}

import java.util.Random

println(if (solve24(n)) "" else "No solution")

}

Sample output:

=={{header|Liberty BASIC}}==

input "Enter 4 digits: "; a$

nD=0

exit function

[handler]

=={{header|Lua}}==

Generic solver: pass card of any size with 1st argument and target number with second.

local SIZE = #arg[1]

local GOAL = tonumber(arg[2]) or 24

permgen(input, SIZE)

{{out}}

=={{header|Mathematica}} / {{header|Wolfram Language}}==

The code:

treeR[n_] := Table[o[trees[a], trees[n - a]], {a, 1, n - 1}]

treeR[1] := n

Permutations[Array[v, 4]], 1]],

Quiet[(# /. v[q_] :> val[[q]]) == 24] &] /.

The <code>treeR</code> method recursively computes all possible operator trees for a certain number of inputs. It does this by tabling all combinations of distributions of inputs across the possible values. (For example, <code>treeR[4]</code> is allotted 4 inputs, so it returns <code>{o[treeR[3],treeR[1]],o[treeR[2],treeR[2]],o[treeR[1],treeR[3]]}</code>, where <code>o</code> is the operator (generic at this point).

**For each result, turn the expression into a string (for easy manipulation), strip the "<code>HoldForm</code>" wrapper, replace numbers like "-1*7" with "-7" (a idiosyncrasy of the conversion process), and remove any lingering duplicates. Some duplicates will still remain, notably constructs like "3 - 3" vs. "-3 + 3" and trivially similar expressions like "(8*3)*(6-5)" vs "(8*3)/(6-5)". Example run input and outputs:

{{out}}

An alternative solution operates on Mathematica expressions directly without using any inert intermediate form for the expression tree, but by using <code>Hold</code> to prevent Mathematica from evaluating the expression tree.

evaluate[x_] := x;

combine[l_, r_ /; evaluate[r] != 0] := {HoldForm[Plus[l, r]],

solveMaintainOrder[1/5, Range[2, 5]]

solveCanPermute[1/5, Range[2, 5]]

=={{header|Nim}}==

{{works with|Nim Compiler|0.19.4}}

type

echo fmt"solve({nums}) -> {solve(nums)}"

{{out}}

=={{header|OCaml}}==

| Const of float

| Sum of expression * expression (* e1 + e2 *)

| x::xs -> comp x xs

| [] -> assert false

<pre>

Note: the <code>permute</code> function was taken from [http://faq.perl.org/perlfaq4.html#How_do_I_permute_N_e here]

# http://faq.perl.org/perlfaq4.html#How_do_I_permute_N_e

sub permute (&@) {

}

}

{{out}}

<pre>E:\Temp>24solve.pl

=={{header|Phix}}==

<span style="color: #000080;font-style:italic;">-- demo\rosetta\24_game_solve.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

--solve24({6,9,7,4})</span>

<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

=={{header|Picat}}==

foreach (_ in 1..10)

Nums = [D : _ in 1..4, D = random() mod 9 + 1],

Exp3 =.. [Op,Exp1,Exp2],

solve([(Num3,Exp3)|NumExps2]).

{{trans|Raku}}

main =>

R := replace(R, F,T.to_string())

end,

{{out}}

Another approach:

main =>

check(A,X,B,Y,C,Z,D,Target,Expr) =>

Expr = [A,X,"(","(",B,Y,C,")", Z,D,")"].to_string2(),

{{out}}

=={{header|PicoLisp}}==

We use Pilog (PicoLisp Prolog) to solve this task

(permute @Lst (@A @B @C @D))

(member @Op1 (+ - * /))

(println @X) ) )

{{out}}

<pre>(* (+ 5 7) (- 8 6))

Note

This example uses the math module:

:a

editvar /newvar /withothervar /value=-random- /title=1

printline you could have done it by doing -c-

stoptask

{{out}}

rdiv/2 is use instead of //2 to enable the program to solve difficult cases as [3 3 8 8].

game(Len, Range, Goal, L, S),

maplist(my_write, L),

my_write(V) :-

{{out}}

<pre>?- play24(4,9, 24).

{{Works with|GNU Prolog|1.4.4}}

Little efforts to remove duplicates (e.g. output for [4,6,9,9]).

solve(N,Xs,Ast) :-

test(T) :- solve(24, [2,3,8,9], T).

{{Output}}

<pre>(9-3)*8//2

The function is called '''solve''', and is integrated into the game player.

The docstring of the solve function shows examples of its use when isolated at the Python command line.

The 24 Game Player

print ("Thank you and goodbye")

{{out}}

==={{header|Python}} Succinct===

Based on the Julia example above.

import operator

from itertools import product, permutations

[3,3,8,8], # Difficult case requiring precise division

]:

{{out}}

==={{header|Python}} Recursive ===

This works for any amount of numbers by recursively picking two and merging them using all available operands until there is only one value left.

# Python 3

from operator import mul, sub, add

except StopIteration:

print("No solution found")

{{out}}

===Python: using tkinter===

''' Python 3.6.5 code using Tkinter graphical user interface.

Combination of '24 game' and '24 game/Solve'

g = Game(root)

root.mainloop()

=={{header|Quackery}}==

<code>permutations</code> is defined at [[Permutations#Quackery]] and <code>uniquewith</code> is defined at [[Remove duplicate elements#Quackery]].

permutations ] constant is numorders ( --> [ )

unbuild

2 split nip

{{out}}

=={{header|R}}==

This uses exhaustive search and makes use of R's ability to work with expressions as data. It is in principle general for any set of operands and binary operators.

library(gtools)

return(NA)

}

{{out}}

> solve24()

8 * (4 - 2 + 1)

> solve24(ops=c('-', '/')) #restricted set of operators

(8 - 2)/(1/4)

=={{header|Racket}}==

The sequence of all possible variants of expressions with given numbers ''n1, n2, n3, n4'' and operations ''o1, o2, o3''.

(define (in-variants n1 o1 n2 o2 n3 o3 n4)

(let ([o1n (object-name o1)]

`(,n1 ,o1n ((,n2 ,o3n ,n3) ,o2n ,n4))

`(,n1 ,o1n (,n2 ,o2n (,n3 ,o3n ,n4))))))))

Search for all solutions using brute force:

(define (find-solutions numbers (goal 24))

(define in-operations (list + - * /))

(define (remove-from numbers . n) (foldr remq numbers n))

Examples:

Since Raku uses Rational numbers for division (whenever possible) there is no loss of precision as is common with floating point division. So a comparison like (1 + 7) / (1 / 3) == 24 "Just Works"^&trade;

my @digits;

my %h = map { $_.Str => $_ }, @array;

%h.values;

{{out}}

Alternately, a version that doesn't use EVAL. More general case. Able to handle 3 or 4 integers, able to select the goal value.

sub MAIN (*@parameters, Int :$goal = 24) {

demo and will show this message.\e[0m

========================================================================

{{out}}

When supplied 1399 on the command line:

=={{header|REXX}}==

/* start-of-help

┌───────────────────────────────────────────────────────────────────────┐

ger: say= '***error*** for argument:' y; say arg(1); errCode= 1; return 0

p: return word( arg(1), 1)

Some older REXXes don't have a &nbsp; '''changestr''' &nbsp; BIF, so one is included here ──► &nbsp; &nbsp; [[CHANGESTR.REX]].

<br><br>

{{trans|Tcl}}

{{works with|Ruby|2.1}}

EXPRESSIONS = [

'((%dr %s %dr) %s %dr) %s %dr',

puts "found #{solutions.size} solutions, including #{solutions.first}"

puts solutions.sort

{{out}}

=={{header|Rust}}==

{{works with|Rust|1.17}}

enum Operator {

Sub,

[numbers[order[0]], numbers[order[1]], numbers[order[2]], numbers[order[3]]]

}

{{out}}

<pre>

A non-interactive player.

case Nil => List(Nil)

case x :: xs =>

}

Example:

This version outputs an S-expression that will '''eval''' to 24 (rather than converting to infix notation).

#!r6rs

(filter evaluates-to-24

(map* tree (iota 6) ops ops ops perms))))

Example output:

> (solve 1 3 5 7)

((* (+ 1 5) (- 7 3))

> (solve 3 4 9 10)

()

=={{header|Sidef}}==

'''With eval():'''

'((%d %s %d) %s %d) %s %d',

'(%d %s (%d %s %d)) %s %d',

}

}

'''Without eval():'''

{|a,b,c|

Hash(

}

}

{{out}}

=={{header|Simula}}==

OUTIMAGE;

END.

{{out}}

<pre>

=={{header|Swift}}==

import Darwin

import Foundation

} else {

println("Congratulations, you found a solution!")

{{out}}The program in action:

This is a complete Tcl script, intended to be invoked from the command line.

{{tcllib|struct::list}}

# Encoding the various expression trees that are possible

set patterns {

}

}

{{out}}

Demonstrating it in use:

non-terminal nodes of a tree in every possible way. The <code>value</code> function evaluates a tree and the

<code>format</code> function displays it in a readable form.

#import nat

#import rat

format = *^ ~&v?\-+~&h,%zP@d+- ^H/mat@d *v ~&t?\~& :/`(+ --')'

test program:

output:

<pre>

{{trans|Kotlin}}

{{libheader|Wren-dynamic}}

import "/dynamic" for Tuple, Enum, Struct

System.write(": ")

System.print(solve24.call(n) ? "" : "No solution")

{{out}}

=={{header|Yabasic}}==

space$ = " "

next n

return true

=={{header|zkl}}==

File solve24.zkl:

fcn u(xs){ xs.reduce(fcn(us,s){us.holds(s) and us or us.append(s) },L()) }

var ops=u(H.combosK(3,"+-*/".split("")).apply(H.permute).flatten());

catch(MathError){ False } };

{ f2s(digits4,ops3,f) }]];

println(solutions.len()," solutions:");

One trick used is to look at the solving functions name and use the digit in it to index into the formats list.

{{out}}