-3h -35m -10s

aoc-2017

#122

Ho avuto un po’ di tempo libero e mi sono rimesso sotto ma…
il 23b non ho ancora capito come risolverlo…
il 24 pensavo fosse facile invece dopo qualche prova siamo ancora 1:0 per il grafo…
il 25 finalmente è una passeggiata…
…peccato che non mi fa concludere la seconda parte se prima non risolvo tutto il resto. :worried:
Sono bloccato! :grimacing:
Qualche consiglio!?


#123

La seconda parte del 25 non esiste. Ti ricorda solo quante stelle ti mancano, e ti omaggia di una senza dover fare alcuno sforzo.

Per quanto riguarda il 23b, ci sono 2 strade:
a) ottimizzare l’assembler sperando di farlo girare in un tempo ragionevole (molto ma molto difficile)
b) capire cosa fa e scrivere la soluzione in un linguaggio più ad alto livello (the way to go). Considera che la soluzione sono 2 righe di codice (con l’aiuto di una funzione che dice se un numero è oppure no un certo tipo di numero…).
Dato per scontato di prendere la strada b, posso dirti che l’operazione che fa ha a che fare con i fattori primi. Cerca di leggere il tutto outside-in, ovvero partendo dal loop esterno per identificare quante volte fa quel loop, da quale valore parte e a quale valore arriva.
Il valore del registro f è fondamentale, e se capisci quello ti rendi conto che buona parte del loop più interno diventa inutile non appena f viene scritto, visto che non può cambiare ulteriormente valore.

Il 24 invece necessita di sfruttare lo stack della ricorsione. Si tratta di trovare tutti i bridges possibili, andando a ricordare quali components hai già utilizzato. Il tutto è reso un po’ più complicato dal fatto che puoi connettere i components da entrambe le parti, e pertanto devi ricordare anche quale parte dell’ultimo component collegato al bridge che stai costruendo è libera.
La signature della funzione ricorsiva potrebbe essere una cosa del genere:

findBridges ( bridges, current_bridge, used_components )

dove:
bridges è un array che contiene tutti i ponti completati, dove per completato si intende sia un bridge a cui non puoi collegare nessun altro component, sia un qualsiasi suo pezzo partendo dal primo component (che è quello che ha uno 0).
current_bridge è la serie di components che hai già collegato in ogni stack ricorsivo. Questa struttura deve anche memorizzare quale parte dell’ultimo component è stata collegata al resto del ponte, in modo da considerare solo l’altra nella ricerca di un component tra quelli non ancora utilizzati che vi si possa collegare. Deve essere immutabile, ovvero ogni chiamata alla funzione deve essere una copia indipendente.
used_components è la serie di components utilizzati dal current_bridge, ed è importante che anche questa sia una collezione immutabile, ovvero ogni volta che richiami la funzione deve essere una copia, visto che ogni current_bridge è una storia a se stante.
La prima volta che chiami la funzione, bridges sarà vuoto, current_bridge sarà una struttura con il component di partenza ed il lato usato (o libero), ed used_components contenente questo stesso 0-? component. Volendo bridges può anche essere una variabile globale, senza sbattersi a passarla di volta in volta alla funzione.
Il resto del problema, ovvero calcolo della strength e quello che ti chiederà nella seconda parte, è semplice.

Mi rendo conto di non aver fatto un buon lavoro nella spiegazione del meccanismo, ma spero che possa comunque darti qualche spunto. Trovo che sia uno dei puzzle più difficili di questa edizione.


#124

Houston, abbiamo un problema…
Tanto per fare il bastian contrario ho preso la strada a.
Ho copiato il tuo pseudocode, l’ho trasformato in C, l’ho compilato e l’ho lasciato eseguire per tutta la notte.
La mattina mi sono ritrovato bella e pronta la soluzione!
Peccato che era sbagliata. :confused:
Allora ho ripreso direttamente il mio puzzle, l’ho studiato bene e l’ho trasformato in C, ma prima di rilanciarlo l’ho confrontato con l’altro e sembrano uguali…
A sto punto prenderei la strada b, ma non capisco perché quella che dovrebbe essere la risposta in realtà non va bene…


#125

Interessante. Mi posti il tuo input? Potrebbe essere un off-by-one error nel loop principale, oppure il compilatore C che ha introdotto delle ottimizzazioni che hanno cambiato la natura del programma. Comunque credo che senza ottimizzarlo (riscrivendo i 2 loop interni) il runtime, anche se compilato, dovrebbe essere assai più lungo di una nottata (mi pare si parlasse di 17 giorni…).
Per fare un test sarebbe da riscrivere in x86 assembly direttamente (è più semplice di quanto possa sembrare. se vuoi cimentarti questi video e poi questi altri possono aiutare a partire, anche se vanno cambiati i flags di nasm per usare il formato macho32 o 64, ed anche quelli del linker, se vuoi creare un eseguibile per macOs). Credo che tenterò a questo punto la strada “a” anche io, visto che era da un po’ che giravo attorno al set di istruzioni asm x86…


#126

Giusto per avitare dubbi, ti posto sia il mio input che il codice C usato per soluzione.

[details=Input Day23]set b 93
set c b
jnz a 2
jnz 1 5
mul b 100
sub b -100000
set c b
sub c -17000
set f 1
set d 2
set e 2
set g d
mul g e
sub g b
jnz g 2
set f 0
sub e -1
set g e
sub g b
jnz g -8
sub d -1
set g d
sub g b
jnz g -13
jnz f 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -23[/details]

[details=Day23 C]

#include <stdio.h> 


int main() {

    int a = 1;
    int b = 0;
    int c = 0;
    int d = 0;
    int e = 0;
    int f = 0;
    int g = 0;
    int h = 0;

    b = 93;
    c = b;

    if( a != 0 ) {
        b *= 100;
        b += 100000;
        c = b;
        c += 17000;
    }

    //loop_a:
    do {
        f = 1;
        d = 2;
        
        //loop_b:
        do {
            e = 2;

            //loop_c:
            do {
                g = d;
                g *= e;
                g -= b;

                if( g == 0 ) {
                    f = 0;
                }

                e += 1;
                g = e;
                g -= b;
            } while( g != 0 );

            d += 1;
            g = d;
            g -= b;
        } while( g != 0 );

        if( f == 0 ) {
            h += 1;
        }

        g = b;
        g -= c;

        if( g == 0 ) {
            // END
            break; //loop_a
        }
        b += 17;
    } while( 1 );

    printf("RESULT: %d\n", h);

    return 0;

}
```[/details]

#127

Hai per caso dato come risposta 910? Se si, è l’off-by-one error di cui parlavo. Il loop esterno deve fare un giro in più.


#128

Per rendere l’asm più semplice, ho tolto l’include di stdio ed usato semplicemente l’exit code del programma per fare output di h. Godbolt usando clang genera questo: https://godbolt.org/g/QsLUxk. Vedo un sacco di dead code (tutto quello che non ha un colore di background nella parte sinistra con il source in C). Forse ha ottimizzato troppa roba. Disabilitando le ottimizzazioni del compilatore con il flag -O0 invece genera questo: https://godbolt.org/g/7Kd3o9.


#129

Godbolt è una delle cose più belle che ci sono su internet.


#130

No, mi pare 946, anche se non me lo sono appuntato da qualche parte…
Il resto che hai scritto non l’ho capito. :stuck_out_tongue:


#131

946 è troppo alta.
Per spiegare meglio quello che ho scritto sopra, i 2 link a Compiler Explorer hanno lo stesso codice in C che hai scritto tu, il primo lasciando il compilatore C libero di ottimizzare il codice macchina (che viene poi disassemblato e visualizzato sulla parte destra), mentre il secondo con queste ottimizzazioni disabilitate. Quel sito evidenzia le varie parti di codice sorgente e disassemblato usando lo stesso colore di background. Le parti che restano bianche sono state ottimizzate del tutto, ovvero ignorate. Se guardi la differenza tra le 2, la versione senza ottimizzazioni “copre” tutto il codice C originale, mentre quella con le ottimizzazioni taglia via un sacco di roba (tra cui h del tutto, mi sembra). Potrebbe anche essere che il 946 che hai ottenuto sia una variabile non inizializzata, e pertanto potrebbe essere un numero diverso ogni volta che esegui il programma. Tanto per provare, ho compilato il tuo sia con le ottimizzazioni che senza. Vediamo cosa esce fuori e quanto tempo ci mette.


#132

Comunque ho fatto una prova semplificata abbassando i valori e l’output è costante ed uguale sia per la versione ottimizzata che per quella non ottimizzata. Mi rimangio pertanto le conclusioni ipotizzate. I compilatori sono estremamente più intelligenti di me e riescono a fare delle ottimizzazioni che non comprendo.


#133

Oggi non sono in forma. Non va bene nemmeno sfruttare l’exit code del programma per ottenere la soluzione, visto che è un unsigned char (range [0…255]) e non abbastanza grande per memorizzare il risultato…


#134

In attesa di capire qual è il problema del 23, sono finalmente riuscito a risolvere il 24.
Devo dire che una volta finito (e capito il funzionamento) sembra più facile di quello che mi sembrava all’inizio.
Comunque i tuoi consigli mi sono stati utili, anche se come funzione ricorsiva ho usato una cosa del genere:
findBridges(current_bridge, free_components)


#135

Go go go! Per restare nell’ottica del 23 guarda il post che sto per fare.


#136

Ce l’ho fatta!
Confesso di aver fatto qualche ricerca per capire quello che ancora mi sfuggiva (la storia dei numeri primi), ma alla fine l’ho risolto di mano mia.
Devo dire che difficilmente ci sarei arrivato da solo senza qualcuno che mi indirizzasse sulla via giusta…


#137

Bene. 49 stelle e mezza per te allora :stuck_out_tongue_winking_eye:. Comunque non c’è nulla di male. Credo che di quelli che hanno completato i puzzles, un buon 10% ha semplicemente copiato le soluzioni di altri, ed almeno il 30% ha chiesto e ricevuto aiuto.
Alla fine hai ottimizzato l’assembly oppure riscritto in un linguaggio ad alto livello?


#138

L’ho riscritto in javascript…
Avevo provato ad ottimizzare il codice in C ma c’era sempre quella storia dei numeri primi che mi impediva di eliminare il vero superflo, ovvero i due cicli più interni dove in pratica venivano moltiplicati d*e.
Avevo capito che se il loro risultato era uguale a b allora f veniva impostata a 0. Quello che non avevo intuito era che se i due valori moltiplicati davano b allora questo non era primo, quindi se b non è primo f=0, quindi h++. In pratica bastava controllare b per togliere i due cicli interni…

Day23
var a = 1;
var b = 0;
var c = 0;
var h = 0;

b = 93;
c = b;
if(a!=0) {
    b *= 100;
    b += 100000;
    c = b;
    c += 17000;
}
while(b<=c) {
    
    if(!isPrime(b)) {
        h ++;
    }

    b += 17;
}
tv(h);


function isPrime(n) {
    for(var i=2, s=Math.sqrt(n); i<s; i++) {
        if(n%i == 0) {
            return false;
        }
    }
    return n != 1;
}