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).