Wygeneruj prawidłowe równanie przy użyciu liczb określonych przez użytkownika

Opiera się na grze, w którą grał mój nauczyciel matematyki w gimnazjum. Napisał na planszy 5 losowych jednocyfrowych liczb, a następnie losową dwucyfrową liczbę. Staramy się stworzyć równanie, w którym wszystkie 5 liczb jednocyfrowych daje dwucyfrową liczbę. Oto kilka przykładów rozwiązań pozwalających lepiej to wyjaśnić:

Input:           Solution:
7 5 4 8 4 34     5*8-7+4/4 = 34
3 1 5 7 6 54     (7+3)*6-5-1 = 54
3 9 2 1 6 87     9*(2+1)*3+6 = 87
2 1 6 9 7 16     (9-7+6*1)*2 = 16
2 4 5 8 6 96     8*(5+6)+2*4 = 96
3 8 4 5 4 49     8*(4+4)-3*5 = 49

Wyzwaniem jest napisanie programu, który może generować takie równania dla danych wejściowych. Dane wejściowe można podać za pomocą wiersza polecenia lub monitu. 5 liczb jednocyfrowych zawsze będzie wprowadzanych jako pierwsze (w określonej kolejności), a następnie dwucyfrowa liczba. Następnie program wydrukuje znalezione równanie rozwiązania; nie musisz radzić sobie z sytuacjami, w których nie ma rozwiązania. Funkcja musi być zdolna do użycia w równaniu następujących operacji: dodawanie, odejmowanie, mnożenie i dzielenie. Jeśli chcesz zezwolić na dodatkowe podstawowe operacje, to dobrze, o ile pozostają w duchu wyzwania (negacja, potęgowanie i moduł byłyby miłymi dodatkami). Kolejność operacji jest zgodna ze standardowymi regułami matematycznymi, więc nawiasy będą potrzebne do grupowania.

Programy będą oceniane na podstawie długości kodu (w tym wymaganej spacji). Uwaga: podział musi być dokładny, nie może być zaokrąglany ani obcinany do najbliższej liczby całkowitej.

Python 2.7 (284), Python 3.x (253)

from __future__ import division #(Remove for Python 3.x)
from itertools import *
a=raw_input().split()
for i in permutations(a[:-1],5):
 for j in product('+-*/',repeat=5):
  for k,l in combinations(range(1,12,2),2):
   d=''.join(sum(zip(i,j),()))[:-1];d='('+d[:l]+')'+d[l:]
   if eval(d)==int(a[-1]):print d;b

Daje błąd (wywołanie nieznanej funkcji b) w rozwiązaniu.

Zasadniczo jest to gigantyczna brutalna siła. Pobiera dane wejściowe, dzieli je według spacji ( 1 2 -> [1,2]), a następnie permutuje przez tę listę. Przy każdej permutacji będzie iterował wszystkie możliwe ciągi długości 5 przy użyciu znaków +-*/. Z każdą z tych iteracji wygeneruje kombinacje długości 2 listy [1,3,5,7,9,11], przeplata permutację i ciąg znaków razem ( 12345 *-/+- -> 1*2-3/4+5-) i umieści w nawiasach. W końcu to oceni, a jeśli odpowiedź i równanie są prawdziwe, to wypisze równanie i zatrzyma się.

Jest to okropnie nieefektywne, O(n!/(n-5)!)=O(n^5)ale działa w rozsądnym czasie dla wejść testowych.

Scala 368:

Druga g = -Linia jest łatwiejsza do przetestowania, pierwsza jest elastyczna, aby przyjmować argumenty poleceń, a obie mają jednakową długość, więc liczę tylko od drugiej - usuń ją, aby przekazać argumenty:

val g=(args.map(_.toDouble))
val g=Array(3,9,2, 1, 6, 87)
val k="+*/-DQ"
val i=(0 to 5)
val f:Seq[(Double,Double)=>Double]=Seq(_+_,_*_,_/_,_-_,(a,b)=>b-a,(a,b)=>b/a)
val h=g.init.permutations;
for(j<-h;o<-i;p<-i;q<-i;r<-i;z=try{f(r)(f(q)(f(p)(f(o)(j(0),j(1)),j(2)),j(3)),j(4))}catch{case _ => 0}
if(z==g(5)))printf("(((%d%c%d)%c%d)%c%d)%c%d=%d\n",j(0),k(o),j(1),k(p),j(2),k(q),j(3),k(r),j(4),g(5))

Przykładowe dane wyjściowe (możesz mieć teraz pytanie - za chwilę):

(((5+7)/1)+6)*3=54
(((5-7)D1)*6)*3=54
(((5D7)+1)*6)*3=54
(((5+7)+6)Q1)Q3=54

Co z tą rzeczą 5D7? D1? Czy to hex? Jest Q1, Q3 - co to jest.

Sir_Lagsalot dopuścił nowe podstawowe operacje w duchu wyzwania, i tak, są to podstawowe operacje, Delta i Iloraz.

Różnią się od a / b i ab tym, że aQb oznacza b / a aDb oznacza ba. Nazwijmy to notacją ukraińską.

Więc

(((5-7)D1)*6)*3=54

znaczy

((1-(5-7))*6)*3=54
 (1-(-2))*6*3
   3*6*3 = 18*3=54

Na bardziej interesujące pytanie, jak i dlaczego: Na początku oszalałem na punkcie możliwości umieszczania nawiasów i czy (a + b) -c = a + bc = (a + bc) = ((a + b ) -c) = (b + a) -c i tak dalej. Możesz zwariować na punkcie tego pytania, ale jeśli zapiszesz możliwe kombinacje w nawiasach, czasami wyrzucasz skrobak i stajesz przed faktem: zawsze wykonujesz 4 operacje pomiędzy 5 wartościami i zawsze zaczynasz od jednej z nich. Jeśli wzorzec jest zawsze (((_x_)x_)x_)x_ ?= _(x jest jednym z 4 operatorów) i pozwala na odwrotny kierunek (xb) i (bxa), uwzględniłeś każdą możliwość.

Teraz dla a + bi a * b nie potrzebujemy żadnego przeciwnego kierunku, są one przemienne. Wynalazłem więc operatora D i Q, który po prostu zmienia kierunek. Mam teraz 2 operatorów więcej, ale nie muszę zmieniać kierunku. Cóż - odbywa się to w funkcji Sekwencja:

 (a,b)=>b-a,(a,b)=>b/a

Moje zrozumienie bierze wartości z Tablicy g i dystrybuuje je na a do e, następnie wybieram 4 indeksy, aby wybrać funkcję, a później (tylko według indeksu) powiązany symbol operatora. Muszę wychwycić błędy div / 0, ponieważ odejmowanie może prowadzić do zer, podczas gdy przykładowe dane wejściowe nie zawierają 0.