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...