Java Introduction to Recursion Assigment

Note: Use the test code to check if the code works

Test Code:

import java.io.ByteArrayOutputStream;

import java.io.File;

import java.io.PrintStream;

import java.nio.file.Files;

import java.nio.file.Paths;

import java.security.MessageDigest;

import java.security.NoSuchAlgorithmException;

import java.util.Arrays;

import java.util.Random;

public class RecursionIntroTest {

public static void rowColumn(String source, int offset) {

int row = 1;

int col = 1;

for (int i = 0; i

if (source.charAt(i) == ' ') {

row++;

col = 1;

} else if (source.charAt(i) == '\t')

col += (4 - (col - 1) % 4);

else

col++;

}

System.out.println("Above problem is on line " + row + "

column " + col + " (Assuming tab width of 4)");

}

public static void main(String[] args) throws

NoSuchAlgorithmException {

String source = null;

try {

source = new

String(Files.readAllBytes(Paths.get("src" + File.separator +

"RecursionIntro.java")));

} catch (Exception e) {

System.out.println(

"Couldn't find

RecursionIntro.java! Run this from the same Eclipse project as

RecursionIntro.");

return;

}

if (source.matches("(?s).*\\sfor[\\s\\(].*")) {

System.out.println(

"Detected 'for' statement in

your program! Please remove anything that resembles a 'for'.");

System.exit(-1);

}

if (source.matches("(?s).*\\swhile[\\s\\(].*")) {

System.out.println(

"Detected 'while' statement

in your program! Please remove anything that resembles a 'while'.");

System.exit(-1);

}

if (source.matches("(?s).*\\simport\\s.*") ||

source.indexOf("import") == 0) {

System.out.println("Detected 'import'

statement in your program! Please remove any word 'import'.");

System.exit(-1);

}

if

(source.matches("(?s).*\\spublic\\s+static\\s+\\w+[^(]*=.*")

||

source.matches("(?s).*\\spublic\\s+static\\s+\\w+[^(]*;.*")) {

System.out.println("Detected static variable

in your program! Please remove static variables.");

System.exit(-1);

}

for (int dotIndex = source.indexOf('.'); dotIndex != -1;

dotIndex = source.indexOf('.', dotIndex + 1)) {

if

("System.out.println".equals(source.substring(dotIndex - 6, dotIndex +

12))

||

"System.out.println".equals(source.substring(dotIndex - 10, dotIndex + 8))

||

"length".equals(source.substring(dotIndex + 1, dotIndex + 7))

||

Character.isDigit(source.charAt(dotIndex+1))) {

continue;

}

System.out.println("Bad dot! Context: "

+

source.substring(Math.max(0, dotIndex - 20), Math.min(dotIndex + 20,

source.length())));

rowColumn(source, dotIndex);

System.exit(-1);

}

System.out.println("Passed syntax checks!");

System.out.println("If you don't see a score, your

program didn't get to the end!");

PrintStream out = System.out;

MessageDigest md5 = MessageDigest.getInstance("MD5");

int score = 0;

int eduoddScore = 0;

int fibbyScore = 0;

int stGenScore = 0;

int median3Score = 0;

try {

try { // Part 1: eduodd

long[] ns = {0, 27, 987654321, -8443,

11121113, -11, 99999999999L, -987654321, -1016548095, -458096230};

long[] eos = {1, 36, 896745230, -9552,

30002, 0, 88888888888L, -896745230, -107459184, -549187321};

System.out.println("Testing

eduodd...");

for (int i = 0; i

long eo =

RecursionIntro.eduodd(ns[i]);

if (eo != eos[i]) {

System.out.println("Expected eduodd("+ns[i]+") = "+eos[i]+" but got

"+eo);

} else {

eduoddScore++;

}

}

Random r = new Random(123456789);

long[] rando = new long[1000];

for (int i = 0; i

{

rando[i] =

RecursionIntro.eduodd(r.nextInt());

}

byte[] b =

md5.digest(Arrays.toString(rando).getBytes());

byte[] good = {-106, 111, -96, -46, -

125, 4, 30, 41, 69, -39, 87, -114, -123, -119, -12, 22};

if (!Arrays.equals(b, good)) {

System.out.println("Your

eduodd method doesn't always work. Please consult the assignment

carefully.");

if (eduoddScore == 10) {

System.out.println("It looks like you passed the above test cases!

You may want to ask your instructor for help!");

}

} else {

eduoddScore += 20;

}

} catch (Throwable t) {

t.printStackTrace();

}

try { // Part 2a: fibby

int[] fibbys = { 1, 2, 3, 4, 6, 6, 8,

8, 11, 11};

System.out.println("Testing fibby...");

for (int i = 0; i

{

long fib =

RecursionIntro.fibby(i);

if (fib != fibbys[i]) {

System.out.println("Expected fibby(" + i + ") = " + fibbys[i] + "

but got " + fib);

} else

fibbyScore++;

}

int[] fibbys2 = new int[10000];

for (int i = 0; i

fibbys2[i] =

RecursionIntro.fibby(i);

}

byte[] b =

md5.digest(Arrays.toString(fibbys2).getBytes());

byte[] good = {-54, -34, -99, -113, -3,

-71, -109, 113, 63, 127, 114, 95, 109, -82, 114, -108};

if (!Arrays.equals(b, good)) {

System.out.println("Your

fibby method doesn't work for some value between 0 and 9999. Please

consult the definition carefully.");

} else {

fibbyScore += 10;

}

} catch (Throwable t) {

t.printStackTrace();

}

try { // Part 2b: printsparsetable

System.out.println("Testing

printsparsetable...");

int[] starts = { 1, 1000, 101 };

int[] ends = { 100, 1020, 999 };

byte[][] md5s = { { 58, 46, 104, 125, -

11, -80, -18, 110, -37, -96, 106, 87, -22, 122, 72, 64 },

{ 19, 45, 112, -

113, -33, 77, 114, 123, -71, -95, -38, 101, 59, 57, 45, -54 },

{ -87, 94, 100,

67, -96, 45, -42, -83, -84, 111, -39, 102, -87, -70, -112, -84 } };

for (int i = -2; i

i++) {

ByteArrayOutputStream ba =

new ByteArrayOutputStream();

System.setOut(new

PrintStream(ba));

if (i == -2) {

RecursionIntro.printsparsetable(5, 10);

System.setOut(out);

String expected =

"5 6 6 8 8 11 ";

if

(!Arrays.equals(expected.split("\ ?\ "),

ba.toString().split("\ ?\ "))) {

System.out.println("For printsparsetable(5, 10), expected: " +

expected + " , got: " + ba);

} else {

stGenScore

++;

}

} else if (i == -1) {

RecursionIntro.printsparsetable(13, 20);

System.setOut(out);

String expected =

"13 15 15 18 16 21 20 24 ";

if

(!Arrays.equals(expected.split("\ ?\ "),

ba.toString().split("\ ?\ "))) {

System.out.println("For printsparsetable(13, 20), expected: " +

expected + " , got: " + ba);

} else {

stGenScore

++;

}

} else {

RecursionIntro.printsparsetable(starts[i], ends[i]);

System.setOut(out);

byte[] digest =

md5.digest(Arrays.toString(ba.toString().split("\ ?\ ")).getBytes());

if

(!Arrays.equals(md5s[i], digest)) {

System.out.println(

"Didn't get expected output for printsparsetable(" + starts[i]

+ ", " + ends[i] + ")");

System.out.println("Saw this:");

System.out.println(ba);

System.out.println("MD5 sum of output seen: " +

Arrays.toString(digest));

} else

stGenScore

++;

}

}

ByteArrayOutputStream ba = new

ByteArrayOutputStream();

System.setOut(new PrintStream(ba));

Random r = new Random(918273645);

for (int i = 0; i

int start = r.nextInt(1000);

RecursionIntro.printsparsetable(start, start+r.nextInt(1000)+1);

}

System.setOut(out);

byte[] digest =

md5.digest(Arrays.toString(ba.toString().split("\ ?\ ")).getBytes());

byte[] good = {62, -87, -60, -83, -81,

99, -84, -73, -40, -24, -89, 115, 77, -82, 109, -53};

if (!Arrays.equals(digest, good)) {

System.out.println("Your

printsparsetable method doesn't always work (for starting values up to

1000 and ending values up to 1000 positions away). Please consult the

definition carefully.");

if (stGenScore == 5) {

System.out.println("It looks like you passed the above test cases!

You may want to ask your instructor for help!");

}

} else {

stGenScore += 15;

}

} catch (Throwable t) {

t.printStackTrace();

} finally {

System.setOut(out);

}

try { // Part 3: median3

System.out.println("Testing

median3...");

int[][] a = {{1}, {1, 2}, {3, -10,

100}, {123,234,345}, {100, 50, -1000}, {3, 100, -10}, {1, 200, 30}, {2000,

-1, 300}, {1, 2, -5, 10, 100, 6}, {1, 2, -10, 7, 20, -3, 100, 6}, {1, 2, -

20, -10, 7, 20, -3, 100, 6, 92}};

double[] rets = {1.0, 1.5, 3, 234, 50,

3, 30, 300, 2.5, 6, 1.0};

for (int i = 0; i

double ra =

RecursionIntro.median3(a[i]);

if (ra != rets[i]) {

System.out.println("Expected median3("+Arrays.toString(a[i])+") =

"+rets[i]+" but got "+ra);

} else {

median3Score++;

}

}

Random r = new Random(54321);

double[] rando = new double[2000];

for (int i = 0; i

int[] b = new

int[r.nextInt(100000)+1];

for (int j = 0; j

b.length; j++) {

b[j] =

r.nextInt()/1024;

}

rando[i] =

RecursionIntro.median3(b);

}

byte[] b =

md5.digest(Arrays.toString(rando).getBytes());

byte[] good = {29, 25, 56, -24, -17, -

68, 24, 78, -9, 25, -22, -28, -8, 123, 0, 46};

if (!Arrays.equals(b, good)) {

System.out.println("Your

median3 method doesn't always work (for arrays up to 100,000 elements).

Please consult the definition carefully.");

if (median3Score == 11) {

System.out.println("It looks like you passed the above test cases!

You may want to ask your instructor for help!");

}

} else {

median3Score += 19;

}

} catch (Throwable t) {

t.printStackTrace();

}

} finally {

System.out.println("eduodd: " + eduoddScore +

" / 30");

System.out.println("fibby: " + fibbyScore + "

/ 20");

System.out.println("printsparsetable: " +

stGenScore + " / 20");

System.out.println("median3: "+median3Score+"

/ 30");

score = eduoddScore + fibbyScore + stGenScore

+ median3Score;

System.out.println("Tentative score: " +

score + " / 100");

}

}

}