I want to create a 2D dynamic bool array (or char is fine too). I'm doing the n-queens problem and I've figured everything out except for this part. Any help?
Name:
Anonymous2006-01-03 16:45
oh yeah, forgot to mention its in c++.
Name:
Anonymous2006-01-03 17:16
Here's a hint for you: Are you ever going to want to place two queens on the same row? No. You don't need a matrix to hold the board state.
Name:
Anonymous2006-01-03 20:58
>>1
char a[8][8] is fine too, but read >>3. int a[8] is a better solution; make that cols and a[n] is the row it's in or -1. Use ints because they'll be aligned and you want that.
Name:
Anonymous2006-01-03 23:48
hay guys, i made a program in that makes the n-queens tree (if it's 8 deep, you win). am i cool yet?
import List
data Tree = Node Int [Tree]
deriving Show
queens lines = map (\n -> que n [] lines) [1..lines]
que n hist lines = Node n (map (\t -> que t (n:hist) lines) (posbs (n:hist) lines))
posbs s lines = [1..lines] \\ f s 1 where
f [] _ = []
f (x:xs) c = x:x+c:x-c:f xs (c+1)
Name:
Anonymous2006-01-03 23:50
err, make that n levels deep
Name:
Anonymous2006-01-04 3:12 (sage)
do your own goddamn homework and fuck off.
Name:
Anonymous2006-01-04 4:24
thanks guys. i'm done. the 1d array suggestion was great.
Name:
Anonymous2006-01-04 17:46
spamming my code lulz import List
queens :: Int -> [[Int]]
queens n = q n [] where
q :: Int -> [Int] -> [[Int]]
q 0 h = [h]
q c h = concatMap (\h -> q (c-1) h) (map (:h) (p h ([1..n]\\h) 1))
p :: [Int] -> [Int] -> Int -> [Int]
p [] s _ = s
p (y:ys) s c = p ys (delete (y+c) . delete (y-c) $ s) (c+1)
Name:
Anonymous2006-01-05 2:03
last question. i finished the nqueens code. works for n=1,...,7. anything higher and i get a "0xC00000FD: stack overflow" error on runtime. i tried to look for any flaws in the recursion but i couldn't spot any. my code is pretty short. can any one take a look at it for me and tell me why this is happening? if u can, can u email me at csx16@yahoo.com any help appreciated.
Name:
Anonymous2006-01-05 2:16
>>4
chars are always aligned, on IA32, so you don't get any performance loss for using chars instead of ints.
You're using recursion and the stack to store too much state. Increase your stack size (bad solution) or modify your algorithm to not use recursion in this explosive manner.
This is similar to the mistake of using recursion to calculate fibonacci numbers.
/quick reading of your code
Name:
Anonymous2006-01-06 9:50
>>12
too bad c doesn't optimize tail recursion. the easiest way to fix it seems to be goto's.
Clarity of algorithm is superior to to any particular technique. Fact of the matter is that most developers find iteration more understandable than recursion except in a very few well-defined situations. (e.g., what percentage of developers program in a Lisp without any iterative capabilities?)
Name:
Anonymous2006-01-09 20:16
>>22
I would say you are a retard if you don't understand simple recursion (not even recursion, it's really iteration). they should go back to programming school.
Name:
Anonymous2006-01-09 20:18
There are some basic things that programmers should know and I put understanding of recursion as one of them. In a math equation, how would one express the 'for' construct except with recursion. There is no other way. Recursion is something basic that all programmers should know.
Reality is most people are retarded, and they maintain your code and you maintain theirs. Deal with it and play nice.
Name:
Anonymous2006-01-10 1:33
Hello again. Thanks again guys for the suggestions. It sounds like everyone here knows a lot about recursion. So I have my last question. I've never used tail recursion and vaguely understand it right now, but I'll google it in a bit. My question is, can tail recursion fix this (note: 3 lines of code needed most likely): http://csx16.bol.ucla.edu/recursion.htm
Name:
Anonymous2006-01-10 3:36
>>26
Well, you won't get O(1), more like O(N). Try using an accumulator to add up the numbers.
>>26
You don't need tail recursion to fix this. In fact, I'd say that you've allowed yourself to get blinded by code and missed the trivial mathematical properties of the problem. It is quite possible to solve so that you can get lookups in O(1) time, and only use O(n) space, if you just stop and think about it.
Name:
Anonymous2006-01-10 12:05
Now, to explain tail recursion. Tail recursion is possible whenever the last thing a function does is call itself. Simple as that. That is all you need to know if you want to use it.
For example, in this code of yours int distance(int a, int b)
{
if(a==b)
return 0;
else
return (cities[b-1] + distance(a, b-1));
}the last thing that happens is not a function call, but an addition.
The compiler will most likely rewrite and optimize this to use tail recursion anyway. And finally, the compiler will optimize any tail recursion to become something closer to a for/while loop. But teachers generally do not like arguments like "the compiler is clever and makes up for my cluelessness", so you should favor iteration instead of recursion in your C code.
Name:
Anonymous2006-01-10 12:53
But teachers generally do not like arguments like "the compiler is clever and makes up for my cluelessness", so you should favor iteration instead of recursion in your C code.
Then your teachers are teaching the wrong thing. The programmer should not have to be clever and make up for the compiler's cluelessness. If you like hand optimizing enjoy your assembly code.
Name:
Anonymous2006-01-10 13:23
>>31
HAHAHAHAAHAHAHAHAHAHAHAH SO TRUE
Jesus if you haven't figured out your silly program by now I think you're going to fail your course.
Name:
Anonymous2006-01-10 13:30
>>31
You go to school with the teachers you have, not the teachers you wish you have, and neither #26 nor his teachers seem to understand what and how a compiler can optimize.
Name:
Anonymous2006-01-10 13:54
Well, this has been one of the lamest problems I have ever done, and it's sad to see i'm stuck on it. I'll just take in what u guys said and do this http://csx16.bol.ucla.edu/fail.htm
however that fails.
Name:
Anonymous2006-01-10 15:35
>>30,31,32
Umm...maybe the teacher is trying to teach the student how to differentiate between recursion and iteration?
Retards, you can't rely on the compiler for every thing. How about when the the code gets a tiny bit more complex, eh? Say goodbye to you iteration, lol.
Name:
Anonymous2006-01-11 3:11
>>35 does not understand tail recursion.
A compiler does not have to be smart to convert tail recursion to iteration; it merely has to avoid being dumb. It's trivially optimizable. That's why Scheme can include it as part of its spec; the programmer can expect it to be implemented so that he knows he doesn't have to use ugly loop contructs.
You might as well say programmers should assign memory addresses for all their variables because you can't rely on on the compiler for every little thing.
Name:
Anonymous2006-01-11 3:21
>>36
I was not talking about tail recursion. I was talking about this recursion: return (cities[b-1] + distance(a, b-1));
Name:
Anonymous2006-01-11 3:51
>>37
*sigh* changing your story only makes you look even more like an idiot. I bet that you are one of those still working on useless shit like using integer math to optimize division. L O L
Name:
Anonymous2006-01-11 5:16
>>38
WTF??? >>30 obviously says that he expected the compiler to optimize that not tail recursing function. i did not even mention tail recusion in >>35. so shut up and go fap to your programming superiority complex fantasies.
Name:
Anonymous2006-01-11 9:10
>>28
If you have an array like char[10], then accessing any char inside it will take the same amount of time. If you are worried about it unaligning the rest of the stack, you should not, because the compiler will add unused space at the end to make sure that everything else stays well aligned (unless of course you are using a shitty compiler).
Name:
Anonymous2006-01-11 9:17
>>35
Everything that can be done as iteration can also be done as tail recursion.
Name:
Anonymous2006-01-11 9:21
As far as gcc4 is concerned these two functions are equivalent (they literally produce the same assembler). As far as gcc3 is concerned the first one sucks donkey balls. extern int cities[];
int distance(int a, int b)
{
if(a==b)
return 0;
else
return (cities[b-1] + distance(a, b-1));
}
int distanceii(int a, int b)
{
int x = 0;
while (a != b)
x += cities[--b];
return x;
}Still, both of them are a flawed solution to the problem.
Name:
Anonymous2006-01-11 12:44
So, can you tell me what is not a flawed solution?
Name:
Anonymous2006-01-11 13:07
And give away the answer to someone's homework? Fuck no.
Name:
Anonymous2006-01-11 13:08
haha, well it's obvious you dont know the answer.
Name:
Anonymous2006-01-11 15:27 (sage)
>>45
Oh noes, I have been insulted over the internets! Now I must listen to Nightwish and cut myself.
Name:
Anonymous2006-01-11 16:44
bare grace misery is my favorite. okay guys, if the solution should some sort of recursion type then let me know. if its iterative tell me. i posted just to know genreally speaking which method would be more efficient.
Name:
Anonymous2006-01-11 17:04
orz...I wasted too much time on this. Not that the original poster would understand this... Not that I tested this either.
int N = 5;
int cities[N] = {5,3,2,6,7};
int *distances;
int sum (int a, int b) { return ((b*(b+1) - a*(a-1))/2); }
int index (int a, int b) { return (a*N - a*(a+1)/2 - 1 + b); }
int distance (int a, int b) { return (a==b ? 0 : distances[index(a,b)]); }
void make_distances (int a, int b) {
distances = malloc (sum(a,b));
int i=0,acc;
for (a=0; a++; a<N) {
acc = cities[a];
for (b=a+1; b++; b<=N) {
distances[i] = acc;
acc += cities[b];
}
}
}
Name:
Anonymous2006-01-11 17:26
>>48
You may have halved memory usage, but you're still in O(n^2). I assure you it can be done in memory O(n), initial calculation time O(n), and lookup time O(1).
>>47
Which means use either recursion or iteration -- but preferably iteration -- for the precalculation and use neither recursion not iteration for lookup.
Name:
Anonymous2006-01-11 17:42
Damnit, there is a mistake in my code in >>48. It should be void make_distances () {
distances = malloc (sum(0,N));
int a,b,i=0,acc;
for (a=0; a++; a<N) {
acc = cities[a];
for (b=a+1; b++; b<=N) {
distances[i] = acc;
acc += cities[b];
}
}
}Memory and initial calculatiion time is still O(n*(n+1)/2) though.
Name:
Anonymous2006-01-12 0:01
well, looking at it again, i got it. int N = 5;
int cities[N] = {5,3,2,8,7};
int *ctsums;
int distance (int a, int b) { return (ctsums[b-1]-ctsums[a-1]); }
void make_ctsums () {
ctsums = malloc(N);
int i,acc=0;
for (i=0; i++; i<N) {
acc += cities[i];
ctsums[i] = acc;
}
}O(n) space and init time. O(1) lookup. the solution was just staring at me...i can't believe i didn't see it before.
Name:
Anonymous2006-01-12 4:19
haha, damn i didn't even think about that. what a fool i am.