Помогите мне закончить последнюю часть моего приложения?Он решает любую игру с обратным отсчетом на канале 4 путем грубого форсирования любого возможного уравнения

Question

Для тех, кто не знаком с игрой. Вам дано 8 номеров, и вы должны достичь цели, используя +, -, / и *.

Таким образом, если целью является 254, а ваши игровые номера 2, 50, 5, 2, 1, вы бы правильно ответили на вопрос, сказав 5 * 50 = 250. Тогда 2 + 2 - это четыре. Добавьте это на aswell, чтобы получить 254.

Некоторые видео игры здесь:

Видео 1 видео 2

В основном я использую грубую силу игры, генерируя все числа любых размеров для чисел и всех символов и использую калькулятор базового инфликса для вычисления решения.

Однако в нем есть недостаток, поскольку все решения решаются следующим образом: ((((1 + 1) * 2) * 3) * 4). Это не переставляет скобки, и это вызывает у меня головную боль.

Поэтому я не могу решить все уравнения. Например, учитывая

Цель из 16 и чисел 1,1,1,1,1,1,1,1 не может быть достигнута, когда должна (1 + 1 + 1 + 1) * (1 + 1 + 1 + 1) = 16

Мне бы хотелось, чтобы кто-то помог закончить это ... на любом языке.

Вот что я написал до сих пор:

 #!/usr/bin/env perl

use strict;
use warnings;

use Algorithm::Permute;

# GAME PARAMETERS TO FILL IN
my $target = 751;
my @numbers = ( '2', '4', '7', '9', '1', '6', '50', '25' );


my $num_numbers = scalar(@numbers);

my @symbols = ();

foreach my $n (@numbers) {
    push(@symbols, ('+', '-', '/', '*'));
}

my $num_symbols = scalar(@symbols);

print "Symbol table: " . join(", ", @symbols);

my $lst = [];
my $symb_lst = [];

my $perms = '';
my @perm = ();

my $symb_perms = '';
my @symb_perm;

my $print_mark = 0;
my $progress = 0;
my $total_perms = 0;

my @closest_numbers;
my @closest_symb;
my $distance = 999999;

sub calculate {
    my @oprms = @{ $_[0] };
    my @ooperators = @{ $_[1] };

    my @prms = @oprms;
    my @operators = @ooperators;

    #print "PERMS: " . join(", ", @prms) . ", OPERATORS: " . join(", ", @operators);

    my $total = pop(@prms);

    foreach my $operator (@operators) {
        my $x = pop(@prms);

        if ($operator eq '+') {
            $total += $x;
        }
        if ($operator eq '-') {
            $total -= $x;
        }
        if ($operator eq '*') {
            $total *= $x;
        }
        if ($operator eq '/') {
            $total /= $x;
        }
    }
    #print "Total: $total\n";

    if ($total == $target) {
        #print "ABLE TO ACCURATELY SOLVE WITH THIS ALGORITHM:\n";
        #print "PERMS: " . join(", ", @oprms) . ", OPERATORS: " . join(", ", @ooperators) . ", TOTAL=$total\n";
        sum_print(\@oprms, \@ooperators, $total, 0);
        exit(0);
    }

    my $own_distance = ($target - $total);
    if ($own_distance < 0) {
        $own_distance *= -1;
    }

    if ($own_distance < $distance) {
        #print "found a new solution - only $own_distance from target $target\n";
        #print "PERMS: " . join(", ", @oprms) . ", OPERATORS: " . join(", ", @ooperators) . ", TOTAL=$total\n";
        sum_print(\@oprms, \@ooperators, $total, $own_distance);
        @closest_numbers = @oprms;
        @closest_symb = @ooperators;
        $distance = $own_distance;
    }

    $progress++;
    if (($progress % $print_mark) == 0) {
        print "Tested $progress permutations. " . (($progress / $total_perms) * 100) . "%\n";
    }
}

sub factorial {
    my $f = shift;
    $f == 0 ? 1 : $f*factorial($f-1);
}

sub sum_print {
    my @prms = @{ $_[0] };
    my @operators = @{ $_[1] };
    my $total = $_[2];
    my $distance = $_[3];
    my $tmp = '';

    my $op_len = scalar(@operators);

    print "BEST SOLUTION SO FAR: ";
    for (my $x = 0; $x < $op_len; $x++) {
        print "(";
    }

    $tmp = pop(@prms);
    print "$tmp";

    foreach my $operator (@operators) {
        $tmp = pop(@prms);
        print " $operator $tmp)";
    }

    if ($distance == 0) {
        print " = $total\n";
    }
    else {
        print " = $total (distance from target $target is $distance)\n";
    }
}

# look for straight match
foreach my $number (@numbers) {
    if ($number == $target) {
        print "matched!\n";
    }
}

for (my $x = 1; $x < (($num_numbers*2)-1); $x++) {
    $total_perms += factorial($x);
}

print "Total number of permutations: $total_perms\n";
$print_mark = $total_perms / 100;
if ($print_mark == 0) {
    $print_mark = $total_perms;
}

for (my $num_size=2; $num_size <= $num_numbers; $num_size++) {
    $lst = \@numbers;
    $perms = new Algorithm::Permute($lst, $num_size);

    print "Perms of size: $num_size.\n";

    # print matching symb permutations
    $symb_lst = \@symbols;
    $symb_perms = new Algorithm::Permute($symb_lst, $num_size-1);

    while (@perm = $perms->next) {
        while (@symb_perm = $symb_perms->next) {
            calculate(\@perm, \@symb_perm);
        }

        $symb_perms = new Algorithm::Permute($symb_lst, $num_size-1);
    }
}

print "exhausted solutions";
print "CLOSEST I CAN GET: $distance\n";
sum_print(\@closest_numbers, \@closest_symb, $target-$distance, $distance);
exit(0);

Вот пример вывода:

[15:53: /mnt/mydocuments/git_working_dir/countdown_solver$] perl countdown_solver.pl
Symbol table: +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *Total number of permutations: 93928268313
Perms of size: 2.
BEST SOLUTION SO FAR: (2 + 4) = 6 (distance from target 751 is 745)
BEST SOLUTION SO FAR: (2 * 4) = 8 (distance from target 751 is 743)
BEST SOLUTION SO FAR: (4 + 7) = 11 (distance from target 751 is 740)
BEST SOLUTION SO FAR: (4 * 7) = 28 (distance from target 751 is 723)
BEST SOLUTION SO FAR: (4 * 9) = 36 (distance from target 751 is 715)
BEST SOLUTION SO FAR: (7 * 9) = 63 (distance from target 751 is 688)
BEST SOLUTION SO FAR: (4 * 50) = 200 (distance from target 751 is 551)
BEST SOLUTION SO FAR: (7 * 50) = 350 (distance from target 751 is 401)
BEST SOLUTION SO FAR: (9 * 50) = 450 (distance from target 751 is 301)
Perms of size: 3.
BEST SOLUTION SO FAR: ((4 + 7) * 50) = 550 (distance from target 751 is 201)
BEST SOLUTION SO FAR: ((2 * 7) * 50) = 700 (distance from target 751 is 51)
BEST SOLUTION SO FAR: ((7 + 9) * 50) = 800 (distance from target 751 is 49)
BEST SOLUTION SO FAR: ((9 + 6) * 50) = 750 (distance from target 751 is 1)
Perms of size: 4.
BEST SOLUTION SO FAR: (((9 + 6) * 50) + 1) = 751

Answer 1

Здесь - Java-апплет ( исходный ) и версия Javascript.

Answer 2

Предложение использовать обратную польскую запись отлично.

Если у вас N = 5 чисел, шаблон будет

{num} {num} {ops} {num} {ops} {num} {ops} {num} {ops}

В любом месте может быть от 0 до N операций,хотя общее количество будет N-1.Вам просто нужно попробовать различные варианты размещения чисел и операций.

Решение (((1+1)+1)+1)*(((1+1)+1)+1)=16 будет найдено, когда вы попробуете

1 1 + 1 + 1 + 1 1 + 1 + 1 + *

Обновление : Возможно, не так хорошо, поскольку нахождение вышеуказанного может занять 433 701 273 600 попыток.Число было получено с использованием следующего:

use strict;
use warnings;

{
   my %cache = ( 0 => 1 );
   sub fact { my ($n) = @_; $cache{$n} ||= fact($n-1) * $n }
}


{
   my %cache;
   sub C {
      my ($n,$r) = @_;
      return $cache{"$n,$r"} ||= do {
         my $i = $n;
         my $j = $n-$r;
         my $c = 1;
         $c *= $i--/$j-- while $j;
         $c
      };
   }
}

my @nums = (1,1,1,1,1,1,1,1);

my $Nn = 0+@nums;  # Number of numbers.
my $No = $Nn-1;    # Number of operators.

my $max_tries = do {
   my $num_orderings = fact($Nn);
   {
      my %counts;
      ++$counts{$_} for @nums;
      $num_orderings /= fact($_) for values(%counts);
   }

   my $op_orderings = 4 ** $No;

   my $op_placements = 1;
   $op_placements *= C($No, $_) for 1..$No-1;

   $num_orderings * $op_orderings * $op_placements
};

printf "At most %.f tries needed\n", $max_tries;