|
Hi,
I would like the following functionality:
- None of the Ellipse elements may be at the same Grid.Row|Grid.Column combination as another Ellipse in the ellipseArray.
- Each Ellipse has to find its unique position on the Grid [x,y].
So I can't have two Ellipses both having the same value for <Border Grid.Row and Grid.Column> (e.g. both ["0","0"]).
See code here:
<Border Grid.Row="0" Grid.Column="0">
<Canvas>
<Ellipse Width="100" Height="100" Fill="Red"/>
</Canvas>
</Border>
..(This code is repeated 9 times, where .Row and .Column are variable. The last <Border> has no <Ellipse>)I have 8 Ellipse elements on a Grid of 9 squares.
It looks sort of like a collision algorithm.
How would I accomplish this?
----
EDIT: I fixed it. See code below.
function checkPositions() {
var j = 0;
var collision;
do {
var newRow = Math.floor(Math.random() * 3 + '');
var newCol = Math.floor(Math.random() * 3 + '');
borderArray[j]['Grid.Row'] = newRow;
borderArray[j]['Grid.Column'] = newCol;
collision = false;
for (var i = 0; i < j; i++) {
if (borderArray[i]['Grid.Row'] == (borderArray[j]['Grid.Row'])
&& borderArray[i]['Grid.Column'] == (borderArray[j]['Grid.Column'])) {
collision = true;
break;
}
}
if (!collision) {
j += 1;
}
} while (j < randomRowsArray.length+1);
modified on Saturday, July 16, 2011 11:53 AM
|
|
|
|
|
What you did is fine for a 3x3 grid. But a more efficient way would be to produce a list of all the possible pairs of points and then randomly pull a pair from that list, assign it to your item and then remove it from the list. This way you can guarantee no collisions. As a bonus, whatever you have left in the list at the end is all your empty cells.
Whether this method is faster than yours depends on the size of the grid and the number of items in the grid. For example, in a 10 x 10 grid with 99 items, it will almost certainly be faster. In a 10 x 10 grid with 1 item, it certainly isn't.
However, the worst case performance of your algorithm is infinity!
modified on Thursday, July 21, 2011 3:45 PM
|
|
|
|
|
Hello,
I have a grid with 9 cells, where each cell has a [row,col].
Please see the following image for my problem description:
problem situation
I would like to have the following functionality:
- When you click on one of the circles in the grid,
the clicked circle takes in the place of the only empty square on the grid.
The empty space then in turn switches places with the circle that has just been moved.
Seems easy enough, but I can't figure out how to do this.
My new code is this:
for (var i = 0; i < borderArray.length; i++) {<br />
if (borderArray[i].findName('ellipse' + (i + 1)) == null) {<br />
alert('sr: '+ sender['Grid.Row']);<br />
alert('sc: ' + sender['Grid.Column']);<br />
alert('br: ' + borderArray[i]['Grid.Row']);<br />
alert('bc: ' + borderArray[i]['Grid.Column']);<br />
<br />
sender['Grid.Row'] = borderArray[i]['Grid.Row'];<br />
sender['Grid.Column'] = borderArray[i]['Grid.Column'];<br />
}<br />
}
sender[row,col] keeps being 0,0 for some reason, no matter which circle I click on.
It should take the [row,col] value of the sender I clicked. This is strange.
//Edit: fixed this partially. The 'MouseLeftButtonUp' should have been on <border> not on <ellipse>
Languages used:
- JavaScript
- Silverlight
Thank you
modified on Friday, July 15, 2011 1:03 PM
|
|
|
|
|
I think your problem is a XAML/JS problem not an algorithm problem. I assume borderArray is a flat array of all 9 cells and you are looking at each one in turn to find the one that is empty. That is a perfectly valid way of doing it, although a better way would be if you have populated the grid in the first place, can't you just keep track of which cell is empty instead of searching every time? That would be much more efficient.
As to what causes your actual problem, I can see a couple of things that strike me as odd, but you don't provide enough information to make sense of it.
Firstly, if every cell in your grid contains a border (which I assume is what borderArray is), setting another control to the same grid row and column does not make it a child of the Border (assuming your sender is the ellipse and not the border itself) in that cell.
Second, your search for 'ellipse' + (i+1); I'm assuming you have 8 ellipses that you've named ellipse1, ellipse2, ellipse3, etc. Then you've put ellipse1 in cell 0,0 ellipse2 in cell 0,1, etc. Now, once you've swapped one of those ellipses to a different cell, your borders (which I'm assuming aren't moving) don't hold the same ellipse (although they don't hold them at all, as I said earlier) as they started with. So looking for ellipse1 in borderArray[0] isn't valid if borderArray[0] now contains ellipse2.
Finally, if, as I suspect, you set this up so that the ellipse originally are children of Border controls that are actually in the grid, then it's not a surprise that you get Grid.Row and Grid.Column of 0,0. The ellipses aren't actually in the grid, their parents are.
|
|
|
|
|
How do you take transactional information and post it on a web sight in different financial indications like nasdaq.com?
|
|
|
|
|
|
Richard,
Thank you for the response. My apoligies for not posting algorithmic specific content here, I am new to the site and just needed some help.
Thank you for the link.
Regards,
Burt123
|
|
|
|
|
Burt123 wrote: I am new to the site
No problem; take a look at the posting guidelines[^] for future reference.
The best things in life are not things.
|
|
|
|
|
I have made a lot of modulo things last days and it's totally blowing my mind. Could somebody give me a hand with this one?
I'd like to replace this snippet:
while (x < -7)
x += 12;
while (x > 7)
x -= 12;
with some smart modulo one-liner. Any ideas?
Greetings - Jacek
|
|
|
|
|
Are you sure it is correct? Shouldn't it be
while (x <= -7)
x += 12;
while (x >= 7)
x -= 12;
If indeed it should be that, maybe x = ((x + 6) % 12) - 6; would work (not tested)
|
|
|
|
|
I agree that the question was probably meant to constrain to ±6. I would use ((x+18)%12)-6 because mod with negative numbers doesn't do what you expect, in some languages at least.
Edit: that sentence was rubbish, the number needs to be brought into [-18,] before that is useful.
This has a potential overflow if x can be near the top of the range for the numeric type in question. To avoid that you can do something like
x = x % 12;
if(x < 0) x += 12;
if(x > 6) x -= 12;
(You can one line it: x = (((x%12)+18)%12) - 6 ... but two mods is likely to be slower than the branched version. You can also one line the branches:
x = (x = (x = x % 12) < 0 ? x + 12 : x) > 6 ? x - 12 : x;
... but your manager is likely to shoot you and it is no faster.)
|
|
|
|
|
You're right of course, so have your 5
|
|
|
|
|
No, it shouldn't. The original post was correct.
Greetings - Jacek
|
|
|
|
|
That's unusual and I couldn't find a simple solution, but I found a way that at least removes the loops.
static int SpecialModulo(int x)
{
x = x % 12;
if (x < 0)
return x < -7 ? x + 12 : x;
else
return (x & 7) - ((x & 8) >> 1);
}
|
|
|
|
|
(x & 7) - ((x & 8) >> 1);
Could you explain this line of code? I seriously don't know what does it do.
Greetings - Jacek
|
|
|
|
|
If it's above 7 (well, 7-15, but we have done mod 12 already), i.e. it has an 8 bit set, it drops the 8 bit (via the &7) and subtracts 4 (x&8 will be 8), i.e. subtracts 12. I would think that x-12 would be faster though so I'm not sure why it's written this way.
|
|
|
|
|
Because you shouldn't Always subtract 12, but only when it is bigger than 7. Of course a conditional would also work
|
|
|
|
|
Yes, I meant
if(x > 7) x -= 12;
... apologies for missing the first part. I still think that will be faster than the ands, shift and subtract, though it would be close.
|
|
|
|
|
Ok, so what you want to do is map numbers over 7 onto [-5, 7], and those below -7 onto [-7, 5]. Your modulo is 12 but the range size is 14, so there won't be a one liner with mod. I can make one with a ternary:
x += 12 * (((x < -7) ? 5 - x : (x > 7) ? -5 - x : 0) / 12);
... though, as above, this can overflow, and it is probably better to do
if(x < -7){
x = (x + 7) % 12;
if(x < -7) x += 12;
} else if(x > 7) {
x = (x - 7) % 12;
if(x > 7) x -= 12;
}
|
|
|
|
|
Yea that's probably better than mine..
|
|
|
|
|
Actually, it is impossible for x to exceed range (-12,12). I have changed from if to while "just in case", but I doubt there would be more than one iteration. So, since a solution with modulo seems to be very sophisticated and not clear then I decide to use a more readable form with while "loops".
I just though that there is a simple solution in form (x - a)%b+c which I missed.
Anyway, thanks for help. Sincerely, your modulo skills impressed me (that ternary thing is awbeatyful).
Greetings - Jacek
|
|
|
|
|
For a constrained range the simple version with ifs (I don't really recommend the ternary approach in production code, it's just fun to see what you can do with it) will be faster than any 'clever' approach with a modulo. Mod and div are extremely slow and a couple of branches to do the same task as one should win.
You shouldn't use the while loops if you have set your domain to (-12,12). They are adding an extra test for nothing, but worse, they are confusing to people reading the code (including yourself in three months) because it looks like the domain is unconstrained. If you're concerned you can put a range check and throw an exception (or language equivalent, this could be any C family language) if the input is outside the domain.
|
|
|
|
|
I started doing crazy things such as:
static int SpecialModulo(int x)
{
return (x & 7) - ((x & 8) >> 1) - ((x >> 31) & 4);
}
Trying to make a branchless version..
And then I realized.. why not just use a lookup table?
int[] table = new int[] { 0, 1, 2, 3, 4, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, -4, -3, -2, -1 };
x = table[x + 12];
|
|
|
|
|
int[] table = new int[] { 0, 1, 2, 3, 4, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, -4, -3, -2, -1 };
x = table[x + 12];
Nice. I think you missed %table.Length though.
Greetings - Jacek
|
|
|
|
|
Not if x is only in [-12, 12], which you said at some point..
As an alternative I have a slower way that only uses arithmetic (I just like doing that)
(((abs(x)+4)%12)-4)*sign(x)
int abs(int x)
{
int t = x >> 31;
return (x + t) ^ t;
}
int sign(int x)
{
return 1 | (x >> 31);
}
|
|
|
|
|