mar 23

Quesiti da colloquio (2)

Quesiti da colloquio (2)

Runaround

runaround [ˈrʌnəˌraʊnd] n(fam) to give sb the runaround far girare a vuoto qn

Runaround

Questo è un quesito posto a un mio collega durante un colloquio.

Una stringa runaround ha le seguenti caratteristiche

  • E’ composta da N<10 elementi nell’alfabeto [1-9]
  • Ogni elemento dell’alfabeto può comparire una sola volta
  • Ogni elemento della lista può essere usato una sola volta
  • Il primo elemento della sequenza è detto testa.
  • Gli elementi successivi alla testa rappresentano la posizione del prossimo elemento nella lista di output ( la lista viene considerata come un anello)
  • Percorrendo tutta la stringa secondo i salti contenuti nella stringa stessa si ritorna alla posizione iniziale

Analizziamo per esempio il runaround 81362

Cifra Posizione
Testa 8 1362
8 813 6 2
6 8136 2
2 8 1 362
1 81 3 62
3 8 1362

Si richiede un algoritmo per verificare se una data stringa rappresenta un runaround.

Allego dati per il test

Validi Non Validi
13 12
147 123
1263 1234
81236 81111
83491 82222
913425 7654321
8124956 911111

Soluzione

Per verificare che una stringa sia un runaround semplicemente proviamo a percorrerla


def check_runaround(runaround)
  disponibili=("1".."9").to_set
  k=0
  runaround.size.times{
    return false if not disponibili.include?(runaround[k])
    salto=(k+runaround[k].to_i) % runaround.size
    disponibili.delete(runaround[k])
    k=salto
  }
  return true if k==0
  false
end

Share Button

mar 21

Quesiti da colloquio (1)

Quesiti da colloquio (1)

Il percorso critico

Anni fa feci il mio primo colloquio in un’azienda di Milano. Non ricordo il nome dell’azienda, potrei trovarlo facilmente cercando nelle email ma non mi va… e non mi va perchè andò male. Era un quesito abbastanza semplice. Lo risolsi tornato a casa in un foglio di carta in molto meno dei 40 minuti che mi diedero,ma sul momento andai nel pallone.

Ho deciso di postare il quesito e la sua soluzione.
(E’ la mia soluzione, non ho voluto cercarae conferme in letteratura nemmeno dopo)

Il quesito era qualcosa del genere

Sia L una lista di jobs ognuno dei quali ha un proprio tempo di esecuzione e dipende da un certo numero di jobs anchessi presenti in L. Calcolare il tempo di esecuzione di tutti i lavori supponendo di avere un numero illimitato di worker.

( era presentato in modo molto più discorsivo, parlava di antenne e di tecnici riparatori… ma la storiella proprio non la ricordo)

Analizzando il problema si può subito tirare fuori una soluzione basata sulla semplificazione di un grafo.
Inventiamoci una lista un minimo complessa e vediamo che succede.
Poniamo caso di avere la seguente lista di jobs:

ID Tempo Dipendenze
0 3
1 21 5 6
2 20
3 17 0 1 5 6
4 13 5
5 11 7
6 7 2 9
7 19
8 23
9 8
10 3 11
11 1
12 5 13
13 7 14
14 11

Dalla lista possiamo trarre direttamente un grafo direzionato

Colloquio

Si è aggiunto un nodo End che connette tutti i nodi da cui non partirebbe nessun arco.
Ha un valore puramente “visivo”
Un modo per affrontare il problema è semplificare il grafo fino ad arrivare ad un grafo costituito da n nodi collegati direttamente ad End.

Considerando che da ogni nodo escono archi che hanno tutti lo stesso peso per comodità di notazione chiameremo peso del nodo il peso dei suoi archi
Il tempo di esecuzione sarà il peso del ramo più pesante.
La regola di semplificazione è la seguente:

  • Per ogni nodo a cui sono collegate solo foglie
  • Si cerca la foglia più pesante
  • Si eliminano le foglie collegate al nodo ( lo si rende foglia) e si aggiorna il suo peso al vecchio peso più il peso della foglia più pesante a cui era collegato.
  • Si ripete la procedura fino ad avere solo foglie.

In questo modo si può semplificare il grafo ed arrivare alla soluzione.
La codifica in Ruby dell’algoritmo è molto semplice:

JOBS=[
 { time: 2 ,dependencies: [] },
 { time: 21,dependencies: [5,6] },
 { time: 20,dependencies: [] },
 { time: 17,dependencies: [0, 1, 5, 6] },
 { time: 13,dependencies: [5] },
 { time: 11,dependencies: [7] },
 { time: 7 ,dependencies: [2,9] },
 { time: 19,dependencies: [] },
 { time: 23,dependencies: [] },
 { time: 8,dependencies: [] },
 { time: 3,dependencies: [11] },
 { time: 1,dependencies: [] },
 { time: 5,dependencies: [13] },
 { time: 7,dependencies: [14] },
 { time: 11,dependencies: [] },
]

Adesso l’algoritmo vero e proprio, solo 14 righe in Ruby

 

def calcola(i) 
 return JOBS[i] if JOBS[i].class == Fixnum
 return JOBS[i][:time].to_i if JOBS[i][:dependencies].size==0
 m=0
 JOBS[i][:dependencies].each{|d|
 JOBS[d]=calcola(d)
 m=[m,JOBS[d]].max 
 }
 m + JOBS[i][:time]
end

JOBS.size.times{ |i| 
 JOBS[i]=calcola(i) 
} 
puts JOBS.inspect
puts JOBS.max

L’output dell’algoritmo è questo


[2, 51, 20, 68, 43, 30, 27, 19, 23, 8, 4, 1, 23, 18, 11]
68
Share Button

gen 26

L’algoritmo del Klout svelato ( o così dicono )

L’algoritmo del Klout svelato ( o quasi )

Klout-Data-blog-image

La funzione fondamentale di Klout e misurare l’influenza dei propri utenti attraverso uno stimatore.
L’algoritmo usato per il calcolo di questo punteggio è sempre stato segreto e questo ha contribuito ad attirare sopra Klout molte critiche ( alcune delle quali condivise anche da me).

C’è molto da dire e da criticare sul Klout da diversi punti di vista. Io in questo post cercerò di occuparmi principalmente di questioni algoritmiche.

Molte critiche affermano che l’algoritmo ( che viene definito come un complesso algoritmo di machine learning) sia in realtà molto rudimentale e poco efficiente nel misurare l’influenza.

Questa affermazione è intrinsecamente non verificabile visto che non esiste una misurazione standard dell’influenza e nemmeno una definizione standard ma esistono prove di questa “rudimentalità” che invece sono molto meno opinabili.

Nel 2011 Sean Golliher ha sviluppato un algoritmo alternativo che semplicemente utilizzando il numero di followers riusciva a ottenere uno stimatore del klout score con coefficente di correlazione dell 94%.

La formula utilizzata da Golliher è effettivamente rudimentale:

Klout= w1 * (followers/following) + w2 (listed/followers)

I valori di w1 e w2 non sono dichiarati ma sembra sia facile ottenerli “fittando” quel modello di regressione su un dataset.

La sua analisi è parziale e studia un solo social network ( twitter), ma è comunque sufficiente a rendere dubbio l’algoritmo.

L’articolo originale è purtroppo stato rimosso ( prima o poi scriverò una mail al tipo, mi incuriosisce molto)

Forse per questo il 28 Ottobre 2015 Klout si è decisa a dare maggiori informazioni sul funzionamento del suo algoirtmo.

Come funziona veramente?

L’ “evento” della rivelazione dell’algoritmo è stato ripreso da varie testate ( wired, forbes) ma nessuna è veramente scesa nel dettaglio analizzando i contenuti del paper pubblicato che peraltro non è particolarmente tecnico.

Vediamo quindi di capire veramente come funziona analizzando il paper.

Per prima cosa gli autori definiscono cosa lo stimatore dovrebbe stimare:

  • Sia G una rete sociale.
  • Sia A l’insieme delle azioni attraverso le quali gli utenti di G possono interagire.
  • Sia u il nostro utente e Gu il sottoinsieme di G con cui esso può interagire.

Possiamo definire l’influenza come una misura della quantità e della qualità delle interazioni che l’utente u può indurre in Gu in un tempo T.

( Non molto rigorosa, nevvero? In compenso suona assai bene )

Per calcolare questo punteggio Klout analizza circa 3600 features prese da 9 social network diversi.
Le features sono però raggruppate per social.
Ad ogni social è quindi associato uno score parziale che contribuisce alla formazione dello score globale.

Questo approccio è dovuto alle differenze fra le strutture di vari social network che offrono informazioni diverse e non direttamente comparabili.

Le features dipendono sia dalla struttura della rete sociale che dalle interazioni.
La struttura costituisce la componente “lenta” mentre le interazioni quella “dinamica”.

Esempi di componenti lente sono:

  • Followers ( o amici, fans, subscrivers, link entranti)
  • Coefficenti della struttura del grafo, utilizzati solo per Wikipedia ( pageRang, inlink/outlink)
  • Caratteristiche del profilo, utilizzate per LinkedIn e Lithium ( Titolo di lavoro, livello di educazione, awards, badge, certificazioni).

Le componenti dinamiche sono invece più complesse da calcolare perchè devono includere un “peso” dell’azione.
Devono infatti prendere in considerazionen oltre al tipo di azione l’audience dell’azione, quando l’azione è avvenuta, quanto movimento ha provocato l’azione nella rete sociale.
Il confronto con altre azioni dello stesso tipo permette di normalizzare il valore dell’azione rendendola comparabile.

Le componenti dinaniche e le compnenti lente sono quindi utilizzate per calcolare lo score relativo a un singolo social.
Lo score generale è quindi calcolato come la norma Euclidea del prodotto del vettore degli score con un vettore dei pesi W.

Il vettore dei pesi W è calcolato attraveso un algoritmo di machine learning che fitta il modello in base a un training set costituito da degli influencer.

Il training set viene generato utilizzando dei valutatori umani.

Si scelgono dei valutatori e ai valutatori si propongono delle coppie di influencer chiedendogli di scegliere quello più influente fra i due.
Avendo abbastanza valutatori si può generare ordinamento fra gli influencer presi in esame che viene utilizzato per calcolare il loro klout score da immettere nel training set.

E quindi? dov’è l’algoritmo?

Non c’è. Non rivelano i particolari, ed era prevedibile.

Altrimenti conoscendolo si potrebbe manipolare il proprio klout score.
Il sogno di ogni SEO applicato ai social network.

Ok, ma non dice proprio niente!

Eh si, non solo viene descritto sommariamente l’algoritmo, non vengono nemmeno date informazioni sul vettore dei pesi che ha un ruolo fondamentale. Più importante dell’algoritmo stesso.
Esso rappresenta le informazioni sul modello che l’algoritmo di machine learning è riuscito ad estrarre dal dataset.

Non dicendo niente dei pesi non si può capire quanto un social conta rispetto ad un altro e quanto un’azione conta rispetto ad un’altra.

In Klout.com si afferma genericamente che:

Postare un migliaio di volte e ottenere zero risposte è meno influente che postare unan volta sola è ottenere un migliaio di risposte. Non è una questione di quanto si parla ma di quante persone ti stanno ad ascoltare.

Ok, bellissimo, ma quanto?

E quindi, funziona?

Beh, Klout calcola il klout-score… funziona per definizione.

Non esiste un unità di misura standard per fare confronti.

Il problema è però alla base, è nel concetto di “influenza” e nella definizione di influencer.

Influence is the ability to drive action.

Dice Klout.com, ma di che azioni stiamo parlando?

Obama ha 99 e Justin Bieber 92.
Solo 7 punti di scarto.

Se volete far vendere qualcosa in effetti farvela sponsorizzare da Bieber è un ottima cosa ma dire che è il secondo influencer del pianeta richiede una definizione di influencer molto diversa da quella che ho io.

E rassegnatevi, potete essere influenti su argomenti complessi quanto volete, collegare tutti i social che volete.

Non batterete mai le foto in costume di Emily Ratajkowski che usa solo twitter.

Un’altra questione importante è che attualmetne klout non fa sentiment analisys.
E’ cioè incapace di percepire e tenere conto del tipo di reazioni che i post generano.

Se postate qualcosa di geniale e la gente vi risponde che siete veramente saggio è indifferente dal postare una stupidaggine epocale con gente che vi risponde che avete proprio detto una stronzata.

Emily-Ratajkowski-13

A un costoso corso di web marketing ho imparato che se aggiungo una foto non necessaria di Emily Ratajkowski aumentano le visite alla pagina. Io però non sono pronto alla notorietà ed ho cercato quindi una foto particolarmente vestita.

PS:

Questo post è stato effettivamente scritto intorno al 25 Novembre 2015, le informazioni si riferiscono a quella data.

Share Button

ago 25

Dijkstra ti osserva

DijkstraNonApprova

EWD1213

Share Button

mag 23

Il problema delle 8 regine parte 2, un approccio iterativo

6952100115_de8c56ecd8_h

Questo post è comparso inizialmente nel blog di Fabrizio Mondo qualche anno fa.

In seguito Fabrizio ha deciso di rendere il blog tematico e il post è rimasto disperso nel cyberspazio come“Un fiocco di neve che non cade in nessun posto.”(cit.).

Adesso ho deciso di correggere qualcosa e ri-pubblicarlo.

Il problema delle 8 regine parte 2, un approccio iterativo

In questo articolo ci proponiamo di riscrivere l’algoritmo descritto nel precedente in modo da renderlo completamente iterativo, questo problema è un caso particolare di un problema ricorrente nell’ottimizzazione del software, si tratta di rendere iterativo un algoritmo “intrinsecamente” ricorsivo.

Quando un problema è definibile per induzione risulta molto più semplice progettare il suo algoritmo per ricorsione e l’equivalente iterativo risulta meno leggibile.

I programmi ricorsivi risultano più chiari, più semplici, più brevi e più facili da capire delle corrispondenti versioni iterative perchè l’implementazione riflette fedelmente la strategia di soluzione del problema.

La versione iterativa però è sempre più veloce e meno pesante perchè usa una quantità costante di memoria (con la possibile eccezione delle ricorsioni tail nei linguaggi ottimizzati per la ricorsione…ma come vedremo tra poco quella è una ricorsione “semplificabile”).

Infatti ogni volta che una funzione ricorsiva chiama se stessa vengono riallocate le variabili locali e vengono aggiunti record alla memoria di stack per poi ritornare alla funzione chiamante, questo implica sia un maggiore utilizzo di memoria (pesantezza) sia un maggiore tempo di esecuzione visto che un accesso alla memoria è infinitamente più lento di un accesso a un dato che si trova in un registro.

Piccola digressione:Ricorsione TAIL e ricorsione non-TAIL

Una ricorsione si definisce tail quando la chiamata ricorsiva viene eseguita come ultima operazione, una ricorsione tail è sempre direttamente convertibile in un iterazione, vediamo un esempio banale: stampare tutti gli elementi di una lista.

stampaLista(lista){
        if(not lista.empty){
                print lista.pop;
                stampaLista(lista);
        }
}

noterete che questa ricorsione è facilmente e direttamente sostituibile con un un ciclo while.

while(not lista.empty){
    print lista.pop;
    stampaLista(Lista);
}

Alcuni linguaggi di programmazione sono pensati per basarsi sulla ricorsione più che sull’iterazione, in questi linguaggi tipicamente l’interprete comprende che si tratta di ricorsione tail e la trasforma in iterazione a runtime. Questo è l’unico caso in cui l’uso della ricorsione tail è ragionevole.

Questo è il modo di procedere tipico del Lisp ( almeno nelle sue declinazioni accademiche):

(defun stampaLista (l)
    (if (null l) ()
        (progn
            (print (car l))
            (stampalista (cdr l)))))

Dico accademico perché il ciclo while esiste in molti dialetti di Lisp. E se non esiste è possibile definirlo. Alcuni dialetti del Lisp possono essere usati in modo totalmente imperativo e procedurale:

(defun stampaLista (list)
  (while list
    (print (car list))
    (setq list (cdr list))))

(Sul Lisp e sulla Tail Call optimization ci sarebbe molto altro da dire, mi ripropongo di farlo in seguito)

Viceversa una ricorsione è non-tail se la chiamata ricorsiva non viene eseguita per ultima. Una ricorsione non-Tail non è direttamente convertibile in un iterazione.

L’esempio canonico di ricorsione non-Tail è la sequenza di Fibonacci.
Com’è noto la sequenza di Fibonacci è definita nel caso generico come: Fib(n) = Fib(n-1) + Fib(n-2)

Il calcolo richiede quindi due chiamate ricorsive.

Vediamone l’implementazione in Lisp

(defun fib (n) 
(cond
 ((eq n 1) 0)
 ((eq n 2) 1)
 (T (+ 
 (fib (- n 1)) 
 (fib (- n 2))))))

Vediamone anche un implementazione in Java

int fib(n){
        if(n==1) return 0;
        if(n==2) return 1;
        return fib(n-1)+fib(n-2);
}

Spesso si cerca di convertire una ricorsione non-tail in una tail aggiungendo una funzione ausiliaria o delle variabili che passano valori alle chiamate successive.

In questo modo sarà possibile convertirla poi in iterazione ( o se si sta lavorando su linguaggio con la Tail Call Optimization si otterrà una ricorsione più veloce).

Cerchiamo di convertire il codice precedente

(defun _fib (n i j)
 (if (zerop n) i
 (_fib (1- n) j (+ i j))))
 
(defun fib (n) 
 (_fib n 0 1))

Ci siamo serviti di una funzione interna che funziona attraverso due variabili ausiliarie.
Questa implementazione ci permette di utilizzare una sola chiamata ricorsiva tail.
Convertiamo ancora una volta in Java

int _fib(int n, int i, int j){
        if(n==0)return i;
        return _fib(--n,j,i+j)
}

int fib(int n){
        return _fib(n,0,1);
}

Fine della digressione, torniamo a noi.

Torniamo al nostro caso adesso

Nel nostro caso le cose sono abbastanza complicate, infatti non solo non è una ricorsione tail, ma non è nemmeno un’approccio puramente ricorsivo. Infatti le colonne vengono percorse per iterazione mentre singole pedine piazzate per ricorsione.

public void generate(){
    int h=0;
    do{
        if(check(n, h)){
            iterazioni++;
            piazza(n,h);
            n++;
            if(n<8){
                generate();
            }
            else
                System.out.println(dump(scacchiera));
            n--;
            rimuovi(n,h);
        }
        h++;
    }while(h<8);
}

E quindi: come si affronta il problema nel caso di ricorsione non-Tail? o peggio ancora di ibridi ricorsione/iterazione?

In questo caso serve astrazione, non si può convertire il listato, si deve guardare al funzionamento dell’algoritmo e riformalizzarlo in modo iterativo. Dobbiamo proprio ripartire da come ci si muove sulla scacchiera e riscrivere l’algoritmo.

Possiamo riscrivere l’algoritmo in questo modo:

  1. Si parte da una configurazione vuota , la riga corrente è la prima, la colonna corrente è la prima.
  2. Dalla riga corrente e dalla colonna corrente si piazza una pedina nella prima posizione disponibile successiva alla colonna corrente, se è possibile, la colonna corrente è adesso la posizione dove si è piazzato.
  3. Se la 2 ha avuto successo e ci sono 8 piedine piazzate l’algoritmo ha trovato una configurazione valida, la si stampa.
  4. Se la 2 ha avuto successo si passa alla riga successiva, la colonna corrente sarà la prima e si ripete il punto 2.
  5. Se la 2 non ha avuto successo e ci si trova sulla prima riga l’algoritmo è concluso.
  6. si toglie una pedina, la riga corrente è la precedente, la colonna corrente è la colonna successiva a quella in cui si trovava la pedina si ripete il punto 2.

Notate che questa implementazione ci permette anche di separare in due l’algoritmo e di ottenere una configurazione per volta, infatti il punto 1 è il setup iniziale e I successivi l’algoritmo vero e proprio. Trattandosi di un algoritmo con backtrack inoltre ci servirà una qualche struttura a stack che nell’implementazione ricorsiva era implementata intrinsecamente dalla ricorsione mentre qui dovrà essere esplicita. Una volta riformulato in maniera iterativa l’implementazione in Java è diretta:

public void generate_iterative()  {
        boolean libero;
        int k,p;
        c = 0;
        n = 0;
        iterazioni=0;
        while (true) {
                libero = false;
                for (k = c; k < 8 && !libero; k++)libero = check(n,k);
                k--;
                if(libero){
                        iterazioni++;
                        push(n,k);
                        n++;
                        c=0;
                        if(n>=8)System.out.println(dump(scacchiera));
                }else{
                        if(n<1)return;//algoritmo concluso
                        p=pop();//rimuovo pedina;
                        c = 1 + p % 8;// parto a cercare dalla colonna dopo
                        n--;
                }
        }
}

Contando le iterazioni allo stesso modo del precedente otteniamo anche qui esattamente 1951 iterazioni per generare la 91 disposizione. Esattamente come doveva essere.

Le funzioni che abbiamo usato per gestire lo stack sono push() e pop() che sono definite in questo modo:

void push(int riga, int colonna) {
        piazza(riga, colonna);
        pedine.add(p(riga, colonna));
    }

    int pop() {
        int p = pedine.pop();
        rimuovi(p / 8, p % 8);
        return p;
    }

dove pedine è uno Stack.

Share Button

mag 21

Il problema delle 8 regine

Questo post è comparso inizialmente nel blog di Fabrizio Mondo qualche anno fa.

In seguito Fabrizio ha deciso di rendere il blog tematico e il post è rimasto disperso nel cyberspazio come “Un fiocco di neve che non cade in nessun posto.” (cit.).

Adesso ho deciso di correggere qualcosa e ri-pubblicarlo.

Il problema delle 8 regine

Il problema delle 8 regine è un problema  matematico che consiste nel trovare il modo posizionare otto regine su una scacchiera in modo che non si possano mangiare tra di loro, quindi in modo che nessuna si trovi sulla stessa riga o colonna o su una delle diagonali occupata da un altra.

E’ un problema molto noto in letteratura perchè è stato usato più volte per la didattica della programmazione.

  • Viene proposto per la prima volta da Max Bezzel, uno studioso di problemi scacchistici, nel 1848.
  • Viene risolto per la prima volta nel 1850 da Franz Nauck (non ho idea di chi sia).
  • Viene studiato, nelle sue versioni generalizzate, da molti altri matematici incluso Carl Friedrich Gauss ( lui c’entra sempre. Gauss è il Chuck Norris della matematica. Gauss può uccidere Chuck Norris con un calcio rotante).
  • Nel 1972 fu usato da Edsger Wybe Dijkstra per illustrare una tecnica fondamentale di programmazione (il backtrack).
  • Sempre nel 1972 Niklaus Wirth lo usa come “toy problem” nel suo famosissimo paper “Program Development by Stepwise Refinement”.

Cominciamo dal principio, tralasciando l’algoritmica per ora.

Avete davanti una scacchiera vuota e 8 regine come fate a piazzarle?

Per comodità consideriamo l’insieme delle caselle come un insieme ordinato di 64 posizioni, questo ci consentirà di rendere un insieme ordinato anche quello delle soluzioni. Piazziamo la prima regina sulla locazione 1 e poi spostiamoci lungo le caselle piazzando una regina ogni volta che sia possibile, arriviamo in questo modo alla situazione illustrata nel Diagramma1.

Diagramma 1

Diagramma 1

A questo punto abbiamo un problema: l’ultima pedina è impossibile da piazzare!

considerato che sappiamo per certo che delle soluzioni devono esistere possiamo concludere che almeno una di quelle regine si trova in una posizione sbagliata , come procedere allora?

Andiamo indietro di una pedina e cerchiamo se la 7 ha altre posizioni in cui essere piazzata (sapendo che ci deve essere una regina in ogni riga abbiamo 2 posizioni da controllare), ci rendiamo conto che anche lei non ne ha, allora togliamo la 7 e lavoriamo sulla 6, ma anche lei non ne ha di disponibili e quindi torniamo alla 5, e così via fino a trovare alternative. una volta trovata un alternativa si rimpiazzano le pedine che abbiamo tolto a partire dalla nuova configurazione trovata e se da essa non ci sono soluzioni valide per tutte le 8 pedine torniamo di nuovo indietro fino a trovarne.

Eseguendo questo procedimento possiamo arrivare alla prima soluzione che si trova molto lontano da quella da cui sono partito, è quella mostrata nel Diagramma2.

Diagramma 2

Diagramma 2

Backtrack

Il procedimento appena descritto si chiama backtrack, è può essere sintetizzato nella frase

“Prova a fare qualcosa, se non funziona torna indietro e riprova qualcos’altro”

è un procedimento molto generico che permette di risolvere molti problemi, anche se non è molto veloce per l’alto numero di combinazioni provate.

Adesso cerchiamo di formalizzare il problema per costruire un algoritmo capace di risolverlo Cominciamo dalla definizione della singola soluzione accettabile, che è composta da due vincoli:

  1. La scacchiera deve contenere 8 regine
  2. Nessuna delle regine deve essere capace di mangiarne un altra

A questo punto cominciamo a utilizzare il modello per trarne le proprietà che ci permetteranno di costruire l’algoritmo.

  1. Ci potrà essere solo una regina in ogni riga, quindi ogni riga contiene necessariamente 1 regina
  2. Lo stesso principio vale per le colonne, quindi ogni colonna contiene necessariamente 1 regina
  3. Nella scacchiera esistono 15 diagonali crescenti ,considerando diagonali anche il caso degenere delle singole caselle agli angoli, e ognuna di esse potrà contenere al massimo una regina, questo significa che ci saranno 7 diagonali libere e 8 occupate ( definiamo crescente una diagonale con verso concorde sia a x che a y)
  4. Lo stesso principio vale per le diagonali decrescenti

E adesso l’ultima considerazione, ovvia ma fondamentale

Partendo da una configurazione valida ( che non viola la condizione B) togliendo una regina si ottiene un’altra configurazione valida.

La 5 ci permette di eseguire con sicurezza il backtrack.

Cominciamo a pensare alle strutture di dati da utilizzare,

  • Ci servirà innanzitutto un vettore di booleani che rappresenta la scacchiera ,quindi un vettore di 64 bit. Non lo useremo per i check comunque, ma solo per gestire l’output
  • Stessa cosa per le colonne
  • Uno per le diagonali decrescenti da 14bit
  • E un ultimo per le diagonali crescenti da 14bit

Nelle diagonali crescenti la somma di riga e colonna è costante, e farà da indice. In quelle decrescenti la sottrazione tra righe e colonne è costante e farà da indice, andrà però sfalzata di 7 posizioni in avanti visto che i vettori partono da 0 nel linguaggio scelto (Java).

Detto questo supponendo di disporre di funzioni per aggiungere e togliere regine, una per verificare la disponibilità di una posizione e un ultima per eseguire il dump della scacchiera su schermo la codifica della funzione principale dell’algoritmo è molto compatta:

void generate(){
        int h=0;
        do{
            if(check(n, h)){
                iterazioni++;
                piazza(n,h);
                n++;
                if(n==8){
                    System.out.println(dump(scacchiera));
                }
                else
                    generate();

                n--;
                rimuovi(n,h);
            }
            h++;
        }while(h<8);
    }

h rappresenta la colonna corrente, n la riga.

Partendo da (0,0) si controlla che la posizione sia disponibile, se lo è si piazza una regina, se le regine sono 8 siamo su una disposizione finale e allora la stampiamo.

Se non lo siamo richiamiamo la funzione che piazzerà un altra regina e richiamerà se stessa fino a trovare una posizione finale.

Al che togliamo l’ultima cominciamo a cercare una posizione finale successiva, l’algoritmo si conclude quando la prima regina è stata spostata nell’intera prima riga.

L’algoritmo trova tutte le 92 soluzioni in 1951 iterazioni. Questa versione genera tutte le combinazioni in maniera ricorsiva, una versione che le genera una per volta è un po’ più complicata da implementare e ce ne occuperemo nel prossimo articolo.

Per la cronaca, la prima soluzione (quella che stavamo svolgendo a mano a inizio articolo) si trova dopo 113 iterazioni

    8 |      *         |
    7 |  *             |
    6 |            *   |
    5 |    *           |
    4 |          *     |
    3 |              * |
    2 |        *       |
    1 |*               |1
     
    113

Per concludere allego il codice completo del progetto

Codice completo del progetto

Queens.java

    package darshan.queen;    
    import java.util.BitSet;

    public class Queens {

        int k=0;
        int n=0;
        int c=0;
        long iterazioni=0;
        BitSet diagonali_c;
        BitSet diagonali_d;
        BitSet righe;
        BitSet colonne;
        BitSet scacchiera;

        public Queens(){
            diagonali_c=new BitSet(14);
            diagonali_d=new BitSet(14);
            colonne=new BitSet(8);
            scacchiera=new BitSet(64);
        }

        int p(int r, int c){
            return r*8+c;
        }

        boolean check(int riga, int colonna){
            return !(colonne.get(colonna) || diagonali_c.get(riga-colonna+7) || diagonali_d.get(riga+colonna));
        }

        void generate(){
            int h=0;
            do{
                if(check(n, h)){
                    iterazioni++;
                    piazza(n,h);
                    n++;
                    if(n==8){
                        System.out.println(dump(scacchiera));
                    }
                    else
                        generate();

                    n--;
                    rimuovi(n,h);
                }
                h++;
            }while(h<8);
        }

        void piazza(int riga, int colonna){
            scacchiera.set(p(riga, colonna));
            colonne.set(colonna);
            diagonali_c.set(7+riga-colonna);
            diagonali_d.set(riga+colonna);
        }

        void rimuovi(int riga, int colonna){
            scacchiera.clear(p(riga, colonna));
            colonne.clear(colonna);
            //righe.clear(riga);
            diagonali_c.clear(7+riga-colonna);
            diagonali_d.clear(riga+colonna);
        }

        public String dump(BitSet scacchiera){
            StringBuffer buffer= new StringBuffer();
            c++;
            for(int a=7;a>=0;a--){
                buffer.append("n"+(a+1)+" |" );
                for(int b=0;b<8;b++){
                    if(scacchiera.get(a*8+b))
                        buffer.append("* ");
                    else
                        buffer.append("  ");
                }
                buffer.append("|");
            }
            buffer.append(c+"n"+iterazioni);
            return buffer.toString();
        }
    }

Main.java

    package darshan.queen;
    public class Main {
        public static void main(String[] args) {
            Queens q= new Queens();
            q.generate();
        }
    }
Share Button

dic 14

Il C++ e 5 malefici cast

Gandal ehm Dumbledore that casts a spell

Gandalfl Dumbledore that casts a spell

In C è facile spararti in un piede;
In Cpp è più difficile ma se ci riesci ti salta via l’intera gamba.
– Bjarne Stroustrup

Una cosa che dico sempre del Cpp è che è un linguaggio che va dominato e che insegnarlo a un principiante sarebbe come dare un mitragliatore al tipo che entra per la prima volta al poligono di tiro.
Ci sono un sacco di funzioni che sono pensate seguendo uno di questi due principi:

  1. La macchina può farlo && tu sei un uomo responsabile –> il compilatore te lo deve permettere.
  2. Nel caso ti trovassi impantanato con una particolare coppia di design pattern che non avresti dovuto usare insieme una certa funzionalità potrebbe essere utile && tu sei un uomo responsabile –> il compilatore te lo deve permettere.

La cosa che dico per chiarire questo concetto è di solito:
"In CPP puoi addirittura scrivere sopra le costanti!"

Oggi voglio parlare di questo mostro cercando però di far capire che se usato correttamente ha un comportamento addirittura più sicuro di quello del C.

Il C++ e i cast

In Cpp esistono ben 5 tipi di cast ordinabili in base alla loro maleficenza nel modo seguente:

dynamic_cast

E’ il tipo di cast più importante quando si lavora ad oggetti, ed è stata un ottima idea.
Permette di effettuare un cast solo se il cast è possibile e il controllo viene fatto sia dal compilatore (controllo statico) sia in fase di runtime ( controllo dinamico, da cui il nome)
E’ stato pensato per castare gli oggetti in caso di ereditarietà e polimorfismo:
Il cast è sempre possibile quando si converte una classe derivata nella sua classe madre.

class Punto2{
	public:
	short x;
	short y;

	Punto2(short x, short y){
		this->x=x;
		this->y=y;
	}

};

class Punto3 : public Punto2{
	public :
	float z;
	Punto3(float x, float y, float z): Punto2(x,y){
		this->z=z;
	}

};


int main(){
	Punto3 p3_1=Punto3(1,2,3);
	Punto2 *p2_1=dynamic_cast<Punto2*>(&p3_1);
	//Questa non funzionerà
	Punto3 *p3_2=dynamic_cast<Punto3*>(p2_1);

	getwchar();
}

Il primo cast di questo codice funziona, il secondo da errore.

Il comportamento in caso di errore di dynamic_cast , nel caso l’analisi statica del compilatore sia incapace di rilevare un errore, è abbastanza strano:

  • Se stiamo castando verso un puntatore ci darà un puntatore nullo
  • Se stiamo castando verso una reference si genererà un eccezione bad_cast

dynamic_cast non funziona nelle classi che non hanno metodi virtuali e, per corollario, non funziona sulle struct.

Quando potrebbe essere utile?

Sempre, quando si fa downcasting di oggetti polimorfici.
Bisogna però tenere a mente che è leggermente più lento di static_cast in quanto fa dei controlli a runtime.

static_cast

E’ sostanzialmente identico al C Cast, con in vantaggio di essere facilmente individuabile nel codice senza dover tirar fuori un espressione regolare ma usando un semplice "trova" ( ehh, quando ero ggiovane gli ide non erano così belli).
Permette di effettuare un cast solo se il cast è possibile e la possibilità viene vagliata solo dal compilatore. Quindi non ci sono controlli a runtime.
Permette di fare cose brutte… ma cose brutte che si possono fare anche in C.

int main(){
	Punto3 p3_1=Punto3(1,2,3);
	Punto2 *p2_1=dynamic_cast<Punto2*>(&p3_1);
	void* mistero=p2_1;
	//Punto3 è incompatibile con Punto2 ed è pure più grande. questa è una cosa pericolosa!
	Punto3 *p3_2=(Punto3*)(mistero);
	Punto3 *p3_3=static_cast<Punto3*>(mistero);
	//Dynamic cast non permette di farlo
	Punto3 *p3_4=dynamic_cast<Punto3*>(mistero);
	getwchar();
}

Quando potrebbe essere utile

Andrebbe sempre usato al posto del C Cast, ma di fatto non lo si usa quasi mai…purtroppo.

reinterpret_cast

Nell’esempio precedente abbiamo ingannato il compilatore convincendolo a fare un cast pericoloso, ma il compilatore è nostro amico, perchè ingannarlo? Cpp ci offre un modo per dirgli di fare cose cattive.

int main(){
	Punto3 p3_1=Punto3(1,2,3);
	Punto2 *p2_1=dynamic_cast<Punto2*>(&p3_1);
	void* mistero=p2_1;
	// Punto3 è incompatibile con Punto2 ed è pure più grande. questa è una cosa pericolosa!
	Punto3 *p3_2=(Punto3*)(mistero);
	Punto3 *p3_3=static_cast<Punto3*>(mistero);
	// Tu ordini, il compilatore lo fa.
	Punto3 *p3_4=reinterpret_cast<Punto3*>(p2_1);
	getwchar();
}

reinterpret_cast non fa nessun controllo sul contenuto, casta e basta.

Quando potrebbe essere utile

Quasi mai. Solo se dovete fare cose veramente strane o se siete persone cattive.
Non lamentatevi se vi siete sparati in un piede… avete premuto voi il grilletto,avete pure tolto la sicura.

const_cast

Eccolo qui il piccolo mostro… leggiamo prima la definizione del modificatore const dal K&R

The qualifier const can be applied to the declaration of any variable to specify that its value
will not be changed
. For an array, the const qualifier says that the elements will not be altered.

Ehh, ma in fondo anche le costanti stanno su locazioni della ram… sono variabili! e quindi il nostro compilatore deve permetterci di modificarle! anche in C possiamo farlo ma dobbiamo ingannare il compilatore.
Invece il compilatore Cpp non è solo nostro amico, si fida proprio di noi e non dobbiamo fargli credere di star facendo qualcosa di buono come a suo nonno compilatore C che va ogni domenica alla chiesa di K&R a venerare UnixSystemV.

			int main() {
				const int a = 0;
				int* b = (int*)&a; // C
				c = const_cast<int*>(&a); // Cpp
			}

Quando potrebbe essere utile

Quasi mai. Solo se dovete fare cose veramente strane E se siete persone cattive.
Non lamentatevi se vi siete sparati in un piede… avete premuto voi il grilletto,avete pure tolto la sicura, avete messo voi le pallottole a punta cava per farvi ancora più male.

C Cast

E’ il cast classico del C, sorpresi di vederlo qui sotto?

int main() {
	const int a = 0;
	int* b = (int*)&a; // C
	c = const_cast<int*>(&a); // Cpp
}

Quando potrebbe essere utile?

Sempre quando non si lavora con oggetti.
Quando si lavora con oggetti lo si può usare per fare tutte le stranezze che si possono fare con gli altri cast, ma in modo più oscuro.

Piccola digressione: static_cast e dynamic_cast nelle classi polimorfiche

Nella parte precedente del post mi sono concentrato fondamentalmente su quello che succede ai dati, ma gli oggetti sono fatti anche di funzioni.
Contrariamente a quanto si possa pensare, in caso di successo, static_cast e dynamic_cast hanno comportamenti assolutamente identici con le funzioni polimorfiche.

L’OOP basata sulle classi si basa su 3 concetti:

  • Incapsulamento
  • Ereditarietà
  • Polimorfismo

Cpp implementa e controlla il polimorfismo attraverso il modificatore virtual.

Un metodo polimorfico di cui si è fatto l’override copre il metodo della classe base anche in caso di cast. con tutti i tipi di cast.
Invece nel caso di metodi non virtual il cast fa in modo che vengano chiamati quelli della classe destinazione.

Per accedere a un metodo virtual della classe base bisogna fare qualcosa di sporco: oggetto.Classebase::metodo()

class Punto2{
	public:
	short x;
	short y;

	Punto2(short x, short y){
		this->x=x;
		this->y=y;
	}

	virtual void toString(){
		cout << x << "," << y << endl;
	}

	void toString2(){
		cout << x << "," << y << endl;
	}

};

class Punto3 : public Punto2{
	public :
	float z;
	Punto3(float x, float y, float z): Punto2(x,y){
		this->z=z;
	}
	virtual void toString(){
		cout << x << "," << y << "," << z << endl;
	}

	void toString2(){
		cout << x << "," << y << "," << z << endl;
	}

};

int main() {
	Punto3 p3_1=Punto3(1,2,3);
	p3_1.toString();
	p3_1.toString2();
	cout << "Dynamic Cast" << endl;
	Punto2 *p2_1=dynamic_cast<Punto2*>(&p3_1);
	p2_1->toString();
	p2_1->toString2();
	cout << "Static Cast" << endl;
	Punto2 *p2_2=static_cast<Punto2*>(&p3_1);
	p2_2->toString();
	p2_2->toString2();
	cout << "C Cast" << endl;
	Punto2 *p2_3=(Punto2*)(&p3_1);
	p2_3->toString();
	p2_3->toString2();
	cout << "Reinterpret Cast" << endl;
	Punto2 *p2_4=reinterpret_cast<Punto2*>(&p3_1);
	p2_4->toString();
	p2_4->toString2();
	cout << "Per accedere a un metodo virtuale dalla classe base bisogna fare questo" << endl;
	p3_1.Punto2::toString();

	getwchar();
}

che da come output:

	1,2,3
        1,2,3
        Dynamic Cast
        1,2,3
        1,2
        Static Cast
        1,2,3
        1,2
        C Cast
        1,2,3
        1,2
        Reinterpret Cast
        1,2,3
        1,2
        Per accedere a un metodo virtuale dalla classe base bisogna fare questo
        1,2

Note finali

Questo post è stato scritto in Markdown nei ritagli di tempo, e poi incollato su wordpress.
(quasi) tutti i codici sono stati provati in remoto con Koding. Spero non ci siano errori.

Share Button

mag 27

Evoluzione genetica applicata agli alberi di classificazione

Evoluzione genetica applicata agli alberi di classificazione ( la mia tesi di laurea)

Ho deciso di pubblicare la mia tesi di laurea all’interno del sito.

La tesi tratta dell’applicazione degli algoritmi genetici agli alberi di decisione ortogonali concentrandosi in particolare sulla limitazione del bloat.

L’algoritmo descritto riesce ad eguagliare in prestazioni gli algoritmi presenti in letteratura riuscendo a diminuire la taglia degli alberi prodotti.

Il software a corredo della tesi è scritto in Java ed è in fase di reingegnerizzazione.

 

La tesi è consultabile qui: http://www.thedarshan.com/tesi

Share Button

feb 14

Il limite della retina e le risoluzioni inutilmente alte

Che risoluzione è capace di percepire l’occhio umano? quando uno schermo diventa inutilmente definito? state veramente sfruttando il vostro costosissimo lettore bluray?

Non so se avete sentito tempo fa Steve Jobs declamare che il suo iPhone4 aveva così tanti pixel che l’occhio non riusciva a distinguerli. (alcuni dicono fosse pubblicità ingannevole, secondo me non lo era, o quantomeno non troppo. E io adoro parlare male di Jobs, quindi fidatevi: non lo era, non troppo)
Senza scendere nel caso particolare oggi vorrei parlare di questo.
Quando un display è inutilmente definito? Quando un video è inutilmente grande?
Cominciamo dal principio:

Cosa è la risoluzione per il nostro occhio?

Pensando alla risoluzione ci viene in mente una cosa planare, la dimensione del pixel sullo schermo per esempio, ma in effetti è una questione di angoli. La risoluzione dell’occhio umano è il minimo angolo a cui il nostro occhio riesce a distinguere due oggetti considerati puntiformi.

Pensiamo, esempio inflazionatissimo, a una macchina che si allontana da noi in rettilineo. A un certo punto non riusciremo a distinguere i due fari e li vedremo come una cosa sola, in quell’istante abbiamo raggiunto il limite di retina. Se calcoliamo l’angolo del triangolo isoscele faro-occhio-faro abbiamo ottenuto la risoluzione dell’occhio umano.
Pare che un buon occhio umano possa distinguere una coppia di linee di 0.35 mm da 1 m , quindi abbiamo un triangolo con la base da 350e-6 e l’altezza da 1, quindi con un po di trigonometria:  tan(\alpha)=(0,5  \cdot 350 \cdot 10^{-6}) \rightarrow \alpha=1,750 \cdot 10^{-4} radianti.
Che in gradi fanno 0,01003° oppure 0,6016′ oppure 36,1” ( ma, con buona pace degli ingegneri, io lavorerò in radianti di qui in poi)

Come traduco questo angolo in una misura piana?

Notando che è sicuramente una funzione lineare quella che stiamo cercando possiamo chiederci
Quanto deve essere lontano un cerchio largo un metro perché io lo veda come un punto?
Abbiamo quindi un triangolo rettangolo con una base di 0,5 e un angolo di 0,5*1,750e-4 e cerchiamo la lunghezza del cateto, quindi:  l= \frac{ 0,5}{sin(0,5 \cdot 1,750 \cdot 10^{-4})} =5714,285 che è il nostro numero magico, un cerchio con diametro x diventerà un punto dopo 5714,285x.
Da questa ovviamente possiamo dedurre che a una lunghezza x il diametro del minimo cerchio percepito sarà x/5714,285.

Però ad essere sincero non credo di avere la vista di un cecchino…

Sul serio? Io si, malgrado stia tutto il giorno davanti al pc ho ancora 10/10.
Pare però la risoluzione angolare dell’occhio dell’uomo medio sia 2,908e-4 rad, il che ci porta ad avere un fattore di circa 3438.

Da questi due fattori possiamo tirare fuori un paio di tabelline interessanti

Gli smartphone

Supponiamo di guardare uno smartphone da 30 centimetri, stiamo superando il limite di retina?
Calcoliamolo, premettiamo che tipicamente le risoluzioni vengono espresse nell’odiosissimo sistema imperiale inglese come pixel per pollice (ppi), che è un unità lineare che rappresenta il numero di pixel che posso incolonnare in una colonna lunga un pollice.

1ppi = 50/127 pixel/cm = 5/127 pixel/mm = 39,370 pixel/m

da 30 centimetri la minima distanza distinguibile è 0,3/5714,285=52,5e-6m=2,066e-3in quindi  sono 1/2,066e-3=484 ppi.
Questo se siete dei cecchini, per la gente normale è 291ppi, questo implica che per un cecchino l’iPhone non supera il limite di retina ma che per una persona normale lo supera insieme a molti telefoni di quella fascia!

iPhone3 165ppi Samsung Galaxy Ace S5830 165ppi
iPhone4 330ppi Samsung Galaxy S3 306ppi
iPhone5 326ppi Sony Xperia T 323ppi
Nokia Lumia 920 332ppi HTC Butterfly 441ppi
BlackBerry Z10 355ppi LG Optimus G Pro 401ppi
Huawei Ascend D2 441ppi Lenovo K900 401ppi

Noto anche che le case asiatiche vanno molto forte, quindi se Apple vuole continuare la gara a chi c’è l’ha più lungo forse la risoluzione di retina non è il campo ideale…

La questione diventa ancora più pubblicitaria se riflettiamo sul fatto che la risoluzione retina è calcolata nel caso di contrasto massimo, tipicamente nel caso in cui stiamo leggendo testo, nel caso in cui stiamo guardando un immagine è più bassa, nel caso in cui sia un video è ancora più bassa.

I televisori

Supponiamo di avere un televisore in 16/9 di una dimensione x con un video a una risoluzione y, dopo che distanza sto superando il limite di retina?
Per i motivi espressi sopra userò soltanto il fattore di retina dell’uomo medio, che considero comunque sovrastimato nel caso di un video.
Gli standard hd presumono tutti schermi con rapporto di forma da 16/9, le risoluzioni vengono infatti espresse da un solo numero che rappresenta il numero di pixel sul lato corto, per esempio
1080=1920 × 1080
I televisori vengono invece ( per una fastidiosa tradizione) misurati con la lunghezza della diagonale espressa in pollici, procediamo in questo modo:
sia a il lato corto , b il lato lungo e c la diagonale.

I rapporti devono essere a=9 ; b=16 ; c=\sqrt{9^2+16^2}=18,357 \rightarrow  a=c \cdot 0,490 b=c \cdot 0,871
( rendetevi conto che sto spiegando l’uso del teorema di pitagora, il prossimo che mi dice che scrivo in modo incomprensibile lo picchio )
a questo punto la distanza al di sopra della quale siamo incapaci di distinguere i pixel è D=k \cdot \frac{lato}{pixel} \cdot conv \rightarrow pixel= k \cdot \frac{lato}{D} \cdot conv (conv nel caso metri → pollici è 0,0254 )
Adesso possiamo tirare fuori due interessanti tabelline

Tabella dimensione/risoluzione → distanza

240 360 480 720 1080
19 3,39 2,26 1,69 1,13 0,75
22 3,92 2,61 1,96 1,31 0,87
32 5,71 3,80 2,85 1,90 1,27
40 7,13 4,75 3,57 2,38 1,58
42 7,49 4,99 3,74 2,50 1,66
47 8,38 5,59 4,19 2,79 1,86
60 10,70 7,13 5,35 3,57 2,38

Tabella dimensione/distanza → risoluzione

19 22 32 40 42 47 60 80 100 200 400
0,5 1626 1883 2739 3423 3594 4022 5135 6846 8558 17116 34231
1 813 941 1369 1712 1797 2011 2567 3423 4279 8558 17116
1,5 542 628 913 1141 1198 1341 1712 2282 2853 5705 11410
2 406 471 685 856 899 1006 1284 1712 2139 4279 8558
2,5 325 377 548 685 719 804 1027 1369 1712 3423 6846
3 271 314 456 571 599 670 856 1141 1426 2853 5705
4 203 235 342 428 449 503 642 856 1070 2139 4279
5 163 188 274 342 359 402 513 685 856 1712 3423
6 135 157 228 285 300 335 428 571 713 1426 2853
8 102 118 171 214 225 251 321 428 535 1070 2139
10 81 94 137 171 180 201 257 342 428 856 1712
12 68 78 114 143 150 168 214 285 357 713 1426
15 54 63 91 114 120 134 171 228 285 571 1141
18 45 52 76 95 100 112 143 190 238 475 951
21 39 45 65 82 86 96 122 163 204 408 815

400in è approssimativamente la dimensione dello schermo di un cinema.

Notiamo che, anche se abbiamo usato un fattore eccessivo che è quello che potremmo usare per appicazioni di videoscrittura con una risoluzione di 720p (inferiore al bluray) guardata da un televisore da 60 pollici ci da una distanza di 3,57 metri, stiamo sprecando risoluzione!

Nel caso mio ho un televisore da 32in e lo guardo da circa 3 metri, riuscirei a malapena a distinguere un 480p, non riuscirei nemmeno a sfruttare al massimo un dvd ( Che nel formato pal sono in 720×570 ).

Un immagine carina e parzialmente appropriata per far fare l'anteprima a facebook

Un immagine carina e parzialmente appropriata per far fare l'anteprima a facebook

I rapporti devono essere

( rendetevi conto che sto spiegando l’uso del teorema di pitagora, il prossimo che mi dice che scrivo in modo incomprensibile lo picchio )

a questo punto la distanza al di sopra della quale siamo incapaci di distinguere i pixel è (conv nel caso metri → pollici è 0,0254 )

Adesso possiamo tirare fuori due interessanti tabelline

Share Button

mag 15

Dart, HTML5 e il frattale di Koch (2/2)

<– parte precedente

Conclusa la descrizione geometrica cominciamo a dare uno sguardo alle applicazioni Dart

Dart, struttura generale delle applicazioni

Un applicazione in Dart è concettualmente molto simile a un applicazione nei linguaggi visuali che usano elementi grafici ( un applet, un applicazione visual studio con le form etc etc) in particolare una cosa che salta all’occhio e la presenza di un entry point obbligatoria nella forma di un main() che viene eseguito al caricamento della pagina.
Tipicamente all’inizio dell’applicazione si trovano anche le import delle library e le risorse dichiarate per esempio la mia applicazione ha questa forma:

#library('koch');
#import('dart:html');
#resource('koch.css');

main() {
new Koch();
}

All’avvio mi limito ad allocare un oggetto Kock che materialmente gestirà il disegno, per quanto riguarda l’html la forma per collegarsi è la seguente:

&lt;!DOCTYPE html&gt;
&lt;html&gt;
[…]
&lt;canvas id="canvas" width="640" height="640" style="background-color: black"&gt;&lt;/canvas&gt;
[…]
&lt;div class="rangeOption"&gt;
&lt;input id="slider" type="range" max="10" value="2" /&gt;
&lt;/div&gt;
[…]
&lt;script type="application/dart" src="koch.dart"&gt;&lt;/script&gt;
&lt;script src="koch.dart.js"&gt;&lt;/script&gt;
&lt;/body&gt;
&lt;/html&gt;

Lo script viene sempre importato due volte, una volta come file dart ( che viene eseguito nel caso sia presente la macchina virtuale) e una volta nella sua versione javascript, l’importazione avviene alla fine dell’html,

La gestione degli eventi

Una peculiarità del dart è che gli handler per gli eventi non devono ( e probabilmente neanche possono) essere dichiarati nell’html ad esempio la input con id slider nell’html precedente viene usata per controllare i livelli di profondità da disegnare ed ha quindi un metodo associato all’evento change. L’associazione avviene in questo modo:

InputElement slider = document.query("#slider");
slider.on.change.add((Event e) {
passi = Math.parseInt(slider.value);
drawFrame();
}, true);

su un elemento che supporta gli eventi col metodo on si accede alla lista degli eventi e col metodo add si aggiungono i listener, il prototipo della funzione è questo

EventListenerList add(void handler(Event event), [bool useCapture])

L’oggetto event in questo caso viene allocato come classe anonima, il flag finale (opzionale) ha un significato abbastanza oscuro:

Immaginate il DOM della pagina come un albero, gli eventi nel DOM vengono propagati prima dai livelli superiori verso il basso ( contenitore verso il contenuto ) e successivamente dal contenuto in alto verso il contenitore, è possibile associare l’handler a una delle due fasi per avere più controllo sull’ordine di esecuzione di eventuali handler multipli, il valore di default è false e quindi gli handler vengono invocati in fase di risalita. ( vi rimando a un ticket che ho aperto nel gruppo per ulteriori informazioni ).

Le Canvas

L’unico oggetto HTML5 che ho usato nel progetto sono le canvas. Le canvas sono degli ogetti al cui interno è possibile disegnare, i disegni sono persistenti finchè la pagina non viene chiusa e possono indirettamente essere salvati, dart ci permette di accedere alle canvas attraverso l’oggetto CanvasElement, e in particolare attraverso il CanvasRenderingContext2D ad esso associato

Il salvataggio di una canvas

La procedura per salvare una canvas è attualmente abbastanza macchinosa, si estrae l’immagine corrente dalla canvas ( come png, gif o jpeg) , la si setta come contenuto di un tag img e poi la si salva dal browser come un immagine normale.

CanvasElement canvas = document.query("#canvas");
var str=canvas.toDataURL("image/png");
ImageElement e=document.query("#canvasImg");
e.src=str;

Quindi torniamo al frattale di Koch

Lo script seguente disegna il frattale partendo da un triangolo ( 3 segmenti) creando una struttura simile a un fiocco di neve, ho fatto in modo che i colori fossero dipendenti dalla posizione e dalla distanza dal centro ( algoritmo assolutamente empirico, creato con i colori Y’UV per avere più controllo sulla luminanza, così empirico che non lo descrivo nemmeno xD ) uno slider permette di scegliere il livello di profondità con cui dovrà essere disegnato il frattale, la fase di plot viene comunque effettuata solo all’ultimo livello. Leggi il resto »

Share Button

Post precedenti «