[Code golf] L'ultima cifra di un numero immenso

[killing_buddha]

Mi stupisce che qui non ci siano esercizi di code golf.

Qualche tempo fa ne ho incontrato uno particolarmente complesso (anche dal punto di vista di quale sia la matematica che lo spiega).

Dato un array di numeri naturali

{x1, x2, x3, ..., xn}

la consegna è scrivere un algoritmo che dica qual è l'ultima cifra del numero

x1 ^ (x2 ^ (x3 ^ (... ^ xn)))

Direi che una cosa del genere viene bene in Python o in Ruby o in Haskell divertitevi

(ah, chiaramente va trovato un modo di gestire il calcolo in un tempo che sia ragionevolmente più basso del millennio: il numero $9^{(9^9)}$ è troppo grosso per calcolarlo davvero).

[Super Squirrel]

Non avevo mai sentito parlare del code golf prima d'ora.
Anche se non ho ben capito le regole del gioco, ho provato a risolvere l'esercizio in C++ implementando la prima soluzione che mi è venuta in mente ragionando un po' sul problema. In pratica sfrutto il fatto che l'ultima cifra di un prodotto dipende dall'ultima cifra dei fattori e il fatto che elevando un numero a potenze successive l'ultima cifra si ripete ciclicamente.

#include <iostream>

using namespace std;

int inserisci_dimensione()
{
    int n;
    while(true)
    {
        cout << "n: ";
        cin >> n;
        if(n > 1)
        {
            return n;
        }
        else
        {
            cout << "INSERIMENTO NON VALIDO" << endl;
        }
    }
}

void inserisci_array(int *v, const int &dim)
{
    for(unsigned int i = 0; i < dim; i++)
    {
        while(true)
        {
            cout << "v[" << i << "] = ";
            cin >> v[i];
            if(v[i] < 0)
            {
                cout << "INSERIMENTO NON VALIDO" << endl;
            }
            else
            {
                break;
            }
        }
    }
}

int main()
{
    int m[10][5] = {{1, 0, 0, 0, 0},
                    {1, 1, 1, 1, 1},
                    {1, 2, 4, 8, 6},
                    {1, 3, 9, 7, 1},
                    {1, 4, 6, 4, 6},
                    {1, 5, 5, 5, 5},
                    {1, 6, 6, 6, 6},
                    {1, 7, 9, 3, 1},
                    {1, 8, 4, 2, 6},
                    {1, 9, 1, 9, 1}};
    int n = inserisci_dimensione();
    int *v = new int[n];
    inserisci_array(v, n);
    v[0] = v[0] % 10;
    for(unsigned int i = 1; i < n; i++)
    {
        if(v[i])
        {
            v[i] = v[i] % 4;
            if(!v[i])
            {
                v[i] = 4;
            }
        }
        v[i] = m[v[i - 1]][v[i]];
    }
    cout << "ULTIMA CIFRA: " << v[n - 1];
    delete[] v;
}

Per non appesantire il codice ho preferito non inserire alcuni controlli per renderlo più veloce e per tener conto della forma indeterminata 0^0 che ho considerato uguale a 1.
Sono abbastanza sicuro che esistano soluzioni più eleganti, ma sembra funzionare.

[killing_buddha]

Santo cielo, no. Un esercizio di code golf si risolve nel minor numero di righe possibile

[Super Squirrel]

Il tuo messaggio però non è che chiarisce molto la questione.

Come detto nel post precedente, avendo implementato la prima cosa che mi è venuta in mente sono conscio del fatto che sicuramente esiste una soluzione più elegante, ma minor numero di righe possibili significa tutto e niente, inoltre lo stesso concetto di riga non è certo un'unità di misura perfetta. Tenendo conto che le funzioni e parte del main servono per testare l'algoritmo, potresti essere più chiaro sulla lunghezza che dovrebbe avere l'algoritmo?
Voglio anche perderci un po' di tempo a pensare, ma senza sapere le regole risulta difficile.

[killing_buddha]

Qui ci sono degli esempi di code golf, tipo questo https://codegolf.stackexchange.com/ques ... ian-matrix oppure https://codegolf.stackexchange.com/ques ... ective-sum

[apatriarca]

Puoi considerare il numero di byte del file se vuoi una unità di misura più precisa..

[killing_buddha]

Vi aiuto un po'?

Vi aiuto un po'.

Il problema si risolve in mezza riga con una semplice ricorsione (lo faccio in Mathematica semplicemente perché ora non ho voglia di aprire millemila terminali, ma inizialmente l'esercizio prevedeva di farlo in python; la mia sfida per voi è di farlo in Haskell, dove la ricorsione è infinitamente meno dispendiosa a causa della valutazione pigra)

fun[x_][1] := Last[x]
fun[x_][k_]:=x[[Length[x]-k+1]]^(fun[x][k-1])

HyperExponentiate[list_]:=fun[list][Length[list]]

Il problema di questa funzione è che stando al metodo con cui Mathematica decide in quanto tempo può valutare un'espressione,

( Timing[HyperExponentiate[{9,2,5}]]//N )[[2]]

è circa $10^23$ anni.

Del resto è difficile non ricordare il piccolo teorema di Fermat: l'ultima cifra di $a^n$ è essenzialmente la sua riduzione modulo 10, e \(a^n\pmod{10}\equiv a^{n\pmod{ \varphi(10)}}\pmod{10}\), dove $\varphi$ è la funzione di Eulero. Questo è il modo in cui si risolve il problema; ora implementatelo, fate degli edge case, insomma diertitevi.

In C, tz. manco nel 1981.

[apatriarca]

Sbaglio o quel teorema è valido solo per valori di a coprimi con 10?

[vict85]

Infatti è falso. In realtà varie cifre hanno come potenza modulo 10 se stessa. E va notato che 0 (senza modulo!) va gestito a parte per quasi tutte le cifre.

In particolare \(0,1,5,6\) sono costanti se elevati a potenze diverse da \(0\). \(3,7,9\) rispettano la formula detta prima, anche se \(9\) ha un ciclo di ordine \(2\). \(2\) e \(8\) hanno un ciclo di ordine \(4\) mentre \(4\) di ordine \(2\). Ma per le cifre pari, lo \(0\) va considerato a parte.
Penso si difficile fare qualcosa di davvero molto breve.

Per quanto riguarda le cifre si può misurare dopo che il codice è stato formattato con uno stile di riferimento.

[killing_buddha]

Vedi, non avrei mai avuto voglia di scoprire che sbagliavo, se non avessi fatto questa domanda. Bene, quindi come si fa?

[apatriarca]

Immagino si possa fare qualcosa come il seguente (haskell):

p = [(0,1), (0,1), (1,4), (0,4), (1,2), (1,1), (1,1), (0,4), (1,4), (0,2)]

powMod10 a b = a' ^ b' where { a' = mod a 10; (s, t) = p !! a';
                               b' = if b < s then b else s + mod (b - s) t }

f = foldr1 powMod10

main = do
    print $ f [9, 5, 2]

[apatriarca]

In effetti ho notato si può ridurre semplicemente al seguente:

f xs = (`mod`10) $ foldr1 (\a b-> a ^ (min b (1 + (b - 1)`mod`4))) xs

main = print $ f [9, 5, 2]

Tutti i periodi dividono infatti \(4\) e posso ovviamente partire da qualsiasi valore e quindi in particolare da 1 per i cicli.

EDIT: Ho corretto il codice..

[killing_buddha]

mmmh, bello!