AP Compsci Help

You know, whatever

Moderators: Blitzen, Silent-sigfig, Almighty Benny

AP Compsci Help

Postby Colette » Mon Oct 08, 2012 2:06 pm

All the recent programming talk has motivated me to ask the brikwars community for help in my Compsci class. I tried on the StackOverflow forums but I thought it wouldn't kill me to ask another source.

So the mission is that I have to construct* a 2D integer matrix with randomly generated dimensions and values given the sums of its rows and columns. To elaborate, the 2d matrix only has ones and zeros- there are no other integers in it. Additionally, I must reconstruct it given only two 1d arrays- one array has the sums of the rows (basically each member of this 1d array indicates how many ones there were on that row) and a second 1d array that details the sums of the columns (same as other one). The solution must be implemented recursively.

The following code functions for matrices 4x4 and below (although performance notably degrades when inputting matrices 4x4 or larger- it sometimes works for 4x5 and 5x5 but performance is not guaranteed). The program specifications mandate that I be able to reconstruct any matrix up to 6x6 in dimensions. Could somebody help me make my code more efficient and explain how it works? Thanks,

*Exact reconstruction is not necessary, as there may be multiple solutions, but the outputted matrix must have the correct row and column sums as the original. ^Also, the language is Java.

Code: Select all
// Name:
// Date:

    public class MatrixRecreate_7_Yum
   {
       public static void main(String[] args)
      {
         int[][] matrix = create();
         int[] rowcount = new int[matrix.length];
         int[] colcount = new int[matrix[0].length];
         count(matrix, rowcount, colcount);
         display(matrix, rowcount, colcount);
         re_create(rowcount, colcount);
      }
       public static int[][] create()
      {
         int[][] fin = new int[(int)(Math.random()*5)+2][(int)(Math.random()*4)+2];
         //int[][] fin = new int[5][5];
         for (int x = 0; x < fin.length; x++) {
            for (int y = 0; y < fin[0].length; y++) {
               fin[x][y] = (int)(Math.random()+.5);
            }
         }
         return fin;
      }
       public static void count(int[][] matrix, int[] rowcount, int[] colcount)
      {
         for(int x = 0; x < matrix.length; x++) {
            int temp = 0;
            for(int y = 0; y < matrix[0].length; y++) {
               temp = temp + matrix[x][y];
            }rowcount[x] = temp;
         }
         for(int z = 0; z < matrix[0].length; z++) {
            int temp = 0;
            for(int a = 0; a < matrix.length; a++) {
               temp = temp + matrix[a][z];
            }colcount[z] = temp;
         }

      }
       public static void display(int[][] matrix, int[] rowcount, int[] colcount)
      {
         System.out.print("---");
         for(int x = 0; x < colcount.length; x++) {
            System.out.print(colcount[x] + " ");
         }System.out.println("\n");
         for (int y = 0; y < rowcount.length; y++) {
            System.out.print(rowcount[y] + ": ");
            for(int z = 0; z < matrix[0].length; z++) {
               System.out.print(matrix[y][z] + " ");
            }System.out.println();
         }
         System.out.println();
      }
       public static void re_create(int[] rowcount, int[] colcount)
      {
         int[][] neo = new int[rowcount.length][colcount.length];
         for (int x = 0; x < neo.length; x++) {
            for (int y = 0; y < neo[0].length; y++) {
               neo[x][y] = 0;
            }
            if(rowcount[x] <= neo[0].length/2) {
               for(int y = 0; y < rowcount[x]; y++) {
                  neo[x][y] = 1;
               }
            }else {
               for(int y = neo[0].length-rowcount[x]; y < neo[0].length; y++) {
                  neo[x][y] = 1;
               }
            }
         }
         recur(neo, rowcount, colcount, 0, 0);

      }
       private static void recur(int[][] m, int[] rowcount, int[] colcount, int row, int col) //recursive helper method
      {
         if(compare(m, rowcount, colcount))    //base case: if new matrix works
         {       
            display(m, rowcount, colcount);    //we're done!
            System.out.println("Success!");
            System.exit(0);
         }else {
            if(((rowcount[row]==0)||(rowcount[row]==m[0].length))&&(row-1>=0)) {recur(m, rowcount, colcount, row-1, col);}
            try {
               if(m[row][col] == m[row][col+1]){recur(m, rowcount, colcount, row, col+1);}
               else{
                  int temp = m[row][col]; m[row][col] = m[row][col+1]; m[row][col+1]=temp;
                  recur(m, rowcount, colcount, row, col+1);
               }
            }catch (ArrayIndexOutOfBoundsException e) {
               if (row == 0) {
                  recur(m, rowcount, colcount, m.length-1, 0);
               }else {
                  if((double)rowcount[row] != (double)m.length/2.0) {
                     for(int x = 0; x < m[0].length; x++) {m[row][x] = 0;}
                     for(int y = 0; y < rowcount[row]; y++) {m[row][y] = 1;}
                  }
                  recur(m, rowcount, colcount, row-1, 0);//test with 0 = col-1
               }
            }catch (StackOverflowError e) {recur(m, rowcount, colcount, row, col);}
         }
      }
            
       private static boolean compare(int[][] m, int[] rowcount, int[] colcount)
      {
         boolean fin = true;
         int[] row1 = new int[rowcount.length]; int[] col1 = new int[colcount.length];
         count(m, row1, col1);
         for(int x = 0; x < rowcount.length; x++) {
            fin = fin && (rowcount[x] == row1[x]);
         }for (int y = 0; y < colcount.length; y++) {
            fin = fin && (colcount[y] == col1[y]);
         }return fin;
      }
   }
Image
Image
Because everything's better with math...and firepower.
User avatar
Colette
I for one personally welcome clown face bologna
 
Posts: 2545
Joined: Tue Apr 12, 2011 6:04 pm
Location: This Forum

Re: AP Compsci Help

Postby Silent-sigfig » Mon Oct 08, 2012 2:31 pm

Take a real AP class
BFenix wrote:
Silent-sigfig wrote: :dog:

Coolest 1000th post ever :D
User avatar
Silent-sigfig
Clown-Face Bologna
 
Posts: 2162
Joined: Fri Mar 14, 2008 5:20 pm
Location: Number one in USA

Re: AP Compsci Help

Postby Colette » Mon Oct 08, 2012 2:33 pm

Silent-sigfig wrote:Take a real AP class

Do AP Español and Calculus BC count?
Image
Image
Because everything's better with math...and firepower.
User avatar
Colette
I for one personally welcome clown face bologna
 
Posts: 2545
Joined: Tue Apr 12, 2011 6:04 pm
Location: This Forum

Re: AP Compsci Help

Postby Zupponn » Mon Oct 08, 2012 3:02 pm

This might help with your Matrix problem:
Image
Image
User avatar
Zupponn
Lovable and funny
Lovable and funny
 
Posts: 5545
Joined: Mon Mar 21, 2011 6:15 pm
Location: Wisconsin, land of the cheese

Re: AP Compsci Help

Postby mgb519 » Tue Oct 09, 2012 6:31 am

Code: Select all
int[][] fin = new int[(int)(Math.random()*5)+2][(int)(Math.random()*4)+2];
[/quote]
Why random?
Tzan wrote:
Semaj Nagirrac wrote:Well, I took some land without checking if it was owned by a faction or not. I'm not going to be banned, am I? I can destroy everything if need be.


That's what Hitler said,
in 1938.
User avatar
mgb519
Pooplord
 
Posts: 2531
Joined: Thu May 26, 2011 8:50 pm
Location: ATL

Re: AP Compsci Help

Postby Silent-sigfig » Tue Oct 09, 2012 1:55 pm

Colette wrote:
Silent-sigfig wrote:Take a real AP class

Do AP Español and Calculus BC count?


Spanish doesn't
BFenix wrote:
Silent-sigfig wrote: :dog:

Coolest 1000th post ever :D
User avatar
Silent-sigfig
Clown-Face Bologna
 
Posts: 2162
Joined: Fri Mar 14, 2008 5:20 pm
Location: Number one in USA

Re: AP Compsci Help

Postby Colette » Tue Oct 09, 2012 4:42 pm

Silent-sigfig wrote:
Colette wrote:
Silent-sigfig wrote:Take a real AP class

Do AP Español and Calculus BC count?


Spanish doesn't

Funny, Español AP seems harder to me than Calculus BC- I have like a 99% in BC.
Image
Image
Because everything's better with math...and firepower.
User avatar
Colette
I for one personally welcome clown face bologna
 
Posts: 2545
Joined: Tue Apr 12, 2011 6:04 pm
Location: This Forum

Re: AP Compsci Help

Postby Silent-sigfig » Tue Oct 09, 2012 9:06 pm

Be a man and take German
BFenix wrote:
Silent-sigfig wrote: :dog:

Coolest 1000th post ever :D
User avatar
Silent-sigfig
Clown-Face Bologna
 
Posts: 2162
Joined: Fri Mar 14, 2008 5:20 pm
Location: Number one in USA

Re: AP Compsci Help

Postby Ham701 » Tue Oct 09, 2012 9:47 pm

Silent-sigfig wrote:Be a man and take German
stubby wrote: my floppy penis gets first dibs on it for tradition's sake, but it doesn't seem likely that he'll want to stick around long enough to play.

Image
User avatar
Ham701
Galidor
 
Posts: 1163
Joined: Mon Nov 29, 2010 11:11 pm
Location: Watching DS9


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 2 guests