Utilizzo di RPN (notazione polacca inversa)

Per l’intro RPN vedi qui .

La dimensione del problema

Dobbiamo build un elenco di quattro numeri, che implica 3 operatori.
Questi numeri e operatori verranno spinti o eseguiti contro uno stack.

Consente di chiamare l’elenco di esecuzione {a1 a2 a3 a4 a5 a6 a7}.

{a1 a2} dovrebbe essere numeri, in quanto non ci sono operazioni unarie nello stack.

{a7} dovrebbe essere un operatore, per completare l’operazione.

Per {a3, a4, a5, a6} abbiamo diverse opzioni, ma per essere in grado di operare sono sempre almeno due i numeri nello stack. Quindi le combinazioni possibili sono: (N = numero, O = Operatore)

{NNO}, {NONO}, {ONON}, {ONNO} e {NOON}.

La combinazione {OONN} è vietata perché lo stack è vuoto per il secondo O.

Quindi abbiamo:

| {NNOO} | | {NONO} | {NN} | {ONON} | {O} | {ONNO} | | {NOON} | 

Ora conteremo le possibili disposizioni. Ovviamente stiamo finendo di contare perché l’operatore commutativo (Plus e Times) può tagliare a metà l’albero di permutazione, ma il problema è abbastanza piccolo da non dargli fastidio. (Stiamo anche sopravvalutando in quei casi in cui la sequenza è {OO}. Ma continuiamo semplicemente ..)

Dobbiamo scegliere 2 numeri su quattro per il primo segmento, cioè 12 possibili accordi.

Per il segmento centrale, i due numeri rimanenti possono essere permutati, ovvero un fattore 2

Ma abbiamo un altro fattore 5 per il conteggio delle cinque alternative per il segmento centrale.

Per i tre operatori, come possono ripetere abbiamo un fattore 4 ^ 3 = 64

Quindi la dimensione del problema è il prodotto dei numeri in grassetto: 12 2 5 64 = 7680 . Non è necessaria alcuna ottimizzazione, potremmo andare avanti con la forza bruta.

Il resto del problema è build gli arrangiamenti 7680 e il valutatore RPN. Entrambi i compiti relativamente facili.

Lo posterò … è ancora una bozza ma qui è troppo tardi! Seguirà domani!

Modifica: RPN Evaluator

Ecco il codice per il valutatore RPN ricorsivo. Ho scelto di farlo in un linguaggio funzionale ( Mathematica ) per semplificare l’analisi dell’operatore

 rpn[listipt_, stackipt_: {}] := Module[{list=listipt,stack=stackipt}, (*recursive rpn evaluator*) If[list == {}, Return[stack[[1]]]]; (*end*) If[NumberQ[list[[1]]], (*if numeric*) [email protected][Rest[list], PrependTo[stack,list[[1]]]]; (*push nbr and recurse*) , (stack[[2]]=list[[1]][stack[[2]], stack[[1]]]; (*if not, operate*) [email protected][Rest[list], Rest[stack]];); (*and recurse*) ]; ]; 

Esempi di utilizzo

 rpn[{1, 1, 1, Plus, Plus}] 3 rpn[{2, 2, 2, Plus, Plus}] 6 rpn[{2, 3, 4, Plus, Times}] (* (4+3)*7 *) 14 rpn[{2, 3, 4, Plus, Divide}] (* (2+3)/4 *) 2/7 

un po ‘più tardi posterò il generatore di tuple, dimostrerò che sono 7680 e alcuni risultati divertenti sulla distribuzione dei possibili risultati delle operazioni (infatti per il set di {1,2,3,4} è ansible ottenere solo 230 risultati diversi!).

Modifica: costruzione di tuple

Per prima cosa costruiamo esplicitamente le possibilità per il segmento centrale

 t1 = {{n3, n4, o1, o2}, {n3, o1, n4, o2}, {o1, n3, o2, n4}, {o1, n3, n4, o2}, {n3, o1, o2, n4}}; 

Ora anteponiamo le due varianti per {n1, n2} e l’ultimo operatore

 t2 = Join[Map[Join[{n1, n2}, #, {o3}] &, t1], Map[Join[{n2, n1}, #, {o3}] &, t1]] ( bahh ... don't mind the code*) 

Risultante nelle nostre 10 diverse configurazioni

Ora dobbiamo compilare tutte quelle configurazioni con tutte le possibili permutazioni dei numeri e degli operatori.

Per prima cosa costruiamo tutte le permutazioni numeriche come regole di assegnazione per le nostre tuple

  repListNumbers = (*construct all number permutations*) Table[{n1 -> #[[1]], n2 -> #[[2]], n3 -> #[[3]], n4 -> #[[4]]} &[i], {i, Permutations[{1, 2, 3, 4}]}]; 

Questi piccoli animali hanno la forma

  {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4} 

E possiamo usarli per sostituire i vallues nelle nostre tuple. Per esempio:

  {n1,n2,n3,o1,o2,n4,o3} /. {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4} 

Risultati in

  {1,2,3,o1,o2,4,o3} 

Naturalmente potremmo aver costruito le regole di sostituzione come una funzione per poter modificare il numero impostato a piacere. Facciamo ora qualcosa di simile con gli operatori

 repListOps = (*Construct all possible 3 element tuples*) Table[{o1 -> #[[1]], o2 -> #[[2]], o3 -> #[[3]]} &[i], {i, Tuples[{Plus, Times, Divide, Subtract}, 3]}]; 

Quindi otteniamo una raccolta di cose come

  {o1->Plus, o2->Plus, o3->Divide} 

Ora combiniamo le nostre tuple e tutte le nostre regole di sostituzione in un’unica grande lista:

 t3 = Flatten[t2 /. repListNumbers /. repListOps, 2]; 

Il che risulta in 15360 calcoli diversi. Ma sappiamo che c’è un overdate di un fattore due, quindi ora eliminiamo gli elementi ripetuti:

 t3 =Union[t3] 

E questo ci dà i 7680 elementi previsti.

Ci sono ancora alcuni sopravvalutamenti, perché {2,3, Times} = {3,2, Times} = 6, ma questo è ok per i nostri attuali purpouses.

Valutare i risultati

Ora abbiamo il nostro valutatore RPN e tutte quelle tuple e vogliamo sapere se è ansible ottenere un determinato risultato finale.

Dobbiamo semplicemente chiedere se quel numero è contenuto nell’insieme di risultati:

 In[252]:= MemberQ[rpn /@ t3, 24] Out[252]= True In[253]:= MemberQ[rpn /@ t3, 38] Out[253]= False 

In effetti i limiti per il set di risultati sono:

 In[254]:= Max[rpn /@ t3] Out[254]= Max[36, ComplexInfinity] In[255]:= Min[rpn /@ t3] Out[255]= Min[-23, ComplexInfinity] 

I risultati dell’infinito sono dovuti al fatto che non mi sono preoccupato delle divisioni per zero, quindi sono lì, solo all’interno del set. L’intervallo numerico è [-23,36].

Se vuoi sapere quanti dei risultati sono pari a 24, contali

  In[259]:= [email protected][t3, rpn[#] == 24 &] Out[259]= 484 

Naturalmente molti di essi sono permutazioni banali a causa delle proprietà commutative di “Plus” e “Times”, ma non tutti:

  {1, 2, Plus, 3, Plus, 4, Times} -> ((1+2)+3)*4 = 24 {2, 1, 4, 3, Times, Divide, Divide} -> 2/(1/(4*3)) = 24 

Non ci sono sequenze che usano “Sottrai” che dà 24!

  In[260]:= MemberQ[[email protected][t3, rpn[#] == 24 &], Subtract] Out[260]= False 

Campione Spettro dei risultati