|
Hello everyone, I have to find the biggest rectangle(square) in a matrix which holds only even numbers.
If I have normal rectangle with even numbers my code is working, but if I have some strange figure like two rectangles in one my code fails.
Please anyone who have done something similar before to give me a clue how to get this rectangle.
I am not very sure is it my post for here, so if its not please excuse me.
Here is my code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace EvenNumberMatrix
{
class EvenNumbers
{
public static int[,] givenArray ={
{5,2,6,8,5,9},
{7,5,3,2,4,7},
{9,6,3,6,4,2},
{8,5,3,6,2,2},
{9,6,3,7,4,7},
{8,5,6,2,2,5}
};
public static int maxCol = 0, maxRow = 0;
public static int[,] tempGivenArray;
static void PrintArray(int[,] a)
{
for (int x = 0; x < a.GetLength(0); x++)
{
for (int y = 0; y < a.GetLength(1); y++)
{
if (a[x, y] != 0)
{
Console.ForegroundColor = ConsoleColor.Green;
}
else
Console.ForegroundColor = ConsoleColor.Gray;
Console.Write(a[x, y] + " ");
}
Console.WriteLine();
}
}
static void Main(string[] args)
{
int number = 6; int countRows = 0, countCollums = 0, x, y;
tempGivenArray = new int[number, number];
for (int i = 0; i < number - 1; i++)
{
for (int j = 0; j < number - 1; j++)
{
if (givenArray[i, j] % 2 == 0 &&
givenArray[i + 1, j] % 2 == 0 &&
givenArray[i, j + 1] % 2 == 0 &&
givenArray[i + 1, j + 1] % 2 == 0)
{
tempGivenArray[i, j] = givenArray[i, j];
tempGivenArray[i + 1, j] = givenArray[i + 1, j];
tempGivenArray[i, j + 1] = givenArray[i, j + 1];
tempGivenArray[i + 1, j + 1] = givenArray[i + 1, j + 1];
}
}
}
for (int i = 0; i < number - 1; i++)
{
for (int j = 0; j < number - 1; j++)
{
x = i; y = j;
while (tempGivenArray[x, y] > 0)
{
x++;
countRows++;
if (countRows > maxRow)
maxRow = countRows;
if (x > number - 1)
break;
}
x = i; y = j; countRows = 0;
while (tempGivenArray[x, y] > 0)
{
y++;
countCollums++;
if (countCollums > maxCol)
maxCol = countCollums;
if (y > number - 1)
break;
}
countCollums = 0;
}
}
PrintArray(tempGivenArray);
Console.WriteLine("The biggest rectangle with even numbers is: "+maxCol * maxRow+" positions!");
}
}
}
Thank you very much in advance
|
|
|
|
|
Hi,
I haven't studied it all in detail, I do have two things for you to reflect on:
1.
why are you using a second int matrix, where 0 means one thing, and non-zero another; all you are interested in is odd or even. BTW: what would happen if some of the input numbers are zero (zero is even!)
2.
when checking for an even subrectangle, how come you have two while loops that are not nested?
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
Thank you for your reply
1. I am using zero based matrix for better visualization and when I make logic conditions to check the numbers are they even is easier for me to check are they more than zero. In my case I have to check for numbers >0.
2. I tried with nested while loops but the result is the same, or my knowledge is not enough to figure it out how to check for rectangle, for that I have nested for loops to get the current position and with while loops I am checking from current positions are they any rectangle existing.
Greetings
|
|
|
|
|
Hello, I have populated my WPF listbox from c# code like this:
private void button1_Click(object sender, RoutedEventArgs e)
{ listbox1.Items.Add("blah"); }
Well, the items appear in the listbox, but I CAN'T SELECT THEM INDIVIDUALLY. I've also found that the "index" property is the same for each item.
However, if I populate the listbox from XAML, it works PERFECTLY: selection is OK, indexes are different.
What's wrong with my code?
|
|
|
|
|
I've found it out, this question is out of... question
|
|
|
|
|
I have two pages. Page A cross postbacks to Page B. On both pages I have a hidden field. I want to set Page B's hidden field with the value from Page A. The problem is that when it leaves Page A a value is in the hidden field. However when it Page B initializes (which is where I am checking the value and writing it to the new hidden field.) the value is an empty string. I have stepped through the code to make sure that when it leaves Page A there is a value and when it "arrives" Page B there is an empty string.
I cannot figure out why this is happening. Can anyone assist? Here are the pieces of my code:
protected void Page_Init(object sender, EventArgs e)
{
Page pg = PreviousPage;
if (pg != null)
{
HiddenField hfPrevStudent = Helpers.FindControl<HiddenField>(pg, "hfStudent");
HiddenField hfPrevSchool = Helpers.FindControl<HiddenField>(pg, "hfSchool");
if (hfPrevStudent != null)
{
hfStudent.Value = hfPrevStudent.Value;
hfSchool.Value = hfPrevSchool.Value;
}
}
}
~Candi
|
|
|
|
|
Hi! I am doing a project about a game - a 5x5 grid with letter. The player must search words from the grid.
void SeekWords(string word, int[,] visited, int x, int y)
{
if (!(x < 0 || x > 4 || y < 0 || y > 4) && visited[x, y] == 0)
{
visited[x, y] = 1;
SeekWords(word + Grid[x, y], visited, x - 1, y - 1);
SeekWords(word + Grid[x, y], visited, x - 1, y);
SeekWords(word + Grid[x, y], visited, x - 1, y + 1);
SeekWords(word + Grid[x, y], visited, x, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y);
SeekWords(word + Grid[x, y], visited, x + 1, y + 1);
visited[x, y] = 0;
}
}
This method is good, but for words longer than 6 letters it's too slow. Are there other algorithms for searching the matrix which are faster?
Thanks
Still learning...
|
|
|
|
|
I can understand this code is slow :P.
But I don't really get what you want to achieve? Can you maybe clearify that?
Is it like a snake? which will check for a word like this:
{a, b, c}
{d, e, f}
{h, i, j}
and if you try the word 'abf' it will find it and starts at point 0,0 and ends at 2,1. But if you try 'abj', it won't find anything?
If it is, I think it is funny and I'll try to code it , if it isn't please explain how and what you mean exactly.
|
|
|
|
|
Yes, it is like a snake. The word 'abj' form your example isn't valid according to the rules of the game. Each next letter must be a neighbor to the previous. For example: 'adi', 'hec'...the word 'ada' is not valid (a letter from a box of the matrix is used only once).
I was thinking of a solution with combinations and a check if the letters are neighbors (this is only an idea, I haven't thought about it much) .
Still learning...
|
|
|
|
|
Hi,
I have several remarks:
1.
From every position you could move to 8 adjacent squars, however you only have 7 SeekWords calls; you skipped one, it will become even slower!
2.
I don't see the word length anywhere in your code; the code as it is will search for all the longest words; i.e. on a 5*5 board it will find several 25-character words, and a lot of shorter ones because "the head of the snake" gets caught in a dead-end. On a 6*6 board, it will find several 36-character words, and a lot of shorter ones, including all the ones found for a 5*5 board. The complexity of the job is more than exponential in z, where z is the size of the board.
Therefore, there is no decent general solution; it grows at an enormous pace.
3.
However, there are ways to improve, not so much by changing the algorithm (you have to investigate all possibilities, there is no escape), but rather by changing the implementation. The biggest factor I can see is the matrix. I suggest you smash it into a linear array, i.e. let Grid[0]...Grid[z-1] represent the first row, Grid[z]...Grid[2*z-1] be the second row, etc.
That means the current position (former x,y) becomes p, and a line such as SeekWords(word + Grid[x, y], visited, x - 1, y - 1); becomes SeekWords(word + Grid[p], visited, p-z-1);
which just is simpler, hence faster.
4.
visited[] could hold booleans instead of ints with values 0 and 1; I don't expect that to influence performance. Also visited[] could be a class member, making it unnecessary to pass it as a method parameter; doing this probably would slow things down, since class members are "farther away" than method parameters.
5.
if x equals 0 there is no need to try three SeekWords(x-1) since they will fail their initial test.
similar for y==0, x==z-1 and y==z-1
you could perform one test inside SeekWords as in
SeekWords(...) {
if (...) {
if (x>0) {
SeekWords(... x-1 y-1)
SeekWords(... x-1 y)
SeekWords(... x-1 y+1)
}
if (x<z-1)>etc.
Of course, in a one-dimensional array it becomes slightly more complex.
One easy and fast way is to make 8 extra boards, one for each direction, initialize them properly and then just do eight times something like if (canStepInDirectionMM[p]) SeekWords( p-z-1)
canStepInDirectionMM[] would contain true everywhere except for those starting positions that don't allow a step in the direction (use M for minus, Z for none, P for plus in both X and Y direction).
Doing so, the complex if at the start of SeekWords reduces to if(!visited[p]) {...}
I expect the above to speed up things by say a factor of 3, so maybe it becomes acceptable for a 6*6 board, but I see no easy way to tackle larger boards unless there were an acceptance test on the words, say "an exact length of N letters", or "all letters appear in alphabetical order". If so, the nesting of SeekWords with be curtailed most of the time, leaving only very few (relatively speaking) combination to be investigated.
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
In the code I have posted, some parts are missing, including the one with the word length. For word with maximum length 5 and minimum length 3 is very good. I will consider your suggestions.
I have an idea. If the current word is 4 characters, the program will also search the first four characters of the dictionary words. If there isn't a match, the words which derive from the current also won't have a match.
Current word: ac
Dictionary:
abcde
abefg
abegh
In the example there is no word starting with 'ac', so the words derived from 'ac' won't be in the dictionary. This will save a lot of roaming in the grid.
Still learning...
|
|
|
|
|
Well, I've managed to accomplish my goals. Before the program searched words with max length 8 letters for about 3 minutes. Now it searches words with max length 15 letters for less than 4 seconds!
Still learning...
|
|
|
|
|
I made an application with a form that starts another thread.
see: http://www.codeproject.com/script/Forums/View.aspx?fid=1649&msg=2979123
Now when I drag or resize the form the thread blocks
for about 1/4 of a second...
Googled a bit and it seems to be a typical Windows problem,
is there a way around it?
I tought of even using a different proces (with "real time priority")
instead of that 2nd thread, but that's maybe a drastic and complex solution.
|
|
|
|
|
invader82 wrote: Googled a bit and it seems to be a typical Windows problem,
is there a way around it?
No. Considering Windows is not a real-time O/S (despite the priority name), your thread, even under the best of conditions, can be put on hold for a while other things are going on in the system. Your thread is never guaranteed a set amount of time to run, nor is it ever on a set schedule.
|
|
|
|
|
Well, the dragging takes place in the gui thread.
So I made a faster multimedia timer that periodically (about 1ms) invokes a method on the gui thread that:
- Sets the ManualResetEvent
- Does Thread.Sleep(0) to give up his quantum
It will never be 100% reliable, but still, it's way better than before
I know that windows is no real time operating system,
but using some real time middleware is not always an option.
|
|
|
|
|
Hi,
One simple thing you can do to reduce the amount of redrawing when dragging and resizing is to change the performance options for your PC.
In XP, go to the System control panel , click the advanced tab and then the performance button. Under Visual Effects there are a few presets but firstly try the best performance option and see if there is any improvement.
Alan.
|
|
|
|
|
I don't think that is a very good solution...
I found my own solution (not 100% reliable ...)
|
|
|
|
|
How exactly do I set s user to be disabled? I can get the value.. but how do I set it:
bool? AuthenticablePrincipal.Enabled
Gets or set a Nullable boolean vlaue that speecifies whether this account can authenticate...
but how do I set it to false?
UserPrincipal getUser = UserPrincipal.FindByIdentity(context, userName);
getUser.Enabled = false;
Does not work.
|
|
|
|
|
You also need to follow those statements with:
getUser.Save();
If you're already doing that, then I don't know. It's worked for me in the past.
BDF
People don't mind being mean; but they never want to be ridiculous.
-- Moliere
|
|
|
|
|
Well our AD is at server 2008 level.. That wouldn't make a difference would it?
I did try with a save before and it didn't work
|
|
|
|
|
I don't know if 2008 would make a difference or not, sorry.
Jacob Dixon wrote: a save before
No, you have to do the save after.
This is an existing user that's been saved to the store, I'm assuming.
BDF
People don't mind being mean; but they never want to be ridiculous.
-- Moliere
|
|
|
|
|
I have a program that contains a “start time” and “end time” to equal TempHours
I would like dHours to be the rounded figure.
I am trying to round the number up to next tenth of an hour
(IE 4.11 hours is 4.2 hours but 4.10 hours stays at 4.1 hours)
What do I need to add to the below statement to get it working
decimal dHours = Math.Round(decimal.Parse(TempHours.ToString()),3);
Thanks
|
|
|
|
|
ok,
Two questions for you
1) What does not working mean?
2) What type is the TempHours variable?
Alan.
|
|
|
|
|
Why are you changing it to a string?
If TempHours is already a numeric type (single, double, decimal, etc), just do this:
decimal dHours = Math.Round(TempHours, 1, MidpointRounding.AwayFromZero);
Second parameter is the number of decimals. 1 = To the nearest tenth. Third parameter tells it you always want to round up to the next value, never down.
|
|
|
|
|
Hi,
why would you call ToString() and then Parse() to turn a number into another number? This is nonsense, as it wastes lots of CPU cycles: numbers are stored in binary for a reason, it takes a lot of divide-by-10s to perform a ToString() on a number.
Math.Round does rounding in the regular way, i.e. 1-4 go down, 5-9 go up.
However you want 1-9 to go up, hence add 0.04 to the original number, then use Math.Round
Warning: you did not define how it should work for negative numbers; whatever straight code you come up with, there is a 50% chance it won't do what you want for negative numbers. If so, test for negative, and provide two different formulas.
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|