CS 106A Final Review - Problem Solving and Bug Identification Practices

Final Review Eric Roberts CS 106A March 13, 2016

Problem 1aPractice #1 private void mystery(int[] array) { int tmp = array[array.length - 1]; for ( int i = 1 ; i < array.length ; i++ ) { array[i] = array[i - 1]; } array[0] = tmp; } i tmp array 1 2 3 4 5 50 10 50 20 10 30 10 40 10 50 10 0 1 2 3 4

Problem 1aPractice #2 public void run() { int[] array = new int[13]; for (int i = 1; i <= 12; i++) { for (int j = i; j > 0; j--) { array[j] += j; } } } i j array 0 0 1 2 3 4 5 6 7 8 9 10 11 12 10 12 14 16 18 20 22 0 2 4 6 8 12 15 18 21 24 27 30 0 3 6 9 12 16 20 24 28 32 36 0 4 8 10 15 20 25 30 35 40 0 5 12 18 24 30 36 42 0 6 14 21 28 35 42 0 7 16 24 32 40 0 8 18 27 36 0 9 10 20 30 0 0 11 22 12 0 0 1 2 3 4 5 6 7 8 9 10 11 12

Problem 1aPractice #2

Bug IdentificationPractice #1 public boolean isAlphabeticallyOrdered(String[] array) { for ( int i = 0 ; i <= array.length ; i++ ) { if ( array[i] > array[i + 1] ) { This test is off by two and should read i < array.length - 1 This test doesn t compile and should read array[i].compareTo(array[i+1] > 0 return false; } else { return true; } This return statement must be outside the loop } }

Bug IdentificationPractice #2 private String acronym(String str) { The variable result needs to be declared here. boolean inWord = false; for ( int i = 0 ; i < str.length() ; i++ ) { char ch = str.charAt(i); This test doesn t compile and should read Character.isLetter(ch) if ( ch.isLetter() ) { if (!inWord) result += ch; The variable inWord must be set to truehere. } else { inWord = false; } } return result; }

Problem 2Practice #1 Write a method private GCompound createPieChart(double r, double[] data) that creates a GCompound object for a pie chart with the specified data values, where r represents the radius of the circle, and data is the array of data values you want to plot.

The createPieChart Method /** * Creates a GCompound object that represents a pie chart composed * of the data in the array. The reference point of the GCompound * is the center of the circle. */ private GCompound createPieChart(double r, double[] data) { GCompound gc = new GCompound(); double total = sumArray(data); double start = 0; for (int i = 0; i < data.length; i++) { double sweep = 360.0 * data[i] / total; GArc arc = new GArc(-r, -r, 2 * r, 2 * r, start, sweep); arc.setFilled(true); arc.setFillColor(WEDGE_COLORS[i % WEDGE_COLORS.length]); gc.add(arc); start += sweep; } return gc; } page 1 of 2

The createPieChart Method /** * Creates a GCompound object that represents a pie chart composed * of the data in the array. The reference point of the GCompound * is the center of the circle. */ double total = 0; for (int i = 0; i < array.length; i++) { total += array[i]; } return total; } /** * Returns the sum of the array. */ private double sumArray(double[] array) { private GCompound createPieChart(double r, double[] data) { GCompound gc = new GCompound(); double total = sumArray(data); double start = 0; for (int i = 0; i < data.length; i++) { double sweep = 360.0 * data[i] / total; GArc arc = new GArc(-r, -r, 2 * r, 2 * r, start, sweep); arc.setFilled(true); arc.setFillColor(WEDGE_COLORS[i % WEDGE_COLORS.length]); gc.add(arc); start += sweep; } return gc; } page 2 of 2

Problem 2Practice #2 Write a GraphicsProgram that implements removing one, two, or three coins from a line of coins.

The GraphicNimApplication public class GraphicNim extends GraphicsProgram { public void init() { setupCoins(); addMouseListeners(); } public void mouseClicked(MouseEvent e) { GObject obj = getElementAt(e.getX(), e.getY()); if (obj != null) { int index = coinList.indexOf(obj); if (index >= Math.max(0, coinList.size() - 3)) { for (int i = coinList.size() - 1; i >= index; i--) { remove(coinList.get(i)); coinList.remove(i); } } } } page 1 of 2

The GraphicNim Application public class GraphicNim extends GraphicsProgram { private void setupCoins() { double widthNeeded = N_COINS * COIN_SIZE + (N_COINS - 1) * COIN_SEP; double x = (getWidth() - widthNeeded) / 2; double y = (getHeight() - COIN_SIZE) / 2; coinList = new ArrayList<GObject>(); for (int i = 0; i < N_COINS; i++) { GOval coin = new GOval(x, y, COIN_SIZE, COIN_SIZE); coin.setFilled(true); coin.setFillColor(Color.GRAY); add(coin); coinList.add(coin); x += COIN_SIZE + COIN_SEP; } } public void init() { setupCoins(); addMouseListeners(); } public void mouseClicked(MouseEvent e) { GObject obj = getElementAt(e.getX(), e.getY()); if (obj != null) { int index = coinList.indexOf(obj); if (index >= Math.max(0, coinList.size() - 3)) { for (int i = coinList.size() - 1; i >= index; i--) { remove(coinList.get(i)); coinList.remove(i); } } } } private ArrayList<GObject> coinList; /* Private instance variables */ } page 2 of 2

Problem 3Practice #1 Write a program called CheckWordLadder that checks if a sequence of words forms a valid word-ladder chain in which each word differs from the previous word in only one letter position. The example at the bottom of the slide checks a word ladder from GOOD to LUCK. CheckWordLadder Program to check a word ladder Enter a sequence of words ending with a blank line GOOD LUCK That word is not legal. Try again. GOOP LOOP LOCP That word is not legal. Try again. LOOK LOCK LUCK

The CheckWordLadder Application /* Program to check a word ladder */ public class CheckWordLadder extends ConsoleProgram { public void run() { println("Program to check a word ladder."); println("Enterasequenceofwordsendingwithablank line."); String previous = "-"; String current = "-"; while (!current.equals("")) { while (true) { current = readLine(); if (current.equals("") || isLegalPair(previous, current)) break; println("That word is not legal. Try again."); } previous = current; } } page 1 of 2

The CheckWordLadder Application /* Program to check a word ladder */ private boolean isLegalPair(String previous, String current) { if (!english.contains(current)) return false; if (previous.equals("-")) return true; if (previous.length() != current.length()) return false; return countCharacterDifferences(previous, current) == 1; } public class CheckWordLadder extends ConsoleProgram { public void run() { println("Program to check a word ladder."); println("Enterasequenceofwordsendingwithablankline."); String previous = "-"; String current = "-"; while (!current.equals("")) { while (true) { current = readLine(); if (current.equals("") || isLegalPair(previous, current)) break; println("That word is not legal. Try again."); } previous = current; } } } private int countCharacterDifferences(String s1, String s2) { int count = 0; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) != s2.charAt(i)) count++; } return count; } /* Private instance variables */ private Lexicon english = new Lexicon("EnglishWords.txt"); page 2 of 2

Problem 3Practice #2 Write a method public boolean isAnagram(String s1, String s2) that returns true if s1 and s2 contain the same letters, even though they may be rearranged. Upper- and lowercase characters are considered the same, and all characters other than letters are ignored. For example, each of the following calls to isAnagram returns true: isAnagram("O, Draconian devil!", "Leonardo da Vinci") isAnagram("Oh, lame saint!", "The Mona Lisa") isAnagram("ALGORITHMICALLY", "logarithmically") isAnagram("Doctor Who", "Torchwood")

The isAnagram Method /* Returns true if s1 and s2 are anagrams of each other */ private boolean isAnagram(String s1, String s2) { int[] table1 = createFrequencyTable(s1); int[] table2 = createFrequencyTable(s2); for (int i = 0; i < table1.length; i++) { if (table1[i] != table2[i]) return false; } return true; } /* Creates a letter-frequency table for the string */ private int[] createFrequencyTable(String str) { int[] letterCounts = new int[26]; for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if (Character.isLetter(ch)) { letterCounts[Character.toUpperCase(ch) - 'A']++; } } return letterCounts; }

Problem 4Practice #1 Write a method private GImage doubleImage(GImage oldImage) that returns an image in which every pixel in the original image is replaced by a square of four pixels in the result.

The doubleImage Method /* * Returns an image that is twice the size of the original in each * dimension. Each pixel in the original is replicated so that * it appears as a square of four pixels in the new image. */ private GImage doubleImage(GImage image) { int[][] oldPixels = image.getPixelArray(); int height = oldPixels.length; int width = oldPixels[0].length; int[][] newPixels = new int[2 * height][2 * width]; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { int pixel = oldPixels[i][j]; newPixels[2 * i][2 * j] = pixel; newPixels[2 * i][2 * j + 1] = pixel; newPixels[2 * i + 1][2 * j] = pixel; newPixels[2 * i + 1][2 * j + 1] = pixel; } } return new GImage(newPixels); }

Problem 4Practice #2 Write a method private void rotateRight(double[] array) that has the effect of shifting every element one position rightward toward the end of the array, with the exception of the last element, which gets moved to the first position. 3.14 2.72 98.6 6.28 22.5 42.0 0 1 2 3 4 5

The rotateRight Method /** * Rotates all elements in the array rightward one position. Each * of the elements from index 0 to index N - 2 moves to the next * higher index position, and the last element becomes the first. * * @param array The array being rotated */ private void rotateRight(double[] array) { int n = array.length; if (n == 0) return; double last = array[n - 1]; for (int i = n - 1; i > 0; i--) { array[i] = array[i - 1]; } array[0] = last; }

Problem 5Practice #1 Implement the EtchASketch application, which draws lines in the directions indicated by the buttons.

The EtchASketch Application public class EtchASketch extends GraphicsProgram { public void init() { add(new JButton("North"), SOUTH); add(new JButton("South"), SOUTH); add(new JButton("East"), SOUTH); add(new JButton("West"), SOUTH); add(new JButton("South"), SOUTH); addActionListeners(); } public void run() { double delta = CROSS_SIZE / 2; cross = new GCompound(); cross.add(new GLine(-delta, -delta, delta, delta)); cross.add(new GLine(-delta, delta, delta, -delta)); add(cross, getWidth() / 2, getHeight() / 2); } page 1 of 3

The EtchASketch Application public class EtchASketch extends GraphicsProgram { /* Called when an action event is detected */ public void init() { add(new JButton("North"), SOUTH); add(new JButton("South"), SOUTH); add(new JButton("East"), SOUTH); add(new JButton("West"), SOUTH); add(new JButton("South"), SOUTH); addActionListeners(); } moveCross(STEP_SIZE, 0); } else if (cmd.equals("West")) { moveCross(-STEP_SIZE, 0); } else if (cmd.equals("Clear")) { removeAll(); add(cross, getWidth() / 2, getHeight() / 2); } } public void actionPerformed(ActionEvent e) { String cmd = e.getActionCommand(); if (cmd.equals("North")) { moveCross(0, -STEP_SIZE); } else if (cmd.equals("South")) { moveCross(0, STEP_SIZE); } else if (cmd.equals("East")) { public void run() { double delta = CROSS_SIZE / 2; cross = new GCompound(); cross.add(new GLine(-delta, -delta, delta, delta)); cross.add(new GLine(-delta, delta, delta, -delta)); add(cross, getWidth() / 2, getHeight() / 2); } page 2 of 3

The EtchASketch Application /* Called when an action event is detected */ /* * Moves the cross and adds a red line to the canvas connecting * its old and new positions. */ public void actionPerformed(ActionEvent e) { String cmd = e.getActionCommand(); if (cmd.equals("North")) { moveCross(0, -STEP_SIZE); } else if (cmd.equals("South")) { moveCross(0, STEP_SIZE); } else if (cmd.equals("East")) { moveCross(STEP_SIZE, 0); } else if (cmd.equals("West")) { moveCross(-STEP_SIZE, 0); } else if (cmd.equals("Clear")) { removeAll(); add(cross, getWidth() / 2, getHeight() / 2); } } private GCompound cross; private double x; private double y; private void moveCross(double dx, double dy) { GLine line = new GLine(x, y, x + dx, y + dy); line.setColor(Color.RED); add(line); x += dx; y += dy; cross.move(dx, dy); } /* Private instance variables */ } page 3 of 3

Problem 5Practice #2 Implement the Piggs application, which keeps track of the number of clicks on each pig image. 0 0 0 0 1 0

The Pigg Application public class Pigg extends GraphicsProgram { public void init() { readPiggData(DATA_FILE); addMouseListeners(); } private void readPiggData(String dataFile) { try { BufferedReader rd = new BufferedReader(new FileReader(dataFile)); while (true) { String imageName = rd.readLine(); if (imageName == null) break; addPiggEntry(new GImage(imageName)); } rd.close(); } catch (IOException ex) { throw new ErrorException(ex); } } page 1 of 3

The Pigg Application public class Pigg extends GraphicsProgram { /* Adds a new Pigg entry to the graphics window */ public void init() { readPiggData(DATA_FILE); addMouseListeners(); } double x = (imageToLabel.size() + 0.5) * CELL_WIDTH; add(image, x - image.getWidth() / 2, 0); add(score); centerScoreUnderImage(score, image); imageToLabel.put(image, score); } private void addPiggEntry(GImage image) { GLabel score = new GLabel("0"); score.setFont("SansSerif-16"); private void readPiggData(String dataFile) { try { BufferedReader rd = new BufferedReader(new FileReader(dataFile)); while (true) { String imageName = rd.readLine(); if (imageName == null) break; addPiggEntry(new GImage(imageName)); } rd.close(); } catch (IOException ex) { throw new ErrorException(ex); } } } /* Repositions the label so that it is centered under the image */ private void centerScoreUnderImage(GLabel score, GImage image) { double x = image.getX() + (image.getWidth() - score.getWidth()) / 2; score.setLocation(x, CELL_HEIGHT + score.getAscent()); page 2 of 3

The Pigg Application /* Adds a new Pigg entry to the graphics window */ /* * Updates the score of the associated label when the mouse is * clicked on a Pigg image. */ private void addPiggEntry(GImage image) { GLabel score = new GLabel("0"); score.setFont("SansSerif-16"); double x = (imageToLabel.size() + 0.5) * CELL_WIDTH; add(image, x - image.getWidth() / 2, 0); add(score); centerScoreUnderImage(score, image); imageToLabel.put(image, score); } if (score != null) { int count = Integer.parseInt(score.getLabel()) + 1; score.setLabel("" + count); centerScoreUnderImage(score, image); } } } public void mouseClicked(MouseEvent e) { GObject obj = getElementAt(e.getX(), e.getY()); if (obj instanceof GImage) { GImage image = (GImage) obj; GLabel score = imageToLabel.get(image); /* Repositions the label so that it is centered under the image */ private void centerScoreUnderImage(GLabel score, GImage image) { double x = image.getX() + (image.getWidth() - score.getWidth()) / 2; score.setLocation(x, CELL_HEIGHT + score.getAscent()); } page 3 of 3

Problem 6Practice #1 Write an application that computes the rebate that Morgan Stanley owes customers from delays on the Facebook IPO. This calculation requires the following sequence of actions: 1. Reads in the date and time at which the customer ordered the sale. 2. Reads in the date and time at which the sale actually took place. 3. Reads in the number of shares involved. 4. Calculates the refund due to the customer. 5. Prints out the refund value or a message No refund due .

The FacebookRefund Application public class FacebookRefund extends ConsoleProgram { public void run() { Map<Date,Double> sharePrice = readData("FBSharePrice.txt"); Date ordered = stringToDate(readLine("Sell ordered at: ")); Date executed = stringToDate(readLine("Sell executed at: ")); int nShares = readInt("Number of shares: "); if (sharePrice.containsKey(ordered) && sharePrice.containsKey(executed)) { double amountPaid = nShares * sharePrice.get(executed); double amountDue = nShares * sharePrice.get(ordered); double balance = amountDue - amountPaid; if (balance > 0) { println("Refund due of $" + balance); } else { println("No refund due"); } } else { println("No shares sold at that time"); } } page 1 of 3

The FacebookRefund Application public class FacebookRefund extends ConsoleProgram { private Map<Date,Double> readData(String filename) { try { Map<Date,Double> map = new TreeMap<Date,Double>(); BufferedReader rd = new BufferedReader(new FileReader(filename)); while (true) { String line = rd.readLine(); if (line == null) break; int equalSign = line.indexOf('='); Date date = stringToDate(line.substring(0, equalSign).trim()); double price = Double.parseDouble( line.substring(equalSign + 1).trim()); map.put(date, price); } rd.close(); return map; } catch (IOException ex) { throw new ErrorException(ex); } } page 2 of 3 public void run() { Map<Date,Double> sharePrice = readData("FBSharePrice.txt"); Date ordered = stringToDate(readLine("Sell ordered at: ")); Date executed = stringToDate(readLine("Sell executed at: ")); int nShares = readInt("Number of shares: "); if (sharePrice.containsKey(ordered) && sharePrice.containsKey(executed)) { double amountPaid = nShares * sharePrice.get(executed); double amountDue = nShares * sharePrice.get(ordered); double balance = amountDue - amountPaid; if (balance > 0) { println("Refund due of $" + balance); } else { println("No refund due"); } } else { println("No shares sold at that time"); } }

The FacebookRefund Application private Map<Date,Double> readData(String filename) { try { Map<Date,Double> map = new TreeMap<Date,Double>(); BufferedReader rd = new BufferedReader(new FileReader(filename)); while (true) { String line = rd.readLine(); if (line == null) break; int equalSign = line.indexOf('='); Date date = stringToDate(line.substring(0, equalSign).trim()); double price = Double.parseDouble( line.substring(equalSign + 1).trim()); map.put(date, price); } rd.close(); return map; } catch (IOException ex) { throw new ErrorException(ex); } } page 3 of 3 /* Parses a string into a java.util.Date structure */ private Date stringToDate(String str) { try { return new SimpleDateFormat("MM/dd/yyyy hh:mma").parse(str); } catch (ParseException ex) { throw new ErrorException(ex); } } }

Problem 6Practice #2 Write a definition for a Localizer class that simplifies the process of converting messages to the local language. The class exports a constructor that takes the name of a data file and a method public String localize(String word, String language) that translates the word into the specified language, if it appears in the localizer s data file.

The Localizer Class public class Localizer { public Localizer(String filename) { map = new TreeMap<String,String>(); try { BufferedReader rd = new BufferedReader(new FileReader(filename)); String word = null; while (true) { String line = rd.readLine(); if (line == null) break; int equalSign = line.indexOf('='); if (equalSign == -1) { word = line; } else { String language = line.substring(0, equalSign); String translation = line.substring(equalSign + 1); map.put(word + "+" + language, translation); } } rd.close(); } catch (Exception ex) { throw new ErrorException(ex); } } page 1 of 2

The Localizer Class public class Localizer { /** * Looks up the localization of the English word. */ public Localizer(String filename) { map = new TreeMap<String,String>(); try { BufferedReader rd = new BufferedReader(new FileReader(filename)); String word = null; while (true) { String line = rd.readLine(); if (line == null) break; int equalSign = line.indexOf('='); if (equalSign == -1) { word = line; } else { String language = line.substring(0, equalSign); String translation = line.substring(equalSign + 1); map.put(word + "+" + language, translation); } } rd.close(); } catch (Exception ex) { throw new ErrorException(ex); } } public String localize(String word, String language) { String key = word + "+" + language; if (map.containsKey(key)) { return map.get(key); } else { return word; } } /* Private instance variables */ private Map<String,String> map; } page 2 of 2

Problem 7Practice #1 In AdvObject, add a new field to record the current location; implement methods setLocation and getLocation to set and retrieve the room name in which the object is located. Use some sentinel string (such as "PLAYER") to indicate that the object is being carried. In Adventure, update the take, drop, and initial placement logic to call setLocation on the object. Also in Adventure, expand the code that interprets commands so that it recognizes ZAP along with the other built-in commands such as LOOK, TAKE, and DROP. Implement the ZAP command so that it has the desired functionality of removing the object from whatever list it is in and restoring it to its initial location. Add the ZAP command to the HELP text.

Problem 7Practice #2 You need to change the initialization code so that it installs superbricks in the brick layout with some probability. If your code does decide to create a superbrick, all you need to do is call setFillColor instead of setColor to have the brick display itself correctly on the screen. Create a GBall class that stores the velocity independently for each ball. Update the code so that all the methods take a GBall parameter and work with that object rather than a single set of coordinate and velocity variables. Define a structure (presumably a List<GBall>) to keep track of all the balls in play. In each time step, you need to update the position of every ball in the list. Change the code so that falling off the bottom deletes a ball from the list of active balls and hitting a superbrick adds a new ball to the list.

The End