Яблоконь LOR Codewars (продолжение): задача на комбинаторику или сраный Сбер теперь FAANG

9-8+7-6-5-4-3+210 = 200
9-8-7-6-5+4+3+210 = 200
98+76-5+43-2-10 = 200
98-7+65+43+2-1+0 = 200
98-7+65+43+2-1-0 = 200

енум Операция {
   ПЛЮС = 0
   МИНУС = 1
   ПРОЧЕРК = 2
}
НОВЫЙ_РАЗРЯД = 3

МАКС_ЦИФРА = 9
RES        = 200
ЗНАКОВ     = МАКС_ЦИФРА - 1

маска = массив(0, ЗНАКОВ + 1)

пока маска.конец == 0:

  сумма = 0
  регистр = МАКС_ЦИФРА
  регистр_знак = 1
  текущая_цифра = МАКС_ЦИФРА

  # считаем сумму по маске
  для номер_знака от 0 до ЗНАКОВ:
    текущая_цифра -= 1
    знак = маска[номер_знака]
    если знак = ПРОЧЕРК:
      регистр *= 10
      регистр += текущая_цифра
    иначе:
      сумма += регистр * регистр_знак
      регистр = текущая_цифра
      если знак = ПЛЮС:
        регистр_знак = 1
      иначе:
        регистр_знак = -1

  # добиваем последнее число
  сумма += регистр * регистр_знак

  # если сумма нужная, вывести
  Если сумма = RES:
    текущая_цифра = МАКС_ЦИФРА
    вывод(текущая_цифра)
    для номер_знака от 0 до ЗНАКОВ:     
      текущая_цифра -= 1
      знак = маска[номер_знака]
      Если знак ПЛЮС:
        вывод(+)
      если знак МИНУС:
        вывод(-)
      вывод(текущая_цифра)
    вывод_нов_строка()
    
  # перейти к новой маске
  маска[0] += 1
  разряд = 0
  пока (разряд < маска.размер) И (маска[разряд] == НОВЫЙ_РАЗРЯД):
      маска[разряд] = 0
      маска[разряд + 1] += 1
      разряд += 1

const expectedValue = 200;

const digits = ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0'];
const operations = ['', '+', '-'];
const permutation = new Uint8Array(digits.length - 1).fill(0);
do {
  const expressionChars = [];
  for (let i = 0; i < digits.length - 1; i++) {
    expressionChars.push(digits[i]);
    expressionChars.push(operations[permutation[i]]);
  }
  expressionChars.push(digits[digits.length - 1]);
  const expressionString = expressionChars.join('');
  const expressionValue = eval(expressionString);
  if (expressionValue === expectedValue) console.log(expressionString);
} while (nextPermutation(permutation, operations.length));


function nextPermutation(permutation, cardinality) {
  let i = permutation.length - 1;
  while (i >= 0 && permutation[i] === cardinality - 1) {
    permutation[i] = 0;
    i--;
  }
  if (i < 0) return false;
  permutation[i]++;
  return true;
}

~   
❯ ipython
Python 3.12.4 (main, Jun  7 2024, 06:33:07) [GCC 14.1.1 20240522]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.26.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: def find_expression_with_expected_value(expected_value):
   ...:     digits = ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']
   ...:     operations = ['', '+', '-']
   ...:     permutation = [0] * (len(digits) - 1)
   ...: 
   ...:     def next_permutation(permutation, cardinality):
   ...:         i = len(permutation) - 1
   ...:         while i >= 0 and permutation[i] == cardinality - 1:
   ...:             permutation[i] = 0
   ...:             i -= 1
   ...:         if i < 0:
   ...:             return False
   ...:         permutation[i] += 1
   ...:         return True
   ...: 
   ...:     results = []
   ...: 
   ...:     while True:
   ...:         expression_chars = []
   ...:         for i in range(len(digits) - 1):
   ...:             expression_chars.append(digits[i])
   ...:             expression_chars.append(operations[permutation[i]])
   ...:         expression_chars.append(digits[-1])
   ...:         expression_string = ''.join(expression_chars)
   ...:         expression_value = eval(expression_string)
   ...:         if expression_value == expected_value:
   ...:             results.append(expression_string)
   ...:         if not next_permutation(permutation, len(operations)):
   ...:             break
   ...: 
   ...:     return results
   ...: 
   ...: # Пример использования:
   ...: expected_value = 200
   ...: expressions = find_expression_with_expected_value(expected_value)
   ...: for expr in expressions:
   ...:     print(expr)
   ...: 
98+76-5+43-2-10
98-7+65+43+2-1+0
98-7+65+43+2-1-0
9-8+7-6-5-4-3+210
9-8-7-6-5+4+3+210

from itertools import product

def evaluate_expression(expression):
    try:
        return eval(expression)
    except:
        return None

def find_expression():
    digits = "9876543210"
    operations = ['+', '-', '']
    target = 200
    
    for ops in product(operations, repeat=len(digits)-1):
        expression = "".join(d + o for d, o in zip(digits, ops + ('',)))
        if evaluate_expression(expression) == target:
            return expression
    return None

result = find_expression()
if result:
    print(f"Expression found: {result} = 200")
else:
    print("No expression found that equals 200.")

import itertools

def find_expression_with_expected_value(expected_value):
    digits = ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']
    operations = ['', '+', '-']
    
    results = []

    for ops in itertools.product(operations, repeat=len(digits) - 1):
        expression_chars = [digits[0]]
        for digit, op in zip(digits[1:], ops):
            expression_chars.append(op)
            expression_chars.append(digit)
        expression_string = ''.join(expression_chars)
        expression_value = eval(expression_string)
        if expression_value == expected_value:
            results.append(expression_string)

    return results

# Пример использования:
expected_value = 200
expressions = find_expression_with_expected_value(expected_value)
for expr in expressions:
    print(expr)

expr = ['9']


def rec(digit, cs, total):
    global expr
    if digit == 0:
        if total == 200:
            yield ''.join(expr)
        return

    expr += [str(digit - 1)]
    yield from rec(digit - 1, cs * 10 + digit - 1, total + cs * 9 + digit - 1)
    expr.pop()
    expr += ['+', str(digit - 1)]
    yield from rec(digit - 1, digit - 1, total + digit - 1)
    expr.pop()
    expr.pop()
    expr += ['-', str(digit - 1)]
    yield from rec(digit - 1, 1 - digit, total - digit + 1)
    expr.pop()
    expr.pop()


for ans in rec(9, 9, 9):
    print(ans)

def rec(digit, cs, total):
    global expr

    if digit == 0:
        if total == 200:
            yield ''.join(expr)
        return

    expr += [str(digit - 1)]
    cs2 = cs * 10 + digit - 1
    if cs < 0:
        cs2 = cs * 10 + 1 - digit
    yield from rec(digit - 1, cs2, total - cs + cs2)
    expr.pop()
    expr += ['+', str(digit - 1)]
    yield from rec(digit - 1, digit - 1, total + digit - 1)
    expr.pop()
    expr.pop()
    expr += ['-', str(digit - 1)]
    yield from rec(digit - 1, 1 - digit, total - digit + 1)
    expr.pop()
    expr.pop()

<?php echo '98+76-5+43-2-10=200'; 

digits="9876543210"
ops="+,-,' '"
result="200"

len=$((${#digits}-1))

exp(){
    echo \
${1:0:1}${2:0:1}\
${1:1:1}${2:1:1}\
${1:2:1}${2:2:1}\
${1:3:1}${2:3:1}\
${1:4:1}${2:4:1}\
${1:5:1}${2:5:1}\
${1:6:1}${2:6:1}\
${1:7:1}${2:7:1}\
${1:8:1}${2:8:1}\
${1:9:1}${2:9:1}\
| tr -d ' '
}

s=$(printf "%0.s{$ops}" $(seq $len))
eval "a=($(eval "printf '\"%s\"\n' $s"))"
for s in "${a[@]}"
do
    e=$(exp "$digits" "$s")
    eval r=$(( $e ))
    if [[ $r == $result ]]
    then
        echo $e=$result
    fi
done

time bash cartesian.sh 
9-8+7-6-5-4-3+210=200
9-8-7-6-5+4+3+210=200
98+76-5+43-2-10=200
98-7+65+43+2-1+0=200
98-7+65+43+2-1-0=200

real	1m45,681s
user	0m47,510s
sys	1m13,866s

const ND:usize = 9;

#[derive(Debug, Copy, Clone)]
enum Op {
    Plus,
    Minus,
    Void,
}
impl Op {
    fn next_op(&mut self, pos: usize, iter: usize) {
        if iter % 3usize.pow(pos as u32) == 0 {
            *self = match self {
                Op::Void => Op::Minus,
                Op::Minus => Op::Plus,
                Op::Plus => Op::Void,
            }
        }
    }
}
fn calc_expr(ops: &[Op]) -> isize {
    let (mut sum, mut num, mut sign) = (0, ND as isize, 1);
    for (di, op) in ops.into_iter().enumerate() {
        let nxt_dig = (ND-1-di) as isize; 
        match op {
            Op::Void => num = num*10 + nxt_dig,
            Op::Plus => {
                sum += num * sign;
                num = nxt_dig; 
                sign = 1;
            }
            Op::Minus => {
                sum += num * sign;
                num = nxt_dig;
                sign = -1;
            }
        };
    }
    sum + num*sign
}
fn expr_to_str(ops:&[Op])->String {
    let mut s = "9".to_string();
    for (di, op) in ops.into_iter().enumerate() {
        match op {
            Op::Minus => s.push('-'),
            Op::Plus => s.push('+'),
            _ => ()
        }
        s.push(char::from_digit((ND-1-di) as u32, 10).unwrap());
    }
    s
}
fn main() {
    let target = 200;
    let mut ops = [Op::Void; ND];
    for i in 0..3usize.pow(ND as u32) { 
        if calc_expr(&ops) == target {
            println!("{}={target}", expr_to_str(&ops));
        }
        for p in 0..ND {
            ops[p].next_op(p, i);
        }
    }
}

cargo r -r
98-7+65+43+2-1-0=200
98-7+65+43+2-1+0=200
98+76-5+43-2-10=200
9-8+7-6-5-4-3+210=200
9-8-7-6-5+4+3+210=200

hyperfine --runs 500 -N  ./target/release/lortst
Benchmark 1: ./target/release/lortst
  Time (mean ± σ):       2.8 ms ±   1.1 ms    [User: 1.5 ms, System: 1.1 ms]
  Range (min … max):     1.2 ms …   4.4 ms    500 runs

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

struct list
{
    char * data;
    struct list * next;
};

int main(int argc, char ** argv)
{
    char     input[]   = "9876543210";
    int      need_found = 200;
    uint8_t  input_len = sizeof(input);
    char     reuse[input_len*2];
    uint16_t limit  = 0x1FF;
    uint64_t reuse_cnt = 0;
    struct list * l = malloc(sizeof(struct list));
    struct list * last = l;
    for (int skip = 0; skip != limit; ++skip )
    {
        for( int opers=limit ;opers != -1; opers--)
        {
            for (int i = 0; i != input_len;i++)
            {
               reuse[reuse_cnt++] = input[i];
               if( i+2 != input_len && ((skip >> i) & 1))
               {
                  reuse[reuse_cnt++] = ((opers >> i) & 1) ? '-' : '+';
               }
            }
            int64_t on[] = {0,0,0,0,0,0,0,0,0,0,0};
            char *  fmt  =  "%li%li%li%li%li%li%li%li%li%li";
            long n = sscanf(reuse, fmt, &on[0],&on[1],&on[2],
                                        &on[3],&on[4],&on[5],
                                        &on[6],&on[7],&on[8],
                                                      &on[9]);

            int64_t result = 0;
            for (int x = 0; x < n; x++)
            {
                 result+=on[x];
            }
            if(result == need_found)
            {
               int found = 0;
               struct list * ln = l;
               while(ln)
               {
                  if(ln->data)
                  {
                      if(strcmp(ln->data,reuse) == 0)
                      {
                         found=1;
                         break;
                      }
                  }
                  ln = ln->next;
               }

               if(found==0)
               {
                  last->next = malloc(sizeof(struct list));
                  last->next->data = malloc(strlen(reuse)+1);
                  memcpy(last->next->data,reuse,strlen(reuse)+1);
                  last=last->next;
               }
            }

            memset(reuse,0,sizeof(reuse));
            reuse_cnt=0;
         }
    }
    while(l)
    {
       if(l->data)
       {
           printf("%-2zu: %-17s == 200\n",++reuse_cnt,l->data);
           free(l->data);
       }
       last = l;
       l = l->next;
       free(last);
    }
    return 0;
}

dron@gnu:~/Рабочий-стол$ gcc -Wall -Werror test.c && ./a.out 
1 : 9-8+7-6-5-4-3+210 == 200
2 : 9-8-7-6-5+4+3+210 == 200
3 : 98+76-5+43-2-10   == 200
4 : 98-7+65+43+2-1-0  == 200
5 : 98-7+65+43+2-1+0  == 200
dron@gnu:~/Рабочий-стол$ 

local loadstring = loadstring or load;
local res = { }
local opr = {'+','-'}
local r = function(data,buf)
    if not buf[1] then
       return '',false
    end
    if data[#data] ~= '+' and data[#data] ~= '-'
       and #data    >  0  and math.random(0,1) == 0 then
       return opr[math.random(1,2)],true
    end
    return table.remove(buf,1),true
end
while(true) do
    local out = {}
    local buf = {9,8,7,6,5,4,3,2,1,0}
    local doi = true
    while(doi) do
        out[#out+1],doi = r(out,buf)
    end
    local static = table.concat(out)
    if loadstring('return '..static)() == 200 then
       if not res[static] then
          res[static] = true
          print(static..' == 200');
       end
    end
end

dron@gnu:~/Рабочий-стол$ lua test.lua 
9-8-7-6-5+4+3+210 == 200
98-7+65+43+2-1+0 == 200
98+76-5+43-2-10 == 200
98-7+65+43+2-1-0 == 200
9-8+7-6-5-4-3+210 == 200
^C

DIGITS = {'9','8','7','6','5','4','3','2','1','0'}
OPS = {'+','-',''}
TARGET = 200

local eval = loadstring or load
local len = #DIGITS
local function bf(pos, expr)
  if pos > len then
    if eval("return " .. expr)() == TARGET then
      print(expr .. "=" .. TARGET)
    end
    return
  end
  for _, o in ipairs(OPS) do
    bf(pos + 1, expr .. o .. DIGITS[pos])
  end
end
bf(2, DIGITS[1])

$ lua bruteforce.lua 
9-8+7-6-5-4-3+210=200
9-8-7-6-5+4+3+210=200
98+76-5+43-2-10=200
98-7+65+43+2-1+0=200
98-7+65+43+2-1-0=200

function f(n, s) {
  if (n === -1) {
    return `if (${s} === 200) console.log('${s}');`;
  } else {
    return f(n - 1, s + n) + f(n - 1, s + '+' + n) + f(n - 1, s + '-' + n);
  }
}

eval(f(8, '9'));

$ echo {0..9}{a..z}

digits="9876543210"
ops="+,-,' '"
result="200"

for (( i=0; i<${#digits}; i=i+1 ))
do
    expr_evl="$expr_evl"'${digits:'$i':1}${l:'$i':1}'
done

len=$((${#digits}-1))
s=$(printf "%0.s{$ops}" $(seq $len))

while read l
do
    l=${l//\"/}
    eval "e=$expr_evl"
    e=${e// /}
    eval r=$(( $e ))
    [[ $r == $result ]] && echo $e=$result
done < <(eval "printf '\"%s\"\n' $s")

9-8+7-6-5-4-3+210=200
9-8-7-6-5+4+3+210=200
98+76-5+43-2-10=200
98-7+65+43+2-1+0=200
98-7+65+43+2-1-0=200

real	0m0,831s
user	0m0,749s
sys	0m0,153s

(defun concat-digit (number digit)
  (if (plusp number)
      (+ (* number 10) digit)
      (- (* number 10) digit)))

(defun solve (first-digit target)
  (labels ((iter (last-number next-digit expr current-value)
             (if (= next-digit -1)
                 (when (= current-value target)
                   (format t "~A = ~A~%" expr target))
                 (let ((next-number (concat-digit last-number next-digit)))
                   ;; +
                   (iter next-digit
                         (1- next-digit)
                         (format nil "~A+~A" expr next-digit)
                         (+ current-value next-digit))
                   ;; -
                   (iter (- next-digit)
                         (1- next-digit)
                         (format nil "~A-~A" expr next-digit)
                         (- current-value next-digit))
                   ;; ничего
                   (iter next-number
                         (1- next-digit)
                         (format nil "~A~A" expr next-digit)
                         (+ current-value (- last-number) next-number))))))
    (iter first-digit (1- first-digit) (format nil "~A" first-digit) first-digit)))

(solve 9 200)

9-8+7-6-5-4-3+210 = 200
9-8-7-6-5+4+3+210 = 200
98+76-5+43-2-10 = 200
98-7+65+43+2-1+0 = 200
98-7+65+43+2-1-0 = 200