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

[Super Squirrel]

Grazie!

"Umby":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 !!)

No no, ho considerato solo i puzzle con un'unica soluzione.

"Umby":Ti confesso, che non ho fatto il "solver" ma solo il "creator"
...
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

Da come la descrivi, la section2 mi sembrerebbe un solver, altrimenti come farebbe a restituire il numero di soluzioni?

Io invece per generare tutte le possibili combinazioni (con ripetizione), di somma $n$ e composte da $m$ addendi di valore minimo pari a $min$, ho implementato due funzioni:
- la funzione inizializza_array_somma() incaricata di trovare la combinazione iniziale;
- la funzione somma_successiva() incaricata di trovare la combinazione successiva dalla sola analisi della combinazione corrente.

Questo il codice completo:

#include <algorithm>
#include <cstdint>
#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;
}

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

bool somma_successiva(unsigned int *u, unsigned int n, unsigned int m)
{
    bool flag = false;
    for(unsigned int i = m - 1; i; --i)
    {
        if(u[i] - u[i - 1] > !flag)
        {
            unsigned int somma = u[i - 1]++;
            for(unsigned int j = i; j < m - 1; ++j)
            {
                somma += u[j];
                u[j] = u[i - 1];
            }
            u[m - 1] = somma + u[m - 1] - u[i - 1] * (m - i);
            return true;
        }
        flag += u[i] - u[i - 1];
    }
    return false;
}

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

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;
    }
    unsigned int MAX = 0;
    for(unsigned int i = 1; i < v.size(); ++i)
    {
        MAX = max(v[i].size(), MAX);
        if(!v[i].size() || v[i].size() > v[0].size())
        {
            return false;
        }
    }
    if(v.size() < 12 && v[0].size() - MAX > 1)
    {
        return false;
    }
    acquisisci_alfabeto();
    return alfabeto.size() < 11;
}

uint64_t puzzle::converti_stringa(unsigned int *u, unsigned int *w, unsigned int i)
{
    uint64_t 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_in_colonna(unsigned int *u, unsigned int *w, bool flag_lettere)
{
    cout << endl << endl;
    for(unsigned int i = 1; i < v.size(); ++i)
    {
        for(unsigned int j = 0; j < v[0].size() - v[i].size(); ++j)
        {
            cout << ".";
        }
        flag_lettere ? cout << v[i] : cout << converti_stringa(u, w, i);
        cout << (i == v.size() - 1 ? " =" : " +") << endl;
    }
    for(unsigned int i = 0; i < v[0].size() + 2; ++i)
    {
        cout << "-";
    }
    cout << endl;
    flag_lettere ? cout << v[0] : cout << converti_stringa(u, w, 0);
}

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

void puzzle::cerca_soluzioni(bool flag_stampa, bool flag_ricerca)
{
    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))
            {
                uint64_t target = converti_stringa(u, w, 0);
                uint64_t somma = 0;
                for(unsigned int i = 1; i < v.size(); ++i)
                {
                    somma += converti_stringa(u, w, i);
                }
                if(somma == target)
                {
                    ++soluzioni;
                    if(flag_stampa)
                    {
                        stampa_soluzione(u, w);
                    }
                    if(flag_ricerca && soluzioni > 1)
                    {
                        return;
                    }
                }
            }
        }
        while(next_permutation(u, u + alfabeto.size()) || combinazione_successiva(u, 10, alfabeto.size()));
        free(u);
    }
}

unsigned int puzzle::get_soluzioni()const
{
    return soluzioni;
}

void acquisisci_dati_puzzle(vector<string> &w, vector<string> &v, unsigned int *u, unsigned int m, unsigned int n)
{
    v.push_back(w[n]);
    for(unsigned int i = 0; i < m; ++i)
    {
        v.push_back(w[u[i]]);
    }
}

void stampa_puzzle(unsigned int *u, unsigned int m, unsigned int n)
{
    cout << n << " = ";
    for(unsigned int i = 0; i < m; ++i)
    {
        cout << u[i];
        if(i != m - 1)
        {
            cout << " + ";
        }
    }
    cout << endl;
}

int main()
{
    vector<string> w = {"zero",
    "uno",         "due",          "tre",          "quattro",          "cinque",          "sei",          "sette",          "otto",         "nove",          "dieci",
    "undici",      "dodici",       "tredici",      "quattordici",      "quindici",        "sedici",       "diciassette",    "diciotto",     "diciannove",    "venti",
    "ventuno",     "ventidue",     "ventitre",     "ventiquattro",     "venticinque",     "ventisei",     "ventisette",     "ventotto",     "ventinove",     "trenta",
    "trentuno",    "trentadue",    "trentatre",    "trentaquattro",    "trentacinque",    "trentasei",    "trentasette",    "trentotto",    "trentanove",    "quaranta",
    "quarantuno",  "quarantadue",  "quarantatre",  "quarantaquattro",  "quarantacinque",  "quarantasei",  "quarantasette",  "quarantotto",  "quarantanove",  "cinquanta",
    "cinquantuno", "cinquantadue", "cinquantatre", "cinquantaquattro", "cinquantacinque", "cinquantasei", "cinquantasette", "cinquantotto", "cinquantanove", "sessanta",
    "sessantuno",  "sessantadue",  "sessantatre",  "sessantaquattro",  "sessantacinque",  "sessantasei",  "sessantasette",  "sessantotto",  "sessantanove",  "settanta",
    "settantuno",  "settantadue",  "settantatre",  "settantaquattro",  "settantacinque",  "settantasei",  "settantasette",  "settantotto",  "settantanove",  "ottanta",
    "ottantuno",   "ottantadue",   "ottantatre",   "ottantaquattro",   "ottantacinque",   "ottantasei",   "ottantasette",   "ottantotto",   "ottantanove",   "novanta",
    "novantuno",   "novantadue",   "novantatre",   "novantaquattro",   "novantacinque",   "novantasei",   "novantasette",   "novantotto",   "novantanove",   "cento"};

    //MODALITA' RICERCA
    unsigned int m = 3;
    unsigned int *u = new unsigned int[m];
    vector<string> v;
    for(unsigned int n = 0; n <= 100; ++n)
    {
        cout << n << ":" << endl;
        if(inizializza_array_somma(u, n, m, 0))
        {
            while(somma_successiva(u, n, m))
            {
                v.resize(0);
                acquisisci_dati_puzzle(w, v, u, m, n);
                puzzle a(v);
                a.cerca_soluzioni(false, true);
                if(a.get_soluzioni() == 1)
                {
                    stampa_puzzle(u, m, n);
                }
            }
        }
    }
    free(u);

     /*
    //MODALITA' PUZZLE SINGOLO
    //vector<string> v = {"ninety", "twelve", "twelve", "twelve", "twelve", "twelve", "thirty"};
    vector<string> v = {w[16], w[1], w[1], w[1], w[1], w[5], w[7]};
    puzzle a(v);
    a.cerca_soluzioni(true, false);
    */
}

Se riscontrate qualche bug fatemi sapere.

EDIT:
Corretto un bug nel codice.

[Umby2]

"Super Squirrel":
No no, ho considerato solo i puzzle con un'unica soluzione.

...allora ci sta qualche bughetto nel mio/tuo programma,
sarei orientato nel mio, visto che:
- tutte le soluzioni da me trovate appaiono nella tua elaborazione
- alcune delle tue, non appaiono nella mia

Pertanto, molto probabilmente, alcune soluzioni valide, sfuggono al mio codice:

ad esempio: la tua soluzione a 3 addendi: [82 = 12 + 32 + 38], sfugge dal mio
solver, e quindi viene skippata, pertanto ti chiedo:
Quale soluzione ti da il tuo solver per questa combinazione ?

----------------------------

"Super Squirrel":
Da come la descrivi, la section2 mi sembrerebbe un solver, altrimenti come farebbe a restituire il numero di soluzioni?

E' proprio come dici: quella SECTION2 non è altro che un solver, ma all'interno di un main, che si occupa di fare altro. Io come solver intendevo un programma che si occupa di accettare da tastiera la combinazione che ti interessa, e ti restituisce l'esito della stessa.

[Super Squirrel]

Ho trovato il problema... nella conversione delle stringhe in numeri utilizzavo il tipo unsigned int che non essendo abbastanza capiente andava in "overflow". Ho risolto utilizzando il tipo uint64_t. Aggiornato anche il codice postato in precedenza.

Ho cercato di nuovo le soluzioni con 3 addendi e ho trovato le seguenti:

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

Il numero è sceso, ma comunque sono più delle due che hai trovato tu.
Magari prova a dare in pasto al solver quella con il 91 e vediamo che succede.

Questo l'output che ottengo io:

SOLUZIONE 1:

a=6   e=4   i=0   n=2   o=7   r=9   t=1   u=5   v=8

.ventitre +
...trenta +
trentotto =
-----------
novantuno

.84210194 +
...194216 +
194217117 =
-----------
278621527


Process returned 0 (0x0)   execution time : 2.014 s
Press any key to continue.

[Umby2]

"Super Squirrel":Ho trovato il problema...

Ehmm... "To ress nu ****tt"

https://www.youtube.com/watch?v=gDaVy1KfQsU&t=134

p.s. il 91 esce anche a me...

[Super Squirrel]

"Umby":Ehmm... "To ress nu ****tt"

https://www.youtube.com/watch?v=gDaVy1KfQsU&t=134

Poi a tempo perso metto il pc a ricalcolare le altre soluzioni e le posto!

[Super Squirrel]

Ecco le soluzioni che ho trovato (anche già formattate per essere eventualmente utilizzate nel programma riportato in precedenza):

    //2 ADDENDI:
    //3 ADDENDI:
    //vector<string> v = {w[13], w[3], w[5], w[5]};
    //vector<string> v = {w[16], w[5], w[5], w[6]};
    //vector<string> v = {w[91], w[23], w[30], w[38]};
    //4 ADDENDI:
    //vector<string> v = {w[7], w[0], w[1], w[3], w[3]};
    //vector<string> v = {w[11], w[0], w[1], w[5], w[5]};
    //vector<string> v = {w[16], w[1], w[5], w[5], w[5]};
    //vector<string> v = {w[16], w[2], w[2], w[5], w[7]};
    //vector<string> v = {w[21], w[2], w[2], w[5], w[12]};
    //vector<string> v = {w[21], w[2], w[5], w[5], w[9]};
    //vector<string> v = {w[21], w[3], w[4], w[7], w[7]};
    //vector<string> v = {w[30], w[0], w[10], w[10], w[10]};
    //vector<string> v = {w[30], w[2], w[7], w[10], w[11]};
    //vector<string> v = {w[30], w[3], w[3], w[12], w[12]};
    //vector<string> v = {w[30], w[3], w[6], w[10], w[11]};
    //vector<string> v = {w[30], w[6], w[6], w[8], w[10]};
    //vector<string> v = {w[40], w[1], w[4], w[7], w[28]};
    //vector<string> v = {w[40], w[5], w[10], w[10], w[15]};
    //5 ADDENDI (FINO A 30):
    //vector<string> v = {w[10], w[0], w[2], w[2], w[3], w[3]};
    //vector<string> v = {w[11], w[0], w[0], w[1], w[5], w[5]};
    //vector<string> v = {w[16], w[1], w[1], w[2], w[5], w[7]};
    //vector<string> v = {w[21], w[2], w[3], w[4], w[4], w[8]};
    //vector<string> v = {w[30], w[0], w[6], w[7], w[8], w[9]};
    //vector<string> v = {w[30], w[1], w[1], w[8], w[8], w[12]};
    //vector<string> v = {w[30], w[1], w[1], w[8], w[10], w[10]};
    //vector<string> v = {w[30], w[1], w[2], w[3], w[12], w[12]};
    //vector<string> v = {w[30], w[1], w[3], w[8], w[8], w[10]};
    //vector<string> v = {w[30], w[1], w[7], w[7], w[7], w[8]};
    //vector<string> v = {w[30], w[2], w[2], w[3], w[11], w[12]};
    //vector<string> v = {w[30], w[2], w[2], w[5], w[10], w[11]};
    //vector<string> v = {w[30], w[2], w[3], w[5], w[10], w[10]};
    //vector<string> v = {w[30], w[5], w[5], w[6], w[7], w[7]};
    //vector<string> v = {w[30], w[5], w[6], w[6], w[6], w[7]};
    //6 ADDENDI (FINO A 30):
    //vector<string> v = {w[7], w[0], w[0], w[0], w[1], w[3], w[3]};
    //vector<string> v = {w[11], w[0], w[0], w[0], w[1], w[5], w[5]};
    //vector<string> v = {w[12], w[0], w[0], w[0], w[2], w[3], w[7]};
    //vector<string> v = {w[16], w[1], w[1], w[1], w[1], w[5], w[7]};
    //vector<string> v = {w[30], w[0], w[0], w[0], w[8], w[10], w[12]};
    //vector<string> v = {w[30], w[0], w[0], w[3], w[3], w[12], w[12]};
    //vector<string> v = {w[30], w[0], w[0], w[6], w[7], w[8], w[9]};
    //vector<string> v = {w[30], w[0], w[2], w[7], w[7], w[7], w[7]};
    //vector<string> v = {w[30], w[0], w[3], w[3], w[7], w[8], w[9]};
    //vector<string> v = {w[30], w[1], w[1], w[2], w[2], w[12], w[12]};
    //vector<string> v = {w[30], w[1], w[1], w[2], w[3], w[11], w[12]};
    //vector<string> v = {w[30], w[1], w[1], w[3], w[3], w[10], w[12]};
    //vector<string> v = {w[30], w[1], w[1], w[3], w[3], w[11], w[11]};
    //vector<string> v = {w[30], w[1], w[1], w[6], w[7], w[7], w[8]};
    //vector<string> v = {w[30], w[1], w[1], w[7], w[7], w[7], w[7]};
    //vector<string> v = {w[30], w[1], w[2], w[2], w[3], w[11], w[11]};
    //vector<string> v = {w[30], w[1], w[2], w[2], w[7], w[9], w[9]};
    //vector<string> v = {w[30], w[1], w[2], w[3], w[3], w[10], w[11]};
    //vector<string> v = {w[30], w[1], w[3], w[5], w[5], w[8], w[8]};
    //vector<string> v = {w[30], w[2], w[2], w[2], w[2], w[10], w[12]};
    //vector<string> v = {w[30], w[2], w[2], w[2], w[3], w[10], w[11]};
    //vector<string> v = {w[30], w[2], w[2], w[2], w[7], w[7], w[10]};
    //vector<string> v = {w[30], w[2], w[2], w[3], w[3], w[8], w[12]};
    //vector<string> v = {w[30], w[2], w[2], w[3], w[6], w[6], w[11]};
    //vector<string> v = {w[30], w[2], w[2], w[3], w[6], w[7], w[10]};
    //vector<string> v = {w[30], w[2], w[3], w[5], w[5], w[5], w[10]};
    //vector<string> v = {w[30], w[3], w[3], w[3], w[5], w[8], w[8]};
    //vector<string> v = {w[30], w[3], w[5], w[5], w[5], w[6], w[6]};
    //7 ADDENDI (FINO A 20):
    //vector<string> v = {w[8], w[0], w[0], w[0], w[0], w[2], w[3], w[3]};
    //vector<string> v = {w[11], w[0], w[0], w[0], w[0], w[1], w[5], w[5]};
    //vector<string> v = {w[16], w[1], w[1], w[1], w[1], w[1], w[5], w[6]};
    //8 ADDENDI (FINO A 20):
    //vector<string> v = {w[11], w[0], w[0], w[1], w[1], w[1], w[1], w[2], w[5]};
    //vector<string> v = {w[12], w[0], w[0], w[0], w[0], w[0], w[2], w[5], w[5]};
    //9 ADDENDI (FINO A 20):
    //vector<string> v = {w[8], w[0], w[0], w[0], w[0], w[0], w[0], w[2], w[3], w[3]};
    //vector<string> v = {w[9], w[0], w[0], w[0], w[0], w[0], w[0], w[3], w[3], w[3]};
    //vector<string> v = {w[11], w[0], w[0], w[0], w[0], w[0], w[0], w[1], w[5], w[5]};
    //vector<string> v = {w[12], w[0], w[0], w[0], w[0], w[0], w[0], w[2], w[5], w[5]};
    //vector<string> v = {w[12], w[0], w[0], w[0], w[1], w[1], w[1], w[2], w[2], w[5]};
    //vector<string> v = {w[16], w[0], w[0], w[0], w[0], w[1], w[1], w[2], w[2], w[10]};
    //10 ADDENDI (FINO A 20):
    //vector<string> v = {w[9], w[0], w[0], w[0], w[0], w[0], w[0], w[0], w[3], w[3], w[3]};
    //vector<string> v = {w[11], w[0], w[0], w[0], w[0], w[0], w[0], w[2], w[2], w[2], w[5]};
    //vector<string> v = {w[11], w[0], w[0], w[0], w[0], w[0], w[1], w[1], w[2], w[2], w[5]};
    //vector<string> v = {w[12], w[0], w[0], w[0], w[0], w[0], w[0], w[0], w[2], w[5], w[5]};
    //vector<string> v = {w[12], w[0], w[0], w[0], w[0], w[0], w[0], w[1], w[1], w[5], w[5]};

Di "materiale" ce n'è abbastanza, credo proprio che la ricerca delle soluzioni per me finisce qui!