Totally willing to pay for this btw.
First year university student needs c# HELP
I have an MxM binary matrix with 1s and 0s and have to find the larges rectangle sub-matrix with no 0s in it.
EXAMPLE:
1110
1110
1011
0111
In this example the largest rextangle would be from 0,0 to 1,2
NOTE: I will also have to explain the code to my prof so please don't use histograms and stuff like that as I have not used them before. A brute force approach would be the best
Other urls found in this thread:
not your personal army
I'm well aware of that and I'm not demanding you to help me but if by chance someone has the knowlage and the spare time or wants to make some money I would really appriciate the help.
It's easy, just do this
it is simple just use the Moore–Penrose inverse
And how would I go about using that?
see
Op if you just gonna brute for this then take the example you gave us, write out all the possible rectangles you can create with that, then figure out how to put that into 2 for loops.
This is easy. Work in one dimension, and then just loop out for the second.
The figuring out part is kind of the problem here haha
Write some code to print out all possible rectangles. After that just do some comparisons.
How can I print out all possible rectangles tho?
Just google 'bruteforce largest rectangle' and read any that don't have histogram in the title.
But seriously I understand this is Sup Forums but if your computer science half the students are like you so go make some friends and then you can ask stuff like this to them.
No one please help him, someone as stupid as OP should not hold a degree
abstract subfields as bytes, call edge-detection routine
Better yet, randomly generate a rectangle of side lengths a,b s.t. a,b
what I would do:
given the input, split it into a multidimensional array
table ( row1 ( number1 , number2), row2 (number1, number2 ) );
then make the bruteforce
values = array
foreach table as rownumber -> row
foreach row as numbernumber -> number
x= 0
while( row [numbernumber] = row[numbernumber + x] ) {
x++
}
while( table [ y ] [ x ] = row [numbernumber] ) {
y++
}
values [] = x*y;
}
}
echo max(values);
Thanks
Everyone's busy with all the exams so I can't bother too many people but I am trying every option
And thanks i'm googling that right now.
stupid brainlet
how about you do it yourself? I am complete shit at programming but how I would do it is go through the matrix, measure rectangle size for every element and store the largest one. you only have to go upward in index because the other way would be redundant. for optimisation you can also add break conditions
How would the Moore–Penrose inverse help at all?
Obvious troll is obvious.
He needs the coordinates, not just the area, which, by the way, can be computed without using so much memory--the matrix is probably already given as a multidimensional array.
I have a 2D array from a text file where the first line contains the size of the array and the number of 0s in it.
These are the solution to your problem. The first is the abstract concept, and the second is the code. If you can't figure out how to complete your project with these posts you shouldn't have waited until the end of the semester to make your first submission to the autograder.
This is an almost trivial dynamic programming problem. Just keep a list of currently active squares, and try to grow them as you move on. If it can't be grown, store its value as final, otherwise grow it. And as you move on, add the new ones to the list of active squares.
I think you should leave cs and try something that is better suited for your low IQ. If you cant solve this simple problem, then why do you study it?
Or you can just store the largest currently active square and do a comparison in-place versus storing a bunch of useless boxes in memory.
Thank you.
English isn't my first language which makes this a bit difficult. What do you mean by "looping out"?
Because that's the point of going to school. Not OP, but speaking as someone who has about a year left in cs degree from a very good university.
No, you can't do that. Some of the smaller squares might grow to be larger than the currently largest.
walk across the matrix in whatever way makes sense to you(probably left to right and downward), and at each position find the largest chain of ones going in a forward direction from said position. Then find the height of the largest rectangle which has that width, who's top-left corner is the current position that you're at. Compare that rectangle's area with the largest you've found so far and the rest you should be able to figure out.
code will fail on
1 1 1
1 1 1
1 0 1
0 0 1
1 0 1
0 1 1
1 0 1
I see. So the way I find the largest chain of ones would be to something like:
While (i
Or any other rectangle that's filled with zeros
Pretty close. But I think you're missing one key step that makes not work.
Whoops I meant
You can use 2 fors.. One to go horizontally until you find a 0 and another to go vertically until you find a 0.
Then you multiply the numbers obtained and check if it's the biggest. If it is, save the coordinates.
Repeat (with a for, increasing the horizontal value and/or vertical value) until you get the biggest number.
so far I have this.
any idea what that missing step would be?
If I only go horizontally and vertically there might be a zero in the middle and i'd never know
I just realised this wouldn't work either since if I go vertically down two for example I'm immedietly not checking if the top line of the rectangle contains a zero or not...
u guys are fucking stupid. make a function to find the largest rectangle containing a point. Do this by walking up and down the column in a straight line and building the longest line you can, and let that be your base max.
then try to expand that line's width to the right. Decrease the height until you can expand the width (, and if the next rectangle has a larger area than your current max, it's the new max. Naturally, you'll shrink the height until it's of height 1.
now call this function on every 1 in the matrix, and keep the biggest.
btw there are optimizations to this but ill leave that to op
Anyone wanna just write it for me? I have ~37$ that I can send via paypal
The more interesting challenge about this exercise is to find the O(n log n) solution.
Korva.
I made this pile of shit for you, it has some easy optimizations you can do.
pastebin.com
I dunno what that means
Thank you I really appriciate it. If you have some free time we could hop over to skype to go over it and the payment is yours ^^
Just write the matrix in an one d array. Sort that with random sort or smth . then count the zeros and devide that number by n/8. On Average this should be right. Bets case is O(n)
Don't lie you little shit, I meant Kurva.
It's just a fill function.
If you want your own implementation that's easy to explain.
>brute force would be best
Excellent.
I'm assuming you're not allowed diagonal rectangles (45 degrees).
You just start at the top left. Assume a 1 width 1 height rectangle from that position. Look to your right, if there's a 1 there you look if there's height-sourceSquareY-1 number of squares up from that. In this case we have height 1 so you check 0 squares. Add 1 to the width. If there wasn't a 1 or you're done with this step you continue on to the next step:
Now check downwards, if there's a 1 you'll check everything on the row towards the left that's not more to the left than the starting pos is also a 1 (alternative way of saying this is what I said before, check width-sourceSquareX-1 squares to the left). Add 1 to height.
Repeat from the start until you've failed both the horizontal and the vertical condition in one go.
Then you iterate through all the squares on the board. Save the starting position that have you the maximum height*width.
I'm explaining this more so you can write it out since you needed understanding.
No payment required. Just remember to git gud and help someone else when you can.
yeah diagonal rectangles don't count
could you please write this out using actual lines of code? I'm having more trouble writing the actual code than coming up with ideas at this point
but i'll have a few weeks to study the actual code before I have to explain it.
This is worse than 1. you don't have the exact location of every 1, so you're still going to need to walk through the matrix
2. you're growing in two directions for every dimension except for one
Writing code from scratch is very important to know user. I suggest you take time to train that. Remember than you're spending a lot of money/time on your university studies. If you don't learn your profession well that's really bad.
I didn't think this was worth mentioning but I do have the the exact location of every 1 and 0
But the locations change based on the imput file (which will be changed a few times to test it) but I wrote a few lines to get the exact location of each
yeah I know I was pretty good at all this up until a few weeks then I had to focus on math classes more and didn't have time for this. But I do plan on learning it properly just not right now since i'm running out of time
will do ^^
quick question tho is array [] [] the same as array [,]? because if not then i'm not sure what most of the code you wrote means haha
I didn't know about [,] until just now. They work similarly. You should be able to change the code to use [,] if you feel more comfortable with that.
ie, array[x][y] becomes array[x,y]
Alright thank you.
So I wrote tried to use your code wrote it in by hand but something doesn't seem to work properly
The problem seems to be here.
If the array needs two "things" in it like array[a][b] then how come at the green circles you've only used one?
and more importantly what could I use to replace the .lenght part? since I don't normally use [][] format I'd like to change that to [,] but i'm not sure how to do that here
array[a,b].getlenght(0) and getlenght(1) gives back the lenght of the array's rows for 0 and collums for 1 (or vice versa idk) maybe I could use those but that still leaves some questions.
If you could just write a few comments explaining that part alone I could probably change it the way I need it
so close to the answer I can't let this thread die now T_T
After some research I've found that array[][] is a jagged array while array[,] is a multidimensional array
now just gotta find out how to change the code from being usable with a jagged array to being usable with a multidimensional array
If variable x is of type int[][], then x[0] is of type int[] and x[0][0] is oof type int
I am so sorry that I have to do this but I still don't understand it could you elaborate?
the code is almost all done the stuff is working perfectly with a jagged array but unfortunately I have to use a multidimensional one
i can do it tomorrow if i remember
I would love that thank you so much. Could I get your skype adress or email adress? or better yet mine are bolf.laci for skype and [email protected]
you can't imagine how much it'd mean to me
ofc I can still pay about 37$ I know it's not much but that's all I can spare. Although I could get some extra money in the following days if it's necessary. Anything just let this thing be done before friday i'm pretty desperate at this point
gotta go now it's getting late in my time zone but I hope this thread won't die until tomorrow.
And please do reach out to me if you can