Groovy example source code file (magicsquares.java)

This example Groovy source code file (magicsquares.java) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Groovy tags/keywords

arraylist, arraylist, classcastexception, comparable, ffmresult, ffmresult, hashset, integer, integer, io, pqnode, pqnode, string, stringbuilder, util

The Groovy magicsquares.java source code

/* The Computer Language Shootout
   http://shootout.alioth.debian.org/

   benchmark implementation (not optimized)
   JRE 1.5 only
   contributed by Josh Goldfoot */

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

public class magicsquares {
    
    static int n;
    static int mn;
    
    public static class FfmResult {
        public int x;
        public int y;
        public int[] moves;
        public FfmResult(int ix, int iy, int[] imoves) {
            x = ix;
            y = iy;
            moves = (int[]) imoves.clone();
        }
    }
    
    public static class PQNode implements Comparable {
        public int [] grid;
        boolean priorityCalculated;
        private int priority;
        private FfmResult ffm;
        
        public PQNode() {
            grid = new int [n * n];
            int i;
            for (i = 0; i < n * n; i++)
                grid[i] = 0;
            priorityCalculated = false;
            ffm = null;
        }
        public PQNode(PQNode other) {
            grid = (int[]) other.grid.clone();
            priorityCalculated = false;
        }

        public int[] gridRow(int y) {
            int[] r = new int[n];
            int x;
            for (x = 0; x < n; x++)
                r[x] = grid[x + y * n];
            return r;
        }

        public int[] gridCol(int x) {
            int[] r = new int[n];
            int y;
            for (y = 0; y < n; y++)
                r[y] = grid[x + y * n];
            return r;
        }

        public int[] diagonal(int q) {
            int[] r = new int[n];
            int i;
            for (i = 0; i < n; i++) {
                if (q == 1)
                    r[i] = grid[i + i * n];
                else if (q == 2) {
                    r[i] = grid[i + (n - 1 - i) * n];
                }
            }
            return r;
        }

        public int[] possibleMoves(int x, int y) {
            int zerocount, sum, highest, j, i;
            
            if (grid[x + y * n] != 0)
                return ( new int [] { });
            ArrayList<int[]> cellGroups = new ArrayList();
            cellGroups.add(gridCol(x));
            cellGroups.add(gridRow(y));
            if (x == y)
                cellGroups.add(diagonal(1));
            if (x + y == n - 1)
                cellGroups.add(diagonal(2));
            HashSet<Integer> usedNumbers = new HashSet();
            for (i = 0; i < grid.length; i++)
                usedNumbers.add(new Integer(grid[i]));
            HashSet<Integer> onePossible = new HashSet();
            highest = n * n;
            for (int[] group: cellGroups) {
                zerocount = 0;
                sum = 0;
                for (int num: group) {
                    if (num == 0)
                        zerocount++;
                    sum += num;
                }
                if (zerocount == 1)
                    onePossible.add(new Integer(mn - sum));
                if (mn - sum < highest)
                    highest = mn - sum;
            }
            if (onePossible.size() == 1) {
                Integer onlyPossibleMove = (Integer) onePossible.iterator().next();
                int opmint = onlyPossibleMove.intValue();
                if (opmint >= 1 && 
                        opmint <= n * n && 
                        ! usedNumbers.contains(onlyPossibleMove))
                    return (new int[] { opmint });
                else
                    return ( new int [] { });
            } else if (onePossible.size() > 1)
                return ( new int [] { });
            ArrayList<Integer> moves = new ArrayList();
            for (i = 1; i <= highest; i++) {
                Integer ii = new Integer(i);
                if (! usedNumbers.contains(ii))
                    moves.add(ii);
            }
            int[] r = new int[moves.size()];
            i = 0;
            for (Integer move: moves) {
                r[i++] = move.intValue();
            }
            return r;
        }

        public FfmResult findFewestMoves() {
            if (ffm != null)
                return ffm;
            int x, y, mx, my, ind;
            int[] minmoves = (new int[] { });
            int[] moves;
            mx = my = -1;
            for (y = 0; y < n; y++)
                for (x = 0; x < n; x++) {
                    ind = x + y * n;
                    if (grid[ind] == 0) {
                        moves = possibleMoves(x,y);
                        if (mx == -1 || moves.length < minmoves.length) {
                            mx = x;
                            my = y;
                            minmoves = (int[]) moves.clone();
                        }
                    }
                }
            ffm = new FfmResult(mx, my, minmoves);
            return ffm;
        }
        
        public void calculatePriority()
        {
            int i, zerocount;
            zerocount = 0;
            for (int cell: grid)
                if (cell == 0)
                    zerocount++;
            priority = zerocount + findFewestMoves().moves.length;
            priorityCalculated = true;
        }
        
        public int getPriority()
        {
            if (priorityCalculated)
                return priority;
            else {
                calculatePriority();
                return priority;
            }
        }
        
        public int compareTo(Object anotherMSquare) throws ClassCastException {
            if (!(anotherMSquare instanceof PQNode))
                throw new ClassCastException();
            PQNode other = (PQNode) anotherMSquare;
            int c = getPriority() - other.getPriority();
            if (c == 0) {
                int i = 0;
                while (c == 0 && i < n * n) {
                    c = grid[i] - other.grid[i];
                    i++;
                }
            }
            return c;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            int y, x;
            for (y = 0; y < n; y++) {
                for (x = 0; x < n; x++) {
                    sb.append(grid[x + y * n]);
                    if (x < n-1)
                        sb.append(' ');
                }
                if (y < n-1)
                    sb.append('\n');
            }
            return sb.toString();
        }

        
    }
    
    public magicsquares() { }
    
    public static void main(String[] args) {
        n = 3;
        if (args.length > 0) 
            n = Integer.parseInt(args[0]);
        mn = n * (1 + n * n) / 2;
        PriorityQueue<magicsquares.PQNode> pq = new PriorityQueue(); 
        pq.offer(new magicsquares.PQNode() );
        while (! pq.isEmpty()) {
            PQNode topSquare = pq.poll();
            if (topSquare.getPriority() == 0) {
                System.out.println(topSquare);
                break;
            }
            magicsquares.FfmResult result = topSquare.findFewestMoves();

            int ind = result.x + result.y * n;
            for (int move: result.moves) {
                magicsquares.PQNode newSquare = new magicsquares.PQNode(topSquare);
                newSquare.grid[ind] = move;
                pq.offer(newSquare);
            }
        }
                
    }
}