Geometry

boogle

/*
 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 3 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, see <http://www.gnu.org/licenses/>.
 */
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
 
/**
 * The driver class
 * 
 * @author $Author: Kandy Software Inc.$
 * @version $Revision: 1.0 $
 */
public class Boggle {
 
    private boolean DEBUG = false;
 
    private int rows;
 
    private int columns;
 
    private char[][] theBoard;
 
    private String[] theWords;
 
    private BufferedReader puzzleStream;
 
    private BufferedReader wordStream;
 
    private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
    public Boggle() throws IOException {
        // open boggle file
        puzzleStream = openFile("Enter boggle file");
 
        // open dictionary file
        wordStream = openFile("Enter dictionary name");
        System.out.println("Reading files...");
 
        readPuzzle();
 
        readWords();
 
        if (DEBUG) {
            System.setOut(new PrintStream(new FileOutputStream("out.txt")));
        }
    }
 
    /**
     * Routine to solve the word search puzzle. Performs checks in all eight
     * directions.
     * 
     * @return number of matches
     */
    public Map<String, List<Position>> solveBoggle() {
        Map<String, List<Position>> results = new TreeMap<String, List<Position>>();
        List<Position> path = new ArrayList<Position>();
 
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < columns; c++) {
                solve(new Position(r, c), "", path, results);
            }
        }
 
        return results;
    }
 
    private void solve(Position thisPos, String charSequence, List<Position> pathParam,
            Map<String, List<Position>> results) {
        // The current position
        int row = thisPos.getRow();
        int column = thisPos.getColumn();
 
        // Make a copy of path we traversed so far
        List<Position> path = new ArrayList<Position>();
        path.addAll(pathParam);
 
        // Add current position to the path
        path.add(thisPos);
 
        // Append the letter in the current position to charSequence
        charSequence += theBoard[row][column];
        if (DEBUG)
            System.out.println(charSequence);
 
        // If the prefix doesn't exist in the dictionary return ...
        int index = prefixSearch(theWords, charSequence);
        if (index == theWords.length) {
            return;
        }
 
        // Otherwise check if the prefix is itself a word. If it is a word
        // add to the results map.
        if (charSequence.equalsIgnoreCase(theWords[index])) {
            results.put(charSequence, path);
        }
 
        // Find neighbors for this position and for each neighbor call solve if
        // the
        // neighbor is not used already
        Set<Position> neighbors = thisPos.findAdjacents(rows, columns);
        if (DEBUG)
            System.out.println(neighbors);
        for (Position p : neighbors) {
            if (!path.contains(p)) {
                solve(p, charSequence, path, results);
            }
        }
    }
 
    /**
     * Gives the points for a word
     * 
     * @return
     */
    private final int getPoints(int wordLength) {
        if (wordLength < 3) {
            return 0;
        }
        switch (wordLength) {
        case 3:
            return 1;
        case 4:
            return 2;
        case 5:
            return 3;
        case 6:
            return 4;
        case 7:
            return 6;
        case 8:
            return 10;
        default:
            return 15;
        }
    }
 
    /**
     * Takes in a set of words and calculates score based on the rule map
     * 
     * @param keys
     * @return
     */
    private void printScores(Map<String, List<Position>> map) {
        Set<String> keys = map.keySet();
 
        // If number of words is less than 200
        // print them all out
        if (keys.size() < 200) {
            System.out.println("Word            | Points | Path");
            System.out.println("----------------+--------+-----------------------");
            for (String aKey : keys) {
                System.out.printf("%15s | %6d | %s\n", aKey, getPoints(aKey.length()), map.get(aKey));
            }
            return;
        }
 
        // If more than 200 words are found, print a summary
        System.out.println("More than 200 words found! Printing brief summary:");
        System.out.println("--------------------------------------------------");
 
        int length = 0;
        Map<Integer, Integer> summary = new TreeMap<Integer, Integer>();
        for (String aKey : keys) {
            length = aKey.length();
            if (length >= 8) {
                System.out.printf("%s (%d points)\n", aKey, getPoints(length));
            } else {
                Integer count = summary.get(length);
                count = count == null ? 1 : (count + 1);
                summary.put(length, count);
            }
        }
        System.out.println();
        for (Integer count : summary.keySet()) {
            System.out.printf("Words with %2d chars: %2d\n", count, summary.get(count));
        }
    }
 
    /**
     * Performs the binary search for word search.
     * 
     * @param a
     *            the sorted array of strings.
     * @param x
     *            the string to search for.
     * @return last position examined; this position either matches x, or x is a
     *         prefix of the mismatch, or there is no word for which x is a
     *         prefix.
     */
    private static int prefixSearch(String[] a, String x) {
        int idx = Arrays.binarySearch(a, x);
 
        if (idx < 0)
            return -idx - 1;
        else
            return idx;
    }
 
    /**
     * Print a prompt and open a file. Retry until open is successful. Program
     * exits if end of file is hit.
     */
    private BufferedReader openFile(String message) {
        String fileName = "";
        FileReader theFile;
        BufferedReader fileIn = null;
        do {
            System.out.println(message + ": ");
            try {
                fileName = in.readLine();
                if (fileName == null)
                    System.exit(0);
                theFile = new FileReader(fileName);
                fileIn = new BufferedReader(theFile);
            } catch (IOException e) {
                System.err.println("Cannot open " + fileName);
            }
        } while (fileIn == null);
 
        System.out.println("Opened " + fileName);
        return fileIn;
    }
 
    /**
     * Routine to read the grid. Checks to ensure that the grid is rectangular.
     * Checks to make sure that capacity is not exceeded is omitted.
     */
    private void readPuzzle() throws IOException {
        String oneLine;
        List<String> puzzleLines = new ArrayList<String>();
 
        if ((oneLine = puzzleStream.readLine()) == null) {
            throw new IOException("No lines in puzzle file");
        }
 
        columns = oneLine.length();
        puzzleLines.add(oneLine);
 
        while ((oneLine = puzzleStream.readLine()) != null) {
            if (oneLine.length() != columns)
                System.err.println("Puzzle is not rectangular; skipping row");
            else
                puzzleLines.add(oneLine);
        }
 
        rows = puzzleLines.size();
        theBoard = new char[rows][columns];
 
        int r = 0;
        for (String theLine : puzzleLines) {
            // the lines of the file are converted to a 2 dim array of charts
            theBoard[r++] = theLine.toCharArray();
        }
    }
 
    /**
     * Routine to read the dictionary. Error message is printed if dictionary is
     * not sorted.
     */
    private void readWords() throws IOException {
        List<String> words = new ArrayList<String>();
 
        String lastWord = null;
        String thisWord;
 
        while ((thisWord = wordStream.readLine()) != null) {
            if (thisWord.trim().length() == 0) {
                continue;
            }
            if (lastWord != null && thisWord.compareTo(lastWord) < 0) {
                System.err.println("Dictionary is not sorted... skipping");
                continue;
            }
            words.add(thisWord);
            lastWord = thisWord;
        }
 
        theWords = new String[words.size()];
        theWords = words.toArray(theWords);
    }
 
    public static void main(String[] args) {
        Boggle p = null;
        try {
            p = new Boggle();
        } catch (IOException e) {
            System.out.println("IO Error: ");
            e.printStackTrace();
            return;
        }
 
        System.out.println("Solving...");
        Map<String, List<Position>> map = p.solveBoggle();
        p.printScores(map);
    }
}

http://www.ardendertat.com/2012/01/09/programming-interview-questions/
http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529

http://www.cnblogs.com/shuaiwhu/archive/2012/06/26/2560284.html
http://tianrunhe.wordpress.com/2012/07/24/convert-an-integer-to-a-roman-numeral-integer-to-roman/

http://tristan-interview.blogspot.com/search/label/dynamic%20programming

http://sudhansu-codezone.blogspot.com/search/label/Strings

http://blog.theliuy.com/
https://haixiaoyang.wordpress.com/page/18/
https://sites.google.com/site/sarvasite/algorithms/trees/tree-traversal#TOC-Post-order-traversal-without-visited-flag-

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License