// ===================================================================== // P6.1 // ===================================================================== // print rightmost, longest, arithmetic subsequence in a // pre-sorted $-1$-terminated input sequence public class P6_1 { public static void main(String[] args) { // initialize $TokenReader$ object $in$ to read from std input TokenReader in = new TokenReader(System.in); // print rightmost, longest, arithmetic subsequence in a // pre-sorted $-1$-terminated input sequence int stopping = -1; // stopping value // prompt user for input System.out.println( "please enter a sequence of integers terminated by " + stopping); System.out.println("separate numbers with white space"); System.out.println("use one or more lines"); int num = in.readInt(); // current input value int prev = num; // previous input value // rightmost, longest arithmetic subsequence so far -- // up to but excluding $num$ int longestLo = num; // start int longestGap = 0; // gap int longestLen = 0; // length // "current" subsequence: longest arithmetic subsequence // ending on $prev$ int curLo = num; // start int curGap = 0; // gap int curLen = 0; // length // process $stopping$-terminated input sequence // inv: maintain variable definitions above while (num != stopping) { // update current subsequence if (curGap == num - prev) { curLen = curLen + 1; } else { curLo = prev; curGap = num - prev; curLen = 2; } // conditional below was moved out of conditional above // update rightmost, longest arithmetic subsequence if (curLen >= longestLen) { longestLo = curLo; longestLen = curLen; longestGap = curGap; } // read next input value prev = num; num = in.readInt(); // current input value } // display rightmost, longest arithmetic subsequence System.out.print("rightmost, longest arithmetic" + " subsequence: ["); int i = 0; while (i < longestLen) { System.out.print(" " + (i * longestGap+longestLo) ); i = i + 1; } System.out.println(" ]"); } } /* erroneous result from original P6_1.java code: please enter a sequence of integers terminated by -1 separate numbers with white space use one or more lines 1 2 -1 rightmost, longest arithmetic subsequence: [ 1 ] */ // class P6_2 is at the end // ===================================================================== // P6.3 // ===================================================================== public class P6_3 { // sum of $(-1)**k * x ** (2*k+1) / factorial(2k+1)$ for $k = 0..N$ public static double f(double x, int N) { double sum = 0.0; // sum so far of terms up to but excluding $k$ int k = 0; int flipflop = 1; // $(-1) ** k$ double x2k1 = x; // $x ** (2*k+1)$ double fact = 1.0; // $factorial(2*k+1)$ while (k <= N) { sum += flipflop * x2k1 / fact; flipflop = -flipflop; x2k1 *= x*x; fact *= (2*k+2) * (2*k+3); k += 1; } return sum; } // print $f(20,10)$ public static void main(String[] args) { double x = 2; int N = 10; System.out.println("f(" + x + "," + N + ") = " + f(x,N)); // System.out.println(Math.sin(x)); // <-- print to compare } } // ===================================================================== // P6.4 // ===================================================================== // read pre-sorted, 100-terminated input sequence,print 2nd-to-last mode public class P6_4 { public static void main(String[] args) { int stopping = 100; // stopping value int nan = stopping; // use $stopping$ to represent $nan$ TokenReader in = new TokenReader(System.in); // prompt user for input System.out.println( "please enter a sequence of integers terminated by " + stopping); int num = in.readInt(); // current input value // these variables are based on the input read so far, // excluding $num$ int mode = nan; // last mode int modeFreq = 0; // frequency of last mode int mode2 = nan; // second to last mode int prev = nan; // previous input value int prevFreq = 0; // frequency of previous input value // read $stopping$-terminated input sequence // inv: maintain variable definitions above while (num != stopping) { // update $prev$ if (prev != num) { prevFreq = 0; } prev = num; prevFreq += 1; // update $mode$, $mode2$ if (prevFreq==modeFreq) { //another mode with same freq? mode2 = mode; mode = prev; modeFreq = prevFreq; } else if (prevFreq>modeFreq) { //new mode has new freq? mode = prev; modeFreq = prevFreq; mode2 = nan; // unique mode: no 2nd-to-last mode } // read next input num = in.readInt(); } // display second-to-last mode if (mode2 == nan) { System.out.println("no 2nd to last moe"); } else { System.out.println("2nd to last mode was " + mode2); } } } // ==================================================================== // P6.5 // ==================================================================== public class P6_5 { public static void main(String[] args) { int[] ages = advance(new int[] { 0 }, 9); int i = 0; System.out.println(ages.length); while (i < ages.length) { System.out.print(ages[i] + " "); i += 1; } System.out.println(); } // given ages $ages$ of bacteria, // return ages of bacteria after $hours>=0$ hours public static int[] advance(int[] ages, int hours) { // inv: $hours$ remaining hours to advance while (hours > 0) { // count number of mature bacteria int i = 0; int mature = 0; //# of mature bact. in $ages[0..i-1]$ while (i < ages.length) { if (ages[i] >= 2) { mature += 1; } i += 1; } // age all and replicate mature bacteria int[] now = new int[ages.length + mature]; i = 0; // in matlab notation, // set $now$ to $1+[ages zeros(1,mature)]$ // inv: $now[0..i-1]$ is done while (i < now.length) { if (i < ages.length) { now[i] = 1 + ages[i]; } else { now[i] = 1; } i += 1; } ages = now; hours -= 1; } return ages; // core: $return null;$ } } // ===================================================================== // P6.2 // ===================================================================== public class P6_2 { // plain Condorcet winners (as letters) for pairwise matrix $pwm$, // which is modified public static String plainCondorcet(int[][] pwm) { int n = pwm.length; // number of candidates String winners = ""; // winners found so far int smallest = 0; // (smallest) magnitude of defeats to delete while (winners.length() == 0) { int next = -1; // either negative, or smallest magnitude // defeat so far that is larger than smallest int j = 0; while (j < n) { int i = 0; boolean defeated = false; // "found any defeats of $j$?" while (i < n) { if (pwm[i][j] > pwm[j][i]) { defeated = true; if (pwm[i][j] == smallest) { pwm[i][j] = pwm[j][i] = 0; } else if (next < 0 || pwm[i][j] < next) { next = pwm[i][j]; } } i += 1; } if (!defeated) winners += (char) (j + 'A'); j += 1; } smallest = next; } return winners; } // pairwise matrix for ballots (same format as for $tally$) in // $election$. // each ballot is assumed to have the same number of candidates. public static int[][] tallies(String[] election) { int i = 0; int[][] pwm = null; while (i < election.length) { pwm = tally(election[i], pwm); i += 1; } return pwm; } /* pairwise matrix obtained from updating $pwm$ with $ballot$. if $pwm = null$, a new matrix is created, otherwise the old matrix is modified and its reference returned. $ballot$ holds ordered sequence of candidates. + candidates are represented by consecutive letters of the alphabet, starting at $"a"$, and ignoring case ($"a"$ and $"A"$ are the same) + between candidates is a comparison -- either $">"$ or $"="$ example: $tally("d>c=e=b>a", null)$ */ public static int[][] tally(String ballot, int[][] pwm) { char[] c = ballot.toCharArray(); int n = (c.length+1)/2; if (pwm == null) { pwm = new int[n][n]; } int i = 0; while (i < c.length) { int j = i + 2; while (j < c.length) { int k = i+1; boolean greater = false; // == "seen $'>'$?" <-- new while (k < j && !greater) { <-- changed greater = c[k] == '>'; // <-- new // if (c[k] == '>') { <-- delete/move // pwm[c[i] - 'A'][c[j] - 'A'] += 1; <-- delete/move // } <-- delete/move k += 2; } if (greater) { // new/moved pwm[c[i] - 'A'][c[j] - 'A'] += 1; // new/moved } // new/moved j += 2; } i += 2; } return pwm; /* untested faster code (body only, using idea of ranks): char[] c = ballot.toCharArray(); int n = (c.length+1)/2; if (pwm == null) { pwm = new int[n][n]; } int[] rank = new int[n]; // rank of each candidate -- smaller is better int i = 0; int r = 0; // rank of candidate $c[i]$ // compute rank of each candidate // inv: maintain $r$ and already processed candidates in $c[0..i]$ while (i+2 < c.length) { r += c[i+1] == '>' ? 1 : 0; i += 2; rank[c[i] - 'A'] = r; } // update $pwm$. inv: rows $0..i-1$ are done i = 0; while (i < n) { // update row $i$ of $pwm$. inv: columns $0..j-1$ are done int j = 0; while (j < n) { pwm[i][j] += rank[i] < rank[j] ? 1 : 0; j += 1; } i += 1; } return pwm; */ } // ***************** nothing for you to modify below this line ********* // test $plainCondorcet$ // note: partial support for $ssdCondorcet$ public static void main(String args[]) { String[] election1 = new String[] { "A>D>E>C>B", "C=B=E>D=A", "A>E>C=D=B", "A>B=E=D=C", "D>C>E>B>A", "D=A=C>B=E", "A>C>E>B=D", "A>D=C>E>B", "A=C>E>B=D", "B=C>E=D>A" }; int[][] pwm1 = new int[][] { new int[] { 0, 7, 5, 6, 7 }, new int[] { 3, 0, 0, 2, 1 }, new int[] { 3, 6, 0, 4, 6 }, new int[] { 2, 4, 2, 0, 4 }, new int[] { 3, 6, 2, 4, 0 } }; System.out.println("winner should be: A"); System.out.println("election1 winners: " + plainCondorcet(tallies(election1))); System.out.println("pwm1 winners: " + plainCondorcet(pwm1)); String[] election2 = new String[] { "B>C=A>E>D", "A>E>C=B=D", "D>E>B=C=A", "C=E=A>B>D", "A>B=D>C=E", "D=C=B=A>E", "A=D=C>B>E", "A>B=C=D=E", "B=A=D=E>C", "C>A>E=D=B", "E>C>B=A>D", "D=E=A=C>B", "C=A>E=D=B", "C>B>D=E=A", "B=A>E>C>D", "D>E=B>A>C", "D>B>A=C>E", "A=D>C=B>E", "D=C>E>B=A", "C>D>A=B>E" }; int[][] pwm2 = new int[][] { new int[] { 0, 9, 7, 9, 12 }, new int[] { 4, 0, 6, 5, 9 }, new int[] { 5, 9, 0, 8, 10 }, new int[] { 5, 8, 6, 0, 9 }, new int[] { 4, 6, 6, 5, 0 } }; System.out.println("winner should be: A"); System.out.println("election2 winners: " + plainCondorcet(tallies(election2))); System.out.println("pwm2 winners: " + plainCondorcet(pwm2)); int[][] pwm3 = new int[][] { new int[] { 0, 47, 52, 58, 60 }, new int[] { 37, 0, 77, 37, 33 }, new int[] { 57, 39, 0, 30, 60 }, new int[] { 42, 67, 65, 0, 57 }, new int[] { 75, 52, 47, 35, 0 } }; System.out.println("winner should be: D"); System.out.println("pwm3 winners: " + plainCondorcet(pwm3)); // 123456789123456789123456789123456789 char[] defeats = "B/C (10) C/D (11) D/B (12) C/A (07) " .toCharArray(); int[][] pwm4 = new int[4][4]; int k = 0; while (k < defeats.length) { pwm4[defeats[k]-'A'][defeats[k+2]-'A'] = 10 * (defeats[k+5] - '0') + (defeats[k+6] - '0'); k += 9; } System.out.println("plain winner is A, SSD winner is C"); System.out.println("plain pwm4 winners: "+plainCondorcet(pwm4)); //1234123412341234123412341234123412341234123412341234123412341234 defeats = "C/G G/H H/C F/K K/I I/M M/F C/B F/D B/E E/D D/B E/A A/J J/L L/A " .toCharArray(); k = 0; int[][] pwm5 = new int[13][13]; while (k < defeats.length) { pwm5[defeats[k]-'A'][defeats[k+2]-'A'] = (int) (Math.ceil(Math.random() * 99)); k += 4; } System.out.println("topmostSets are (subsets of) CGH and IKFM"); System.out.println("plain pwm5 winners: "+plainCondorcet(pwm5)); } }