Сделайте математику с минимальными спичками

15

Мета-фон

Это было задано как вопрос о загадке , и мгновенная реакция была «ну, кто-то просто решит это с помощью компьютера». Был спор о том, насколько сложной должна быть программа для ее решения. Что ж, «насколько сложной должна быть эта программа» - это в значительной степени определение , так что, возможно, PPCG может решить эту проблему?

Фон

Уравнение спички в основном нормальное математическое уравнение, но где цифра и операторы строятся физически, помещая спички на стол. (Главная существенная особенность спичек здесь заключается в том, что они довольно жесткие и имеют постоянную длину; иногда вместо этого люди используют другие предметы, такие как ватные палочки.)

Для этой задачи нам не нужно определять конкретные правила расположения спичек (как это делает связанная задача); Скорее, мы просто заботимся о том, сколько спичек нам нужно, чтобы представить выражение, которое оценивает данное число.

Задание

Вот алфавит цифр и математических операторов, которые вы можете использовать, каждый из которых имеет стоимость в спичках:

  • 0, стоимостью 6 спичек
  • 1, стоимостью 2 спичек
  • 2, стоимостью 5 спичек
  • 3, стоимостью 5 спичек
  • 4, стоимостью 4 спичек
  • 5, стоимостью 5 спичек
  • 6, стоимостью 6 спичек
  • 7, стоимостью 3 спичек
  • 8, стоимостью 7 спичек
  • 9, стоимостью 6 спичек
  • +, стоимостью 2 спичек
  • -, стоимостью 1 спичка
  • ×, стоимостью 2 спичек

(Вы можете представить ×как *в выходных данных вашей программы, если хотите, чтобы избежать необходимости использовать не-ASCII символы. В большинстве кодировок ×занимает больше байтов, чем *, и поэтому я полагаю, что большинство программ захотят воспользоваться этой свободой .)

Вам нужно написать программу, которая принимает неотрицательное целое число в качестве входных данных (с помощью любых разумных средств ) и создает выражение, которое оценивается как это целое число в качестве выходных данных (опять же с помощью любых разумных средств). Кроме того, выражение должно быть нетривиальным: она должна содержать по крайней мере один оператор +, -или ×. Наконец, выводимое вами выражение должно быть самым дешевым (или привязанным к самым дешевым) с точки зрения общей стоимости соответствия, среди всех выходов, которые в остальном соответствуют спецификации.

Разъяснения

  • Вы можете сформировать многозначные числа путем вывода нескольких цифр подряд (например 11-1, это допустимый вывод для производства 10). Просто чтобы быть полностью точным, полученное число интерпретируется в десятичном виде. Такая конкатенация не является операцией, которая работает с промежуточными результатами; только на буквальных цифрах, которые появляются в исходном выражении.
  • Для цели этого вызова. +, -и ×являются инфиксными операторами; им нужен аргумент слева и справа. Вы не можете использовать их в позиции префикса, как +5или -8.
  • У вас нет скобок (или любого другого способа управления приоритетом). Выражение оценивается в соответствии с типичными правилами приоритета по умолчанию (сначала умножения, а затем сложения и вычитания оцениваются слева направо).
  • У вас нет доступа ни к каким математическим операторам или константам, кроме перечисленных выше; Решения «латерального мышления» часто принимаются в Puzzling, но не имеет смысла требовать, чтобы компьютер сам придумывал их, и здесь, в PPCG, нам нравится, когда мы объективны, является ли решение правильным.
  • Применяются обычные правила целочисленного переполнения: ваше решение должно быть в состоянии работать с произвольно большими целыми числами в гипотетической (или, возможно, реальной) версии вашего языка, в которой все целые числа не ограничены по умолчанию, но если ваша программа дает сбой на практике из-за реализации не поддерживает такие большие целые числа, что не делает решение недействительным.
  • Если вы используете одну и ту же цифру или оператора более одного раза, вам придется оплачивать ее стоимость спички каждый раз, когда вы ее используете (поскольку, очевидно, вы не можете повторно использовать одни и те же физические спички в двух разных местах на столе).
  • Там нет ограничения по времени; грубой силы решения приемлемы. (Хотя если у вас есть решение, которое быстрее, чем грубая сила, не стесняйтесь публиковать его, даже если оно длиннее; посмотреть, как альтернативные подходы сравниваются, всегда интересно.)
  • Хотя написание объяснения вашего кода никогда не требуется , это, вероятно, будет хорошей идеей; Решения часто очень трудно читать (особенно людям, не знакомым с языком, на котором они написаны), и может быть сложно оценить (и, следовательно, проголосовать) решение, если вы не понимаете, как оно работает.

Состояние победы

В качестве проблемы ответы с меньшим количеством байтов считаются лучшими. Однако, как обычно, не стесняйтесь публиковать ответы с разными подходами или на определенных языках, даже если они более многословны, чем некоторые другие языки; цель игры в гольф на самом деле - увидеть, насколько далеко вы можете оптимизировать конкретную программу, и выполнение таких действий дает нам множество потенциальных программ для оптимизации. Так что не расстраивайтесь, если кто-то представит решение с использованием совершенно другого подхода или совершенно другого языка и получит гораздо более короткий ответ; вполне возможно, что ваш ответ лучше оптимизирован и показывает больше навыков, и избиратели в PPCG часто это ценят.

Сообщество
источник
Боже, какое наибольшее число нам нужно обработать? Моя текущая попытка не превысила бы ... может быть, 20 на TIO.
Волшебная Осьминог Урна
@carusocomputing: произвольно высокий в теории , но если вы не можете получить более 20 в течение разумного времени на практике, это вполне приемлемо.
4
У вас есть какие-нибудь тесты?
Люк,
Я действительно хотел бы, чтобы это была одна операция, развернутая против нескольких соревнований. Умножение - это проблема делителей, но сложение и вычитание действительно усложняют ситуацию. У меня есть решение, которое работает, но не для сложения и вычитания; сделать эту работу отлично будет утомительно.
Волшебный Осьминог Урна
@carusocomputing: Тогда вас может заинтересовать этот вызов . Я подозреваю, что проблема с умножением только существенно отличается и потребует довольно разных методов решения, чтобы получить хороший результат.

Ответы:

1

Python2, 1̶9̶8̶ ̶b̶y̶t̶e̶s̶ 182 байта благодаря math_junkie

def f(n,c=dict(zip('0123456789+-*',map(int,'6255456376212'))),e=[(0,'')]):
 while 1:
    v=(m,s)=min(e);e.remove(v)
    try:
     if eval(s)==n:return s
    except:0
    e+=[(m+c[x],s+x)for x in c]

Этот алгоритм не делает ничего, чтобы исключить префиксные версии +и -, но они будут либо хуже, либо равны последующим в поиске аналогичным инфиксным аналогам. Поскольку он использует ключевое слово аргумент eизменчиво, он даст недопустимые результаты, если вызывается несколько раз за сеанс. Чтобы исправить это, используйте f(n, e=[(0,'')])вместо просто f(n). Обратите внимание, что отступы в четыре интервала представляют вкладки, поэтому это будет работать только с Python 2.

У меня также есть неопрятная и оптимизированная версия, которая работает быстро даже для довольно большого числа:

from heapq import heappop, heappush

def f(n):
    digits = list('0123456789')
    ops =['+','-','*','']
    costs = dict(zip(digits + ops, [6,2,5,5,4,5,6,3,7,6,2,1,2,0]))
    expressions = [(costs[d], abs(n - int(d)), int(d), d) for d in digits[1:]]
    seen = set()
    while 1:
        cost, d, k, expression = heappop(expressions)
        if d == 0:
            return expression
        for op in ops:
            if op in '+-' and k in seen:
                continue
            for digit in digits:
                if op and digit == '0':
                    continue
                expression1 = expression + op + digit
                k1 = eval(expression1)
                d1 = abs(n - k1)
                if d1 == 0:
                    return expression1
                heappush(expressions, (cost+costs[op]+costs[digit], d1, k1, expression1))
        seen.add(k)
user1502040
источник
Некоторые несовершеннолетние предложили
математик-наркоман
1

PHP, 241 байт

Онлайн версия

function m($i){for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e;}foreach($r=range(0,2*$a=$argv[1])as$v)foreach($r as$w)$x[$v+$w]["$v+$w"]=$x[$v*$w]["$v*$w"]=1+$x[$v-$w]["$v-$w"]=m("$v")+m("$w")+1;echo array_search(min($x[$a]),$x[$a]);

Сломать

function m($i){
    for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e; #return the count of the matchstick for an integer
}

foreach($r=range(0,2*$a=$argv[1])as$v) # limit to an input to 300 in the online version
foreach($r as$w)
       $x[$v+$w]["$v+$w"]=  #fill the 2D array in the form [result][expression] = count matchsticks
       $x[$v*$w]["$v*$w"]=
       1+$x[$v-$w]["$v-$w"]=
       m("$v")+m("$w")+1;
echo $k=array_search(min($x[$a]),$x[$a]); # Output expression with a minium of matchsticks
echo"\t".$x[$a][$k]; #optional Output of the count of the matchsticks

Путь с немного лучшей производительностью

function m($i){
for(;$s<strlen($i);)
$e+="6255456376"[$i[$s++]];return$e;} #return the count of the matchstick for an integer
foreach($r=range(0,2*$a=$argv[1])as$v)
foreach($r as$w){$c=m("$v")+m("$w")+1;
if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
if($a==$v*$w)$x["$v*$w"]=1+$c;
if($a==$v-$w)$x["$v-$w"]=$c;}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
    echo"\t".$x[$k]; #optional Output of the count of the matchsticks

Поддержка отрицательных целых чисел

Версия с отрицательными целыми числами

function m($i){
    $e=$i<0?1:0; # raise count for negative integers
    for($s=0;$s<strlen($i);)$e+=[6,2,5,5,4,5,6,3,7,6][$i[$s++]];return$e; #return the count of the matchstick for an integer
}
$q=sqrt(abs($argv[1]));
$l=max(177,$q);
$j=range(-$l,$l); # for second loop for better performance
foreach($r=range(min(0,($a=$argv[1])-177),177+$a)as$v) 
foreach($j as$w){$c=m("$v")+m("$w")+1;  
    if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
    if($a==$v*$w)$x["$v*$w"]=1+$c;
    if($a==$v-$w)$x["$v-$w"]=$c;
    if($a==$w-$v)$x["$w-$v"]=$c; # added for integers <0
}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
echo"\t".$x[$k]; #optional Output of the count of the matchsticks
Йорг Хюльсерманн
источник
Ох, хватит, это работает и на отрицательных числах!
Волшебный Осьминог Урна
@carusocomputing на самом деле не могло быть, что существует решение с меньшим количеством спичек, потому что отрицательные числа добавляются только вычитанием. в этом случае вы должны также проверить абсолютное значение и добавить одно
Йорг Хюльсерманн
Я не думаю, что литерал 333 был бы здесь приемлем, хотя вы, вероятно, могли бы исправить это, сделав его некоторой функцией ввода. (Программа может работать намного медленнее, так что вы можете оставить жестко запрограммированную версию для тестирования.)
1
@ ais523 выполнено 333 заменено на 2 * вход
Йорг Хюльсерманн
1
Вы можете индексировать строки: $e+="6255456376"[$i[$s++]];.
manatwork