Sic-Oding

Cos'è un dottorato e la ricerca in generale?

2012-11-29T15:28:00.001+01:00

Ogni autunno, spiego ad un nuovo gruppo di studenti dottorandi cosa il dottorato sia.

È difficile descriverlo a parole.

Perciò, io uso le immagini.

Immagina un cerchio che contenga tutta la conoscenza umana:

Nel momento in cui finisci la scuola elementare, tu ne conosci un po':

Quando finisci la scuola superiore, ne sai un po' di più:

Con una Laurea Triennale acquisisci una specialità:

Una Laurea Specialistica (o Master) approfondisce questa specialità:

Leggere pubblicazioni scientifiche ti porta al bordo della conoscenza umana:

Una volta arrivato al limite, metti a fuoco:

Spingi al limite per alcuni anni:

Finché un giorno il confine cede:

E, quell'ammaccatura che avete prodotto si chiama dottorato di ricerca (PhD):

Naturalmente, il mondo vi sembrerà diverso ora:

Perciò, non dimenticate l'immagine più grande:

Continuate a spingere e a creare ammaccature.

Fonte: Matt Might, http://matt.might.net/articles/phd-school-in-pictures/

POV-Ray / MATLAB - Metodo alternativo per creare una mappa di profondità (non-omogenea) di una scena

2012-06-30T23:23:00.000+02:00

Nel precedente articolo abbiamo creato delle sub-mappe in POV-Ray, per poi creare una mappa di profondità non-omogenea utilizzando MATLAB.

Tuttavia, il procedimento di disabilitare tutte le textures in POV-Ray può risultare lungo e delle volte anche complicato. Nel seguente articolo illustrerò brevemente come riuscire ad ottenere lo stesso risultato combinando POV-Ray e MATLAB.

Per prima cosa bisogna creare una union di tutti gli oggetti della vostra scena. A quel punto basta "tagliare" la scena intersecandola con un parallelepipedo.
Fin qui tutto bene, tranne per il semplice fatto che non è possibile assegnare un valore di grigio direttamente da POV-Ray. Cosa che, invece, era possibile ottenere con il metodo precedente.

POV-Ray


#declare enableSlicing = 1;
#if (enableSlicing = 1)
background {color rgbt 1}
#end


#declare allObjects = union {
      Oggetto 1
      Oggetto 2
      ...
      Oggetto n
} // Fine Union



#if (enableSlicing = 1)
intersection {
object {allObjects}
box { 
 < -1000, -1000, startCut>,
 <1000, 1000, endCut>
}
finish {ambient 1 diffuse 0}
}
#else
object {allObjects}
#end

Il codice sottostante è uno script per MATLAB (o Octave) che colora la parte interessata di una sub-mappa utilizzando il grigio appropriato. La formula per calcolare il valore del grigio di una specifica scena è la stessa utilizzata negli articoli precedenti.

 
function Graying(nameFile, totalNumberSubMaps)

rgbCoeff = 255;

offsetLevels = rgbCoeff / (totalNumberSubMaps - 1);

for index = 0:totalNumberSubMaps - 1

    rgbColor = floor(abs(((index) * offsetLevels) - rgbCoeff));

    rgbColor = rgbColor / 255;

    nameMapFile = nameFile; 


    % TODO: Script per aggiungere un suffisso a nameMapFile.

    [A, map, Alpha] = imread(strcat(nameMapFile, '.png'));

    [h, w] = size(Alpha);

    subMap = zeros(h, w, 0);

    modified = 0;

    for i=1:h

        for j=1:w

            if Alpha(i, j) ~= 0

                modified = 1;

                subMap(i, j, 1) = rgbColor;

                subMap(i, j, 2) = rgbColor;

                subMap(i, j, 3) = rgbColor;

            end

        end

    end

    % Salva la nuova sub-mappa.

    if modified == 1

        imwrite(subMap, strcat(nameMapFile, 'MAP', '.png'));

    end

end

Facebook / Sicurezza - Ritrovare la propria password

2012-06-27T10:18:00.001+02:00

Facebook ormai è utilizzato quotidianamente da milioni e milioni di persone. Il Social Network è così utilizzato che molti utenti vi accedono permettendo al proprio browser di ricordarne la password.

Eppure quante volte vi sarà capitato di domandarvi quale password oscura si nasconda lì dietro? Dopotutto capita spesso di dimenticarsi la propria password.

Oggi vi mostrerò come recuperarla utilizzando Chrome (funziona anche su Safari).

Step1: Prima di accedere a Facebook, aprite gli Strumenti per Sviluppatori di Chrome (Visualizza->Opzioni Per Sviluppatori-> Strumenti per Sviluppatori). E selezionate la linguetta Network.

Step2: Fare il login e ritrovarsi nella seguente situazione:

Step3: Recuperate la vostra password. Selezionare login.php dalla colonna all'estrema sinistra. Alla vostra destra comparirà la richiesta POST da parte vostra a Facebook.com . Nella sezione Form Data troverete e-mail e password.

Facile vero? Ci si legge!

JavaZone 2012 - Che Spot!

2012-06-24T12:18:00.001+02:00

JavaZone è un "meeting" per sviluppatori Java ed è il più importante dei paesi Scandinavi e fra i più importanti in Europa.
Il JavaZone consiste in interviste ai massimi esperti del settore, workshops, e presentazioni per un totale di 200mila ore di divulgazione in soli due giorni!

Il JavaZone 2012 si terrà il 12-13 Settembre 2012 nell'Oslo Spektrum (Oslo, Norvegia) e se siete abbastanza fortunati potreste trovare ancora dei ticket disponibili (vedi Fonti a fine pagina).

Negli ultimi anni il JavaZone ha sfruttato l'onda Youtube per pubblicizzarsi in modo alquanto bizzarro:

JavaZone 2012

JavaZone 2011

JavaZone 2012

Fonti:
JavaZone

MATLAB - Creare una mappa di profondità (non-omogenea) di una scena

2012-06-24T11:13:00.003+02:00

Salve!

Nel precedente articolo ho illustrato come creare delle "sub-mappe" utilizzando POV-Ray ed eravamo arrivati ad un punto cruciale in cui ci ritrovavamo con tanti tasselli da mettere insieme.

L'obiettivo di oggi è riuscire a sovra-imporre le nostre sub-mappe per creare una mappa di profondità come quella qui sotto.

Per fare ciò utilizzeremmo MATLAB (potete anche usare Octave che è gratuito).

Per prima cosa apriamo un nuovo scrip vuoto (File->New->Script) e utilizziamo il codice sottostante per caricare le sub-mappe da sovra-imporre.


numeroSubMappe = 100;

mappaEsempio = 'TEST.png'; // usiamo questa mappa per ottenere le dimensioni (h,w) da usare

[A, mappa, Alpha] =  imread(mappaEsempio);

[h, w] = size(Alpha); // Otteniamo altezza e larghezza dalla matrice contenente informazioni sul canale Alpha dell'immagine. 

listaSubMappe = {}; // Inizializziamo la lista delle sub-mappe da caricare.

listaSubMappeAlpha = zeros(h, w, 0); // Inizializziamo il primo elemento di questa lista con degli zero.



// Carichiamo le sub-mappe.

for i = 1: numeroSubMappe 

    nomeSubMappa = 'sub-mappa';

    nomeSubMappa = strcat(nomeSubMappa, num2str(i), '.png');

    [A, sub-mappa, Alpha] =  imread(nomeSubMappa);

    listaSubMappeAlpha(:, :, i) = Alpha;

    listaSubMappe{i} = A; // A è l'immagine in se stessa. 

end



// Inizializziamo lo sfondo della mappa finale utilizzando il colore NERO. Il NERO indica il taglio eseguito in POV-Ray più distante dalla telecamera.  
immagineFinale = zeros(h, w);



for i = 1:h

    for j = 1:w

        immagineFinale(i, j, 1) = 0; // R

        immagineFinale(i, j, 2) = 0; // G 

        immagineFinale(i, j, 3) = 0; // B

    end

end

Adesso sovra-imponiamo le immagini dalla penultima alla prima. Il procedimento inizia dal penultimo taglio al primo così da "nascondere" quelle parti della scena che non sono mai visibili all'occhio umano perché dietro ad altri oggetti.




for n = 0: numeroSubMappe - 1

    mappaAlpha = listaSubMappeAlpha(:, :, numeroSubMappe - n); // Utilizziamo la mappaAlpha per conoscere la forma degli oggetti tagliati da POV-Ray al taglio (numeroSubMappe - n)

    mappa = listaSubMappe{1, numeroSubMappe - n}; // Utilizziamo la mappa per conoscere il grigio da usare.


// Itera la sub-mappa in lungo e in largo.

    for i = 1:h

        for j = 1:w

            if (mappaAlpha(i, j) ~= 0) // Controlla se il taglio ha intersecato un'oggetto o meno. 



                grigioDaUsare =  mappa(i, j, 1); // Otteniamo il grigio da usare. Il grigio era già stato calcolato su POV-Ray.

                grigioDaUsare = double (grigioDaUsare) / 255.0; // In MATLAB i valori RGB sono compresi fra 0.0 e 1.0. Quindi dobbiamo dividere il nostra valore per 255.0 .

                immagineFinale(i, j, 1) =  grigioDaUsare; // R

                immagineFinale(i, j, 2) =  grigioDaUsare; // G

                immagineFinale(i, j, 3) =  grigioDaUsare; // B

            end

        end

    end

end

Adesso abbiamo una matrice (immagineFinale) che rappresenta la nostra mappa di profondità. L'unica cosa che ci rimane da fare è salvare la matrice come un'immagine e il gioco è fatto.


imwrite(immagineFinale, 'MAPPA_FINALE.png');

Alla prossima ;)

Fonti:
MATLAB

POV-Ray - Creare una mappa di profondità (non-omogenea) di una scena

2012-06-08T21:52:00.001+02:00

Nel precedente articolo - POV-Ray - Creare una mappa di profondità (omogenea) di una scena - è stato illustrato come creare delle prime semplici mappe di profondità in POV-Ray. Nel seguente articolo, invece, spiegherò come creare delle mappe di profondità non-omogenee (vedi immagine).

La scena originale è composta da cinque oggetti elementari disposti su un piano orizzontale che tende ad infinito.

L'intera scena viene considerata come un solo oggetto nel seguente modo:

#declare INTERA_SCENA = union {
     Oggetto 1
     Oggetto 2
     ...
     Oggetto N
}

La scena quindi viene "tagliata" a una determinata profondità da un "sottile" parallelepipedo e vengono tenute in considerazione solo le parti intersecanti con l'intera scena. Inoltre la parte rimasta viene colorata utilizzando un determinato grigio (eliminando riflessi e ombre).

Quest'operazione è riassumibile in queste poche linee di codice:

intersection {
   INTERA_SCENA
    
   // Parallelepipedo.
   box {
       <500, -500, inizioTaglioZDepth>, 
       <-500, 500, fineTaglioZDepth>
   }

   pigment {
       rgb<rgbColor / rgbCoeff, rgbColor / rgbCoeff, rgbColor / rgbCoeff> // Grigio da usare per il taglio. 
   }
   finish {ambient 1 diffuse 0} // Colore uniforme al taglio.

}

L'operazione deve essere eseguita un determinata numero di volte, così da poter sezionare tutti gli elementi della scena e con diversi grigi. Quindi non andremmo semplicemente a Renderizzare ogni scena manualmente, ma utilizzeremo l'opzione ANIMATION di POV-Ray.

Nel mio esempio ho attivato l'orologio con i seguenti parametri:
Clock Initial = 0.0, Clock End = 1
Initial Frame = 1, Final Frame = 100.

Quindi l'orologio avanzerà di 0.01 alla fine di ogni renderizzazione per ben 100 volte.
Utilizzando il valore di clock è possibile calcolare i valori dei "tagli", come anche i valori dei grigi.

#declare rgbCoeff = 255;
#declare numeroMappe = 100;
#declare indiceMappa = clock * numberoMappe + 1;
#declare offsetLevels = rgbCoeff / (numberoMappe - 1);
#declare rgbColor = floor(abs(((indiceMappa -1) * offsetLevels) - rgbCoeff));
#declare offsetTaglio = 0.35;
#declare inizioTaglioZDepth = offsetTaglio * clock * numeroMappe;
#declare fineTaglioZDepth = offsetTaglio * (clock + 0.01) * numberMaps;

Inoltre, per un risultato eccellente è bene ricordarsi di disattivare l'Anti-Aliasing.
PANICO!

Adesso vi ritrovate con 100 mappe e non sapete che farne! Tranquilli, nel prossimo articolo illustrerò come mettere il tutto insieme utilizzando MATLAB.

C - Sensore di movimento dei MacBook

2012-04-29T01:23:00.000+02:00

Nel seguente articolo parlerò del SMS: Sudden Motion Sensor. L'SMS è un sensore che è possibile trovare negli ultimi modelli dei portatili di casa Apple.

All Intel-based Apple portables such as the MacBook, MacBook Pro, MacBook Air, PowerBook G4 computers starting with PowerBook G4 (12-inch 1.5GHz), PowerBook G4 (15-inch 1.67/1.5GHz), PowerBook G4 (17-inch 1.67GHz), and iBook G4 computers starting with iBook G4 (Mid 2005) have Sudden Motion Sensor technology.

Questo sensore è stato progettato per rilevare movimenti inusuali del computer, così da ibernare temporaneamente l'hard disk ed evitare danneggiamenti su quest'ultimo.

Questa caratteristica unica dei Mac può essere usata per tanti fini. Un fine sicuramente molto stimolante è quello dei giochi. Il video qui sotto mostra un giochino molto semplice, ma da sicuramente un'idea di cosa sia possibile creare.

Questa semplice applicazione è stata creata utilizzando parte del progetto OpenSource UniMotion.

Qui potete trovare l'implementazione di un'applicazione scritta da me che spero vi semplifichi l'utilizzo dell'SMS.

Fonti:

Wikipedia:
http://it.wikipedia.org/wiki/Sudden_Motion_Sensor

Unimotion:
http://unimotion.sourceforge.net/

Apple:
http://support.apple.com/kb/HT1935
http://support.apple.com/kb/HT1934

Altro:
http://www.shiffman.net/p5/sms/

Per Python:
http://giasone.wordpress.com/tag/sudden-motion-sensor/

POV-Ray - Creare una mappa di profondità (omogenea) di una scena

2012-04-25T22:40:00.001+02:00

POV-Ray è un programma di ray-tracing per creare scene virtuali molto realistiche, quasi fotografiche.

POV-Ray, che a prima impressione fa pensare al suo cugino Blender, è privo di un'interfaccia grafica molto "eccitante".

Tuttavia POV-Ray si dimostra essere uno strumento molto potente perché permette al grafico di creare qualsiasi scena possibile e inimmaginabile, dato che ogni scena (dalla più piccola alla più complessa) viene generata utilizzando un linguaggio di script apposito. Qualcuno potrà non essere d'accordo con me, ma quando si programma non esistono limiti, diversamente da quando ci si affida interamente a uno strumento di supporto ad oggetti.

Nel seguente articolo spiegherò come creare una mappa di profondità di tipo omogenea per una data scena. Prima però mi sembra opportuno dare un pò di spazio ad alcune immagini molto belle, così da assaporare un pò le potenzialità di POV-Ray.

La generazione di ognuna di queste immagini è molto complessa e richiede almeno un paio di minuti. La qualità ha un suo prezzo, motivo in più per cui POV-Ray non è utilizzato nello sviluppo della grafica dei giochi.

Una mappa di profondità di una scena è solitamente utilizzata come metro per misurare la profondità di un determinato pixel, in un'immagine che alla fin fine è pur sempre in 2D.

Nell'esempio sottostante possiamo vedere come le zone bianche indicano gli oggetti più vicini. Man mano che si muove nelle zone più distanti della scena, la mappa di profondità tende verso il nero.

Le due immagini soprastanti sono state elaborate su Adobe Photoshop (plugin DOF-Pro).

Come creare una propria mappa di profondità con POV-Ray? Prima di tutto creiamo la nostra scena.

Questa scena è ottenuta utilizzando il codice sottostante. Per evitare di riscrivere il codice per la scena in se stessa e per creare la mappa di profondità ho utilizzato degli if-statement, che mi permettono di attivare e disattivare alcune porzioni di codice al bisogno.

#include "colors.inc"
#include "shapes.inc"
#include "textures.inc"
  
// Se generateMaps = false -> scena normale
// Se generateMaps = true -> mappa di profondità
#declare generateMaps = false;
    
light_source { <5, 30, -30> color White }
camera {
 location <0.0, 1.0, -10.0>
 look_at  <0.0, 1.0,  0.0>
 focal_point < 1, 1, -6>   
}


// Union to represent the entire scene
union {
 sphere {
  <-2, 0, -6>, 0.5
  
  #if (!generateMaps)
     pigment { NeonPink }
  #end
 }    

 box {
  <4, -2, 0>, < 6,  2,  3>
  rotate <0, -20, 0>

  #if (!generateMaps)
     pigment { Green }
  #end
   
 }       
 
 difference {
        box {
         -1,   1        
         #if (!generateMaps)
            pigment { Red }
         #end
          }
        cylinder {
         -1.0001*z, 1.0001*z, 0.5 
          #if (!generateMaps)
            pigment { Green }
          #end         
        }
 }

 #if (generateMaps)
 pigment {
  gradient z
  pigment_map {
   [ 0.0 White]
   [ 1.0 Black ]
  }
  scale <1, 1, 30>
  translate -10*z
 
 }
 finish {
  ambient 1
  diffuse 0
  specular 0
  phong 0
 }
 #end
 
}  // end union

Osserviamo che quando la variabile generateMaps è attivata (true) le textures degli oggetti delle scene sono disattivate, ed è attivata la seguente porzione di codice:

pigment {
  gradient z
  pigment_map {
   [ 0.0 White]
   [ 1.0 Black ]
  }
  scale <1, 1, 30>
  translate -10*z
 
 }
 finish {
  ambient 1
  diffuse 0
  specular 0
  phong 0
 }

Qui viene applicato un "pigmento" che transita dal Bianco al Nero lungo tutta la profondità (da z = -10 at z = 20).
Inoltre, impostando ambient 1 e diffuse 0, rimuoviamo qualsiasi ombra creata tra gli oggetti nella scena.
Ed ecco il risultato finale:

Per estendere o comprimere la scala dei grigi bisogna semplicemente allontanare o avvicinare il punto dal quale la scena viene colorata di bianco e quello finale in cui la scena è colorata di nero. Questo si ottiene giocherellando un pò con li argomenti di scale e translate.

Inoltre, quando si crea la mappa di profondità è buon uso disattivare l'antialising. Io uso MegaPov (visto che sono su Mac) dove la disattivazione è un'azione molto semplice: Window/ Render Preferences / Image & Quality.
Se si usa Pov-Ray bisogna modificare il file povray.ini aggiungendo: Antialias=false.

Questo è tutto e alla prossima.

Fonti:

Pov-Ray

MegaPov (Pov-Ray per Mac)

POV-Wiki

Immagini scacchi: http://www.dofpro.com/tutorial1.htm

Java - Google Code Jam 2012 (Qualifications, Problem A)

2012-04-20T22:06:00.001+02:00

Dopo una breve introduzione al Google Jam Code 2012 e come prepararsi ad affrontare un problema della competizione nel miglior modo possibile, in questo articolo spiegherò la mia soluzione al primo problema: Speaking in Tongues.

Potete trovare il problema originale alla fine dell'articolo, ma per semplificare la vita un pò a tutti riassumerò un pò il tutto in Italiano.

Ci sono due lingue: l'Inglese e il Googlerese. Entrambe hanno 26 lettere e ogni lettera dell'alfabeto Inglese corrisponde a una lettera dell'alfabeto Googlerese. La mappatura fra i due alfabeti non cambia mai, quindi ogni informazione data dal problema può essere presa per buona.
La prima mappatura che possiamo estrapolare è per le seguenti tre lettere dall'Inglese al Googlerese:
'a' -> 'y', 'o' -> 'e', e 'z' -> 'q'.
Ma dove troviamo il resto della mappatura? Facile! Usiamo l'esempio che ci viene dato.

Sample

Input

3
ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv

Output

Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up

Come potrete vedere nella mia soluzione, che troverete più in basso, io ho semplicemente creato due ArrayList dove inserire in ordine le lettere da entrambi i testi (senza ripetizioni ovviamente). Dopo avere stampato la mia prima "mappatura" mi sono accorto che l'esempio sopra riportato non mi avrebbe permesso di mappare 'z'->'q' e 'q'->'z', quindi ho semplicemente inserito queste due relazioni manualmente visto che la prima era già stata suggerita all'inizio del problema.

Dopodiché non mi è rimasto che scaricare il problema dalla competizione, leggere l'input, tradurre ogni caso proposto, chiudere il file di output e caricarlo nella piattaforma della competizione.

Come potete vedere il problema era veramente semplice, ma se non si riesce a capirlo bene è possibile non venire mai a capo della soluzione.

La mia soluzione (mi scuso in anticipo per lo stile, ma non era un concorso di bellezza):

public class ProblemA {

 public static String initGooglerese;
 public static String initEnglish;
 public static ArrayList listGooglerese;
 public static ArrayList listEnglish;

 public static void main(String[] args) {
  try {
   init();
   Scanner input = new Scanner(new FileReader("A-small-attempt0.in"));
   PrintWriter output = new PrintWriter(new FileWriter("output.txt"));
   int index = 0;
   int numberCases = input.nextInt();
   
   String googlerese = input.nextLine();
   for (int i = 0; i < numberCases; i++) {
    output.print("Case #" + (i + 1) + ": ");
    
    // Get the line.
    googlerese = input.nextLine();
    for (int j = 0; j < googlerese.length(); j++) {
     if (googlerese.charAt(j) != ' ') {
      index = listGooglerese.indexOf(googlerese.charAt(j));
      output.print(listEnglish.get(index));
     } else {
      output.print(" ");
     }
    }
    output.print("\n");
   }
   
   output.flush();
   output.close();
   input.close();
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }
 
 public static void init() {
  initGooglerese = "ejpmysljylckdkxveddknmcrejsicpdrysirbcpcypcrtcsradkhwyfrepkymveddknkmkrkcddekrkdeoyakwaejtysrreujdrlkgcjv";
  initEnglish = "ourlanguageisimpossibletounderstandtherearetwentysixfactorialpossibilitiessoitisokayifyouwanttojustgiveup";
  
  if (initGooglerese.length() != initEnglish.length()) {
   System.out.println("Error");
  } else {
   listGooglerese = new ArrayList();
   listEnglish = new ArrayList();
   for (int i = 0; i < initGooglerese.length(); i++) {
    if (listGooglerese.contains(initGooglerese.charAt(i)) == false) {
     listGooglerese.add(initGooglerese.charAt(i));
     listEnglish.add(initEnglish.charAt(i));
    }
   }
  }
  if (listGooglerese.contains('q') == false) {
   listGooglerese.add('q');
   listEnglish.add('z');
  }
  
  if (listGooglerese.contains('z') == false) {
   listGooglerese.add('z');
   listEnglish.add('q');
  }
  
 }

}

Problema originale:

Problem A. Speaking in Tongues

We have come up with the best possible language here at Google, called Googlerese. To translate text into Googlerese, we take any message and replace each English letter with another English letter. This mapping is one-to-one and onto, which means that the same input letter always gets replaced with the same output letter, and different input letters always get replaced with different output letters. A letter may be replaced by itself. Spaces are left as-is.

For example (and here is a hint!), our awesome translation algorithm includes the following three mappings: 'a' -> 'y', 'o' -> 'e', and 'z' -> 'q'. This means that "a zoo" will become "y qee".

Googlerese is based on the best possible replacement mapping, and we will never change it. It will always be the same. In every test case. We will not tell you the rest of our mapping because that would make the problem too easy, but there are a few examples below that may help.

Given some text in Googlerese, can you translate it to back to normal text?

Solving this problem

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has only 1 Small input. Once you have solved the Small input, you have finished solving this problem.

Input

The first line of the input gives the number of test cases, T. T test cases follow, one per line.

Each line consists of a string G in Googlerese, made up of one or more words containing the letters 'a' - 'z'. There will be exactly one space (' ') character between consecutive words and no spaces at the beginning or at the end of any line.

Output

For each test case, output one line containing "Case #X: S" where X is the case number and S is the string that becomes G in Googlerese.

Limits

1 ≤ T ≤ 30.
G contains at most 100 characters.
None of the text is guaranteed to be valid English.

Sample

Input

3
ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv

Output

Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up

Java - Google Code Jam: Prepararsi alla sfida

2012-04-16T20:33:00.001+02:00

Nel seguente articolo condividerò con tutti voi il codice base che ho usato io per il Google Code Jam durante le qualificazioni e che utilizzerò nelle fasi successive.

Ogni problema proposto dalla competizione ha il seguente input (letto da file, con estensione .in):

- Numero dei casi
- Caso 1
- Caso 2
- Caso 3
etc, etc fino alla fine del file

Per ogni caso bisogna applicare la propria soluzione e scriverla in un'altro file nel seguente modo:

Case #1: Soluzione a Caso 1
Case #2: Soluzione a Caso 2
Case #3: Soluzione a Caso 3
etc, etc.

 
import java.io.*;
import java.util.*;

public class Problema {

 public static void main(String[] args) {
         try {
                        // Apriamo il file contenente l'input.
                        // Una volta scaricato il file della competizione, rinominare input.in con il nome del file scaricato.
                        Scanner input = new Scanner(new FileReader("input.in"));
                        // Creiamo il file dove scrivere le nostre soluzioni
                        PrintWriter output = new PrintWriter(new FileWriter("output.txt"));

                        int numeroDiCasi = input.nextInt();
                        // Saltiamo alla prima linea del file -> Caso 1.   
                        String data = input.nextLine(); 

                        // Risolviamo tutti i casi proposti.
                        for (int i = 0; i < numeroDiCasi; i++) {
                                output.print("Case #" + (i + 1) + ": ");

                                // Leggiamo il caso 1 (un caso potrebbe essere costituito anche da più linee)
                                data = input.nextLine(); 
    
                                // RISOLUZIONE DEL PROBLEMA.

                                output.print(SOLUZIONE);
                                output.print("\n");
                        }
                        // Gli stream d' I/O vengono finalizzati e chiusi.
                        output.flush();
                        output.close();
                        input.close();
                } catch (FileNotFoundException e) {
                             e.printStackTrace();
                } catch (IOException e) {
                            e.printStackTrace();
                }
       }
}

A questo punto, una volta risolto il problema, non ci resta che scaricare il problema "Small Set" ed eseguire il proprio programma con l'input proposto. Poi bisogna caricare sia la l'output.txt che il proprio codice sorgente .java nella piattaforma della competizione e in alto apparirà l'esito: Correct o Incorrect.
Se l'esito è Correct, allora si potrà scaricare il problema "Large Set" ed eseguire il proprio programma con questo nuovo input (più difficile). La piattaforma della competizione, tuttavia, non vi dirà l'esito del Large Set se non dopo la fine del round.
Se l'esito è Incorrect: avrete una penalità "temporale", ma potete comunque provare a risolvere il problema nuovamente.
Nel caso due concorrenti abbiano ottenuto lo stesso punteggio, le loro penalità temporali verranno tenute in considerazione.

Google Code Jam 2012

2012-04-15T11:32:00.000+02:00

Ieri, 14 Aprile 2012, si è svolta la fase di qualificazione per Code Jam 2012 organizzata da Google inc.
Per agevolare le diverse fasce orarie la durata della fase di qualificazione è stata di 25 ore.
I problemi da risolvere erano quattro (in qualsiasi linguaggio di programmazione), ma per passare alla fase successiva basta totalizzare almeno 20 punti di un totale di 100 (quindi bisognava risolvere in media due problemi).

La mia gara è iniziata circa 9 ore dopo l'inizio della gara. Essendo alla prima partecipazione ho impiegato la mia prima mezz'oretta a capire come funzionava il sistema e la fase di invio dei risultati.

Potete trovare i problemi proposti alla fine dell'articolo, mentre scriverò articoli separati per le mie risposte nei giorni successivi.

Riassunto della mia gara:

Il primo problema praticamente serviva per capire chi sapeva programmare, chi no. Il trucco consisteva nel creare una mappatura bidirezionale fra i due linguaggi proposti.

Il secondo problema, invece, era sicuramente più intrigante. Poteva sicuramente essere risolto utilizzando del brute-forcing, ma per rendere la cosa più interessante io ho optato in una risoluzione matematica del problema (che si è rilevata anche più efficiente: O(n) vs O(n^3)).

Il terzo problema mi ha dato qualche difficoltà in quanto non ho inizialmente capito perfettamente il problema, tuttavia sono riuscito a risolverlo in un'oretta circa senza problemi eccessivi (questa volta ho optato nella forza del brute).

Il quarto e ultimo problema era quello più impegnativo. L'ho trovato molto interessante, ma non eccessivamente difficile. Più che altro bisognava scrivere molto codice, ecco perché ho deciso di saltarlo visto che qualche ora dopo iniziava la competizione TCO 2012 che non potevo mancare.

PROBLEMI:

Problem A. Speaking in Tongues

For example (and here is a hint!), our awesome translation algorithm includes the following three mappings: 'a' -> 'y', 'o' -> 'e', and 'z' -> 'q'. This means that "a zoo" will become "y qee".

Given some text in Googlerese, can you translate it to back to normal text?

Solving this problem

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has only 1 Small input. Once you have solved the Small input, you have finished solving this problem.

Input

The first line of the input gives the number of test cases, T. T test cases follow, one per line.

Output

For each test case, output one line containing "Case #X: S" where X is the case number and S is the string that becomes G in Googlerese.

Limits

1 ≤ T ≤ 30.
G contains at most 100 characters.
None of the text is guaranteed to be valid English.

Sample

Input

3
ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv

Output

Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up

Problem B. Dancing With the Googlers

You're watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it'ssurprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 apart.

For example: (8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8, 8) are surprising. (7, 6, 9) will never happen.

The total points for a Googler is the sum of the three scores in that Googler's triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler's triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p?

For example, suppose there were 6 Googlers, and they had the following total points: 29, 20, 8, 18, 18, 21. You remember that there were 2 surprising triplets of scores, and you want to know how many Googlers could have gotten a best result of 8 or better.

With those total points, and knowing that two of the triplets were surprising, the triplets of scores could have been:

The cases marked with a (*) are the surprising cases. This gives us 3 Googlers who got at least one score of 8 or better. There's no series of triplets of scores that would give us a higher number than 3, so the answer is 3.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing integers separated by single spaces. The first integer will be N, the number of Googlers, and the second integer will be S, the number of surprising triplets of scores. The third integer will be p, as described above. Next will be N integers t_i: the total points of the Googlers.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum number of Googlers who could have had a best result of greater than or equal to p.

Limits

1 ≤ T ≤ 100.
0 ≤ S ≤ N.
0 ≤ p ≤ 10.
0 ≤ t_i ≤ 30.
At least S of the t_i values will be between 2 and 28, inclusive.

Small dataset

1 ≤ N ≤ 3.

Large dataset

1 ≤ N ≤ 100.

Sample

Input	Output
`4 3 1 5 15 13 11 3 0 8 23 22 21 2 1 1 8 0 6 2 8 29 20 8 18 18 21`	`Case #1: 3 Case #2: 2 Case #3: 1 Case #4: 3`

Problem C. Recycled Numbers

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.

Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing the integers A and B.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of recycled pairs (n, m) with A ≤ n < m ≤ B.

Limits

1 ≤ T ≤ 50.
A and B have the same number of digits.

Small dataset

1 ≤ A ≤ B ≤ 1000.

Large dataset

1 ≤ A ≤ B ≤ 2000000.

Sample

Input	Output
`4 1 9 10 40 100 500 1111 2222`	`Case #1: 0 Case #2: 3 Case #3: 156 Case #4: 287`

Problem D. Hall of Mirrors

You live in a 2-dimensional plane, and one of your favourite places to visit is the Hall of Mirrors. The Hall of Mirrors is a room (a 2-dimensional room, of course) that is laid out in a grid. Every square on the grid contains either a square mirror, empty space, or you. You have width 0 and height 0, and you are located in the exact centre of your grid square.

Despite being very small, you can see your reflection when it is reflected back to you exactly. For example, consider the following layout, where '#' indicates a square mirror that completely fills its square, '.' indicates empty space, and the capital letter 'X'indicates you are in the center of that square:

######
#..X.#
#.#..#
#...##
######

If you look straight up or straight to the right, you will be able to see your reflection.

Unfortunately in the Hall of Mirrors it is very foggy, so you can't see further than D units away. Suppose D=3. If you look up, your reflection will be 1 unit away (0.5 to the mirror, and 0.5 back). If you look right, your reflection will be 3 units away (1.5 to the mirror, and 1.5 back), and you will be able to see it. If you look down, your reflection will be 5 units away and you won't be able to see it.

It's important to understand how light travels in the Hall of Mirrors. Light travels in a straight line until it hits a mirror. If light hits any part of a mirror but its corner, it will be reflected in the normal way: it will bounce off with an angle of reflection equal to the angle of incidence. If, on the other hand, the light would touch the corner of a mirror, the situation is more complicated. The following diagrams explain the cases:

In the following cases, light approaches a corner and is reflected, changing its direction:

In the first two cases, light approached two adjacent mirrors at the point where they met. Light was reflected in the same way as if it had hit the middle of a long mirror. In the third case, light approached the corners of three adjacent mirrors, and returned in exactly the direction it came from.

In the following cases, light approaches the corners of one or more mirrors, but does not bounce, and instead continues in the same direction:

This happens when light reaches distance 0 from the corner of a mirror, but would not have to pass through the mirror in order to continue in the same direction. In this way, a ray of light can pass between two mirrors that are diagonally adjacent to each other -- effectively going through a space of size 0. Good thing it's of size 0 too, so it fits!

In the final case, light approaches the corner of one mirror and is destroyed:

The mirror was in the path of the light, and the ray of light didn't approach the corners of any other mirrors.

Note that light stops when it hits you, but it has to hit the exact centre of your grid square.

How many images of yourself can you see?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing three space-separated integers, H, W and D. Hlines follow, and each contains W characters. The characters constitute a map of the Hall of Mirrors for that test case, as described above.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of reflections of yourself you can see.

Limits

1 ≤ T ≤ 100.
3 ≤ H, W ≤ 30.
1 ≤ D ≤ 50.
All characters in each map will be '#', '.', or 'X'.
Exactly one character in each map will be 'X'.
The first row, the last row, the first column and the last column of each map will be entirely filled with '#' characters.

Small dataset

There will be no more than 2W+2H-4 '#' characters.

Large dataset

The restriction from the Small dataset does not apply.

Sample

Input	Output
`6 3 3 1 ### #X# ### 3 3 2 ### #X# ### 4 3 8 ### #X# #.# ### 7 7 4 ####### #.....# #.....# #..X..# #....## #.....# ####### 5 6 3 ###### #..X.# #.#..# #...## ###### 5 6 10 ###### #..X.# #.#..# #...## ######`	`Case #1: 4 Case #2: 8 Case #3: 68 Case #4: 0 Case #5: 2 Case #6: 28`

In the first case, light travels exactly distance 1 if you look directly up, down, left or right.

In the second case, light travels distance 1.414... if you look up-right, up-left, down-right or down-left. Since light does not travel through you, looking directly up only shows you one image of yourself.

In the fifth case, while the nearby mirror is close enough to reflect light back to you, light that hits the corner of the mirror is destroyed rather than reflected.

Il futuro in una confezione di vetro

2012-03-26T21:39:00.000+02:00

Corning Incorporated è un'azienda Americana produttrice di vetri, ceramiche e altri materiali a fini industriali e scientifici. Qualche giorno fa navigato per internet mi sono imbattuto in dei video realizzati dalla Corning: A Day Made of Glass.

Questi video, che troverete qui sotto, mostrano come l'azienda immagina il nostro futuro. Un futuro sicuramente più tattile tanto è vero che i video parlano da sè, senza bisogno di spiegazioni o altro.

Di seguito potete trovare il secondo video, ma con qualche spiegazione in più (in Inglese):

Personalmente trovo le idee veramente brillanti e intriganti. Con la tecnologia attuale tutto ciò sembra un sogno, ma è anche vero che da almeno 10 anni non assistiamo ad una vera rivoluzione tecnologica.

Voi cosa ne pensate? Come lo immaginate il vostro futuro tecnologico perfetto?

MIPS32 - Gestione della Memoria

2012-03-24T23:38:00.005+01:00

MIPS (Microprocessor without Interlocked Pipeline Stages) è un processore con architettura (ISA - Instruction Set Architecture) di tipo RISC (Reduced Instruction Set Computer). Le prime architetture MIPS erano a 32 bit, mentre quelle più moderne sono 64 bit.

L'architettura a 32 bit rimane tutta via quella più usata a scopo didattico perché ci permette di capire il funzionamento dell'architettura rimanendo in un'ambiente semplice da capire.

Per i più curiosi ritengo che sia giusto riportare che alcuni dispositivi di Windows CE, Cisco, come la anche la Nintendo64, Sony: PlayStation, PlayStation2 e PSP usano processori MIPS.

Nel seguente articolo proporrò una mia soluzione alla gestione della memoria in MIPS32. Chi, invece, desidera leggere di più sull'architettura MIPS e la sua storia può trovare interessante quest'articolo su Wikipedia come alcune delle fonti sotto riportate.

In ogni sistema la quantità di memoria è finita. Per un processore a 32bits sono disponibili 4Gbytes di memoria (virtuale). Il sistema operativo preserva parte di questa memoria per se stesso, il resto è utilizzato da terzi.

La sezione incapsulata fra gli indirizzi 0x0040000 e 0x10000000 (nell'immagine sottostante, nella realtà può variare) è chiamata Text Segment e contiene il linguaggio macchina del programma eseguito (in questo caso quello che andremmo a scrivere noi). Oltre l'indirizzo 0x10000000 troviamo la sezione Data Segment che contiene la porzione di memoria "richiesta" dal programma ad inizio esecuzione. La sezione Stack è utilizzata dallo stack del programma che si espande e comprime in continuazione in fase di esecuzione.

L'area di memoria fra lo Stack e il Data Segment è comunemente chiamato Heap ed è quella memoria non ancora allocata (richiesta dall'utente/programmatore).

Durante l'esecuzione di un programma non è raro che quest'ultimo richieda una porzione di memoria. Tale porzione di memoria viene allocata dinamicamente dall'Heap tramite il sistema operativo. Porzioni di memoria possono anche essere de-allocati quando non più in uso. In MIPS32, tuttavia, quest'ultima operazione non è gestita dal sistema operativo, quindi è compito del programmatore gestire tutte quelle porzioni di memoria non più in uso.

Per poter illustrare facilmente come gestire la memoria in MIPS32 utilizzeremmo una semplice Singly Linked List.

Innanzitutto vediamo come richiedere una porzione di memoria dal sistema operativo usando syscall:

li $v0, 9 # Servizio 9 del sistema.

li $a0, 8 # Spazio richiesto: 8bytes

syscall # Spazio richiesto allocato

move $s1, $v0 # Spostiamo lo spazio allocato nel registro $s1

Tuttavia, una soluzione più efficace è quella di richiedere una porzione di memoria più grande da syscall. L'uso di syscall, infatti, è abbastanza dispendioso e tale soluzione diminuirebbe il suo utilizzo durante l'esecuzione di un programma.

Quindi supponiamo che il nostro nodo della lista sia di 8bytes e usiamo i primi 4bytes per immagazzinare l'informazione voluta (un numero per esempio) e gli altri 4bytes come riferimento al nodo successivo nella lista.

Per prima cosa dobbiamo definire due "etichette" (Labels in Inglese), una per far riferimento alla prima posizione libera ed usabile (quindi allocata) in memoria e un'altra per indicate l'ultima posizione disponibile. Quando l'ultima posizione disponibile è usata bisogna allocare nuova memoria.

prossimoSpazioLibero:

.word 0

ultimoSpazioLibero:

.word 0

Quando gli indirizzi di memoria salvati su prossimoSpazioLibero e ultimoSpazioLibero sono identici, allora allochiamo nuova memoria altrimenti usiamo quella allocata precedentemente.

lw $s1, prossimoSpazioLibero

lw $s2, ultimoSpazioLibero

beq $s1, $s2, memoria_da_allocare # Se le etichette puntano allo stesso luogo in memoria allora bisogna allocare nuova memoria

j memoria_disponibile # Altrimenti si usa la memoria già allocata

memoria_da_allocare:

li $v0, 9

li $a0, 40 # 40 bytes -> 5 Nodi

syscall

move $s1, $v0

sw $s1, prossimoSpazioLibero # Salviamo l'indirizzo della memoria allocata

addi $s2, $s1, 40

sw $s2, ultimoSpazioLibero # Calcoliamo l'indirizzo dell'ultimo spazio disponibile

j memoria_disponibile # Adesso la memoria è usabile e "saltiamo" a memoria_disponibile

Nel seguente metodo assumiamo che i registri $a1 e $a2 contengono rispettivamente il contenuto da salvare nel nodo corrente e il riferimento al nodo successivo.

memoria_disponibile:

sw $a1, 0($s1) # Contenuto del nodo

sw $a2, 4($s1) # Riferimento al prossimo nodo

move $v0, $s1 # Indirizzo in memoria del nodo

addi $s1, $s1, 8

sw $s1, prossimoSpazioLibero # Adesso prossimoSpazioLibero fa riferimento al prossimo nodo

Se il nostro obiettivo è quello di creare una lista, dovendo semplicemente inserire nuovi elementi ad essa, allora non dobbiamo preoccuparci del resto. Se invece vogliamo aggiungere la possibilità di poter eliminare un determinato elemento da una lista, la storia continua.

L'espediente qui proposto non è l'unico disponibile, ma secondo me è quello più semplice ed anche molto efficace.

Ogni qualvolta che un' elemento della lista deve essere rimosso seguiamo il seguente processo logico:

Troviamo il nodo (A) della lista che "punta" al nodo (B) contenente l'elemento da eliminare
Memorizziamo l'indirizzo del nodo (B) da eliminare
Facciamo si che il nodo (A) punti al prossimo valido nodo (C) della lista
Aggiungiamo il nodo (B) eliminato a una lista speciale (LS) contenente tutti i nodi eliminati e che possono essere riutilizzati in futuro

La nostra lista speciale verrà identificata dall'etichetta:

listaNodiRiusabili:

.word 0

Ogni volta che un nodo o una determinata porzione di memoria vuole essere aggiunta alla lista dobbiamo far si che questa nuova porzione di memoria punti al primo nodo della listaNodiRiusabili.

Dopodiché la nuova porzione sarà il nuovo primo nodo della listaNodiRiusabili. Questo approccio è efficace perché eseguito tempo costante O(1).

lw $t0, listNodiRiusabili # Ripristiniamo il primo nodo della lista

sw $t0, 8($a0) # Facciamo si che il nuovo nodo riusabile punto al primo nodo della lista

sw $a0, listaNodiRiusabili # Il nuovo nodo adesso è il primo nodo della lista.

Adesso è giunto il momento di modificare la nostra porzione di codice per richiedere nuova memoria. Se la nostra lista speciale (LS) contiene porzioni di memoria riutilizzabili, allora, bisogna preferire questi ad un ulteriore utilizzo di syscall.

lw $t0, listaNodiRiusabili # Ripristina il primo nodo della lista

bne $t0, $zero, riusa_nodo # Se la lista contiene almeno un nodo allora usiamolo!

#La porzione di codice sottostante è identica a quella precedente e così le relative procedure

lw $s1, prossimoSpazioLibero

lw $s2, ultimoSpazioLibero

beq $s1, $s2, memoria_da_allocare # Se le etichette puntano allo stesso luogo in memoria allora bisogna allocare nuova memoria

j memoria_disponibile # Altrimenti si usa la memoria già allocata

riusa_nodo:

lw $s1, listaNodiRiusabili

lw $t0, 8($s1) # Otteniamo l'indirizzo del secondo nodo riusabile (questo è 0 se non c'è un secondo nodo)

sw $t0, listaNodiRiusabili # Fa si che il secondo nodo diventi il primo nodo della lista.

sw $a1, 0($s1) # Contenuto del nodo

sw $a2, 4($s1) # Riferimento al prossimo nodo

move $v0, $s1 # Indirizzo in memoria del nodo

Fonti:

MIPS: http://it.wikipedia.org/wiki/Architettura_MIPS

SPIM MIPS Simulator: http://spimsimulator.sourceforge.net/

MARS MIPS Simulator: http://courses.missouristate.edu/KenVollmar/MARS/

MIPS Tutorial (en): http://www.cse.hcmut.edu.vn/~vtphuong/KTMT/Links/TutorialContents.html

Lista servizi di sistema (en): http://courses.missouristate.edu/KenVollmar/MARS/Help/SyscallHelp.html

ComputerSystems (en): http://wiki.cse.unsw.edu.au/cs1917cgi/10s1/ComputerSystems/Notes

C - Controllare che un numero inserito sia corretto

2012-02-29T18:00:00.000+01:00

Una delle regole fondamentali della programmazione è quella di creare un software robusto: un software che sappia come reagire ad ogni evenienza e non vada in tilt ogni volta che avviene un'operazione non prestabilita.

Per chi ha un pò di esperienza in Java o in Python, sicuramente, sa che un blocco try and catch o semplicemente un throw exception (solo Java) risolverebbe la questione.

Tuttavia in un linguaggio più a basso livello come C creare un software robusto richiede uno sforzo maggiore. Nel seguente articolo verrà spiegato come controllare che un numero intero, inserito da tastiera dall'utente, sia corretto o meno.

In C un numero intero di tipo int è definito fra -2147483648 (INT_MIN) e 2147483647 (INT_MAX). Quindi qualsiasi numero inserito da tastiera che sia minore di INT_MIN o maggiore di INT_MAX non è da considerarsi valido.

Affinché il software sia robusto, è necessario riuscire a individuare altri tipi di errori come:

L'input non è un numero ma un carattere o una sequenza di caratteri
L'input è costituito da numeri e caratteri
L'input è costituito da un solo numero

Innanzitutto bisogna ricevere un input da tastiera. La soluzione più ovvia sarebbe quella di utilizzare scanf().

numeroElementi = Scanf("%d", &numero);

Scanf(), infatti, restituirebbe un numberoElementi diverso da 1 nel caso l'input non sia valido.

Tuttavia, utilizzando scanf(), non è possibile controllare che il numero inserito sia nel range dei numeri perché scanf() converte qualsiasi input contenente delle cifre in un numero.
Quindi se viene inserito un numero troppo grande come 100000000000, scanf() restituirà un altro numero, per esempio -2452145, che rientra nel range dei numeri interi. Ciò non ci permette di controllare che il nostro numero sia valido.

La soluzione è utilizzare fgets(), che ci permette di leggere alcun tipo di stringa (indipendentemente dalla sua lunghezza). Qualora l'input contenga più caratteri di quelli permessi, quelli in eccesso vanno a finire nel buffer che può sempre essere ripulito tramite un'operazione di flush.

Utilizzando fgets(), quindi, non leggiamo l'input direttamente come un numero, ma come una stringa. La stringa deve essere allora convertita in un numero e ciò avviene tramite la funzione: strtol().

Nel nostro caso strtol() accetta i seguenti parametri:

stringa - La stringa da convertire in numero.
&endptr - Un pointer dove viene "immagazzinato" tutto ciò che è superfluo
10 - la base numerica. In questo caso il numero sarà in base 10.

Il numero ritornato da strtol() è di tipo long. Inoltre, strtol() setta la variabile errno (importata da errno.h) a un valore diverso da 0 se alcun tipo di errore è stato individuato.

Test no. 1-> Affinché l'input possa considerarsi valido:

Nessun errore di tipo generico deve essere stato individuato
L'input deve contenere esclusivamente cifre

Test no. 2 -> L'input per poter essere considerato un numero intero valido deve essere maggiore o uguale a INT_MIN e minore o uguale a INT_MAX. E' importante notare che non sempre il range long è uguale a quello di int, quindi bisogna eseguire un operazione di cast da long a int.

Ecco il codice intero per validare un numero intero da tastiera:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h> 
#include <errno.h>

int validaNumeroIntero() {
 
 // La lunghezza massima è 13
 // INT_MIN = '-' + 11 cifre + '\0'
 // '\0' indica la fine di una stringa.
 int lunghezza = 13; 
 char stringa[lunghezza];
 long risultato;
 int temporaryBuffer;
 
 do{
  int i;
  char *endptr;
  
  printf("Inserire un numero intero: \n");
  fgets(stringa, lunghezza, stdin);
  // L'ultimo carattere in stringa deve essere
  // sostituito con '\0' per indicarne la fine.
  i = strlen(stringa)-1;
  if( stringa[i] == '\n') 
   stringa[i] = '\0';
  else {
   // Flush del buffer
   // La funzione flush() non può essere utilizzata in questo caso
   while (((temporaryBuffer = getchar()) != '\n')
       && (temporaryBuffer != EOF));
  }

// Convertire stringa in un numero di tipo long
  // in base 10 
  // Maggior informazioni su strtol() al sito:
  // http://linux.die.net/man/3/strtol
                // errno è una variabile di tipo int importata dalla libreria
                // errno.h. Qui viene settata a 0 per default per indicare che 
                // nessun errore è stato trovato.
  risultato = strtol(stringa, &endptr, 10);
  errno = 0;
  
  // Controlla che l'input sia valido:
  // 1. nessun errore generico sia stato individuato
  // 2. non siano stati trovati dei caratteri oltre che a dei numeri
  if ( errno
       || endptr == stringa 
       || *endptr != '\0') {
   errno = 1;
   printf("Errore 1\n");
  } 
   
  // Controlla che l'input sia tra INT_MIN e INT_MAX
  // INT_MAX = 2147483647
  // INT_MIN = -2147483648
  if ((risultato < (long)INT_MIN) || (risultato > (long) INT_MAX)) {
   errno = 1;
   printf("Errore 2\n");
  }
  
 } while (errno); // Uscire dal loop solo quando nessun errore sia stato individuato.
 
 return (int)risultato;
}

Java - Giochi da tavolo, Bit-Boards e Bit-Masks

2012-02-01T16:25:00.000+01:00

Quasi ad ogni programmatore, più o meno esperto che sia, è capitato almeno una volta nella propria carriera di creare un programma per gioco da tavolo.

Il gioco da tavolo è un gioco che richiede una superficie di gioco prestabilita at priori sulla quale vengono disposti i pezzi dei giocatori. Molte volte il tavolo da gioco può essere rappresentato geometricamente in modo molto semplice e intuitivo (vedi la scacchiera degli scacchi, dama o reversi). Altre volte, invece, ciò può apparire più complicato, come nel gioco di Risiko. Tuttavia, anche in queste situazioni la "mappa" può essere ridotta a un modello più semplice di grafo e come ben sappiamo un grafo può facilmente essere rappresentato da una matrice 2x2.

Se stiamo programmando in Java, o in qualsiasi altro linguaggio ad oggetti, rappresentare la stato del tavolo di gioco risulta abbastanza diretto. Basta, infatti, creare un array 2x2 di oggetti e inserire i pezzi dei giocatori nelle apposite posizioni.

Molte altre volte non è possibile rappresentare il tavolo da gioco usando degli oggetti oppure persiste la necessità di aumentare la velocità di calcolo quando si eseguono determinate operazioni sui pezzi della superficie. In questi casi useremmo le Bit Boards!

Per Bit Board si indica un tavolo da gioco rappresentato come una sequenza di bits. Quindi di 0 e 1. Per chi non fosse famigliare con il sistema binario consiglio il seguente articolo. In Java esiste la classe BitSet che potrebbe essere utilizzata per rappresentare le sequenze di bits. Tuttavia le operazioni Booleane e di shifting risultano alquanti tediose. Una soluzione più semplice ed efficace, quindi, è quella di rappresentare le sequenza di bit in formato decimale. Per un tavolo da gioco 4x4 useremmo short (dato che è 16 bits) e long per un tavolo 8x8 (dato che è 64 bits). Questi tipi primitivi, oltre a favorire le operazioni prima elencate, favoriscono una velocità di calcolo maggiore rispetto all'uso di oggetti (che occupano più spazio in memoria). Ciò si rileva fondamentale se stiamo programmando un sistema d'intelligenza artificiale e nell'uso dell'algoritmo di MiniMax si producono centinaia di migliaia di casi e relative tavole da gioco virtuali.

Di seguito riporto un esempio grafico molto semplice per illustrare un utilizzo di Bit Board.

Tramite operazioni di shifting, inoltre, è possibile calcolare le mosse disponibili per ogni giocatore. In Java le operazioni di shifting avvengono tramite gli operatori '<<' (shift a sinistra) e '>>' (shift a destra). Tuttavia questo va oltre l'obbiettivo del seguente articolo perché ogni gioco da tavolo possiede regole diverse e quindi le operazioni di shifting avverranno di conseguenza.

Un altro elemento importante sono le Bit Masks. Le Bit Masks sono un sottotipo di Bit Boards utilizzate per rimuovere certe parti del tavolo da gioco. Le Masks in generale trovano anche altri utilizzi, come nell'ambito della grafica.

Ecco un esempio che illustra come creare una Bit Mask per rimuovere la prima riga e la prima colonna di un tavolo da gioco.

 
int[][] mask = { { 1, 1, 1 },
                          { 1, 0, 0 },
                          { 1, 0, 0 } };

short bitMask = 0; 
short power2 = 1;

for ( int i = mask.length - 1; i >= 0; i-- ) {
      for ( int j = mask[0].length - 1; j >= 0; j-- ) {
            bitMask += power2 * mask[i][j];
            power2 *= 2;
            }
      }

Capire e usare Bit Boards e Bit Masks può non essere facile e immediato, ma come per ogni cosa nella programmazione bisogna: provare e sbagliare finché non ci si riesce.

Per ulteriori informazioni e approfondimenti consiglio vivamente di visitare i link citati tra le fonti.

Fonti:

http://chessprogramming.wikispaces.com/Bitboards
http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

Haskell - Grafica 2D con Gloss

2012-01-25T10:11:00.000+01:00

La libreria Gloss, in Haskell, ci permette di creare delle semplici interfacce grafiche 2D. Gloss è particolarmente conosciuta per la sua semplicità e facilità d'uso.

In questo articolo spiegherò le basi per poter utilizzare la libreria Gloss.

Il primo passo è importare la libreria nel proprio documento .hs :

import Graphics.Gloss

A questo punto viene richiamata la funzione display della libreria, come nell'esempio qui sotto:

main
= display
(InWindow
"Hello World" -- titolo della finestra
(400, 150) -- dimensione della finestra
(10, 10)) -- posizione della finestra
white -- colore sfondo
picture -- immagine da visualizzare.

La palette dei colori usata da Gloss è la seguente:
Black, White, Red, Green, Blue, Yellow, Cyan, Magenta, Rose, Violet, Azure, Aquamarine, Chartreuse, Orange. Per ulteriori informazioni sui colori in Gloss e il loro utilizzo raccomando la seguente pagina.

Con picture si può intendere una singola immagine, come una collezione di immagini da visualizzare.
Nel seguente esempio Picture è:

picture
= Translate (-170) (-20) -- sposta l'immagine al centro della finestra
$ Scale 0.5 0.5 -- visualizza l'immagine al 50% della dimensione originaria
$ Text "Hello World" -- testa da visualizzare

Alcuni degli esempi ufficiali della libreria possono essere trovati qui.

Nell'esempio Clock possiamo notare come Picture rappresenti un insieme di "Pictures":

Pictures
  [ Line [(0, 0), ( 0,  a)]
  , Line [(0, 0), ( 1, -b)]
  , Line [(0, 0), (-1, -b)] ]

Dove a e b rappresentano delle variabili che definiscono le coordinate dell'oggetto Line. La libreria Gloss da la possibilità di usare anche delle forme più complesse oltre che alla semplice linea. Qui è possibile trovare la pagina ufficiale di Gloss con tutte le forme e i rispettivi parametri, come rectangleSolid e Circle.

Inoltre è possibile impostare colore e coordinate di ogni singolo oggetto come nell'esempio seguente:

Pictures [(Color red  (translate x y
                                      (rectangleSolid width height)))
             ]

In questo esempio viene creato un rettangolo di colore rosso (red) in posizione (x, y) dall'origine rispetto all'asse cartesiano e con larghezza width e larghezza height.

Altre volte, invece, il numero di oggetti da visualizzare non è conosciuto. In questo caso la soluzione risiede nella tecnica più usata in Haskell: la ricorsione.

listaImmagini :: Int -> Picture

listaImmagini 0 = Pictures [Blank]

listaImmagini n = Pictures [(Color

red

(translate x y

(rectangleSolid width height)))

, listaImmagini (n - 1)]

Come gli operatori ':' e '++' vengono comunemente usati per appendere un qualcosa ad una lista, in Picture l'operatore di "aggiunta" è ',' e la funzione listaImmagini viene chiamata ricorsivamente finché non si raggiunge il caso base zero e l'ultima immagine ad essere aggiunta è quella nulla: Blank.

Ecco un esempio tratto dal gioco Core War (versione scritta dal sottoscritto).

Fonti:

http://gloss.ouroborus.net/
http://hackage.haskell.org/packages/archive/gloss/1.0.0.1/doc/html/Graphics-Gloss.html

KisMAC - Scovare e crackare reti Wireless (WEP e WAP)

2012-01-10T17:51:00.001+01:00

KisMAC è un OpenSource software per Mac in grado di scovare reti wireless e crackarle.

Prima di iniziare a parlarvi di questo fantastico strumento premetto che KisMAC non dovrebbe essere utilizzato per scopi illeciti. KisMAC è per chi ha intenzione di imparare qualcosa di nuovo.

Prima di iniziare a vedere come usare KisMAC bisogna scaricare l'applicazione dal sito ufficiale: KisMAC.

Cosa fa KisMAC

Rileva SSIDs (nome con cui una rete WiFi si identifica ai suoi utenti) nascoste, mascherate e/o chiuse.
Mostra gli utenti connessi (con indirizzo MAC, IP e potenza di segnale)
PCAP: API per registrare il traffico di rete
Supporta gli standard 802.11b/g
Supporta diversi attacchi alla rete (WPA, WEP, etc)

In poche parole KisMAC ci permette di "sniffare" una rete.

Innanzitutto bisogna definire le due modalità supportate dalla schede di rete: Active Mode e Passive Mode.

Active Mode:

Invia sonde per esplorare la rete (probes)
Poco utilizzato perché raccoglie anche dati che non sono utili

Passive Mode (Monitor Mode):

Permette di vedere qualsiasi cosa entro un certo raggio
Permette injection-attacks
Permette de-authentication attacks

Configurare KisMAC

Dopo aver installato KisMAC recarsi nel pannello di preference (KisMAC/ Preferences) e nello specchietto dei Drivers selezionare il driver da utilizzare per la scansione della rete.

Selezionando il driver avrete una schermata simile a quella mostrata qui in basso. Nell'area Dump Filter ho selezionato No Dumping perché personalmente non sono interessato nel conservare i dati raccolti per poi analizzarli con altri strumenti.

Ecco, comunque, a cosa servono le altre tre opzioni:

Keep everything - Il traffico raccolto è memorizzato in un file di log
Data only - Solo i pacchetti con del contenuto sono memorizzati nel file di log
Weak frames only - Solo pacchetti con vettori d'inizializzazione debole sono memorizzati nel file di log

Osservare il traffico

WEP

Injection: cos'è e quando usarlo.

Per Injection ci si riferisce ad una particolare tecnica per ottenere più pacchetti possibili da una rete. Se la propria scheda di rete supporta Injection allora uno speciale pacchetto (che sarà come dire "Ciao" al telefono) verrà inviato ad un computer e questo molto probabilmente invierà indietro una risposta. Se quest'operazione è eseguita centinaia di volte, allora noi riceveremmo altrettanti pacchetti risposta e sarà più facile crackare la chiave di cifratura. Per iniziare la fase di Injection selezionare dal menù: Network / Reinject Packets.

Injection è una tecnica usata solamente per crackare una rete protetta da cifratura WEP. Per riuscire a trovare la chiave di cifratura bisogna raccogliere almeno 200,000 pacchetti ed ecco perché usiamo Injection. E' comunque consigliabile comprare una scheda di rete apposita, invece della scheda Airport Extreme che esce con il vostro Mac.

Dopo aver collezionato abbastanza pacchetti selezionare: Network / Crack / Weck Scheduling Attacks / Against 40-bit. Se questo tipo di attacco non funziona, allora provate gli altri. Se nessuno degli attacchi funziona allora è consigliabile raccogliere più pacchetti o visitare il sito ufficiale per maggiori informazioni.

WPA

Scovare una chiave WPA, per KisMAC, può essere semplice o impossibile. Il problema risiede nel fatto che per crackare una rete protetta da WPA, KisMAC deve riuscire a "catturare" un handshake. Per ottenere un handshake bisogna utilizzare un de-authenticate attack: Network / Deauthenticate

Inoltre, una ragione per cui KisMAC non potrebbe mai trovare la chiave è che l'handshake è basato su una lista di parole: wordlist poco adatta. Esistono tuttavia altre modi per crackare una rete protetta da WPA che non funzionano con KisMAC e che discuterò in futuro.

Ok, passiamo avanti e vediamo come scovare la chiave WPA se si è ricevuto l'handshake. Se si è ricevuto l'handshake l'icona sull'ultima colonna a destra nella figura in basso sarà verde, altrimenti rossa.

Se l'icona è verde allora si può partire con l'attacco: Network / Crack / Wordlist Attack / Against WPA Key (scegliere quindi un file contenente la lista di parole. E' possibile trovarne qui).

Note:

Purtroppo l'Injection non funziona con Airport Extreme sotto MAC OS X Leopard.

Il sito ufficiale consiglia, comunque, di aquistare un supporto USB esterno con chip: Prism2, RT73, RT2570, o RTL8187.

Fonti:

Sito ufficiale: http://kismac-ng.org/

Wiki: http://trac.kismac-ng.org/

Guida: http://stagingkiller.wordpress.com/2009/06/26/the-definitive-kismac-article/

Forum: http://forum.kismac-ng.org/

Bubble Sort vs Merge Sort

2012-01-09T23:30:00.000+01:00

In questo articolo parlerò di un analisi degli algoritmi Bubble Sort e Merge Sort che ho fatto in uno dei miei progetti universitari.

I due algoritmi appena citati vengono utilizzati per ordinare un insieme di elementi (numeri, lettere, e qualsiasi oggetto che può essere confrontato con un suo simile sulla base maggiore di, minore di, uguale a).

Di seguito riporto entrambi gli algoritmi con descrizione:

Grafica
Letterale
usando Pseudo-codice o codice

Bubble Sort

Pseudo-codice

- Traversare un array (o lista) scambiando i numeri adiacenti che non sono in ordine. L'ordinamento finisce quando non è più necessario scambiare numeri adiacenti.

while scambio

scambio = Falso (False)

for j = 0 to j < (Array.length - i - 1) <-- Bolla

if Array[j] > Array[j + 1]

scambia Array[j] con Array[j + 1]

scambio = Vero (True)

Merge Sort

Pseudo-codice

Se l'array (o la lista) ha lunghezza 0 o 1 allora è ordinata. Altrimenti:
Dividere l'array disordinato in due sub-array la cui lunghezza è la metà dell'array iniziale
Ordina ogni sub-array ricorsivamente usando Merge Sort
Merge (unire) i due sub-array in un unico ordinato array.

In questo caso ritengo più opportuno riportare il codice in Java, invece, che in pseudo-codice perché ritengo che il funzionamento dell'algoritmo Merge Sort possa essere compreso più facilmente in questo modo.

public int[] mergeSort (int[] array) {

if (array.length <= 1) return array;

int metaDimensione = array.length / 2;

int[] primoArray = new int[metaDimensione];

int[] secondoArray = new int[array.length - metaDimensione];

// Crea il primoArray

for(int i = 0; i < metaDimensione; i ++) {

primoArray[i] = array[i];

}

// Crea il secondoArray

for(int i = metaDimensione; i < array.length; i ++) {

secondoArray[i - metaDimensione] = array[i];

}

primoArray = mergeSort(primoArray);

secondoArray = mergeSort(secondoArray);

int[] arrayOrdinato = merge(primoArray, secondoArray);

return arrayOrdinato;

}

private int[] merge(int[] primoArray, int[] secondoArray) {

int[] arrayFinale = new int[primoArray.length + secondoArray.length];

int indicePrimoArray = 0;

int indiceSecondoArray = 0;

int indiceArrayFinale = 0;

while ((indicePrimoArray < primoArray.length) && (indiceSecondoArray < secondoArray.length)) {

if (primoArray[indicePrimoArray] <= secondoArray[indiceSecondoArray]) {

arrayFinale[indiceArrayFinale] = primoArray[indicePrimoArray];

indicePrimoArray ++;

} else {

arrayFinale[indiceArrayFinale] = secondoArray[indiceSecondoArray];

indiceSecondoArray ++;

}

indiceArrayFinale ++;

}

// Append all the rest of the left Array

while (indicePrimoArray < primoArray.length) {

arrayFinale[indexResult] = primoArray[indicePrimoArray];

indicePrimoArray ++;

indiceArrayFinale ++;

}

// Append all the rest of the right Array.

while (indiceSecondoArray < secondoArray.length) {

arrayFinale[indexResult] = secondoArray[indiceSecondoArray];

indiceSecondoArray ++;

indiceArrayFinale ++;

}

return arrayFinale;

}

Algoritmi a confronto

Prima di iniziare a fare un confronto fra i due algoritmi ritengo opportuno dare un'occhiata agli algoritmi singolarmente.

Bubble Sort

Osservando lo pseudo-codice (vedi sopra) possiamo subito notare che la prima volta che l'array in questione è "traversato" l'elemento con il valore più alto è spostato all'estrema destra dell'array (ordinamento ascendente). Quindi, supponendo che l'array è di dimensione n, l'algoritmo traversa (n - 1) elementi la volta successiva. All'iterazione jth, l'algoritmo di Bubble sort traversa (n - j) elementi, dove j è un intero compreso fra 0 e (n - 1).

Possiamo quindi dire che la complessità è O(n^2). Nel miglior caso è O(n) dato che la lista è subito riconosciuta come ordinata e non c'è alcun bisogno di traversala altre volte.

Eseguendo l'algoritmo migliaia di volte su lista diverse di dimensioni diverse ho collezionato una certa quantità di dati che ho poi espresso graficamente:

Utilizzando Excel ho potuto confrontare i dati con la linea di miglior approssimazione, verificando la credibilità dei dati raccolti. Inoltre, sempre usando Excel, ho calcolato l'equazione della curva ottenuta e ho potuto notare che il grado è 2, come ci si aspettava da un algoritmo di complessità O(n^2).

Merge Sort

La complessità dell'algoritmo di Merge Sort avviene in due fasi:

La lista viene divisa in due parti ricorsivamente -> O(log n)
Due liste vengono unite in una -> O (n)

Quindi la complessità è O(n (log n)).

Il grafico sottostante è il risultato ottenuto dopo aver ordinato migliaia di liste usando Merge Sort.

Faccio notare che, a differenza del algoritmo Bubble Sort, la curva ottenuta è lineare e di grado 1 ad una prima analisi. Tuttavia, dopo una più attenta analisi con Excel ho potuto constatare che l'equazione della linea di migliore approssimazione (linea rossa) è:

f(n) = 55 * n * log (n) + 50000, che è di ordine n * log(n) come previsto.

Tuttavia, per capire meglio quale dei due algoritmi è migliore bisogna sovrapporre i due grafici, che parlano da sè:

Analisi Avanzata degli Algoritmi

Nel mio esperimento universitario ho ben deciso di analizzare anche altri aspetti degli algoritmi per capire quando un algoritmo "consuma" di più.

Bubble Sort

Il seguente grafico mostra il tempo impiegato ad ogni bolla (un iterazione dell'array). Il grafico mostra come il tempo speso su ogni bolla diminuisce come l'array diventa più ordinata. Tuttavia all'inizio il tempo impiegato su ogni bolla incrementa probabilmente. Questo purtroppo è un fatto che non sono riuscito a capire del tutto.

I dati possono essere meglio analizzati osservando il grafico cumulativo di quello appena mostrato:

Osserviamo come la pendenza della curva, man mano che l'array diventa più ordinato, diminuisce. Questo è un segno che l'algoritmo diventa più veloce sulle ultime bolle rispetto all'inizio, quando la lista è completamente disordinata.

Merge Sort

Il grafico sottostante mostra i dati che ho collezionato per il tempo speso ogni volta che la funzione Merge è stata utilizzata. Ho deciso di analizzare solo la funzione di Merge perché è la parte dell'algoritmo dove viene speso più tempo.

Quando ho analizzato l'algoritmo, l'albero che ne nasce dall'algoritmo è stato traversato post-order.

Il puntino blu in alto a destra mostra il tempo impiegato per unire (Merge) le due liste ottenute dalla lista originale e che sono già ordinate (i due puntini blu sottostanti, time: 25000 circa sull'asse delle y).

Da notare che i puntini alla stessa altezza nell'asse del tempo (asse delle y) sono sempre potenze di due. L'agglomerato di puntini blu rappresenta tutte quelle liste di dimensione molto piccola per cui la fase di Merge avviene molto rapidamente.

Note:
I dati sono stati raccolti usando un MacBookPro (CPU: Intel Core 2 Duo 2,4 GHz, RAM: 4GB)
I dati sono stati analizzati usando Microsoftft® Excel® per Mac 2011.

Fonti:
Immagini: wikipedia.org

Internet - Un pò di storia

2012-01-05T21:00:00.000+01:00

Internet, personalmente, è l'invenzione più geniale di sempre perché ha permesso all'uomo di immagazzinare tutta la propria conoscenza al servizio di tutti. Inoltre, Internet ha eliminato distanze e tempi rendendo il concetto di globalizzazione realizzabile. Ma cos'è Internet? E com'è nato?

Definizione di Internet

Internet è un sistema globale di reti di calcolatori interconnessi fra di loro tramite la suite di protocolli TCP/IP. Il TCP e l'IP costituiscono il "linguaggio comune" utilizzato fra i computer connessi a Internet (host). L'Internet contiene una quantità inimmaginabile di informazioni e servizi: come i documenti del World Wide Web (pagine web) o le infrastrutture che supportano i servizi di email.

Un pò di storia

Il concetto di "interazioni sociali" attraverso una rete risale al Agosto 1962 da parte di J. C. R. Licklider e prendeva il nome di "Rete Galattica". L'idea si basava su un insieme di computer interconnessi globalmente a cui ognuno poteva avere accesso. Licklider era a capo della DARPA. Nel 1966 Lawrence G. Roberts, un ricercatore del MIT, propose all'agenzia DARPA il concetto proposto anni prima da Licklider su una rete di computer. Ebbe inizio il progetto: ARPANET, pubblicato nel 1967. Il progetto ARPANET nasceva come una rete di computer a scopo militare in grado di resistere agli attacchi nemici (l'epoca in questione è quella della guerra fredda). Se un host sarebbe stato distrutto dal nemico la rete ARPANET, infatti, garantiva l'operabilità fra il resto degli host.

Nel 1969, il progetto entrò nella sua fase sperimentale e l'Università della California, Los Angeles (UCLA) divenne il primo host di ARPANET. Entrò la fine dello stesso anno altre tre università di attaccarono alla rete: Standford, Santa Barbara e Utah.

Negli anni successivi molti altri host si attaccarono alla rete e tra il 1971 e il 1972 gli utenti della rete poterono iniziare a sviluppare le loro prime applicazioni da usare oltre la rete.

Nel 1982 fu coniata la parola Internet e TCP/IP per il corrispettivo protocollo. Inoltre, presero strada le seguenti quattro idee:

Ogni rete deve essere indipendente e deve essere in grado di collegarsi alla rete globale: Internet
Le comunicazioni devono cercare di essere efficienti e affidabili: un pacchetto dati viene ritrasmesso se non è stato ricevuto da un destinatario entro un certo lasso di tempo
L'uso di ponti nella comunicazione che si basino sull'idea della scatola nera, dove il contenuto delle informazioni è sconosciuto
Nessun controllo globale al livello operazionale

Già nel 1985, Internet era una struttura stabile e usata a livello internazionale da ricercatori e programmatori e iniziava ad essere usata per comunicare tramite e-mail.

Tuttavia, fu solo tra il 1989 e il 1990 che Internet conobbè il suo boom. Tim Berners-Lee, un ricercatore del Conseil Européenne pour la Recherche Nucleaire (CERN), a Ginevra (Svizzera), sviluppò il concetto di HyperText e World Wide Web. Da allora il numero di utenti crebbe vertiginosamente fino all'Internet che conosciamo oggi: in moltissimi dispositivi elettronici di uso comune e con tantissime applicazioni: motori di ricerca, social networks, blogs, etc...

Mappa di Internet (2005)

fonte: http://www.caida.org/research/topology/as_core_network/pics/ascoreApr2005.png

Date principali della storia di Internet (da it.wikipedia.org)

1960: Avvio delle ricerche di ARPA, progetto del Ministero della Difesa degli Stati Uniti
1967: Prima conferenza internazionale sulla rete ARPANET
1969: Collegamento dei primi computer tra 4 università americane
1971: La rete ARPANET connette tra loro 23 computer
1972: Nascita dell'InterNetworking Working Group, organismo incaricato della gestione di Internet. Ray Tomlinson propone l'utilizzo del segno @ per separare il nome utente da quello della macchina.
1973: La Gran Bretagna e la Norvegia si uniscono alla rete con un computer ciascuna.
1979: Creazione dei primi Newsgroup (forum di discussione) da parte di studenti americani
1981: Nasce in Francia la rete Minitel. In breve tempo diventa la più grande rete di computer al di fuori degli USA
1982: Definizione del protocollo TCP/IP e della parola "Internet"
1983: Appaiono i primi server dei nomi dei siti
1984: La rete conta ormai mille computer collegati
1985: Sono assegnati i domini nazionali: .it per l'Italia, .de per la Germania, .fr per la Francia, ecc.
1986: Viene lanciato LISTSERV, il primo software per la gestione di una mailing list. In aprile, da Pisa, sede del Centro Nazionale Universitario di Calcolo Elettronico (Cnuce) viene realizzata la prima connessione Internet dall'Italia con gli Stati Uniti.
1987: Sono connessi 10 000 computer. Il 23 dicembre viene registrato “cnr.it”, il primo dominio con la denominazione geografica dell'Italia; è il sito del Consiglio Nazionale delle Ricerche.
1989: Sono connessi 100mila computer
1990: Scomparsa di ARPANET; apparizione del linguaggio HTML
1991: Il CERN (Centro Europeo di Ricerca Nucleare) annuncia la nascita del World Wide Web
1992: Un milione di computer sono connessi alla rete
1993: Apparizione del primo browser pensato per il web, Mosaic
1996: Sono connessi 10 milioni di computer
1999: Gli utenti di Internet sono 200 milioni in tutto il mondo
2008: Gli utenti di Internet sono circa 600 milioni in tutto il mondo
2009: Gli utenti di Internet sono circa 1 miliardo in tutto il mondo
2011: Gli utenti di Internet sono circa 2 miliardi in tutto il mondo

Video

Breve storia di Internet, con Stefano Quintarelli

La storia di Internet [English]

Fonti e ulteriori informazioni:

http://www.internetsociety.org/internet/internet-51/history-internet/brief-history-internet
http://it.wikipedia.org/wiki/Storia_di_Internet
http://www.pinzani.it/storia-internet.php
http://youtube.com
http://gandalf.it/dati/dati1.htm

Python - Richieste GET e POST su HTTP

2012-01-03T00:00:00.000+01:00

L'HTTP (HyperText Transfer Protocol) è il protocollo principale al Livello Applicazioni (i livelli sono quattro: Applicazioni, Trasporto, Internetworking, Collegamento) usato per la trasmissione di informazioni sul web. Generalmente, un Server HTTP utilizza il protocollo TCP (Transmission Control Protocol) sulla porta 80.

L'HTTP si basa su un meccanismo: richiesta/risposta (client/server). Il client esegue una richiesta e il server restituisce la risposta. E' importante tenere in mente che una applicazione può agire sia da client che da server.

Se la nostra applicazione sta effettuando, per esempio, il login ad un sito allora è buon uso utilizzare un cookie per salvare le impostazioni di login.

I metodi HTTP (versione 1.1) sono i seguenti, ma noi analizzeremmo solo i primi due:

GET
POST
HEAD
PUT
DELETE
TRACE
OPTIONS
CONNECT

In Python è possibile utilizzare il codice qui sotto per effettuare delle richieste HTTP.

Codice in Python

"""Questa classe effettua delle richieste HTTP"""
import urllib
import urllib2
import cookielib

#Inizializza il cookie
cookie = None

# Effettua una richiesta HTTP dati i seguenti:
# 1: metodo: GET o POST
# 2: sito, per esempio: www.blogger.com
# 3: url_api, per esempio: api/comment
# 4: **parametri: argomenti aggiuntivi per la richiesta
# per esempio: modhash, title, id, etc..

def effettua_una_richiesta_HTTP (metodo, sito, url_api, ** parametri):

# cookie diventa globale così da essere usato all'interno di questo metodo
global cookie

# Se il cookie non è presente allora crearlo.
if cookie == None:
# Crea il cookie per salvare cookie HTTP.
cookie = cookielib.CookieJar()

# Gestisce i cookie.
http_cookie = urllib2.HTTPCookieProcessor(cookie)
opener = urllib2.build_opener(http_cookie)

# Apre l'url così che urlopen usa l'opener.
urllib2.install_opener(opener)

# Se dei parametri sono stati passati alla funzione
# allora convertirli in formato url
if parametri != None:
postdata = urllib.urlencode(parametri)

#Se il metodo è GET allora creare un link appropriato per la richiesta HTTP.
if metodo == "GET":
  url_api += "?"
# Aggiunge i parametri al link.
for key in parameters:
  url_api = (url_api +
key + "=" +
parametri[key] + "&")

  parametri = None

# Effettua la richiesta.
richiesta = urllib2.Request(sito + url_api, parametri)
risposta = urllib2.urlopen(richiesta)

# Estrae i cookie e li muove nella variabile cookie.
cookie.extract_cookies(risposta, richiesta)

# La risposta dal sito viene restituita dalla funzione.
return risposta

Tale funzione può essere usata come di seguito:

GET

risposta = effettua_una_richiesta_HTTP("GET",

url_sito,

url_home_page)

POST

risposta = effettua_una_richiesta_HTTP("POST",

url_sito,

url_login,

user = username,

passwd = password,

api_type = "json")

Nota: consultare sempre l'API di un sito per accertarsi che la richiesta viene effettuata correttamente.

La risposta ottenuta contiene tre parti:

Riga di stato
Header
Body

La riga di stato consiste in un codice di tre cifre:

1xx : Messaggi informativi
2xx : La richiesta è stata effettuata con successo
3xx : Non c'è risposta immediata, ma la richiesta è sensata
4xx : La richiesta non può essere effettuata perché errata
5xx : La richiesta non può essere effettuata per un errore nel server.

Per un elenco più dettagliato cliccare qui.

Gli header più comuni sono due:

Server: indica tipo e versione del server
Content-Type: indica il tipo di contenuto resistuito. Alcuni fra questi:

text/html
text/plain
text/xml
image/jpeg

Il body contiene il contenuto della risposta.

Fonti

https://github.com/gehsekky/reddit-scripts/blob/master/reddit_friend_sync.py
http://it.wikipedia.org

Virus - Trojan.Win32.FakeGdF.

2011-12-31T11:30:00.000+01:00

Qualche giorno fa mi sono imbattuto in un computer infettato da un virus che blocca il computer e visualizza una pagine della Guardia di Finanza con il seguente indirizzo URL: http://78.47.58.6 .
Analizziamo un pò questo virus e scopriamo come eliminarlo.

Descrizione

Il Trojan.Win32.FakeGdF.<A-R> (Versioni attualmente identificate dalla A alla R) è un malware che blocca completamente il computer collegandosi ad un sito in Russia. Il sito in questione si spaccia per quello della Guardia di Finanza e appare come il seguente:

Il sito appare a tutto schermo non permettendo all'utente alcuna interazione con il sistema operativo. La barra di navigazione del browser scompare e l'unica operazione disponibile è inserire i codici pin di Ukash o Paysafe.
Il sito, in pratica, avverte l'utente che al vostro indirizzo IP sono ricollegate operazioni illecite:

atti di terrorismo
download di pornografia minorile

Per ripristinare il computer al suo stato precedente, quindi, viene chiesto di pagare 100 euro tramite Ukash o PaysafeCard.
La multa è solo un pretesto per rubare soldi all'utente!!! In realtà, infatti, è il virus Trojan.Win32.FakeGdF.<A-R> che blocca il computer sotto il falso nome: WPBT0.DLL nella cartella: <user> / IMPOSTAZIONI LOCALI / TEMP /

Nome file:	WPBT0.DLL
dimensione:	174592 byte
MD5	37f939b59edce18204f3db1fc18e79ff
File compresso:	UPX
Time Stamp del file:	17/07/2011 21.58.49
Esecuzione automatica:	dal menu Avvio (%user%\Menu Avvio\Programmi\Esecuzione automatica\wpbt0.dll.lnk

Del virus ne esistono diverse versioni che agiscono in modi alquanto analoghi.

Versioni:

Nome	Dimensione	MD5	Sito ip	Time stamp
Trojan.Win32.FakeGdF.A	174592	37f939b59edce18204f3db1fc18e79ff	83.69.236.38	17/07/2011 21.58.49
Trojan.Win32.FakeGdF.B	203264	1d10fb2bb8fac1122e2452975acfb701	31.31.200.105	14/12/2011 09.35.29
Trojan.Win32.FakeGdF.C	203264	58bca204698ff459697e6c1d9b8a5519	31.31.200.105	14/12/2011 15.34.14
Trojan.Win32.FakeGdF.D	180736	ef9b87a2780047307ac6c7280dc5feff	78.47.58.6	12/01/2011 09.08.08
Trojan.Win32.FakeGdF.E	194048	d0d0b5b6023d7534e05e44d18e7e11e1	78.47.58.6	15/12/2011 16.21.14
Trojan.Win32.FakeGdF.F	203776	78900f3e233ac18e29795bf0381526c9	85.17.168.194	11/12/2011 20.43.32
Trojan.Win32.FakeGdF.G	182272	750d4b7b1b0278b34f3afe15d81df559	46.161.31.157	26/06/2011 08.22.02
Trojan.Win32.FakeGdF.H	171008	b9a08f4e586f278e2c3420676bcde367	64.120.143.226	14/03/2011 10.04.03
Trojan.Win32.FakeGdF.I	193024	ec31d1eef414fefa17fef71573dd62f1	64.120.143.226	09/04/2011 13.07.01
Trojan.Win32.FakeGdF.J	179200	76376367a43a2ac4e718ca6fc8932648	83.69.236.38	14/05/2011 11.16.59
Trojan.Win32.FakeGdF.K	184320	3f657024d7a7e9da7215df7f87982df6	85.17.168.194	26/03/2011 08.38.56
Trojan.Win32.FakeGdF.L	165376	4b6de49e05c9c27892f465ac663b387f	64.120.143.226	28/02/2011 05.29.55
Trojan.Win32.FakeGdF.M	185344	26caa122cc0d01f788af005ea0135d08	64.120.143.226	14/03/2011 07.02.45
Trojan.Win32.FakeGdF.N	185856	d3b6c37e2de28822aae217b5e8b85d68	62.76.190.68	14/06/2011 09.30.20
Trojan.Win32.FakeGdF.O	204288	102ac369ffb35df07fb0ead427e45955	78.47.15.197	15/07/2011 02.33.58
Trojan.Win32.FakeGdF.P	195584	fc6042028b7b552cb2b2b09e8a28e550	78.47.15.197	27/04/2011 01.43.55
Trojan.Win32.FakeGdF.Q	190464	73e8702fcb76dfb5dbf1a6ba48ef8325	64.120.143.226	16/02/2011 19.34.00
Trojan.Win32.FakeGdF.R	199680	def27a897bff7e75155e7255083f868f	64.120.143.226	28/02/2011 16.06.38

La cura

Riavviare il computer in modalità provvisoria (premere F8 prima che Windows parta)

Per la versione A:

Cancellare il file: <user> / Menu Avvio / Programmi / Esecuzione Automatica / wpbt0.dll.lnk
Cancellare il file: <user> / IMPOSTAZIONI LOCALI / TEMP / WPBT0.DLL

Per le altre versioni:

Cancellare il file: <user> / Menu Avvio / Programmi / Esecuzione Automatica / 0.[numero casuale].exe.lnk
Cancellare il file: <user> / IMPOSTAZIONI LOCALI / TEMP / 0.[numero casuale].exe

Dove <user> si trova nelle seguenti directory:

Windows 2000 / XP / Server 2003: c:\documents and settings\<nome utente>
Windows Vista / 7 / Server 2008: c:\users\<nome utente>

Se file e cartelli non sono presenti nel vostro computer rendere file e cartelle nascoste visibili (premere qui per scoprire come).

Fonte:

C.R.A.M. by TG Soft www.tgsoft.it

Abstract Factory

2011-12-30T00:30:00.000+01:00

L'Abstract Factory è uno dei design pattern base descritti nel famoso libro Design Patterns: Elements of Reusable Object-Oriented Software (1994).

L'uso dell'Abstract Factory è utile per creare famiglie di oggetti (connessi o dipendenti per loro) in modo tale che la classe che li implementa non deve specificare la classe dell'oggetto esplicitamente.

In tal modo un software si può suddividere in due parti: la parte concreta e la parte client. La prima implementa il "cuore" del software, mentre la seconda si appoggia alla prima. Ad esempio, la parte client potrebbe essere una suite di JUnit Tests e usando la tecnica dell'Abstract Factory è possibile utilizzare la stessa suite per testare diverse implementazioni del software.

Il diagramma seguente è la rappresentazione logica dell'Abstract Factory Pattern.

Ecco alcuni punti principali presi da wikipedia e che ritengo abbastanza validi:

si vuole un sistema indipendente da come gli oggetti vengono creati, composti e rappresentati
si vuole permettere la configurazione del sistema come scelta tra diverse famiglie di prodotti
si vuole che i prodotti che sono organizzati in famiglie siano vincolati ad essere utilizzati con prodotti della stessa famiglia
si vuole fornire una libreria di classi mostrando solo le interfacce e nascondendo le implementazioni.

Di seguito porto un esempio di come si possa usare questa tecnica in Java.

Nota: consiglio vivamente di mettere le interfacce in un package "Interfacce" e le classi concrete in un package "Implementazione".

Per prima cosa iniziamo con le interfaccia, così ci si rende già conto di cosa devono fare le classi concrete.

Interfaccia Fattoria

public interface IFattoria {

IProdotto creaProdotto();

}

Interfaccia Prodotto

public interface IProdotto {

// I metodi del prodotto (no costruttore come di regola).

}

Osservando le due interfacce qui sopra ci rendiamo conto che è la fattoria il cuore di questa tecnica (come ci si aspettava dal nome, dopotutto).

Fattoria

public class Fattoria implements IFattoria {

@Override

public IProdotto creaProdotto() {

// Crea il prodotto dal suo costruttore.

return new Prodotto();

}

Mac OS X- Disabilitazione Screensaver come Desktop

2011-12-02T21:30:00.001+01:00

Ciao!

Lo so che è da tanto che non scrivo ma sono stato e sono molto impegnato in questo periodo. Mi concedo comunque il tempo di scrivere questo articoletto oggi.

Finalmente, infatti, ho risolto un problema molto discusso per i fan Mac ma irrisolto. Perlomeno io ho cercato per un anno in tutti i siti in inglese e in italiano una soluzione ma nessuna funzionava.

Come ben sappiamo i Mac hanno un terminale e si possono fare tante cose carine. Una di queste è impostare uno screensaver come desktop usando questo comando:

/System/Library/Frameworks/ScreenSaver.framework/Resources/
ScreenSaverEngine.app/Contents/MacOS/ScreenSaverEngine -background

Tuttavia se si chiude il terminale l'effetto svanisce. La soluzione per averlo sempre lì quindi è mettere l'ampersand alla fine:

/System/Library/Frameworks/ScreenSaver.framework/Resources/
ScreenSaverEngine.app/Contents/MacOS/ScreenSaverEngine -background &

Ma come fermarlo? Premendo Control+C ....questo è quello che suggerivano in molti: ma nada de nada..
L'unica soluzione era uccidere il processo:

Killall -9 ScreenSaverEngine

Ma poi ho scoperto che ogni volta che aprivo il mio terminale mi spuntava questa cosa...e mi consumava tutta la CPU! che rottura eseguire sempre il comando Killall -9 ScreenSaverEngine ogni volta che aprivo il terminale.

Ci ho sbattuto la testa per un anno per capire dove stava il problema...suggerimenti assurdi da tanti forum, ma nessuno funzionante..

Ma oggi..per caso ho risolto tutto! Viva la serendipità :)

Ecco come fare dal terminale:

Andare alla home directory:
cd ~

Visualizzare tutti gli elementi (anche quelli nascosti):
ls -a

Aprire il file del profilo:
open .profile

oppure
open .bash_profile

Ed ecco fatto....troverete nelle prime linee del documento questo:

/System/Library/Frameworks/ScreenSaver.framework/Resources/
ScreenSaverEngine.app/Contents/MacOS/ScreenSaverEngine -background &

Toglietelo, eliminatelo, bruciatelo....e godetevi nuovamente il vostro stupendo terminale con serenità...

Python - Generare l'Insieme di Mandelbrot

2011-11-27T20:30:00.000+01:00

L'insieme (o frattale) di Mandelbrot (1975) è uno dei frattali più famosi. Un frattale è un oggetto geometrico che si ripete nella propria struttura su scale diverse. I frattali sono molto comuni in natura e un esempio ne è la costa della Gran Bretagna.

L'insieme di Mandelbrot è definito per i numeri complessi c per i quali la seguente successione è vera e limitata:

Z(n + 1) = Z(n) ^ 2 + c , Z(0) = 0

Per informazioni più dettagliate clicca qui.

L'insieme prende il nome dal suo creatore: Benoît Mandelbrot, famoso matematico polacco per aver reso i frattali celebri. Tuttavia si seppe dare una forma o una rappresentazione grafica all'insieme di Mandelbrot solo grazie all'aiuto dell'informatica.

Nel 1985 fu pubblicato sulla rivista Scientific American il primo algoritmo per calcolare l'insieme di Mandelbrot.

L'algoritmo (per ogni punto C):

Z ha valore iniziale 0;
Scegliere C come il punto corrente. C è un numero complesso, quindi C = Parte Reale + Parte Immaginaria. Nel piano cartesiano l'asse delle ascisse (retta orizzontale) rappresenta la parte reale, mentre l'asse delle ordinate (retta verticale) rappresenta la parte immaginaria di C;
Iterazione = Z = Z^2 + C;
Fermarsi quando Z^2 è più grande del raggio massimo;
Count = numero di iterazioni prima di superare il raggio massimo;
Colore = dipende dal valore di Count.

Di seguito vi invito a provare questo generatore di Mandelbrot.
L'esecuzione di questo programma è molto lenta e può impiegare vari minuti per generare un immagine discreta dell'insieme. L'immagine verrà salvata come M.bmp sulla directory in cui state eseguendo il programma.
Vi propongo questa versione per tre motivi:

E' molto corta;
E' offuscata: cosa molto rara in Python dove l'indendatione e gli spazi sono significativi;
La sua forma ricorda l'insieme di Mandelbrot.

_ = (
255,
lambda
V ,B,c
:c and Y(V*V+B,B, c
-1)if(abs(V)<6)else
( 2+c-4*abs(V)**-0.4)/i
) ;v, x=1500,1000;C=range(v*x
);import struct;P=struct.pack;M,\
j ='<QIIHHHH',open('M.bmp','wb').write
for X in j('BM'+P(M,v*x*3+26,26,12,v,x,1,24))or C:
i ,Y=_;j(P('BBB',*(lambda T:(T*80+T**9
*i-950*T **99,T*70-880*T**18+701*
T **9 ,T*i**(1-T**45*2)))(sum(
[ Y(0,(A%3/3.+X%v+(X/v+
A/3/3.-x/2)/1j)*2.5
/x -2.7,i)**2 for \
A in C
[:9]])
/9)
) )

Nell'ottava riga x = 1500, 1000 indica la dimensione dell'immagine che verrà generata. E' possibile cambiare questi valori, ma ricordatevi che il tempo impiegato per generare l'immagine varierà drasticamente. Io personalmente l'ho provato con una risoluzione 7200x4800 e mi ci sono volute circa 2-3 ore prima di vedere l'immagine (ho usato un MacBook Pro CPU = 2.4GHZ. La CPU era impiegata al 50% durante l'esecuzione dell'algoritmo).

Siti di riferimento:
Preshing On Programming
Wikipedia

Per coloro alle prime armi:

Se non avete un compilatore python scaricatelo al seguente link.
Copiare il proprio codice in un normale text editor (non usate word o open office)
Dalla vostra finestra del terminale digitate python "nome del file dove avete copiato il programma"
Se volete evitare di usare il terminale potete trovare degli ambienti di sviluppo su grafica (IDE) qui.

Python - Creare un network: Server-Client (UDP)

2011-11-25T22:57:00.001+01:00

Lo User Datagram Protocol (UDP) è il protocollo principale (insieme a quello TCP) a livello di trasporto nella comunicazione fra hosts. Qui trovate una descrizione dei livelli di comunicazione.

L'UDP è :

connectionless: un messaggio non viene mandato a un altro host tramite un apposito stream di dati stabilito in precedenza. I dati quindi possono facilmente essere persi senza che chi li invii ne venga a conoscenza;
I dati ricevuti non sono necessariamente in ordine. Un file di dimensione A, infatti, viene suddiviso in n pacchetti di dimensione A/n e ognuno di essi viene inviato separatamente. Per ricostruire A, tuttavia, i pacchetti devono essere "uniti" nell'ordine esatto;
Rapido (ottimo per l'invio di Audio/Video in streaming);
Supporta il Broadcast (dati inviati a tutti nel network locale) e il Multicasting (dati inviati a tutti coloro che lo richiedono);
Non supporta il controllo di congestione della rete.

Possiamo ben notare che questo protocollo presenta alcuni pregi, ma anche molti difetti. Allora perché preoccuparsi tanto?

L'UDP, a differenza del TCP, è molto più flessibile. Volendo è possibile costruite un proprio protocollo TCP partendo dall'UDP. In poche parole l'UDP è flessibile (personalizzabile).

Un pacchetto dati UDP (Datagram) contiene le seguenti principali informazioni:

Indirizzo mittente (IP + Porta) (Facoltativo)
Indirizzo destinatario (IP + Porta)
Lunghezza del pacchetto in ottetti
I dati da inviare

                  0      7 8     15 16    23 24    31
                 +--------+--------+--------+--------+
                 |     Source      |   Destination   |
                 |      Port       |      Port       |
                 +--------+--------+--------+--------+
                 |                 |                 |
                 |     Length      |    Add. Info    |
                 +--------+--------+--------+--------+
                 |
                 |               DATA ...
                 +---------------- ...

Di seguito troverete le istruzioni base per inviare informazioni tramite UDP:

MITTENTE

import socket

# Indirizzo destinatario (in questo caso è lo stesso host del mittente)
IP_UDP = "127.0.0.1" # "localhost" o ""
PORTA_UDP = 5005
MESSAGGIO = "Sic-Oding"

# AF_INET --> Uso del protocollo IP /IPv4
# usare AF_INET6 per IPv6 se disponibile
# SOCK_DGRAM --> Crea una socket di tipo Datagram (UDP)
sock = socket.socket( socket.AF_INET, socket.SOCK_DGRAM )

# Invia il messaggio all'indirizzo specificato
# L'indirizzo è sotto forma di una TUPLA.
sock.sendto(MESSAGGIO, (IP_UDP, PORTA_UDP))

RICEVENTE

import socket

IP_UDP = "127.0.0.1"
PORTA_UDP = 5005

sock = socket.socket( socket.AF_INET, socket.SOCK_DGRAM )
# L'indirizzo specificato è vincolato per la socket sock.
sock.bind( (UDP_IP,UDP_PORT) )

# Ascolta ripetutamente per dei dati.
while True:
    # Riceve 1024 bytes alla volta.
    messaggio, indirizzo = sock.recvfrom( 1024 )
    print "Messaggio ricevuto :", messaggio

Tutorial di approfondimento in Inglese (mi dispiace ma non ne ho trovati in Italiano):
Wiki.Python
UDP RFC
Sockets programming in python
Docs.Python