Красивая задачка

[vak]

Дана строка:

123456789

Вставить кое-где между цифрами знаки + или *, чтобы при вычислении формулы получилось ровно 100.

Comments

[juan_gandhi]

Это программировать надо, или в голове решить?

[spamsink]

Я ленив, я запрограммировал (см. ниже).

[vak]

Программировать, конечно. Зачем голову напрягать. :)

[spamsink]

Что, простите?

sh-4.2$ for i in 1{,\+,\*}2{,\+,\*}3{,\+,\*}4{,\+,\*}5{,\+,\*}6{,\+,\*}7{,\+,\*}8{,\+,\*}9 ; do j=$(($i)); if [ $j = 100 ] ; then echo $i; fi; done
12+34+5*6+7+8+9
12+3*4+5+6+7*8+9
1+2+3+4+5+6+7+8*9
1+2*3+4+5+67+8+9
1*2+34+5+6*7+8+9
1*2*3+4+5+6+7+8*9
1*2*3*4+5+6+7*8+9

[vak]

Красиво!
Шелл мощная штука.

[spamsink]

И я ещё переборщил, плюсы от страха заэкранировал, хотя не надо было.

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

[juan_gandhi]

Думал, на скале примерно столько же. Ан нет. Не меньше четырех (неинтересно, в результате).

[vak]

Можно ещё маленько упростить.

for i in 1{,+,\*}2{,+,\*}3{,+,\*}4{,+,\*}5{,+,\*}6{,+,\*}7{,+,\*}8{,+,\*}9; do (($i == 100)) && echo $i; done

[spamsink]

(($i == 100))

Я не знал, что так можно.

[vak]

Когда-то много лет назад я сел и проштудировал статью про все расширения bash. Потом пригодилось по жизни.

[vak]

Еще красивее выходит, если чуть изменить задачу: вставлять знаки плюс и минус.

$ for i in 1{,+,-}2{,+,-}3{,+,-}4{,+,-}5{,+,-}6{,+,-}7{,+,-}8{,+,-}9; do (($i == 100)) && echo $i; done
123+45-67+8-9
123+4-5+67-89
123-45-67+89
123-4-5-6-7+8-9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
1+23-4+56+7+8+9
1+23-4+5+6+78-9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9

[henry_flower]

1-liner на рубі:

$ ruby -v
ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-linux]

$ ruby -e 'pp ["","+","*"].repeated_permutation(8).map{|v| (1..9).zip(v).join }.filter {|v| eval(v) == 100}'
["12+34+5*6+7+8+9",
 "12+3*4+5+6+7*8+9",
 "1+2+3+4+5+6+7+8*9",
 "1+2*3+4+5+67+8+9",
 "1*2+34+5+6*7+8+9",
 "1*2*3+4+5+6+7+8*9",
 "1*2*3*4+5+6+7*8+9"]

[vak]

Оце мабуть саме елегантне рішення.

[euthanasepam]

(Записал в блокнотЪ.)

[henry_flower]

те саме, але без циклів, ггг:

eval echo $(seq -f '%.f{,+,*}' -s '' 1 8)9 | sed -E 's/\S+/if (& == 100) print "&\\n"\n/g' | bc

[vak]

На лінуксі працює, але на Mac не той sed мабуть.

[euthanasepam]

Cygwin, bash:

$ time eval echo $(seq -f '%.f{,+,*}' -s '' 1 8)9 | sed -E 's/\S+/if (& == 100) print "&\\n"\n/g' | bc

12+34+5*6+7+8+9
12+3*4+5+6+7*8+9
1+2+3+4+5+6+7+8*9
1+2*3+4+5+67+8+9
1*2+34+5+6*7+8+9
1*2*3+4+5+6+7+8*9
1*2*3*4+5+6+7*8+9

real    0m4,019s
user    0m0,592s
sys     0m2,759s


$ time for i in 1{,\+,\*}2{,\+,\*}3{,\+,\*}4{,\+,\*}5{,\+,\*}6{,\+,\*}7{,\+,\*}8{,\+,\*}9 ; do j=$(($i)); if [ $j = 100 ] ; then echo $i; fi; done

12+34+5*6+7+8+9
12+3*4+5+6+7*8+9
1+2+3+4+5+6+7+8*9
1+2*3+4+5+67+8+9
1*2+34+5+6*7+8+9
1*2*3+4+5+6+7+8*9
1*2*3*4+5+6+7*8+9

real    0m0,222s
user    0m0,203s
sys     0m0,000s

[spamsink]

Много ли корысти в отсутствии циклов, если приходится аж три внешних процесса вызывать? И гораздо медленнее получается.

[euthanasepam]

Да, очень медленнее. Я как раз только что запостил, вашего коммента ещё не было.

[henry_flower]

то була пародія на code golf з metaprogramming

[sun_jr]

Ничоси!!!

Решение на Питоне

[vak]

from itertools import product, chain

s = list(map(str, range(2, 10)))
for x in product(*[["", "+", "*"]] * len(s)):
    expr = "1" + ''.join(chain.from_iterable(zip(x, s)))
    if eval(expr) == 100:
        print(expr)

На Прологе

[yury_yuschenko]

/* На Прологе решение тоже почти в одну строку. Три очень простых: подготовительных, а остальное можно в одной строке записать.
Лично мне больше всего по душе прозрачность и читабельность решения на Прологе, чем другими средствами.
Уж очень люблю Пролог.*/

/* Определяем трехэлементную множество: */
d ( "+").
d ( «*»).
d ( "").
/* остальное можно записать в одной строке */

s (S): - d (X1), d (X2), d (X3), d (X4), d (X5), d (X6), d (X7), d (X8), / * эта строка : строим восьмую декартову степень 3-х элементной множества: количество элементов: 3 ^ 8 = 6561 * /

/* Заполнения между 9 цифрами всеми возможными вариантами */
/* Формируем строку для пользователя: конкатенация кортежей с элементами кортежей декартова произведения: */

/* Конкатенацию "1 ++ X1 ++ 2 ++ X2 ++ 3 ++ X3 ++ 4 ++ X4 ++ 5 ++ X5 ++ 6 ++ X6 ++ 7 ++ X7 ++ 8 *" необходимо записать длинным текстом, но при решении с использованием списков и рекурсии получится лаконично и без привязки к длине входной строки цифр */
concat (1, X1, S01), concat (S01, 2, S02),
concat (S02, X2, S03), concat (S03, 3, S04),
concat (S04, X3, S05), concat (S05, 4, S06),
concat (S06, X4, S07), concat (S07, 5, S08),
concat (S08, X5, S09), concat (S09, 6, S10),
concat (S10, X6, S11), concat (S11, 7, S12),
concat (S12, X7, S13), concat (S13, 8, S14),
concat (S14, X8, S15), concat (S15, 9, S).

/* Строку для пользователя преобразуем в терм (формулу). Подсчет с фильтрацией. Печать. (вынесено в отдельную строку для простоты восприятия */
ss (X): - s (A), term_string (Q, A), X is Q, print (Q).

Это всё. Далее запрос и его результат:

? - ss (100).

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9
1true
1 + 2 * 3 + 4 + 5 + 67 + 8 + 9
2true
1 * 2 + 34 + 5 + 6 * 7 + 8 + 9
3true
1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9
4true
1 * 2 * 3 * 4 + 5 + 6 + 7 * 8 + 9
5true
12 + 3 * 4 + 5 + 6 + 7 * 8 + 9
6true
12 + 34 + 5 * 6 + 7 + 8 + 9
7true

[vak]

А как этот код можно запустить?
Я пробовал GNU Prolog 1.5.0 и SWI-Prolog 8.2.4 - оба дают ошибки.

В онлайне, например:

[yury_yuschenko]

https://swish.swi-prolog.org/
Это в SWI-Prolog, который поддерживает стандарт.
В GNU Prolog 1.5.0 и SWI-Prolog 8.2.4 не должно давать ошибки.
При копировании и вставке кода были вставлены в недопустимых местах пробелы и заменены кавычки на неправильные.
Этот код проверен в он-лайн интерпретаторе SWI:

/* На Прологе решение тоже почти в одну строку. Три очень простых: подготовительных, а остальное можно в одной строке записать.
Лично мне больше всего по душе прозрачность и читабельность решения на Прологе, чем другими средствами.
Уж очень люблю Пролог.*/

/* Определяем трехэлементную множество: */
d("+").
d("*").
d("").
/* остальное можно записать в одной строке */

s(S) :- d(X1), d(X2), d(X3), d(X4), d(X5), d(X6), d(X7), d(X8), /* эта строка: строим восьмую декартову степень 3-х элементной множества: количество элементов: 3 ^ 8 = 6561 */

/* Заполнения между 9 цифрами всеми возможными вариантами */
/* Формируем строку для пользователя: конкатенация кортежей с элементами кортежей декартова произведения: */

/* Конкатенацию "1 ++ X1 ++ 2 ++ X2 ++ 3 ++ X3 ++ 4 ++ X4 ++ 5 ++ X5 ++ 6 ++ X6 ++ 7 ++ X7 ++ 8 *" необходимо записать длинным текстом, но при решении с использованием списков и рекурсии получится лаконично и без привязки к длине входной строки цифр */
concat(1, X1, S01), concat(S01, 2, S02),
concat(S02, X2, S03), concat(S03, 3, S04),
concat(S04, X3, S05), concat(S05, 4, S06),
concat(S06, X4, S07), concat(S07, 5, S08),
concat(S08, X5, S09), concat(S09, 6, S10),
concat(S10, X6, S11), concat(S11, 7, S12),
concat(S12, X7, S13), concat(S13, 8, S14),
concat(S14, X8, S15), concat(S15, 9, S).

/* Строку для пользователя преобразуем в терм (формулу). Подсчет с фильтрацией. Печать. (вынесено в отдельную строку для простоты восприятия */
ss(X) :- s(A), term_string(Q, A), X is Q, print(Q).

Re: В онлайне, например:

[vak]

Пробую в онлайне.
Уже на первую строку выдаёт ошибку:

d("+").
procedure `d(A)' does not exist

Только одна строка?

[yury_yuschenko]

Пробуй:
1. Всё перед строкой удалить (могли "вкрасться" нежелательные символы до этой строки).
2. Оставить только эту строку. Запрос: ?- d(X).

Имею единое предположение: перед строкой нечто есть, что интерпретатор воспринимает в качестве синтаксической лексемы, что приводит к обнаружению ошибки в последующем тексте.

[vak]

Одна строка, ничего больше.

[yury_yuschenko]

Проще не бывает:
man(serg).

Запрос:
?- man(Who).

Неверное понял. Ты из режима блокнота, а программа ещё "пустая" и Пролог не видит "d".

В программу (режим "Program") и всё будет работать (создать Программу).

[vak]

Действительно, в режиме Program всё заработало.
Спасибо!

ss(100).
1+2+3+4+5+6+7+8*9
true
1+2*3+4+5+67+8+9
true
1*2+34+5+6*7+8+9
true
1*2*3+4+5+6+7+8*9
true
1*2*3*4+5+6+7*8+9
true
12+3*4+5+6+7*8+9
true
12+34+5*6+7+8+9
true

[x86128]

На Прологе это конечно сильно :)
Какая там глубина рекурсии интересно получилась?

[xexe]

Ванілла жабоскрипт:

// Permutations as radix 3 numbers
Array.from({ length: parseInt('22222222', 3) }, (_, i) => i.toString(3).replaceAll(/[0-2]/g, m => [' ','+','*'][m]).padStart(8, ' '))
// Zip
.map(p => Array.from(p).reduce((exp, o, i) => `${exp}${o === ' ' ? '' : o}${i+2}`, '1'))
// Eval and filter
.map(e => [e, eval(e)]).filter(([_, r]) => r === 100).map(p => p[0])

[vak]

Решение на SQL:

WITH 
signs AS (
    SELECT '+' AS s, 1 AS sv 
    UNION 
    SELECT '-' AS s, -1 AS sv 
    UNION 
    SELECT NULL AS s, NULL AS sv
),
curr (s, c, expr, value) AS (
    SELECT signs.s, 1 AS c, CAST(1 * signs.sv AS varchar(20)) AS expr, 1 * signs.sv AS value
    FROM signs WHERE signs.s IS NOT NULL
    UNION ALL
    SELECT signs.s, curr.c + 1 AS c, 
        CAST(curr.expr + ISNULL(signs.s, '') + CAST((curr.c + 1) AS varchar(1)) AS varchar(20)) AS expr, 
        CASE 
            WHEN signs.s IS NULL THEN 
                CASE 
                    WHEN curr.value >= 0 THEN curr.value * 10 + (curr.c + 1) 
                    ELSE curr.value * 10 - (curr.c + 1) 
                END
            WHEN signs.s = '+' THEN curr.value + curr.c + 1
            ELSE curr.value - (curr.c + 1)
        END AS value
    FROM curr CROSS JOIN signs
    WHERE curr.c < 9
)
SELECT expr FROM curr
WHERE value = 100

Отсюда: https://arbinada-com-feed.dreamwidth.org/10751.html

[abalaeff]

Я в детстве такую задачку решал для каждого автобусного билета 🙂 Получить 100 и 101. Знаки – все 4 действия арифметики, плюс скобки.

[vak]

Точно, было по малолетству такое развлечение! Я уже и забыл. Для билета, конечно, все операции нужны, цифр ведь маловато.