Skip to content

Instantly share code, notes, and snippets.

@alcedo

alcedo/Problem_123.java

Created October 24, 2013 06:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save alcedo/7132198 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save alcedo/7132198 to your computer and use it in GitHub Desktop.
Download ZIP
UVA Problem Sets
Raw
Problem_123.java
import java.io.BufferedOutputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import static java.lang.System.out;
//NOTE THIS CODE ISNT WORKING ie: theres a run time error :(
/**
* Use this file to submit. UVA only accepts class Main
*/
public class Main {
public static final boolean DEBUG = false;
public static void main(String[] args) throws IOException {
BufferedOutputStream output = new BufferedOutputStream(System.out);
InputReader input = new InputReader(System.in);
StringBuilder sb = new StringBuilder(2000); //assume initial size of 2000 chars
HashSet<String> ignoreList = new HashSet<String>();
ArrayList<MyChar> kwicList = new ArrayList<MyChar>();
String str;
// extract ignore list
while((str = input.readLine()).compareTo("::") != 0 ) {
ignoreList.add(str.toUpperCase());
}
int index = 0;
while((str = input.readLine()).length() > 0 ) {
HashSet<String> keyWordList = removeIgnoreWords(ignoreList, str); //strip away ignore words and store.
for(String key : keyWordList) {
kwicList.add(new MyChar(key, str, index));
}
index++;
}
Collections.sort(kwicList, new CustomComparator());
for(int i=0; i<kwicList.size(); i++){
out.print(kwicList.get(i).output());
}
output.write(sb.toString().getBytes());
output.flush();
output.close();
}// end of static void main
// Given a string, remove words within the ignoreList, and return the remaining strings as a List<String>
public static HashSet<String> removeIgnoreWords(HashSet<String> ignoreList, String str) {
HashSet<String> keyWordList = new HashSet<String>();
StringTokenizer st = new StringTokenizer(str);
while(st.hasMoreTokens())
keyWordList.add(st.nextToken().toUpperCase());
keyWordList.removeAll(ignoreList);
return keyWordList;
}
// Simple Tuple Class
static class MyChar {
public String keyword; // order in the input file
public String phrase;
public int index;
public MyChar(String keyword, String phrase, int index) {
this.keyword = keyword.toLowerCase();
this.phrase = phrase.toLowerCase();
this.index = index;
}
public String toString(){
return keyword + ":" + phrase + " idx: " + index;
}
public String output() {
StringBuilder sb = new StringBuilder();
// find all occurrences of keyword in the phrase and caps them
int posn = 0;
int index = 0;
while((index = phrase.indexOf(keyword, posn))!= -1){
// out.println("pos: " + posn + " index: " + index);
posn = index + keyword.length(); // scan for keyword in new position marker
String s1 = phrase.substring(0, index); //string part before the keyword
String s2 = phrase.substring( index+keyword.length() ); //string part after the keyword
if(s1.endsWith(" ") || s1.length() == 0)
sb.append(s1).append(keyword.toUpperCase()).append(s2).append("\n");
// out.println("s1[" + s1 + "], keyword:[" + keyword + "], s2:[" + s2 + "]");
}
return sb.toString();
}
}
static class CustomComparator implements Comparator<MyChar> {
@Override
public int compare(MyChar o1, MyChar o2) {
String o1String = o1.keyword + o1.index;
String o2String = o2.keyword + o2.index;
return o1String.compareTo(o2String);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readLine() {
int c = read();
while (isSpaceChar(c)) {
c = read();
if(c == -1) return ""; //note: theres no ASCII -1 value, -1 signify EOF, and we return empty string
}
StringBuilder res = new StringBuilder();
while (!isNewLineChar(c)) {
res.appendCodePoint(c);
c = read();
if(c == -1) break;
}
return res.toString();
}
public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public boolean isNewLineChar(int c) {
return c == '\n' || c == '\r' || c == -1;
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object...objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
public void flush() {
writer.flush();
}
}
static class IOUtils {
public static int[] readIntArray(InputReader in, int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}
}
}//End of Main Class
/**************************************************************************
* Fast I/O functions (prevents i/o flushing by buffering)
**************************************************************************/
//BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
/*
Slightly less efficient
BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
output.write(stringBuilder.toString());
More efficient:
BufferedOutputStream output = new BufferedOutputStream(System.out); // more efficient
output.write(stringBuilder.toString().getBytes());
*/
//or we can use the below utilitiy classes:
/**
* Various utility class for Fast I/O in java.
* Readings: http://www.codechef.com/wiki/java#IO_in_Java
* BufferedInputStream > BufferedReader > Scanner
*
* USAGE:
* InputReader in = new InputReader(System.in);
* OutputWriter out = new OutputWriter(System.out);
*
* int i = in.readInt(); //read int
* String s = in.readString(); //read string
* int[] x = IOUtils.readIntArray(in,N); //read int array of size N
* String s = in.readLine() // read a line ( to be used with tokenizer );
*
* out.printLine("X");
*
* out.flush(); // flush output
* out.close(); // remember to close the outputstream, at the end (might be able to not do this to save some time)
*/
Raw
Problem_414.java
import java.io.BufferedOutputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.StringTokenizer;
import static java.lang.System.out;
/**
* Use this file to submit. UVA only accepts class Main
*/
public class Main {
public static final boolean DEBUG = false;
public static void main(String[] args) throws IOException {
BufferedOutputStream output = new BufferedOutputStream(System.out);
InputReader input = new InputReader(System.in);
StringBuilder sb = new StringBuilder(2000); //assume initial size of 2000 chars
String str;
while((str = input.readLine()).length() > 0) {
StringTokenizer stringTokenizer = new StringTokenizer(str);
int rows = Integer.parseInt(stringTokenizer.nextToken());
if(rows == 0) break;
// out.println("rows: " + rows);
ArrayList<Integer> spaceTracker = new ArrayList<Integer>();
for(int i=0; i<rows; i++) {
int spaceCount = 0;
char[] line = input.readLine().toCharArray();
for(int j=0; j<line.length; j++) {
if(line[j] == ' ') spaceCount++;
}
spaceTracker.add(spaceCount);
}
// smallest value is at posn 0, find difference b/w this and the rest to get soln
int ans = 0;
Collections.sort(spaceTracker);
for(int i=1; i<spaceTracker.size(); i++) {
ans += spaceTracker.get(i) - spaceTracker.get(0);
}
sb.append(ans).append("\n");
}
output.write(sb.toString().getBytes());
output.flush();
output.close();
}// end of static void main
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readLine() {
int c = read();
//theres no ASCII -1 value. this signify EOF, and we return empty string
if(c == -1) return "";
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (c != '\n' );
return res.toString();
}
public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object...objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
public void flush() {
writer.flush();
}
}
static class IOUtils {
public static int[] readIntArray(InputReader in, int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}
}
}//End of Main Class
/**************************************************************************
* Fast I/O functions (prevents i/o flushing by buffering)
**************************************************************************/
//BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
/*
Slightly less efficient
BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
output.write(stringBuilder.toString());
More efficient:
BufferedOutputStream output = new BufferedOutputStream(System.out); // more efficient
output.write(stringBuilder.toString().getBytes());
*/
//or we can use the below utilitiy classes:
/**
* Various utility class for Fast I/O in java.
* Readings: http://www.codechef.com/wiki/java#IO_in_Java
* BufferedInputStream > BufferedReader > Scanner
*
* USAGE:
* InputReader in = new InputReader(System.in);
* OutputWriter out = new OutputWriter(System.out);
*
* int i = in.readInt(); //read int
* String s = in.readString(); //read string
* int[] x = IOUtils.readIntArray(in,N); //read int array of size N
* String s = in.readLine() // read a line ( to be used with tokenizer );
*
* out.printLine("X");
*
* out.flush(); // flush output
* out.close(); // remember to close the outputstream, at the end (might be able to not do this to save some time)
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment