Alphametic

[axpgn]

$$
$$
[size=150][tt]T W E L V E +[/tt]

[tt]T W E L V E +[/tt]

[tt]T W E L V E +[/tt]

[tt]T W E L V E +[/tt]

[tt]T W E L V E +[/tt]

[tt]T H I R T Y =[/tt]

[tt]=============[/tt]

[tt]N I N E T Y[/tt][/size]




Cordialmente, Alex

[Umby2]

"Super Squirrel":
Può essere un inizio, appena ho tempo comincio a buttare giù qualche linea di codice!

Sono decisamente più avanti di te... Fatta già la screen, con richiesta numeri addendi...

[Umby2]

Hai fatto il "solver" ?



La soluzione: 5+5+6=16 non è ammessa.

[axpgn]

Ho trovato questa $426195+426195+852=853242$.

Ma è unica?

Cordialmente, Alex

[axpgn]

È unica

Cordialmente, Alex

[Umby2]

"axpgn":

È unica

Cordialmente, Alex

[Umby2]

Altro giro:

[axpgn]

$923054+923054+184=1846292$

[Super Squirrel]

"Umby":Hai fatto il "solver" ?

Eccolo qui:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool combinazione_successiva(unsigned int *u, unsigned int n, unsigned int k)
{
    for(unsigned int i = 0; i < k; ++i)
    {
        if(u[k - i - 1] < n - i - 1)
        {
            ++u[k - i - 1];
            for(unsigned int j = k - i; j < k; ++j)
            {
                u[j] = u[j - 1] + 1;
            }
            return true;
        }
    }
    return false;
}

class puzzle
{
    unsigned int soluzioni;
    vector<string> &v;
    string alfabeto;
    void acquisisci_alfabeto();
    bool verifica_fattibilita();
    unsigned int converti_stringa(unsigned int *u, unsigned int *w, unsigned int i);
    bool verifica_caratteri_iniziali(unsigned int *u, unsigned int *w);
    void stampa_soluzione(unsigned int *u);
public:
    puzzle(vector<string> &V):v(V), soluzioni(0){}
    void cerca_soluzioni();
};

void puzzle::acquisisci_alfabeto()
{
    unsigned int u[26] = {0};
    for(unsigned int i = 0; i < v.size(); ++i)
    {
        for(unsigned int j = 0; j < v[i].size(); ++j)
        {
            if(!u[v[i][j] - 'a']++)
            {
                alfabeto.push_back(v[i][j]);
            }
        }
    }
}

bool puzzle::verifica_fattibilita()
{
    if(v.size() < 3)
    {
        return false;
    }
    for(unsigned int i = 1; i < v.size(); ++i)
    {
        if(!v[i].size() || v[i].size() > v[0].size())
        {
            return false;
        }
    }
    acquisisci_alfabeto();
    return alfabeto.size() < 11;
}

unsigned int puzzle::converti_stringa(unsigned int *u, unsigned int *w, unsigned int i)
{
    unsigned int n = 0;
    for(unsigned int j = 0; j < v[i].size(); ++j)
    {
        n = n * 10 + u[w[v[i][j] - 'a']];
    }
    return n;
}

bool puzzle::verifica_caratteri_iniziali(unsigned int *u, unsigned int *w)
{
    for(unsigned int i = 0; i < v.size(); ++i)
    {
        if(!u[w[v[i][0] - 'a']])
        {
            return false;
        }
    }
    return true;
}

void puzzle::stampa_soluzione(unsigned int *u)
{
    cout << "SOLUZIONE " << soluzioni << ":" << endl;
    for(unsigned int i = 0; i < alfabeto.size(); ++i)
    {
        cout << alfabeto[i] << " = " << u[i] << "\t";
    }
    cout << endl << endl;
}

void puzzle::cerca_soluzioni()
{
    if(verifica_fattibilita())
    {
        sort(alfabeto.begin(), alfabeto.end());
        unsigned int *u = new unsigned int[alfabeto.size()];
        unsigned int w[26] = {0};
        for(unsigned int i = 0; i < alfabeto.size(); ++i)
        {
            w[alfabeto[i] - 'a'] = u[i] = i;
        }
        do
        {
            if(verifica_caratteri_iniziali(u, w))
            {
                unsigned int target = converti_stringa(u, w, 0);
                unsigned int somma = 0;
                for(unsigned int i = 1; i < v.size(); ++i)
                {
                    somma += converti_stringa(u, w, i);
                }
                if(somma == target)
                {
                    ++soluzioni;
                    stampa_soluzione(u);
                }
            }
        }
        while(next_permutation(u, u + alfabeto.size()) || combinazione_successiva(u, 10, alfabeto.size()));
        free(u);
    }
}

int main()
{
    //vector<string> v = {"ninety", "twelve", "twelve", "twelve", "twelve", "twelve", "thirty"};
    //vector<string> v = {"tredici", "cinque", "cinque", "tre"};
    //vector<string> v = {"sedici", "cinque", "cinque", "sei"};
    vector<string> v = {"trenta", "sette", "sette", "sette", "nove"};
    puzzle a(v);
    a.cerca_soluzioni();
}

Come si può vedere dal main() ho testato il puzzle del topic e i due postati da Umby e sembra funzionare bene. Ho poi perso giusto un paio di minuti per cercarne uno nuovo a mano ed è uscito fuori quello riportato per ultimo: purtroppo ha due soluzioni, ma almeno la differenza in valore assoluto tra di loro è pari a trenta*10^3!

A questo punto bisognerebbe creare un "vocabolario" ed implementare un algoritmo di ricerca, non ora però!

[Umby2]

"axpgn":

$923054+923054+184=1846292$

[Umby2]

"Super Squirrel":
Eccolo qui:
...
A questo punto bisognerebbe creare un "vocabolario" ed implementare un algoritmo di ricerca, non ora però! :-

Bene,
Se hai fatto il "solver", puoi fare anche il "creator".
Attenzione: devi anche controllare che la somma in cifre, sia valida,
esempio: 5+10+10+15 = 40 (vedi sotto)
cosa, che mi sembra di non aver letto nel tuo codice.

La mia banca dati è limitata ai numeri da 1 a 100,
creata con un programmino, che avevo già, che mi trasforma
un numero da cifre a lettere ( il classico, per la stampa delle assegni circolari )

Con 3 addendi: 2 soluzioni (quelle sopra esposte)
Con 4 addendi: 7 soluzioni (non le metto tutte per non annoiare chi ci legge)
Con 5 addendi: una marea di soluzioni
Con 6 addendi: Nessuna...

[axpgn]

@Super Squirrel

Sarebbero queste due?

$53113+53113+53113+4073=163412$

$63113+63113+63113+4073=193412$

[Super Squirrel]

@axpgn
Ma li stai risolvendo con il ragionamento? In tal caso secondo te è emerso qualche puzzle "valido" (intendo come gioco di logica) per il momento?

"Umby":Attenzione: devi anche controllare che la somma in cifre, sia valida,
esempio: 5+10+10+15 = 40 (vedi sotto)
cosa, che mi sembra di non aver letto nel tuo codice.

Non credo ce ne sarà bisogno, in quanto avrei pensato di utilizzare come "vocabolario" un vettore di stringhe in cui ogni stringa contiene la parola del corrispondente indice. Per esempio:

vocabolario[16] = "sedici";

In questo modo quando l'algoritmo incaricato di definire le somme comunicherà

21 = 1 + 5 + 7 + 8

basterà passare al "solver" il vettore

{v[21], v[1], v[5], v[7], v[8]}

"Umby":La mia banca dati è limitata ai numeri da 1 a 100

Cos'hai contro lo zero?

[axpgn]

@Super Squirrel

"Super Squirrel":Ma li stai risolvendo con il ragionamento?

Beh, sì, è questo il bello
Non fraintendermi: apprezzo molto il lavoro che state facendo, è molto più complicato della risoluzione del singolo puzzle, ci sono molte più problematiche e soprattutto state generalizzando.
Semplicemente abbiamo obiettivi diversi: io un po' più ludico, voi un po' più professionale.

"Super Squirrel":In tal caso secondo te è emerso qualche puzzle "valido" (intendo come gioco di logica) per il momento?

Cosa intendi di preciso con "valido"? Dato che sono arrivato alla soluzione con il ragionamento è logicamente "valido"; inoltre il crittogramma ha senso "di per sé" quindi anche in questo senso è "valido".
Se invece intendi se fosse impegnativo, direi abbastanza, né troppo né poco, il giusto, ma questo dipende troppo dai gusti e dalle capacità e penso sia difficile gestirlo "a priori"

Cordialmente, Alex

[Umby2]

"Super Squirrel":
Cos'hai contro lo zero?

Effettivamente lo zero mi sta un po sulle XXXXX,
ti accontento, ora il mio dizionario da 100 elementi, è passato a 101!!!

Ovviamente, con la presenza dello [ZERO], le soluzioni si sono ampliate,
questa è la più carina, senza alcuna ripetizione di membri.
[size=85](P.s. Noti qualcosa di particolare in questa soluzione?)[/size]

[size=150][tt]..ZERO[/tt]
[tt]...SEI[/tt]
[tt].SETTE[/tt]
[tt]..OTTO[/tt]
[tt]..NOVE[/tt]
[tt]=======[/tt]
[tt]TRENTA[/tt][/size]

[axpgn]

$4206+827+82112+6116+9652=102913$

Hai usato tutte le dieci cifre

[Umby2]

"axpgn":

$4206+827+82112+6116+9652=102913$

"axpgn":

Hai usato tutte le dieci cifre

[axpgn]

Mo' basta, però

[Super Squirrel]

"axpgn":Semplicemente abbiamo obiettivi diversi: io un po' più ludico, voi un po' più professionale.

Sarà, ma mi diverto molto a fare programmi del genere!

"axpgn":Se invece intendi se fosse impegnativo, direi abbastanza, né troppo né poco, il giusto, ma questo dipende troppo dai gusti e dalle capacità e penso sia difficile gestirlo "a priori"

Capisco, poi quando ho tempo provo a risolverne qualcuno anche io!


Scritto il "vocabolario" ed implementato l'algoritmo sulle somme, questi i risultati:

2 ADDENDI:

da ricalcolare...

3 ADDENDI:

13 = 3 + 5 + 5
16 = 5 + 5 + 6
91 = 23 + 30 + 38

4 ADDENDI:

da ricalcolare...

5 ADDENDI:

da ricalcolare...

6 ADDENDI:

da ricalcolare...

7 ADDENDI (fino a 20):

da ricalcolare...

To be continued... il "procio" chiede un po' di tregua!

"Umby":Con 3 addendi: 2 soluzioni (quelle sopra esposte)
Con 4 addendi: 7 soluzioni (non le metto tutte per non annoiare chi ci legge)
Con 5 addendi: una marea di soluzioni
Con 6 addendi: Nessuna...

Ipotizzando che io non abbia commesso errori, come hai implementato l'algoritmo che ricerca tutte le possibili somme pari ad $n$ composte da $m$ addendi di valore minimo pari a $min$?
Già che ci siamo ne approfitto anche per chiederti se il tuo solver ha un funzionamento simile al mio o se hai previsto delle ottimizzazioni che io non ho inserito (a tal proposito ti informo che rispetto alla versione postata in precedenza ho inserito un nuovo controllo preliminare, ossia che fino a 10 addendi ci deve essere almeno un addendo la cui relativa stringa deve avere al massimo un carattere in meno rispetto alla lunghezza della stringa relativa alla somma).

EDIT:
Aggiornate le soluzioni dopo aver corretto un errore nel codice.

[axpgn]

"Super Squirrel":[quote="axpgn"]Semplicemente abbiamo obiettivi diversi: io un po' più ludico, voi un po' più professionale.

Sarà, ma mi diverto molto a fare programmi del genere! [/quote]
Non ho detto che lo fai solo per lavoro, ma che il tuo approccio è più professionale del mio (o meno amatoriale, vedila come vuoi )

Cordialmente, Alex

[Umby2]

"Super Squirrel":
Ipotizzando che io non abbia commesso errori, come hai implementato l'algoritmo che ricerca tutte le possibili somme pari ad $n$ composte da $m$ addendi di valore minimo pari a $min$?

Innanzitutto. COMPLIMENTI.

Vedo che il tuo "creator" ha trovato molti più puzzle, rispetto al mio.
Ti faccio presente, che quando ha fatto quella elaborazione, non avevo il fantomatico [ZERO] nel dizionario, pertanto molte soluzioni non sono uscite proprio per la mancanza di tale dato.
In ogni caso, tu ne hai trovate di più, e a tal proposito ti chiedo:
- Come hai considerato le soluzioni multiple? Io le ho scartate, presupponendo, di considerare valido solo i puzzle a soluzione unica.
(non vorrei che sia proprio questa la diff. tra la mia elaborazione e la tua !!)
-----------------------
Ti confesso, che non ho fatto il "solver" ma solo il "creator",
(mi interessava poco risolvere puzzle già composti, ma di più poterli creare), anche perchè inizialmente, non sapevo manco se ce ne fossero o meno in lingua italiana.

In estrema sintesi:
il mio programma è strutturato in due [SECTION].
La prima si occupa di generare le combinazioni dei numeri in base al numero di addendi impostato ad inizio programma,
la [SECTION1] passa la combinazione creata alla seconda [SECTION2] che ne verifica la
validità, passando una variabile, con il numero di soluzioni trovate:
0 - Puzzle non valido (Nessuna soluzione)
1 - Puzzle valido (una sola soluzione)
2...xx - Puzzle non valido (Soluzioni multiple)

A titolo di esempio:
il primo puzzle che elaboro (con 3 addendi) è
[UNO-UNO-UNO] [TRE] ed il risultato della [SECTION2] sarà 0 (non valido)
il secondo sarà:
[UNO-UNO-DUE] [QUATTRO] che sarà immediatamente scartato da [SECTION2] in
quanto "non ammissibile" ... e così via...
scarto anche puzzle del tipo:
[CINQUANTA-DIECI-CINQUANTA] [Totale>100] in quanto il totale dei 3 addendi
è superiore al massimo numero presente in dizionario.

Per quanto riguarda le ottimizzazioni, direi che il programma è nudo e crudo, fatto in piedi, giusto per giocare un po, ho solo voluto controllare il numero di cifre del totale, che deve essere pari al numero di cifre del numero maggiore o al più una cifra in più (per un eventuale riporto),
questo per dire che non ci sono particolari strategie adottate per rendere il programma più efficiente durante il ciclo di elaborazione.