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

(use-modules (ice-9 match))
(use-modules (ice-9 format))
(use-modules (statprof))

(define result 200)

(define (plus xs x)
  (list '+ xs x))

(define (minus xs x)
  (list '- xs x))

(define (glue xs x)
  (match xs
    ((op rest y)
     (list op rest (+ (* 10 y) x)))
    (y (+ (* 10 y) x))))

(define (eval-expr expr)
  (match expr
    ((op expr1 n1)
     (let ((n2 (eval-expr expr1)))
       (cond
	((eq? op '+) (+ n2 n1))
	((eq? op '-) (- n2 n1)))))
    (n n)))

(define (print-expr expr)
  (match expr
    ((op expr1 n1) (format #f "~a ~a ~a" (print-expr expr1) op n1))
    (n (number->string n))))

(define (check-result expr)
  (when (= result (eval-expr expr))
    (format #t "~a = ~a~%" (print-expr expr) result)))

(define (iter expr n)
  (if (< n 0) (check-result expr)
      (begin
	(iter (plus expr n) (- n 1))
	(iter (minus expr n) (- n 1))
	(iter (glue expr n) (- n 1)))))

(define (run-yablokon)
  (statprof
   (λ ()
     (iter 9 8)))

scheme@(guile-user)> (run-yablokon)
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
%     cumulative   self             
time   seconds     seconds  procedure
100.00      0.02      0.02  <current input>:1212:16:glue
  0.00      0.10      0.00  <current input>:3402:16:iter
---
Sample count: 1
Total time: 0.016578398 seconds (0.0 seconds in GC)

 fn main() {
    let target = 200;
    let digs: Vec<char> = "9876543210".chars().collect();
    let ops = ["", " +", " -"];
    let mut expr = "".to_string();
    let mut inds = [0; 10];
    for i in 0..3usize.pow(9u32) {
        tern_inds(&mut inds, i);
        for pi in 0..inds.len() {
            expr.push(digs[pi]);
            expr.push_str(ops[inds[pi]]);
        }
        if target == expr.split_whitespace().map(|s| s.parse::<i64>().unwrap()).sum::<i64>() {
            println!("{}={target}", expr.replace(' ', ""));
        }
        expr.clear();
    }
}
fn tern_inds(ps: &mut [usize], iter: usize) {
    let mut q = iter;
    for p in ps { 
        (q, *p) = (q / 3, q % 3);
    }
}

Benchmark 1: ./target/release/lortst
  Time (mean ± σ):       7.6 ms ±   2.9 ms    [User: 6.1 ms, System: 1.3 ms]
  Range (min … max):     3.6 ms …  13.2 ms    500 runs

#include <stdint.h>
#include <stddef.h>
#include <stdio.h>

#define TARGET 200
#define FIRST 9
#define LAST 0

#define SIZEOF(a) (sizeof(a)/sizeof((a)[0]))
#define NUM(i) (FIRST - 1 - (i))
#define Q(t) Q_(t)
#define Q_(t) #t

typedef enum Op {INIT = -2, SUB = -1, CAT = 0, ADD = 1, DONE = 1} Op;

static int64_t eval(Op *ops, size_t n)
{
    int64_t res = 0, a = FIRST;
    size_t i = 0;
    Op op = ADD;
    for(i = 0; i < n; i++) {
        if(ops[i] == CAT) {
            a *= 10;
        } else {
            res += a * op;
            a = 0;
            op = ops[i];
        }
        a += NUM(i);
    }
    res += a * op;
    return res;
}

static void output(Op *ops, size_t n)
{
    size_t i;
    fputc('0' + FIRST, stdout);
    for(i = 0; i < n; i++) {
        if(ops[i] != CAT) fputs(ops[i] == ADD ? "+" : "-", stdout);
        fputc('0' + NUM(i), stdout);
    }
}

int main()
{
    Op ops[FIRST - LAST] = {INIT};
    size_t i = 0;
    while(!(i == 0 && ops[0] == DONE)) {
        if(ops[i] == DONE) {
            i--;
        } else {
            ops[i]++;
            if(i + 1 < SIZEOF(ops)) {
                ops[++i] = INIT;
            } else if(eval(ops, SIZEOF(ops)) == TARGET) {
                output(ops, SIZEOF(ops));
                fputs(" == " Q(TARGET) "\n", stdout);
            }
        }
    }
    return 0;
}

target = 200

data Op = Cat | Add | Sub
    deriving Enum
type Expr = [Op]
type Result = [Expr]

walk :: Result -> Expr -> Integer -> Op -> Result
walk r e 0 op = (reverse (op:e)):r
walk r e i op = concat $ map (walk r (op:e) (i-1)) [toEnum 0 ..]

showExpr :: Expr -> String
showExpr e = concat $ map s $ zip e $ reverse [0 .. 9]
    where
        o Cat = ""
        o Add = "+"
        o Sub = "-"
        s (a, b) = o a ++ show b

evalExpr :: Expr -> Integer
evalExpr = eval_ (0::Integer) (0::Integer) Add
    where
        fop Add = (+)
        fop Sub = (-)
        num = toInteger . length
        eval_ :: Integer -> Integer -> Op -> Expr -> Integer
        eval_ r n op [] = fop op r n
        eval_ r n op (Cat:e) = eval_ r (10*n+(num e)) op e
        eval_ r n op (o:e) = eval_ (fop op r n) (num e) o e

main = mapM_ (putStrLn . showExpr) $  filter t $ walk [] [] 9 Cat
    where
        t e = evalExpr e == target

package test;

import java.util.regex.MatchResult;
import java.util.regex.Pattern;

public class Test {

  public static void main(String[] args) {
    generate(8, "9");
  }

  private static void generate(int n, String s) {
    if (n == -1) {
      check(s);
    } else {
      generate(n - 1, s + n);
      generate(n - 1, s + "+" + n);
      generate(n - 1, s + "-" + n);
    }
  }

  private static final Pattern pattern = Pattern.compile("[+-]?\\d+");

  private static void check(String s) {
    var value = pattern.matcher(s).results()
        .map(MatchResult::group)
        .mapToLong(Long::parseLong)
        .sum();
    if (value == 200) {
      System.out.println(s);
    }
  }

}

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

int main() {
  int bits[9];
  for (int mask = 0; mask < 19683; ++mask) {
    int64_t total = 9, cs = 9;
    for (int i = 8, cur = mask; i >= 0; --i, cur /= 3) {
      bits[i] = cur % 3;
      if (bits[i] == 2) { // 56
        total -= cs;
        cs = cs * 10 + i * ((cs >> 63) * 2 + 1);
      } else // 5 +- 6
        cs = i * (1 - bits[i] * 2);
      total += cs;
    }
    const char sign[] = "+-\0";
    if (total == 200) {
      printf("9");
      for (int i = 8; i >= 0; --i)
        printf("%c%d", sign[bits[i]], i);
      puts("");
    }
  }
}

$ gcc main.c && ./a.out | tr -d '\0' | bc -i | tail
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

#include <stdio.h>

void f(char *s0, char *s1, int n, long long x, long long y, int z) {
  if (n >= 0) {
    s1[0] = '0' + n;
    f(s0, s1 + 1, n - 1, x, y * 10 + n, z);
    s1[0] = '+';
    s1[1] = '0' + n;
    f(s0, s1 + 2, n - 1, x + y * z, n, 1);
    s1[0] = '-';
    f(s0, s1 + 2, n - 1, x + y * z, n, -1);
  } else if (x + y * z == 200)  {
    s1[0] = 0;
    puts(s0);
  }
}

int main(void) {
  char s0[18] = "9";
  f(s0, s0 + 1, 8, 0, 9, 1);
}

let numbers = ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']
const MATCH_NUMBER = 200

const eval_expr = (expr) =>
  expr
    .replaceAll('-', '+-')
    .split('+')
    .map(Number)
    .reduce((a, b) => a + b, 0)

let expression = []
function calc(numbers) {
  const num = numbers.shift()
  expression.push(num)

  if (numbers.length) {
    expression.push('+')
    calc(numbers)
    expression.pop()

    expression.push('-')
    calc(numbers)
    expression.pop()

    expression.push('')
    calc(numbers)
    expression.pop()
  } else {
    const expr = expression.join('')
    if (eval_expr(expr) === MATCH_NUMBER) {
      console.log(`${expr} = ${MATCH_NUMBER}`)
    }
  }
  expression.pop()
  numbers.unshift(num)
}

calc(numbers)

let input = '9876543210'.split('')
const MATCH_NUMBER = 200

const eval_expr = (expr) =>
  expr
    .replaceAll('-', '+-')
    .split('+')
    .map(Number)
    .reduce((a, b) => a + b, 0)

function calc(numbers, expr = []) {
  const [num, ...rest] = numbers
  if (rest.length) {
    calc(rest, [...expr, num, '+'])
    calc(rest, [...expr, num, '-'])
    calc(rest, [...expr, num])
  } else {
    const expression = [...expr, num].join('')
    if (eval_expr(expression) === MATCH_NUMBER) {
      console.log(`${expression} = ${MATCH_NUMBER}`)
    }
  }
}

calc(input)