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-