I made a program today that performs gauss-jordan elimination on a matrix.

Code:
package matrices;

import javax.swing.JOptionPane;

class matrix {

    private final int rows;
    private final int columns;
    private double[][] arr;
    private int k = -1;

    matrix(int r, int c, double[][] a) {
        rows = r;
        columns = c;
        arr = a;
    }

    public void printMatrix() {
        System.out.println();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                System.out.print(arr[i][j] + "  ");
            }
            System.out.println();
        }

    }

    public double[][] putAOne() {
        k++;
        double temp = arr[k][k];
        if (temp < -1.0E-12 || temp > 1.0E-12) {
            for (int i = k; i < columns; i++) {
                arr[k][i] = arr[k][i] / temp;
            }
            printMatrix();
        }
        return arr;
    }

    public double[][] emptyUnderOne() {

        for (int i = k + 1; i < rows; i++) {
            double temp = arr[i][k];
            for (int j = 0; j < columns; j++) {
                arr[i][j] = arr[i][j] - temp * arr[k][j];
            }
        }
        printMatrix();
        return arr;
    }

    public double[][] roundMatrix() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                arr[i][j] = Math.round(arr[i][j] * 1.0E12) / 1.0E12;
            }
        }
        printMatrix();
        return arr;
    }

    public double[][] checkAndFixLeadingOnes() {
        double temp;
        for (int i = 0; i < rows; i++) {
            boolean goodRow = false;
            double accumulator = 0.0;
            int pos = 0;

            for (int j = 0; j < columns && goodRow == false; j++) {
                accumulator += arr[i][j];
                if (accumulator == 1.0) {
                    goodRow = true;
                } else {
                    if (accumulator != 0.0 && pos == 0) {
                        pos = j;
                    }
                }
            }
            if (goodRow == false && accumulator != 0.0) {
                temp = arr[i][pos];
                for (int j = 0; j < columns; j++) {
                    arr[i][j] = arr[i][j] / temp;
                }
            }
        }
        printMatrix();
        return arr;
    }

    public double[][] jordan() {
        for (int i = (rows - 1); i >= 0; i--) {
            int pos = -1;
            double accumulator = 0.0;
            for (int j = 0; j < columns; j++) {
                accumulator += arr[i][j];
                if (accumulator == 1.0 && pos == -1) {
                    pos = j;
                }
                if (accumulator > 1.0E-12 || accumulator < -1.0E-12) {
                    for (int m = (i - 1); m >= 0; m--) {
                        if (arr[m][pos] > 1.0E-12 || arr[m][pos] < -1.0E-12) {
                            double temp = arr[m][pos];
                            for (int n = 0; n < columns; n++) {
                                arr[m][n] -= temp * arr[i][n];
                            }
                        }
                    }
                }
            }
        }
        printMatrix();
        return arr;
    }

}

public class Matrices {

    public static void main(String[] args) {

        String row = JOptionPane.showInputDialog("Enter the number of rows in the matrix");
        int rows = Integer.parseInt(row);
        while (rows < 1) {
            row = JOptionPane.showInputDialog("There must be at least 1 row.");
            rows = Integer.parseInt(row);
        }

        String column = JOptionPane.showInputDialog("Enter the number of columns in the matrix");
        int columns = Integer.parseInt(column);
        while (columns < 2) {
            column = JOptionPane.showInputDialog("There must be at least 2 columns");
            columns = Integer.parseInt(column);
        }
        String value;
        double[][] arr = new double[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                value = JOptionPane.showInputDialog("Enter the value in row " + (i + 1) + ", and in column " + (j + 1));
                arr[i][j] = Double.parseDouble(value);
            }
        }
        matrix matrix1 = new matrix(rows, columns, arr);
        matrix1.printMatrix();
        for (int a = 1; a <= rows; a++) {
            matrix1.putAOne();
            if (a != rows) {
                matrix1.emptyUnderOne();
            }
        }
        matrix1.roundMatrix();
        matrix1.checkAndFixLeadingOnes();
        System.out.println("REF");
        matrix1.jordan();
        System.out.println("RREF");
    }

}

I decided to make it print the entire matrix after each step, which sometimes leads to the same matrix being printed two or more times in a row in the event that it performs a check that doesn't result in the matrix being modified, but still prints after the check. Here is a sample of the output it produces:

Code:
1.0  -1.0  -3.0  1.0 
3.0  -2.0  -4.0  6.0 
3.0  0.0  6.0  12.0 

1.0  -1.0  -3.0  1.0 
3.0  -2.0  -4.0  6.0 
3.0  0.0  6.0  12.0 

1.0  -1.0  -3.0  1.0 
0.0  1.0  5.0  3.0 
0.0  3.0  15.0  9.0 

1.0  -1.0  -3.0  1.0 
0.0  1.0  5.0  3.0 
0.0  3.0  15.0  9.0 

1.0  -1.0  -3.0  1.0 
0.0  1.0  5.0  3.0 
0.0  0.0  0.0  0.0 

1.0  -1.0  -3.0  1.0 
0.0  1.0  5.0  3.0 
0.0  0.0  0.0  0.0 

1.0  -1.0  -3.0  1.0 
0.0  1.0  5.0  3.0 
0.0  0.0  0.0  0.0 
REF

1.0  0.0  2.0  4.0 
0.0  1.0  5.0  3.0 
0.0  0.0  0.0  0.0 
RREF

There may still be mistakes in there, but it has worked on all the funky cases I could think of Razz
Basically, the program asks the user to input the size of the matrix, then the contents, and stores that to a 2d array. Then it recursively puts leading 1s and clears under them by subtracting multiples of the row that just got a leading 1, to make a diagonal line through the matrix. The recursion is done by incrementing the k variable which serves as an offset for the row and column. Then there is a routine (checkAndFixLeadingOnes()) that checks that all rows have leading 1s and divides the ones that don't in order to account for the fact that some matrices may not have unique solutions, so a perfect diagonal line won't work in those cases. At this point, we have a matrix in row-echelon form. Then the jordan() method recursively (this time with the m and n variables) checks above the leading 1s, and subtracts multiples of the rows from bottom to top to clear above the leading 1s. And then the matrix is in reduced row-echelon form! Along the way, the entire matrix gets rounded once in an attempt to reduce the amount of error that gets put into matrix as these operations take place. Of course, this rounding will help the accuracy if the final matrix should have whole numbers, and will hinder the accuracy if the final matrix should have fractional numbers, but I figured textbook problems often have nice integer solutions, so the rounding would help overall. #RuleUtilitarianism?
Alright guys, I've got a difficult one Laughing
I participated in the Canadian Computing Competiton (CCC) Waterloo yesterday, representing my college. In this contest, there are 5 questions in ascending order of difficulty. I managed to complete the first 3 with ease, my 4th entry was too slow and I was consequently awarded no points for it, and I was unable to complete the last (most difficult) question. Overall, a pretty poor score, but I'm still happy I participated, as it was a fun experience nonetheless.
I was warned that the questions were not going to be easy, and I think they definitely lived up to that statement. I thought the last question was particularly difficult, even considering this is on the national stage, although I guess they want really clever programmers to have a chance to stand out.
Anyways, here is the final question that I wasn't able to solve (at least not in what was left of my 3 hours, which is the amount of time you get to complete all 5 questions.)
CCC Waterloo wrote:
Problem S5: Maximum Strategic Savings

Problem Description

A long time ago in a galaxy far, far away, there are N planets numbered from 1 to N. Each planet
has M cities numbered from 1 to M. Let city f of planet e be denoted as (e, f).
There are N P two-way flights in the galaxy. For every planet e (1 ≤ e ≤ N), there are P
flights numbered from 1 to P. Flight i connects cities (e, ai) and (e, bi) and costs ci energy daily
to maintain.
There are M Q two-way portals in the galaxy. For all cities with number f (1 ≤ f ≤ M), there
are Q portals numbered from 1 to Q. Portal j connects cities (xj, f) and (yj, f) and costs zj energy
daily to maintain.
It is possible to travel between any two cities in the galaxy using only flights and/or portals.
Hard times have fallen on the galaxy. It was decided that some flights and/or portals should be shut
down to save as much energy as possible, but it should remain possible to travel between any two
cities afterwards.
What is the maximum sum of energy that can be saved daily?

Input Specification

The first line contains four space-separated integers N, M, P, Q (1 ≤ N, M, P, Q ≤ 10^5).
Then P lines follow; the i-th one contains three space-separated integers ai, bi, ci (1 ≤ ai, bi ≤M, 1 ≤ ci ≤ 10^8 ).
Then Q lines follow; the j-th one contains three space-separated integers xj, yj, zj (1 ≤ xj, yj ≤N, 1 ≤ zj ≤ 10^8 ).
It is guaranteed that it will be possible to travel between any two cities using flights and/or portals.
There may be multiple flights/portals between the same pair of cities or a flight/portal between a
city and itself.
For 2 of the 15 available marks, P, Q ≤ 100 and ci = 1 for all 1 ≤ i ≤ P, and zj = 1 for all 1 ≤ j ≤ Q.
For an additional 2 of the 15 available marks, P, Q ≤ 200.
For an additional 5 of the 15 available marks, N, M ≤ 200.

Output Specification

Output a single integer, the maximum sum of energy that can be saved daily.

Sample Input 1

2 2 1 2
1 2 1
2 1 1
2 1 1

Output for Sample Input 1

3

Sample Input 2

2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5

Output for Sample Input 2

41

Explanation for Output for Sample Input 2

One possible way is to shut down the flights between cities (1, 1) and (1, 1), (2, 1) and (2, 1), (1, 1)
and (1, 2), (1, 3) and (1, 2), (2, 3) and (2, 2), and shut down the portal between cities (2, 3) and
(1, 3) for total energy savings of 8 + 8 + 6 + 7 + 7 + 5 = 41.


Feel free to give it a go, if you succeed, I would love to see how others approached this problem.
Here are the languages that were permitted:
Quote:
C, C++, Java, Pascal, Python 2, Python 3, PHP, Perl

The question doesn't mention it, but there were time limitations in place for how long your program took to execute. I don't know what it was for this question because I didn't submit a good program, but if it was anything like the other questions, it was probably on the order of 2-3 seconds.
Teacher wrote:
Just use jQuery to do your ajax, it's so much better and shorter

Me wrote:
My final project in Java was about jaxafx, linked lists, exception handling, inheritance, etc.
The program had to do the following things:
  1. return a list of distinct items in a file, along with the frequency of each item (how many times it was in the list)
  2. remove the items that were found in a 2nd file
  3. sort the list by frequencies

Obviously the program had to have a javafx GUI, the list had to be in a linked list class that was created manually (not using the built-in class) and the sorting algorithm had to be implemented manually (I used selection sort). The theme was birdwatching, so the 1st files contained names of birds that were spotted, and the 2nd file contained the names of non-indigenous birds, which should for some reason be removed. Here is an example of how the program should be used:

Inputs:
Code:
File 1:
Robin
Starling
House Sparrow
Robin
Chickadee
Grackle
House Sparrow
Cardinal
Indigo Bunting
Robin
Starling
House Sparrow
Robin
Chickadee
Grackle
Chickadee
Grackle
House Sparrow
Cardinal
Purple Martin
Chickadee
Grackle
House Sparrow
Cardinal
Starling
Robin
Robin
Ruby Throated Humming Bird
Blue Jay
Purple Martin
Chickadee
Grackle
House Sparrow
Cardinal
Starling
Robin
Purple Martin
Chickadee
Grackle
House Sparrow
Cardinal
Starling
Robin
Starling
House Sparrow
Robin
Starling
Robin
Starling
House Sparrow
Robin
Yellow-Bellied Sap Sucker
Blue Jay
Starling
Robin
Starling
House Sparrow
Robin
Baltimore Oriole
Starling
Robin
Starling
House Sparrow
Robin
Purple Finch
Robin
Starling
House Sparrow
Robin
Purple Finch
Blue Jay
Starling
Robin
Starling
House Sparrow
Robin
Baltimore Oriole
Chickadee
Grackle
House Sparrow
Cardinal
Indigo Bunting
Robin
Starling
House Sparrow
Robin
Chickadee
Grackle
Chickadee
House Sparrow
Robin
Chickadee
Grackle
Chickadee
Grackle
House Sparrow
Cardinal
House Sparrow
Robin
Yellow-Bellied Sap Sucker
Blue Jay
Starling
Robin
Robin
Robin
Ruby Throated Humming Bird
Blue Jay
Purple Martin
White Throated Sparrow
American Goldfinch
Robin
Robin
Ruby Throated Humming Bird
Blue Jay
Purple Martin
Tree Swallow
Robin
Starling
House Sparrow
Robin
Chickadee
Grackle
House Sparrow
Cardinal
Red Headed Woodpecker
Robin
Starling
House Sparrow
Robin
Chickadee
Grackle
House Sparrow
Cardinal
Robin
Chickadee
Grackle
Chickadee
Grackle
House Sparrow
Cardinal
House Sparrow
Robin
Yellow-Bellied Sap Sucker
Blue Jay
Chickadee
Grackle
House Sparrow
Cardinal
Robin
Chickadee
Grackle
Chickadee
Grackle
House Sparrow
Cardinal
House Sparrow
Robin
Rose Breasted Grosbeak
Robin
Purple Finch
Blue Jay
Starling
Robin
Starling
House Sparrow
Robin
Baltimore Oriole
Chickadee
Grackle
House Sparrow
Cardinal
Indigo Bunting
Robin
Starling
House Sparrow
Robin
Chickadee

File 2:
Robin
Grackle
Starling
Chickadee

Outputs:

Code:
Show original list:
Robin 41
Starling 22
House Sparrow 30
Chickadee 20
Grackle 18
Cardinal 13
Indigo Bunting 3
Purple Martin 5
Ruby Throated Humming Bird 3
Blue Jay 8
Yellow-Bellied Sap Sucker 3
Baltimore Oriole 3
Purple Finch 3
White Throated Sparrow 1
American Goldfinch 1
Tree Swallow 1
Red Headed Woodpecker 1
Rose Breasted Grosbeak 1

Remove non-indigenous Birds:
House Sparrow 30
Cardinal 13
Indigo Bunting 3
Purple Martin 5
Ruby Throated Humming Bird 3
Blue Jay 8
Yellow-Bellied Sap Sucker 3
Baltimore Oriole 3
Purple Finch 3
White Throated Sparrow 1
American Goldfinch 1
Tree Swallow 1
Red Headed Woodpecker 1
Rose Breasted Grosbeak 1

Sort By Frequency:
White Throated Sparrow 1
American Goldfinch 1
Tree Swallow 1
Red Headed Woodpecker 1
Rose Breasted Grosbeak 1
Yellow-Bellied Sap Sucker 3
Baltimore Oriole 3
Purple Finch 3
Indigo Bunting 3
Ruby Throated Humming Bird 3
Purple Martin 5
Blue Jay 8
Cardinal 13
House Sparrow 30

I've placed the code on my GitHub in the form of an html file along with the UML diagram, in case you want to see the actual code. I've also added a download button at the bottom of the page, which will download the executable java file, in case you would want to try it out.
THE CODE
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement