Courses‎ > ‎AP Computer Science 2‎ > ‎

Konstantinovich

2017-02-16

posted Feb 16, 2017, 7:56 AM by Samuel Konstantinovich   [ updated Feb 17, 2017, 7:00 AM ]


Trip forms: print and try to get them signed and handed in by end of Monday, or end of today. The deadline is a hard deadline and if you miss it, that is your fault for waiting until the last minute!

Quiz the Wed after break. 

Extra Credit: 
 Make a folder   EC01/  on your repo.
 Place a copy of your extra credit KnightBoard.java in this folder if you would like it to be graded.
 You must have an additional public method: solveFast().
 If you do not have  EC01/KnightBoard.java , and the method is not named solveFast(), you will not get credit.
 You must find a tour using a much faster method than plain brute force. I will test on boards with sizes between 16 and 50.

Goal: Reminder: Files are useful.

Checked vs. Unchecked exceptions.



import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class ReadFile {
  public static void main(String args[]) throws FileNotFoundException {
        //instead of a try/catch, you can throw the FileNotFoundException.
        File infile = new File("input.txt");// can be a path"/full/path/to/file.txt" 
        Scanner inf = new Scanner(text);
        int lineNumber = 1;
        while(inf.hasNextLine()){
            String line = inf.nextLine();
            System.out.println(line);
        }       
    }   
}

Place this maze into a text file, and read it into 
Maze1.txt
###################################
#   #         #   #   #     # # #E#
# # ### ######### # # # ### # # # #
# # #   #           #   #         #
# # # ### ######### ##### ### ### #
# # # # #   #     #   #     # # # #
### # # ### # # ### # # # ### # ###
#S            #   # # # # #   #   #
###################################

Read it into your program. Print it. 
Then try reading it into an array of characters, and print that.


2017-02-14 HW03 + Terminal Things

posted Feb 14, 2017, 6:54 AM by Samuel Konstantinovich   [ updated Feb 14, 2017, 11:09 AM ]


Full day trip to NYU, where you listen to several interesting lectures by NYU CS professors. The topics are interesting, and food will be provided. It is not open to Seniors (sorry...)
    If you are and interested JUNIOR please fill out this form:


Your goal is to write a knight's tour solver. This is due the Tuesday after break.
Place it in your git repo:

03*/KnightBoard.java


KnightBoard has 2 public methods and a constructor, a private helper is needed as well.


public KnightBoard(int startingRows,int startingCols) 

public String toString() //blank if you never called solve or when there is no solution

public void solve() 

private boolean solveH(int row ,int col, int level) // level is the # of the knight


*Use the following format for toString: 

(THESE ARE NOT VALID SOLUTIONS, They JUST TO DEMONSTRATE FORMAT)

Single spaces between numbers, but leading spaces on single digit numbers:
 1  2  5
 3  4  6
 7  8  9

When there are two digit numbers (rows*cols >= 10) Put a leading space in front of single digit numbers: 
(spaces replaced with to show the difference)
__2 15 _6
___7 11
_8 _9 10 12
13 14 _5 16

So it looks like this:
 1  2 15  6
 3  4  7 11
 8  9 10 12
13 14  5 16

*I will not be testing boards that have a rows*cols that is >= 100, as the program would take a long time to complete.





-You only have to step on every square exactly once, starting on the 1st square counts.

-You do not have to come back to where you started. This is called a closed tour (it is a loop that is closed) and closed tours take much longer to find (potentially).



From Wikipedia:

Any m × n board with m ≤ n, a closed knight's tour is always possible unless one or more of these three conditions are met:

  1. m and n are both odd
  2. m = 1, 2, or 4
  3. m = 3 and n = 4, 6, or 8.
 
This also means an open tour is certainly possible when none of those are true!!!!! 

Your solve should work on 7x7 easily.



Here is something as a bonus:
public class Text{
    private static final int BRIGHT = 1;
    private static final int DARK = 2;
    private static final int ITALICS = 3;
    private static final int BLACK = 30;
    private static final int RED = 31;
    private static final int GREEN = 32;
    private static final int YELLOW = 33;
    private static final int BLUE = 34;
    private static final int MAGENTA = 35;
    private static final int CYAN = 36;
    private static final int WHITE = 37;
    private static final String CLEAR_SCREEN =  "\033[2J";
    private static final String HIDE_CURSOR =  "\033[?25l";
    private static final String SHOW_CURSOR =  "\033[?25h";

    //use this to go back to normal terminal colors
    private static final String RESET = color(40,37)+SHOW_CURSOR;

    //use this to convert from color to background (30 to 37 becomes 40 to 47)
    public static int background(int color){
	return color + 10;
    }

    //terminal specific character to move the cursor to a location
    //top left is 1,1
    private static String go(int x,int y){
        return ("\033[" + x + ";" + y + "H");
    }

    
    private static String color(int a, int b){
        return ("\033[0;" + a+ ";" + b + "m");
    }
    private static String color(int a, int b,int c){
        return ("\033[0;" + a+ ";" + b + ";" + c+ "m");
    }
    private static String color(int a, int b,int c, int d){
        return ("\033[0;" + a+ ";" + b + ";" + c + ";" + d + "m");
    }


    //And don't forget you can easily delay the printing if needed:
    private static void wait(int millis){
        try {
            Thread.sleep(millis);
        }
        catch (InterruptedException e) {
        }
    }


    public static void main(String[]args){
	System.out.println(CLEAR_SCREEN);
	System.out.println(HIDE_CURSOR);

	//SHOW A LOT OF COLORS!
	for(int i = 0; i < 8; i++){
	    for(int j = 0; j < 8; j++){
		System.out.println(go(i+1,j+1)+color(30+i,40+j) + "#");
		System.out.println(go(i+1,j+10)+color(30+i,40+j,BRIGHT) + "#");
		System.out.println(go(i+1,j+19)+color(30+i,40+j,DARK,ITALICS) + "#");
	    }
	}

	//HOW TO USE FOR SOME PARTS:
	System.out.println(go(15,20)+color(ITALICS,RED,background(BLUE))+"ITALICS FISH!~~~~");
	System.out.println(go(20,20)+color(GREEN,background(YELLOW))+"+=+ ^o^ ");


	System.out.println(RESET);
	
    }

}


2017-02-08 HW02

posted Feb 8, 2017, 6:33 AM by Samuel Konstantinovich   [ updated Feb 14, 2017, 6:23 AM ]

HW02 on github: (due Tuesday!!!!! 8am)
02NQueens/QueenBoard.java

You should not write any code until you:
 - write pseudo-code written to outline your solving method. (the recursive helper not the wrapper) 
 - have 2 of your classmates read over your pseudo-code

public class QueenBoard{
    private int[][]board;
    private int solutionCount;

}

Discussion on what you need to have working

requirements: *see below*

Optional: Animation of nqueen solver (do this after you get the homework!)

You need a few public methods:
public void solve()  - find the 1st solution it can and stop, this updates the board to be displayed in toString()
public void countSolutions() - look for all solutions, and update the instance variable solutionCount to reflect the number found. 
public int getSolutionCount() - return the instance variable solutionCount, which should be -1 if the countSolutions was never run.
public String toString() - when solve was run, this shows you the solution, otherwise a blank board.

Constructor:
QueenBoard(int size)

Private methods you will want to test before writing other parts of the code:
addQueen(r,c)
removeQueen(r,c)

public class QueenBoard{
    private int[][]board;
    private int solutionCount;
    public QueenBoard(int size){
	board = new int[size][size];
    }

    /**
     *precondition: board is filled with 0's only.
     *@return false when the board is not solveable. true otherwise.
     *postcondition: 
     *if false: board is still filled with 0's
     *if true: board is filled with the 
     *final configuration of the board after adding 
     *all n queens. Uses solveH
     */
    public boolean solve()
    {
	return solveH(0);
    }

    private boolean solveH(int col){
	return false;
    }

    /**
     *@return the number of solutions found, or -1 if the board was never solved.
     *The board should be reset after this is run.    
     */
public int getSolutionCount(){ return -1; }
    /**toString
     *and all nunbers that represent queens are replaced with 'Q' 
     *all others are displayed as underscores '_'
     */
    public String toString(){
    	return "";
    }
}


 N queens number of solutions:
1 (N)1 (num solutions)
20
30
42
510
64
7 840 92
9352
10724

"Adequate"

Set moveCount to 1
FOR each row on the board {
    FOR each column on the board {
        IF gameBoard position (row, column) is occupied THEN {
            CALL findAdjacentTiles with row, column
            INCREMENT moveCount 
        }
    }
}

(Note: the logic is restructured to omit the "do nothing" clause) 


"Not So Good"

FOR all the number at the back of the array 
    SET Temp equal the addition of each number 
    IF > 9 THEN 
        get the remainder of the number divided by 10 to that index 
        and carry the "1" 
    Decrement one 
Do it again for numbers before the decimal 
 

2017-02-07 *HW

posted Feb 7, 2017, 6:13 AM by Samuel Konstantinovich   [ updated Feb 8, 2017, 5:56 AM ]

Homework: FILLOUT WITH NEW REPO:

Goal: N-Queens

"The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 or n=3."

A top down design of an N-Queen solver.

Top Down design: 

Many of the functions and programs you write are simple enough to complete without designing them. This is because you can easily understand the whole algorithm. A formula, or a simple set of if statements don't seem to require a design. 

As you write more complex code, you cannot understand the whole algorithm/process AND all of the consequences of the code you need to write all at once. This is why it is a good idea to DESIGN your program rather than just hack it together by writing code until it works, even though it may seem like a waste of time for now.

Your design will be in plain English, which makes it faster and easier to write than actual code. It is also easier to find errors in your logic, and faster to fix than after you have coded the algorithm. (This is why rubber ducky debugging works because it forces you to state your algorithm in plain English)

Start with the big ideas and no code at all.
After you do that you can write pseudo-code and use high-level* function calls then refine each part as you plan it. 

*high level meaning, placeholder methods that describe complex things, rather than the code to do the complex things:
       swapParts(list);
       x=getNextElement();
       addQueen(x);

Afterward, you can think about how to represent the data, and how you will implement the code you planned. 




2017-02-06 HW01

posted Feb 6, 2017, 7:07 AM by Samuel Konstantinovich   [ updated Feb 7, 2017, 5:54 AM ]

Goal: Basic Recursion + Getting stuff done!

Lab + Homework:
Deadline is Wed Feb 8th 8am. I will clone everyone's repo by then.
I will grade and post results. 
No late submissions will be graded without prior permission/approval.


Discussion and working on Recursion2 problems.


1.0 BEFORE WE START:
How do you compare floating point values for equality? Why is this different than integers?



1.1 You are writing a class called Recursion for grading purposes this must be exact.
IMPORTANT NOTE: The methods will be static.   

You are solving 1 problem recursively:

sqrt

public static double sqrt(double n);
    -throws an IllegalArgumentException when n < 0. 

Now to think a little:
There is a formula to calculate square root
Guess any number for the sqrt of n. (like n/2, or even 1)

n = 100
guess = 1

Make a better_guess this way: 
better_guess =  ( n / original_guess + original_guess) / 2

guess = 50.5

(then do it again, then do it again)
guess = 26.24009900990099
guess = 15.025530119986813
guess = 10.840434673026925
guess = 10.032578510960604
guess = 10.000052895642693
...
Notice how fast this converges onto the correct value (10).

** You MUST make a helper function because you need a function with two parameters (n, and the guess) even though the sqrt function only takes 1 parameter.

What is a good base case? 
How do you know you found the square root?

1.2 Make your class matches the following:
public class Recursion{
public static String name(){...};
public static double sqrt(double n){...};
}

Note: name():  return your name: format: "Last,First" as it appears on your school documentation without spaces, or special symbols.

2. Need to study longer? (You are doing it wrong)
Let me end with a link to a video about how to study for less time and get more out of it. Even if you only watch the first 5-10 minutes you will be much smarter.
You can watch as little or as much of this video as you want, I won't ever check... but you won't increase your GPA either.  If this video helps you do better please let me know!
This pairs nicely with every article about sleeping more to remember things better...

2017-02-03

posted Feb 3, 2017, 7:14 AM by Samuel Konstantinovich   [ updated Feb 3, 2017, 9:14 AM ]

Override a method -> replace a superclass method with a child class by naming it the same (e.g. toString() )

Polymorphism:  objects and methods can have more than one form
    objects:     If shark extends fish, a shark can be treated 3 different ways because 
        a shark is-a fish, 
        a shark is-a shark, 
        a shark is-a object
    functions:  By overloading the methods they can have several forms. e.g. 
        foo(int x)   
        foo(int x, int y)   
        foo(char c)

Recursion1:
-count8
Recursion-2:
-groupSumClump
 -splitArray 
 -splitOdd10
 -split53

2017-02-02 HW

posted Feb 2, 2017, 9:35 AM by Samuel Konstantinovich

Goal: Recursive Backtracking

Recursion-2
groupSum  groupSum6 groupNoAdj

2017-02-01

posted Feb 1, 2017, 7:55 AM by Samuel Konstantinovich   [ updated Feb 1, 2017, 7:55 AM ]

Goal: Miracles (recursion)

Yesterday we talked about:
  1. Tail Recursion
    • No pending operations  e.g. 1 + foo(n-1)  //the 1 + has to wait for the foo, so it would be pending.
    • Partially computed answer is stored as a parameter 
    • Java does not have tail recursion optimization: tail recursion still blows the stack after less than 11,000 calls, much less if you have more parameters.
Today We will develop some algorithms together:
sumDigits(int n)
isPrime(int n)
countx()



Homework:
1.
Make a new github repo for this semester's homework.  MKS22X-HW or something similar. 
You will make a new folder on the TOP LEVEL OF YOUR REPO* for each homework starting with a 2 digit homework number. *Do not make a folder and put all of your homework assignments into it. The repo IS your "folder".

-MKS22X
--01Blah
--02Bl

2. Complete the recursion1 problems on codingbat:
changeXY, array6, allStar, countPairs, StringClean, nestParen


1-8 of 8