Robitex's Blog

Ideas in the web

Archivi Mensili: gennaio 2010

Sudoku in java Parte 2


Il codice completo

Il codice seguente implementa un applicazione java con output nella console, per la risoluzione del gioco del Sudoku con una funzione ricorsiva, completando il post precedente.

Questa soluzione fa uso di classi enum, costrutto di Java 5 (JDK 1.5) e di operazioni bitmask per incrementare le performance (bit 0 = valore ammesso nella cella, bit =1 valore non ammesso). Infatti potenzialmente passando al codice la griglia vuota, vengono trovate TUTTE le soluzioni possibili del gioco. Peccato che occorrano circa 10.000 anni di lavoro per un PC desktop per terminare il compito…

/*
 * Sudoku.java
 * Solve the game Sudoku with a recursive function.
 * 
 * Versione base: 0.1.0.0
 * Date: 10/11/2005 - Start date: 22/08/2005
 * 
 * Copyright (C) 2005  Roberto Giacomelli
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
 
/**
 * The new class Sudoku implements new java feature enum
 * to manage the grid game symbols.
 * Not filled cells are treatment with null reference.
 * Another change to original Sudoku code is bitwise operation
 * for indicates the possible values in an empty cell.
 *
 * Conception: 18 novembre 2005
 * Author: Roberto Giacomelli
 * @param v is an array of int that represent start grid of game
 */
public class Sudoku {
    
    public enum      gridSymbol {
    // non è possibile inserire l'enum in grid
   // perché in una inner class non sono
   // ammessi metodi static.
        A, B, C, D, E, F, G, H, I ;
    }

    private Grid  startGame;
    public  int   solutionsCount;
    
    /**
     * Costruttore unico della classe Sudoku
     */
    public Sudoku(int[] v) {
        startGame = new Grid( v );
    }
    
    /**
     * Wrapper method to calling recursive function
     */
    public void solve() {
            solutionsCount = solveRecursive( startGame );
    }
    
    /**
     * Solve game with a recursive method
     * and return the number of grid's solutions.
     */
    private int solveRecursive( Grid PlayGame ) {
        if ( !(PlayGame.isCoherence() ) ) {
            return 0 ;
        }
        
        PlayGame.fillOnes();
        
        if (PlayGame.isSolution()) {
            PlayGame.print();
            return 1 ;
        }
        
        int posMinCell = PlayGame.minPossibilityCell();
        int cellPossibility = PlayGame.avalaibleValues[ posMinCell ]; 
        int solCount = 0;
        
        for (int val = 0; val < 9; ++val) {
            if ( ( cellPossibility & 1 ) == 0 ) {
               Grid Game1 = new Grid( PlayGame );
               Game1.setCell(posMinCell , gridSymbol.values()[val]);
               Game1.updatePossibility( posMinCell );
                solCount += solveRecursive( Game1 );
            }
            cellPossibility = cellPossibility >> 1;
        }
        return solCount;
    }
    
    public void printGrid() {
        startGame.print();
    }
    
    
    /**
    * Grid inner class:
    * store data game and esposed essential methods
    * to solve game in a recursive manner.
    */
    private class Grid {
        // store grid values (enum type)
        private gridSymbol[] Cells;
      // store not empty cell count of possibility values
        private int[] avalaibleValuesCount;

      // zero is 'possible all values'
      // eight is 'possible only one value'
        private int[] avalaibleValues;
       // store not empty cell possibility values
      // an int is bitwise intended
        
        public Grid( int[] vector ) {
        // costruttore standard
            Cells = new gridSymbol[ 81 ];
            avalaibleValuesCount = new int[81];
            avalaibleValues = new int[81];
       // zero are default value
            
            for (int i=0 ; i<81 ; ++i ) {
                if ( vector[ i ] != 0 ) {
                    Cells[i] = gridSymbol.values()[vector[i] - 1];
                }
            }
            
            // build array avalaible...
            for (int i = 0; i<81; ++i){
               if (Cells[ i ] != null) {
                   updatePossibility( i );
               }
            }
        }
        
        public Grid( Grid BaseGame ) {
          // costructor overload
            Cells = new gridSymbol[ 81 ];
            avalaibleValuesCount = new int[ 81 ];
            avalaibleValues = new int[ 81 ];
            
            //~ Cells = ( gridSymbol[] ) BaseGame.Cells.clone();
        // cast from object to array
            //~ avalaibleValuesCount = ( int[] ) BaseGame.avalaibleValuesCount.clone();
            //~ avalaibleValues = ( int[] ) BaseGame.avalaibleValues.clone();
            
            // code equivalent to clone() array method
            for (int i=0 ; i<81 ; ++i){
                Cells[ i ] = BaseGame.Cells[ i ];
           // copy grid values
                avalaibleValuesCount[ i ] = BaseGame.avalaibleValuesCount[ i ];
                avalaibleValues[ i ] = BaseGame.avalaibleValues[ i ];
            }
        }
        
        public boolean isCoherence() {
            for (int valueCount : avalaibleValuesCount ) {
                if ( valueCount>8) {
                    return false;
                }
            }
            
            // array booleaneani per il controllo
            // di congruenza base (applicazione delle regole base)
            boolean[] h = new boolean[9];
            boolean[] v = new boolean[9];
            boolean[] q = new boolean[9];
            
            int rowIndex ;
            int colIndex ;
            int squareIndex ;
            int CellValue;
            
            // check di coerenza sulle regole base
            for ( int i = 0 ; i<9 ; ++i) {
                for ( int j = 0 ; j<9 ; ++j) {
                    rowIndex = i*9 + j;
                    colIndex = i + 9*j;
                    squareIndex = (i/3)*27 + i*3 -(i/3)*9 + j + (j/3)*6;
                    
                    if ( Cells[ rowIndex ] != null ) {                 // per le righe
                        CellValue = Cells[ rowIndex ].ordinal();
                        if ( h[ CellValue ] ) {
                            return false;
                        } else {
                            h[ CellValue ] = true;
                        }
                    }
                    
                    if ( Cells[ colIndex ] != null ) {                 // per le colonne
                        CellValue = Cells[ colIndex ].ordinal();
                        if ( v[ CellValue ] ) {
                            return false;
                        } else {
                            v[ CellValue ] = true;
                        }
                    }
                    
                    if ( Cells[ squareIndex ] != null ) {                 // per i quadri
                        CellValue = Cells[ squareIndex ].ordinal();
                        if ( q[ CellValue ] ) {
                            return false;
                        } else {
                            q[ CellValue ] = true;
                        }
                    }
                }
                
                java.util.Arrays.fill( h , false );
                java.util.Arrays.fill( v , false );
                java.util.Arrays.fill( q , false );
            }
            
            // se tutti i controlli hanno dato esito positivo:
            return true;
        }
            
        public void updatePossibility( int PosCell ) {   // shift bitwise operator
            final int BITMASK = 1 << Cells[ PosCell ].ordinal();
           // initial cell pos in row
            final int H = PosCell / 9;
          // initial cell pos in column
            final int V = PosCell - H * 9;
          // initial cell pos in square
            final int Q = (H/3)*27 + (V/3)*3;
            
            // cell position in row
            int row;
            // cell position in column
            int column;
            // cell position in square
            int square;
            
            for ( int t = 0 ; t<9 ; ++t){
                row = H*9 + t;
                column = V + t*9;
                square = Q + t + (t/3)*6;
                
                if (Cells[ row ] == null) {
                    if ( ( avalaibleValues[ row ] & BITMASK ) == 0 ) {
                        avalaibleValues[ row ] = ( avalaibleValues[ row ] | BITMASK );
                        avalaibleValuesCount[ row ] += 1;
                    }
                }
                if (Cells[ column ] == null) {
                    if ( ( avalaibleValues[ column ] & BITMASK ) == 0 ) {
                        avalaibleValues[ column ] = ( avalaibleValues[ column ] | BITMASK );
                        avalaibleValuesCount[ column ] += 1;
                    }
                }
                if (Cells[ square ] == null) {
                    if ( ( avalaibleValues[ square ] & BITMASK ) == 0) {
                        avalaibleValues[ square ] = ( avalaibleValues[ square ] | BITMASK );
                        avalaibleValuesCount[ square ] += 1;
                    }
                }
            }
        }
            
        public void fillOnes() {
            int index = 0;          // cycle index
            int i = 0;              // inner counter
            int temp;               // temp variable shifted to right
            
            while (index<81) {
                if ( Cells[ index ] == null ) {
                    if ( avalaibleValuesCount[ index ] == 8 ) {
                        temp = avalaibleValues[ index ];
                        while ( (temp & 1) == 1 ) {
                            temp = temp >> 1 ;
                            ++i;
                        }
                        Cells[ index ] = gridSymbol.values()[ i ];
                        i = 0 ;
                        updatePossibility( index );
                        index = 0;
                    }
                }
               ++index;
            }
        }
        
        public boolean isSolution() {
            for ( gridSymbol index : Cells ) {
                    if ( index == null) {
                        return false;
                    }
            }
            return true;
        }
        
        public void setCell(int cellPosition , gridSymbol cellValue) {
            Cells[ cellPosition ] = cellValue;
        }
        
        public int minPossibilityCell() {
            int possibility = 0;
            int pos = 0;
            for (int i = 0; i < 81; ++i) {
                if (Cells[ i ] == null) {
                    if ( avalaibleValuesCount[ i ] > possibility ) {
                        possibility = avalaibleValuesCount[ i ];
                        pos = i;
                    }
                }
            }
            return pos;
        }
        
        public void print() {
            for(int i = 0 ; i<81 ; ++i){
                if ( Cells[ i ] == null ) {
                    System.out.print( 0 );
                } else {
                    System.out.print( Cells[ i ].ordinal() + 1 );
                }
                
                if ( (i+1) % 27 == 0 ){
                    System.out.println();
                    System.out.println();
                } else if ( (i+1) % 9 == 0 ) {
                    System.out.println();
                } else if ( (i+1) % 3 == 0 ) {
                    System.out.print("  ");
                } else {
                    System.out.print(" ");
                }
            }
        }
    }
}

La classe Sudoku può essere utilizzata in questo modo:

// Performance del seguente programma:
// circa 6.000 solutionspersec on T1000 (Athlon 1 GHZ)
// circa 15.000 solutionspersec on Pentium 4 HT 3 GHZ
//
public class TestConsole {
    public static void main( String[] args ) {
        int[] diabolic = {  0,1,4,  0,0,0,  9,5,0,
                                 0,0,8,  0,4,0,  2,0,0,
                                 0,9,0,  5,0,3,  0,6,0,

                                 0,0,0,  3,8,4,  0,0,0,
                                 7,0,0,  0,0,0,  0,0,6,
                                 0,0,0,  6,9,7,  0,0,0,

                                 0,4,0,  2,0,1,  0,8,0,
                                 0,0,1,  0,6,0,  3,0,0,
                                 0,5,2,  0,0,0,  6,1,0};
				 
            System.out.println("Start game...");
            Sudoku Game = new Sudoku( diabolic );
            Game.printGrid();
	    Game.solve();
	    System.out.println("Done");
            System.out.println("First Solution of the game:");
            System.out.println("Number of Solutions: " + Game.solutionsCount );
            System.out.println();
        }
    }

Il codice deve essere compilato installando un JDK versione 1.5 o seguente.
Alla prossima.

Differenza tra due date con LuaTeX


Il problema

Alcune volte ci troviamo a dover calcolare la differenza in giorni che intercorre tra due date. Se stiamo lavorando in un Word processor occorre rivolgersi ad uno strumento esterno come un foglio di calcolo, mentre con gli strumenti di tipografia asincrona (LaTeX e compagnia), linguaggi naturalmente estensibili, una macro risolverebbe brillantemente questo problema.

Una soluzione in Lua

I linguaggi come LaTeX o ConTeXt sono attualmente basati su TeX, il motore di composizione di Donald Knuth, perfetti per produrre documenti di elevata qualità, ma proprio per questo, non così facili da programmare.

Da qualche tempo il mondo TeX si sta preparando ad accogliere un nuovo motore di composizione basato sia su TeX stesso sia su Lua, un efficiente linguaggio di scripting portabile ed estensibile a sua volta: luatex.

Attualmente luatex è in fase di sviluppo, ma se sul vostro sistema è installata una distribuzione recente di LaTeX come la TeX Live 2009, probabilmente è già a vostra disposizione.

Utilizziamo la funzione os.time() della operating system library di Lua per tradurre le date in un unico valore numerico, il numero di secondi trascorsi da un certo epoch. A questo punto basta fare la differenza ed esprimere il risultato in giorni anziché in secondi ed il gioco è fatto. Ecco il frammento di codice:

local date1 = os.time({day=1,month=1,year=2010})
local date2 = os.time({day=28,month=7,year=2010})
local secperdays = 24*60*60
local daysdiff = (date2 - date1) / secperdays
print("Days difference: " .. daysdiff)

La funzione os.time() accetta una tabella con le tre chiavi day, month ed year. Nel codice abbiamo dunque racchiuso tra parentesi graffe la tabella nella constructor expression prevista dal linguaggio Lua.

Una soluzione in luatex

In luatex scriveremo dunque una macro utilizzando il classico comando \def per cui si prevede due argomenti: la data precedente e poi quella successiva dell’intervallo temporale:

\def\datediff#1#2{\directlua{
    local date1 = os.time({#1})
    local date2 = os.time({#2})
    local secperdays = 24*60*60
    local daysdiff = (date2 - date1) / secperdays

    tex.print(math.floor(daysdiff))}}

% inizio documento
Dalla mia nascita ad oggi sono trascorsi esattamente
\datediff{year=1900,month=1,day=1}{year=2010,month=1,day=10}
giorni.

Eppure mi pare un numero del tutto privo di emozioni...
\end

Salvate il codice in un file con estensione .tex e compilate il tutto con il comando:

luatex nomefile.tex

Nella directory trovere il file pdf di output con il risultato.
Le funzioni della libreria standard di Lua sono facili da usare e generalmente il codice è compatto ed efficiente. Così è facile prevedere una stagione ancora più ricca per gli utenti di LaTeX e compagnia.

Alla prossima. Gulp.

%d blogger hanno fatto clic su Mi Piace per questo: