Summary: voting for the interactive-fiction competition has started
Le avventure testuali sono vive e più che mai vitali! Su http://ifcomp.org/ si possono scaricare i giochi che concorrono all’undicesima competition annuale. Se non sai che cosa sia, provane qualcuno e preparati a qualche sorpresa… se pensavi che le avventure testuali fossero morte e sepolte negli anni ottanta, sbagli! Sono probabilmente più vive ora di allora.
Summary: natural language processing is coming back, as seen in free-format input in popular web apps, in the Inform programming language, or in the Ruby on Rails framework
Il linguaggio naturale per l’input è un trend che si comincia a notare: le applicazioni web più cool accettano input in formato naturale. Google Calendar accetta “15:00 dentista” senza bisogno di un box separato per l’ora e uno per il nome dell’evento. Basecamp va oltre (http://backpackit.com/calendar):
Type like you think:
“6pm Dinner” or “Doctor Wednesday 3pm” or “Call Jim tomorrow”.
L’ultima revisione di Inform, il linguaggio per avventure testuali, è radicalmente innovativo rispetto alle versioni precedenti, e anche rispetto a tutti gli altri sistemi analoghi.
Enfasi data al test: molti autori di narrativa interattiva iniziano a lavorare da uno scritto di interazione, da una lista di comandi e risposte che il gioco dovrebbe produrre una volta funzionante. Inform 7 conserva queste tracce di interazione, e permette di rilevare automaticamente quando il programma da noi realizzato riesce finalmente a rispondere all’interazione nella maniera desiderata. Questo riecheggia meravigliosamente con Kent Beck: prima scrivi l’output atteso, poi modifica il programma fino a che l’output del programma non sia uguale a quello atteso.
L’uso del linguaggio naturale per l’input. Lo so che questo chiama alla mente obbrobri di linguaggi di programmazione cammuffati da linguaggio naturale, come AppleScript o Cobol. Ma Inform 7 è un po’ più raffinato di così. Consideriamo questo frammento da The Reliques of Tolti-Aph di G. Nelson:
Chapter 1 – Fundamentals
Section 1(a) – Substance
A material is a kind of value. The materials are stone, wood, paper, magic-imbued wood, metal, clay, flesh, sustenance and air. A thing has a material. Things are usually stone. People are usually flesh.
Questo è il vero e proprio codice sorgente di un gioco. E a leggerlo sembra un moderno De Rerum Natura. “Things are usually stone. People are usually flesh.” è poesia.
L’adozione di uno stile di programmazione “per relazioni” piuttosto che ad oggetti. Da anni tenevo la mia copia del Clocksin & Mellish in cantina e sono andato a riprenderla. Mi sono ritrovato a pensare al tema del mio esame di Prolog di tanti anni fa. Siamo abituati a pensare ad oggetti da tanto tempo che ci sembra l’unica maniera naturale di programmare. Mi è tornato in mente che la programmazione logica alla Prolog permette di scrivere certi tipi di programmi in maniera estremamente concisa. E la concisione è potere.
Giocare con I7 mi ha riportato alle radici della fantascienza che amavo da bambino. Un programma che capisce le mie istruzioni in inglese! E chi se ne importa se “capisce” solo un epsilon della complessità del linguaggio naturale. E’ più sofisticato di qualsiasi altro sistema abbia mai usato. E’ sufficiente per scrivere programmi. Scusate se è poco.
I7 è un domain-specific language per realizzare narrativa interattiva. Il problema di “comprendere il linguaggio naturale”, che è di una complessità tale da sfuggire di gran lunga alle nostre capacità di programmazione, diventa gestibile quando la comprensione viene limitata a un dominio specifico, quale nel nostro caso è la scrittura di avventure testuali.
Mi sono divertito a scrivere codice Inform 7 che fa semplici ragionamenti geometrici
A geometric shape is a kind of thing.
A triangle is a kind of geometric shape. It has a number called side A. It has a number called side B. It has a number called side C. After printing the name of a triangle: say “, with sides ([side A],[side B],[side C])”.
To decide whether (x – a number) equals (y – a number) and (z – a number):
if x is y and y is z, decide yes;
otherwise decide no.Definition: A triangle is equilateral if its side A equals its side B and its side C.
The blue triangle is a triangle with side A 10, side B 10, and side C 10.
The green triangle is a triangle with side A 5, side B 5, and side C 10.
The pink triangle is a triangle with side A 3, side B 4, and side C 5.
The Geometry lab is a room. “You are in a weird lab.” The green triangle, the pink triangle and the blue triangle are in the lab.
A tester is a kind of container. They are always fixed in place.
The equilateral box is a tester. It is in the lab. “A large box is here; gold letters on it say ‘drop equilateral triangles here.'”
Instead of inserting something (called the supposed equilateral) into the equilateral box:
if the supposed equilateral is not an equilateral triangle, say “My, my. Read again the definition of ‘equilateral.'” instead;
Increase the score by one;
move the supposed equilateral to the equilateral box.To decide whether (x – a number) equals (y – a number):
if x is y, decide yes;
decide no.Definition: A triangle is isosceles if its side A equals its side B, or its side B equals its side C, or its side C equals its side A.
The isosceles box is a tester. It is in the lab. “A small box is here; silver letters on it say ‘drop isosceles triangles here.'”
Instead of inserting something (called the object) into the isosceles box:
if the object is not an isosceles triangle, say “A mysterious force prevents you from doing that.” instead;
Increase the score by one;
Move the object to the isosceles box.Instead of taking something which is in a tester, say “You can’t reach inside the box.”.
Test remove with “put green into isosceles box / get green / get pink”
To decide what number is the square of (x – a number): decide on x times x.
To decide what number is the lesser of (x – a number) and (y – a number):
if x is greater than y, decide on y;
decide on x.To decide what number is the greater of (x – a number) and (y – a number):
if x is less than y, decide on y;
decide on x.To decide what number is the lesser of (x – a number) and (y – a number) and (z – a number):
let a be the lesser of x and y;
decide on the lesser of a and z.To decide what number is the greater of (x – a number) and (y – a number) and (z – a number):
let a be the greater of x and y;
decide on the greater of a and z.To decide what number is the middle value of (x – a number) and (y – a number) and (z – a number):
let a be the lesser of x and y;
let b be the lesser of y and z;
let c be the lesser of x and z;
decide on the greater of a and b and c.To decide whether (x – a number) forms a pythagorean triple with (y – a number) and (z – a number):
let a be the lesser of x and y and z;
let b be the middle value of x and y and z;
let c be the greater of x and y and z;
if the square of a plus the square of b is the square of c, decide yes;
decide no.Definition: a triangle is rectangle if its side A forms a pythagorean triple with its side B and its side C.
Mi riesco facilmente a immaginare come la concisione di Inform potrebbe essere catturata in un sistema per la realizzazione di applicazioni gestionali.
Un impiegato è una persona. Un impiegato ha una data di nascita, un nome, un cognome, e un numero chiamato salario…
Un utente appartiene a molti gruppi. Un gruppo contiene molti utenti. Un gruppo ha un insieme di diritti di accesso…
Tutti questi esperimenti con la generazione di applicazioni, e la comprensione del linguaggio naturale, sono stati fatti e abbandonati negli anni 80-90. Andavano sotto il nome di “linguaggi di quarta generazione”. Perché fallirono negli anni 90? Perché potrebbero avere successo oggi? Non c’è una singola ragione precisa. La ragione c’è, e dipende da come vengono fatte le cose. Prima di tutto, potremmo osservare che ci sono centinaia di framework per realizzare applicazioni web, ma solo una manciata sono di qualità paragonabile a Rails.
Rails mi ha subito colpito per l’attenzione che dava alla gestione del linguaggio naturale, sia nel presentare output all’utente (niente “0 file(s) copied”!) sia in come appare il sorgente al programmatore.
class User < ActiveRecord::base validates_presence_of :name, :address validates_uniqueness_of :nickname, :email has_many :posts has_and_belongs_to_many: groups end
Definire "has_many :posts" aggiunge alla classe User una serie di metodi: ad esempio "user.posts" che restituisce gli oggetti "post" associati all'utente. Questo implica che Rails deve sapere che il singolare di "posts" è "post", così che venga usata la classe Post. Rails è preconfigurato con le regole più comuni della lingua inglese, ma posso benissimo estenderlo con regole aggiuntive. Per esempio, recentemente ho dovuto scrivere questo, per permettere a Rails di lavorare con un database legacy con i nomi delle tabelle in italiano:
Inflector.inflections do |inflect| inflect.irregular 'campagna', 'campagne' inflect.irregular 'promotore', 'promotori' inflect.irregular 'provincia', 'province' inflect.irregular 'regione', 'regioni' inflect.irregular 'trattativa', 'trattative' end
E' stato sufficiente dare a Rails questa lezioncina di italiano per integrare i nomi di tabelle italiani nell'applicazione. Questo ti dà il senso che programmare bene significa definire un linguaggio. O meglio insegnare alla macchina un linguaggio, che ne estende le capacità.
Summary: we have a new XP user group in Varese
Oggi un gruppo di coraggiosi ex-essap si è riunito in un aula dell’Università dell’Insubria. Sono molto contento… c’è entusiasmo. Abbiamo ascoltato una presentazione di Max Pepe, che ci ha raccontato come ha imparato ad amare TDD insieme a Rails. Abbiamo deciso il nome del gruppo (varese-xpug, con sottotitolo Open Team) Abbiamo fatto una mappa mentale di Examinando, un’applicazione che svilupperemo a mo’ di esercitazione. Prossima riunione fra due settimane. Yay!
Summary: “Pirates of the Caribbean: Dead Man’s Chest” sucks.
Ho visto “I pirati dei Caraibi”. Due ore e mezzo in cui praticamente non succede nulla, e il finale in sospeso per aspettare il terzo episodio. I personaggi, che erano così fighi nel primo film, vengono diluiti, sprecati, buttati via. Mi sembra molto scarso, anche per la media dei seguiti.
Summary: a few new neat things in the Rails world. Keep rocking!
E’ appena finita la conferenza europea, e DHH ha già bloggato sulle novità. Un mio cliente è stato là, e non vedo l’ora di strappargli tutto quello che ha imparato… (c:
DHH continua sulla sua strada di radicale semplificazione attraverso REST, come aveva già mostrato alla conferenza americana. Ora però c’è Simply Helpful, un nuovo stile per le view. Ho la sensazione che dovremo aspettare un bel pezzo per la seconda edizione di Agile Web Development, dato che DHH continua a riscrivere Rails. Ma non mi lamento: sono tutte modifiche che vanno nella direzione di semplificare la vita per le cose che si fanno più di frequente! Non di aggiungere a Rails ogni immaginabile cazzillo.
Capistrano è stato aggiornato, una novità è una shell interattiva che ti permette di manipolare interattivamente un insieme di server.
Da un po’ di tempo si sente parlare di Unobtrusive JavaScript; l’idea è che non è bello vedere codice JS inframmezzato un po’ a casaccio in mezzo all'(X)HTML. Molto meglio confinare il JS in un singolo file caricato separatamente. E’ possibile in tale file attaccare comportamenti ai vari elementi della pagina tramite codice che se ne sta comunque confinato nel suo file. Per lo meno questo è il tipo di approccio preferito dagli assi del web design. Ora c’è un plugin per Rails che serve a fare proprio questo.
HAML è un nuovo linguaggio di templating per Rails; mentre il linguaggio originale di Rails (RHTML) è semplice e un po’ troppo casereccio per i gusti degli sviluppatori più sofisticati, HAML è, appunto, molto più elegante e sofisticato.
E non ultimo, l’esplosivo Why The Lucky Stiff (autore fra l’altro di una versione semplificata di Rails che permette di scrivere un’intera web app in un solo file Ruby) ha parlato di Sandbox, un meccanismo per condividere molte applicazioni Rails su un solo processo di web server (Mongrel, per la precisione). E questa è musica per le mie orecchie… manutenere il server per le applicazioni degli studenti è improvvisamente diventato più facile.
All this coolness, so little time.
Summary: last meeting of the Milano XP UG was about TTDing a program to solve Sudoku games. Pretty good fun.
Non ho mai avuto la pazienza per risolvere i sudoku. Essendo pigro, scriverò un programma per risolverli…
L’ultimo meeting del Milano XP User Group ha avuto come tema “risolviamo il Sudoku con TDD”. Il problema è: dato un sudoku, scrivi un programma che per ogni cella mi dice quali sono i numeri che posso legalmente scriverci dentro.
In coppia con l’ottimo Roberto Valenti abbiamo affrontato il problema in Ruby. Abbiamo cominciato decidendo arbitrariamente di rappresentare il tabellone con un singolo array di interi. E’ la rappresentazione più semplice, e fino a quando non risulterà inadeguata non c’è bisogno di usarne una più complicata. YAGNI!
TEST_BOARD = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, ]
(Questa tabella di test è stata generata con un semplice programma.)
Da qualche parte bisogna iniziare. Abbiamo deciso di iniziare sviluppando metodi per estrarre righe, colonne e quadranti dalla tabella.
def test_row_col assert_equal [18, 19, 20, 21, 22, 23, 24, 25, 26], row(TEST_BOARD, 2) assert_equal [1, 10, 19, 28, 37, 46, 55, 64, 73], col(TEST_BOARD, 1) assert_equal [27, 28, 29, 36, 37, 38, 45, 46, 47], quad(TEST_BOARD, 4, 1) end
Da notare solo che quad(board, r, c) restituisce il quadrante dentro cui cade r, c. Quindi quad(board, 0, 0) sarà uguale a quad(board, 2, 2) perché entrambi restituiscono il primo quadrante.
A questo punto il problema è già quasi risolto. È più facile ottenere prima i numeri proibiti. Prima di tutto, se il tabellone è tutto vuoto, non ci sono vincoli.
# rappresentiamo le caselle vuote con 0 EMPTY_BOARD = Array.new(81, 0) def test_forbidden_numbers_on_empty_board assert_equal [], forbidden_numbers(EMPTY_BOARD, 4, 4) end
e la soluzione è facile:
def forbidden_numbers(board, r, c) [] end
Poi testiamo che vengano considerati proibiti i numeri che appaiono nel quadrante. Inputiamo un sudoku diagonale giusto per testare questo:
DIAG_BOARD = [ 1,0,0,0,0,0,0,0,0, 0,2,0,0,0,0,0,0,0, 0,0,3,0,0,0,0,0,0, 0,0,0,4,0,0,0,0,0, 0,0,0,0,5,0,0,0,0, 0,0,0,0,0,6,0,0,0, 0,0,0,0,0,0,7,0,0, 0,0,0,0,0,0,0,8,0, 0,0,0,0,0,0,0,0,9, ] def test_forbidden_numbers_on_quadrant assert_equal [1,2,3], forbidden_numbers(DIAG_BOARD, 0, 1) assert_equal [7,8,9], forbidden_numbers(DIAG_BOARD, 8, 7) end
e modifichiamo di conseguenza la funzione
def forbidden_numbers(board, r, c)
quad(board, r, c).reject {|x| 0 == x}
end
Ora vogliamo tenere conto anche dei numeri che stanno sulle colonne
def test_forbidden_numbers_on_columns assert_equal [1], forbidden_numbers(DIAG_BOARD, 8, 0) assert_equal [6], forbidden_numbers(DIAG_BOARD, 0, 5) end
E fin qui è facile
def forbidden_numbers(board, r, c)
result = quad(board, r, c) + col(board, c)
result.reject {|x| 0 == x}
end
E così via per le righe
def forbidden_numbers(board, r, c)
result = quad(board, r, c) + col(board, c) + row(board, r)
result.reject {|x| 0 == x}
end
Ora, è facile prevedere problemi nel caso in cui il tabellone non è una diagonale: rischiamo di avere numeri duplicati, e comunque non nell’ordine crescente che i nostri test si aspettano. Scriviamo un test che espone un problema, e lo risolviamo in stile Unix, con sort e uniq
def forbidden_numbers(board, r, c)
result = quad(board, r, c) + col(board, c) + row(board, r)
result = result.reject {|x| 0 == x}
result.sort
result.uniq
end
I numeri permessi, a questo punto, sono semplicemente il complemento di quelli proibiti.
def possible_numbers(board, r, c)
complement(forbidden_numbers(board, r, c))
end
def complement(ar)
universe = [1,2,3,4,5,6,7,8,9]
universe.reject {|x| ar.member?(x) }
end
Avrai notato che fino ad ora abbiamo lavorato in maniera molto poco object-oriented. Poco male! Il punto è risolvere il problema nella maniera più semplice possibile. Però a questo punto il nostro codice comincia ad avere parecchie “funzioni” che se ne stanno appese nel vuoto. E non mi piace il fatto che in parecchi punti dobbiamo convertire le coordinate “lineari” della nostra lista in coordinate quadrate (r,c).
Decidiamo di rifattorizzare il codice per nascondere l’implementazione della tabella. Creiamo una classe Board inizializzata da un array
class Board
def initialize(list)
@list = list.dup
end
end
e passiamo 10 minuti a convertire tutti i nostri test, spostando dentro alla classe i metodi che prima fluttuavano nel vuoto. Sempre però un test alla volta, spostando solo i metodi necessari, e sempre rieseguendo i test. Alla fine abbiamo questi test
class TestNameOfTestCases < Test::Unit::TestCase
def test_board_at
b = Board.new(SOLVED_BOARD)
assert_equal b.at(0, 0), 8
assert_equal b.at(2, 3), 1
end
def test_set
b = Board.new(SOLVED_BOARD)
b.set(2,3,255)
assert_equal 255, b.at(2, 3)
end
def test_board_find_hole
b = Board.new(SOLVED_BOARD)
assert_equal nil, b.find_hole
b.set(1, 2, 0)
assert_equal [1, 2], b.find_hole
end
def test_row_col
b = Board.new(TEST_BOARD)
assert_equal [18, 19, 20, 21, 22, 23, 24, 25, 26], b.row(2)
assert_equal [1, 10, 19, 28, 37, 46, 55, 64, 73], b.col(1)
assert_equal [0, 1, 2, 9, 10, 11, 18, 19, 20], b.quad(0, 0)
assert_equal [0, 1, 2, 9, 10, 11, 18, 19, 20], b.quad(1, 1)
assert_equal [0, 1, 2, 9, 10, 11, 18, 19, 20], b.quad(2, 2)
assert_equal [27, 28, 29, 36, 37, 38, 45, 46, 47], b.quad(4, 1)
assert_equal [30, 31, 32, 39, 40, 41, 48, 49, 50], b.quad(5, 5)
end
def test_forbidden_numbers_on_quadrant
assert_equal [], Board.new(EMPTY_BOARD).forbidden_numbers(4, 4)
assert_equal [1,2,3], Board.new(DIAG_BOARD).forbidden_numbers(0, 1)
end
def test_forbidden_numbers_on_quad_and_row
b = Board.new(DIAG_BOARD)
b.set(0, 4, 4)
assert_equal [1,2,3,4], b.forbidden_numbers(0, 1)
end
def test_forbidden_numbers_on_quad_and_col
b = Board.new(DIAG_BOARD)
b.set(4, 0, 5)
assert_equal [1,2,3,5], b.forbidden_numbers(1, 0)
end
def test_possible_numbers_on_problem
b = Board.new(PROBLEM)
assert_equal [3], b.possible_numbers(0, 1)
end
def test_complement
assert_equal [], Board.complement([1,2,3,4,5,6,7,8,9])
assert_equal [9], Board.complement([1,2,3,4,5,6,7,8])
assert_equal [1,4,9], Board.complement([2,3,5,6,7,8])
end
e questo codice
class Board
def initialize(list=nil)
@list = list.dup
end
def at(r, c)
@list[r*9 + c]
end
def set(r, c, val)
@list[r*9 + c] = val
end
def forbidden_numbers(r, c)
result = quad(r, c)
result += row(r)
result += col(c)
result = result.reject { |n| n == 0 }
result.sort
result.uniq
end
def possible_numbers(r, c)
Board.complement(forbidden_numbers(r, c))
end
def self.complement(ar)
universe = [1,2,3,4,5,6,7,8,9]
universe.reject {|x| ar.member?(x) }
end
def quad(r, c)
result = []
for rr in ((r/3)*3...(r/3)*3+3)
for cc in ((c/3)*3...(c/3)*3+3)
result << at(rr, cc)
end
end
result
end
def row(n)
@list[n*9...(n+1)*9]
end
def col(c)
(0...9).map {|r| at(r, c)}
end
def list
@list
end
private
def linear_to_r_c(index)
[index / 9, index % 9]
end
end
Facciamo un test di accettazione: prendiamo un sudoku risolto, e a turno cancelliamo un elemento. La funzione possible_numbers deve restituire il numero appena tolto.
def test_solved_board
b = Board.new(SOLVED_BOARD)
for r in (0...9)
for c in (0...9)
element = b.at(r, c)
b.set(r, c, 0)
assert_equal [element], b.possible_numbers(r, c)
b.set(r, c, element)
end
end
end
Funziona! E' vero che potremmo fare dei test più accurati, ma sono abbastanza confidente che la nostra soluzione sia corretta. Comunque, se non fossimo al pub alle 8 di sera probabilmente mi metterei il berretto da tester e farei qualche test in più.
Avevamo ancora un filo di energia, così abbiamo deciso di continuare scrivendo un metodo solve(board) che restituisca un sudoku completato.
In generale, questo tipo di problemi si risolvono per mezzo di ricerca. Ovvero, non c'è un algoritmo che mi possa dire in un colpo solo qual'è il numero da mettere. Quasi tutti i puzzle ricadono in questo schema: il problema delle N regine, il problema del 15, il cubo di Rubik...
Abbiamo uno stato iniziale; per ogni stato abbiamo un certo numero di mosse a disposizione. Risulta un albero di stati. Le foglie di questo albero sono stati in cui il gioco è risolto (yuppi!), oppure stati in cui il gioco non è risolto e non ci sono altre mosse possibili (buuu).
Il problema allora è esplorare l'albero degli stati in maniera da trovare il prima possibile un nodo-soluzione. Ci sono due strategie di base, che si applicano a tutti i puzzle. La strategia breadth-first: partendo dalla radice, considero tutti i nodi raggiungibili. Ho trovato la soluzione? Se no, per ogni nodo trovato, considero tutti i suoi nodi raggiungibili. Cioè, esamino tutti i nodi di livello 2. Vado avanti così, esaminando tutti i nodi di livello n fino a che non trovo una soluzione.
Il vantaggio del breadth-first è che trova di sicuro la soluzione più breve. Lo svantaggio è che rischio di metterci moltissimo tempo a trovarla.
L'altra strategia agnostica è depth-first: dalla radice scelgo la prima mossa, poi la prima mossa, e sempre la prima mossa fino a quando non raggiungo una foglia. Se è un fallimento, torno indietro di *un* passo e esamino la seconda mossa. Se esaurisco tutte le mosse possibili a quel livello, torno indietro di un altro passo e considero la seconda mossa da lì.
Lo svantaggio del depth-first è che non è garantito che possa mai trovare una soluzione. Nel caso del sudoku, però, questo non è un problema perché la profondità dell'albero è sempre limitata dal numero di caselle vuote da riempire.
E' facile implementare una ricerca depth-first, usando una funzione ricorsiva.
def solve(prob)
return prob if prob.solved?
for move in prob.possible_moves
try = solve(prob.apply(move))
# if solved, stop here
return try if try
end
# no more moves
return false
end
Lo stack implicito nella valutazione della funzione ricorsiva mi tiene traccia di a che punto sono nella mia esplorazione dell'albero.
Con questo schema in mente, scriviamo il nostro primo test. Se il problema è risolto, deve restituire la tabella risolta
def test_solve assert_equal SOLVED_BOARD, solve(Board.new(SOLVED_BOARD)) end
E fin qui è facile. Poi proviamo a togliere una posizione dal gioco completato, e ci aspettiamo che ritrovi di nuovo la soluzione
def test_solve b = Board.new(SOLVED_BOARD) assert_equal SOLVED_BOARD, solve(b) b.set(0,0,0) # metto 0 alla posizione 0,0 assert_equal SOLVED_BOARD, solve(b) end
Anche questo si risolve facilmente. Ci serve una funzione che trovi il primo "buco". Se il buco non c'è, assumiamo che il gioco sia risolto
class Board
def find_hole
@list.each_with_index { |e, index|
return linear_to_r_c(index) if e == 0
}
nil
end
end
def solve(board)
if !board.find_hole
return board.list
end
r, c = board.find_hole
possibles = board.possible_numbers(r, c)
board.set(r, c, possibles.first)
end
Questo però assume che ci sia per forza un numero possibile. Cosa succede se siamo a un nodo di fallimento? Lo simuliamo passandogli un sudoku irrisolvibile
def test_failure_node
b = Board.new(SOLVED_BOARD)
b.set(0, 1, 8 ) # mossa non valida! ma non importa
b.set(0, 0, 0) # questo buco ora è irrisolvibile
assert_equal false, solve(b)
end
def solve(board)
if !board.find_hole
return board.list
end
r, c = board.find_hole
possibles = board.possible_numbers(r, c)
return false if !possibles
board.set(r, c, possibles.first)
end
A questo punto facciamo emergere la nostra soluzione presentando problemi sempre più difficili. In realtà essendo un po' stufi abbiamo preso una scorciatoia: abbiamo preso un problema da risolvere completo, e abbiamo implementato direttamente la soluzione ricorsiva. Con qualche calcio l'abbiamo fatta funzionare:
PROBLEM = [
1, 0, 2, 0, 0, 0, 7, 0, 0,
0, 4, 7, 0, 2, 1, 3, 0, 0,
0, 8, 0, 7, 0, 3, 0, 1, 0,
4, 6, 0, 1, 0, 0, 0, 8, 0,
0, 0, 0, 2, 6, 4, 0, 0, 0,
0, 5, 0, 0, 0, 9, 0, 6, 4,
0, 9, 0, 5, 0, 7, 0, 2, 0,
0, 0, 1, 3, 4, 0, 9, 7, 0,
0, 0, 6, 0, 0, 0, 8, 0, 3,
]
def test_solution
sol = sove(PROBLEM)
assert sol, "non ha risolto il problema :-("
do_print sol
end
def solve(board)
if !board.find_hole
return board.list
end
r, c = board.find_hole
possibles = board.possible_numbers(r, c)
for p in possibles
board.set(r, c, p)
solved = solve(Board.new(board.list))
return solved if solved
end
return false
end
Questo problema viene risolto in 0.2 secondi sul mio Mac G4. Un problema più difficile, a livello evil da www.websudoku.com, viene risolto in 10 secondi. Sono molto soddisfatto.
Penso che la performance si possa migliorare nettamente, per il caso difficile, modificando semplicemente il metodo find_hole. Se invece di restituire il primo buco restituisse il buco che è maggiormente vincolato, immagino che taglieremmo di molto il numero di tentativi falliti. E questo, caro lettore, resta come esercizio...
Riassunto: ecco come aggiungere un’immagine a un modello in una applicazione Rails
Just a summary of what it takes to add an image to a model in a Rails application. This is to remind myself of the steps it took to make it work.
There are two plugins out there: file_column and acts_as_attachment. The second is more full-featured, and requires a separate table for each attachment. So I chose to use the former, for simplicity. I can always change my mind later.
Using file_column is straightforward, unless you wish to change the default place where image files are saved; in which case you must add options that are not well documented. The default location is not good, because it chooses a different directory for every model: public/people, public/places, public/foobar, and so on. This is not good when deploying with capistrano, because you will need to make all of these dirs symbolic links. Much better to have a single root for all uploads: public/uploads/people, public/uploads/places, …
Suppose you want to add an “image” file attachment to a model “Foobar”. First you must add an “image” column to the foobars table:
$ script/generate migration AddImageColumnToFoobars
...
edit the migration file
class AddColumnImageToFoobars < ActiveRecord::Migration
def self.up
add_column :foobars, :image, :string
end
def self.down
remove_column :foobars, :image
end
end
and execute the migration
$ rake migrate
...
Time to do a little functional test. Open up test/functional/foobar_controller_test.rb and write something like
def test_update_image
post :edit, :id => 2, :foobar => {
:image => upload(Test::Unit::TestCase.fixture_path
+ '/files/animal.jpg', 'image/jpg'),
}
assert_redirected_to :action => 'page', :name => old_content.name
updated_foobar = Content.find(2)
assert_not_nil updated_foobar.image, "what? no image?"
assert_equal '2/animal.jpg', updated_foobar.image_relative_path
end
Run the test. Does it fail? Good! Failure is progress.
Now modify the Foobar model
class Foobar < ActiveRecord::Base
file_column :image,
:root_path => File.join(RAILS_ROOT, "public", "upload"),
:web_root => "upload/"
end
The :root_path option says we want to save all uploads beneath the “public/uploads” directory. The :web_root is needed so that the proper url for the pictures can be computed. A bit redundant, but I see how this can be handy for apps that are deployed on multiple servers.
Try the functional test again. It should work now.
Now modify the views/foobar/_form.html adding
<%= file_column_field "foobar", "image" %>
You must also modify the form tag in views/foobar/edit.rhtml and new.rhtml adding multipart encoding, this way:
<%= form_tag({:action => 'update', :id => @foobar},
{:multipart => true}) %>
otherwise, upload will not work.
At last, you can show the image in your Foobar pages:
<%= image_tag url_for_file_column(@foobar, "image") if @foobar.image %>
The “if” part is needed in case no image has been uploaded yet.
The finishing touch is to add validations to the model:
class Foobar < ActiveRecord::Base
file_column :image,
:root_path => File.join(RAILS_ROOT, "public", "upload"),
:web_root => "upload/"
validates_file_format_of :image, :in => ["gif", "png", "jpg"]
validates_filesize_of :image, :in => 15.kilobytes..1.megabyte
validates_image_size :image, :min => "1200x1800"
end
The “file_column” plugin is simple and it works beautifully, even if the docs could be better. Be sure to consult the rdoc within the source files.
If you need to run searches on your uploaded files, such as, for instance, looking for all pictures in “landscape” format, then file_column does not help. The other solution, acts_as_attachment could be the right choice.
Summary: The Good Life by Jay McInerney is not one of his “great” novels.
Ho appena finito di leggere The Good Life di Jay McInerney. E’ la storia di Luke, un esperto finanziario di Wall Street di grande successo, sposato a Sasha, una donna estremamente bella e sofisticata; e di Corrine, una autrice di sceneggiature di scarso successo, mamma di due gemelli e sposata a Russel, un editore di modesto successo.
Quello che segue è un riassunto senza troppi spoiler.
Luke è in crisi di mezza età, e si è preso un “sabbatico” dal suo lavoro per riprendere i contatti con sua moglie e sua figlia Ashley, che a 13 anni è in piena adolescenza e non ne vuole sapere.
Russel è in crisi di mezza età; ha un’amante che soddisfa i suoi desideri sessuali e per il resto quando è a casa si dedica in parte ai gemelli, ma soprattutto al suo grande hobby, la cucina (immaginatevi che palle.)
Corrine è in crisi perché Russel è distante (a letto legge i manoscritti); perché non riesce a completare la sceneggiatura a cui sta lavorando; perché i gemelli sono nati con la fecondazione artificiale; perché è convinta di essere una cattiva madre…
La vicenda si svolge a New York dal 10 settembre 2001 fino al Natale dello stesso anno. Il giorno dell’attacco aereo Luke si salva per caso. Incontra Corrine; cominciano a frequentarsi.
Prima di tutto mettiamo in chiaro che si tratta di un libro di un autore di prima classe. I personaggi escono fuori dalla pagina, si capisce che l’autore descrive sempre solo persone che conosce e situazioni che ha vissuto. Questo per me è importantissimo: scrivere significa avere delle storie da raccontare.
Dieci anni fa, quando lessi The Last of the Savage, continuavo a pensare a quel libro anche dopo mesi che lo avevo finito. E’ probabilmente uno dei 10 romanzi più belli che ho letto (non che questo significhi gran che) e sicuramente il più bello di McInerney.
Venti anni fa, quando lessi Le mille luci di New York (Bright Lights, Big City) mi fece lo stesso effetto. Un romanzo perfetto, un colpo di fulmine. Lo regalai a tutti i miei amici.
Purtroppo questa cadenza di un grande romanzo ogni dieci anni non ha funzionato; almeno per me, il colpo di fulmine con questo romanzo non c’è stato. Sarà perché non riuscivo a identificarmi, a “tifare” per nessuno dei personaggi? Ma neanche in The Last of The Savage potevo. Però in quella storia c’era un respiro epico che in questo libro non c’è.
The Good Life ha dei buoni momenti, e dei momenti tediosi. Fra i momenti migliori c’è il contrasto fra la New York sofisticata e il Sud rurale degli Stati Uniti (che era un’elemento chiave di Last of the Savage) Fra i momenti più noiosi, le conversazioni degli amici sofisticati di Russel e Corrine (fatta eccezione per Washington, che è fichissimo) e gli eventi mondani di Sasha e Luke.
Un osservazione carina la fa Jim Crespi, amico di Russel e regista di Hollywood negli anni ’70: in quegli anni i produttori di Hollywood si resero conto che non erano più capaci di fare i film, e si affidarono a dei giovani (Scorsese, Altman, Coppola, Cimino…) che ribaltarono il cinema. Poi un anno vado a vedere “Pulp Fiction”, e mi ritrovo a vedere un film dove tutto è fatto per finta, esagerato e ironico. Mentre il cinema dei ’70 era tutto sull’onestà e la verità, quello che va adesso è un cinema di strizzate d’occhio e di scherzi. (Non ho sottomano il libro, se no metterei la citazione esatta.) Nel romanzo Jim scompare sotto le torri.
Se non hai mai letto McInerney, comincia dai due che ho elogiato qui sopra. Non te ne pentirai. (Statisticamente, questo autore piace molto di più ai maschi. Non so perché.) Se conosci McInerney, questo è un buon libro: ma non è uno dei suoi libri “A”. Mettiamolo insieme ai suoi libri “B”, come Riscatto (Ransom) o Tanto per cambiare (The Story of My Life).
Summary: the Essap people met on July 24 for a Rails workshop and a pizza. Good fun.
Riunione Essap del 24 luglio. Ci siamo incontrati alle 15 in un aula dell’Università dell’Insubria per un seminario/laboratorio su Rails. Appena arrivati abbiamo visto che l’aula non era attrezzata per quello che volevamo fare. Ma… si vede che alla Essap i ragazzi hanno imparato bene, perché hanno subito spostato tutte le sedie negli angoli, e portato un tavolone dal corridoio dentro all’aula. Così si fa!
L’obiettivo del seminario era introdurre Rails. La ragione dietro a Rails è che è troppo noioso sviluppare web app in Java, tanto che alla Essap (e anche al Milano XP-UG) ci siamo impantanati su questioni tecniche noiosissime.
Argomenti del seminario:
Siamo arrivati fin qui. Il passo successivo sarebbe stato aggiungere al controller un’azione per inserire un nuovo utente, il che dimostra il funzionamento delle form. Sempre in TDD!
Come sempre abbiamo avuto alcuni problemi. Avere le macchine correttamente installate è sempre un problema. La soluzione è arrivare con i kit appositi per Linux (Rails Live), Mac (Locomotive + RadRails) e Windows (InstantRails + RadRails).
UPDATE: fornire agli studenti una procedura da eseguire per verificare che sul loro computer sia tutto installato correttamente. A volte sembra tutto a posto, ma non lo è.
Poi l’idea di avere un PC per due persone non va bene; nella prima fase gli esercizi sono semplicemente “fai come ti ho mostrato e fallo funzionare”, e non ha molto senso fare pair programming (il navigatore non fa nulla.) Magari in un corso di più ampio respiro, posso assegnare degli esercizi da fare in un oretta, e lì va bene fare pair.
Inizialmente avevo deciso di spiegare senza pomodoro. Però abbiamo notato tutti che la cosa funzionava peggio. Dopo un’ora ho iniziato a lavorare con il pomodoro, e la cosa ha funzionato molto meglio. Sono riuscito a fare coincidere con il pomodoro dei “capitoletti” di quello che volevo spiegare. Chissà mai che non sia una buona idea usare il pomodoro anche a lezione?
Renzo mi ha fatto notare che i test con cui ho sviluppato il controller testavano più la vista (con assert_tag) che il controller stesso. Ha ragione, infatti avrei potuto fare prima dei test più semplici con il controller solo.
Comunque credo di avere mostrato un infarinatura di quello che Rails può fare. Tutti i partecipanti (tranne quelli senza PC) hanno seguito il codice con me.
La sera ci siamo spostati al circolino per una pizza, dove ci ha raggiunti il Prof. Lanzarone. L’atmosfera di relax ha fatto nascere alcune idee.
La più carina riguarda il modo di fare proseguire XP all’Insubria. Federico ha proposto che gli studenti si organizzino per fare un “Open Team” in un giorno, un ora e un aula fissi ogni settimana. Io potrei sostenerli con una riunione al mese (ma altri XPer sarebbero benvenuti). L’idea è che l’open team sviluppi l’applicazione proposta durante l’Essap (un’app per gestire le prenotazioni delle date degli appelli). Chiunque si ritrovi di lì ed entri, incuriosito dal cartello “Open Team”, può provare a fare pair programming con i ragazzi. Lanzarone ha dato il suo appoggio all’iniziativa, anzi ha lamentato che di buone iniziative degli studenti non ce ne sono abbastanza!
Spero proprio che questa cosa si riesca a fare.
UPDATE: si è parlato di dove mettere il server svn per il team. Una possibilità è di acquistare un minipc da portare in giro, in modo da poter deployare il team in pochissimo tempo. Sul minipc installiamo la buildix, e lo usiamo anche per creare una rete locale wireless.
Si è parlato di fare degli altri seminari su Rails, ma mi pare pleonastico dato che a settembre inizia il mio corso di Applicazioni Web, che parla sempre di Rails.
Dopo la cena, abbiamo passeggiato per le vie della vecchia Varese fino a una remota gelateria. Torniamo a casa stanchi e contenti.
