What do you need help with? V. 3.0

[Anonim]

[QUOTE=Swebonny;33157270]Helppp![/QUOTE]

The algorithm performs two sub-passes (the for-loops) over the array for every pass through the while-loop. During the first sub-pass it checks if A[i] is greater than A[i+1] for all i <= n - 2 and swaps if that's the case. During the second sub-pass, it checks if there are any remaining A[i] greater than A[i+1], and if there are, it needs to iterate again.

This will continue until it has been sorted (i.e. no A[i] are greater than A[i+1] for all i <= n - 2).

This implementation seems to have a complexity of O(2*(n-1)^2) ~ O(n^2). Listen to Obama: Bubble sort is not the way to go!

[Meatpuppet]

[QUOTE=BlkDucky;33157191]Looks like C. Bool isn't a thing in C. I think the standard way of faking it is to use a char.[/QUOTE]Jookia helped me. Now, it's

int main()
{
    char choice;
    printf("Welcome to Generic Shooter 2. What do you want to do?\n 1. Start New Campaign\n 2. Load Campaign\n 3. Play Multiplayer Campaign\n 4. Play Multiplayer Deathmatch\n 5. Quit Game\n Selection: ");
    scanf("%c", &choice);
    bool valid_input = false;
    while(true)
    {
        switch (choice)
        {
            case '1':
                New();
                valid_input = true;
                break;
            case '2':
                Load();
                valid_input = true;
                break;
            case '3':
                Coop();
                valid_input = true;
                break;
            case '4':
                Deathmatch();
                valid_input = true;
                break;
            case '5':
                printf("Quitting...");
                valid_input = true;
                break;
            default:
                printf("Choice not valid. Returning to Main Menu...\n--------\n");
                main();
                break;
        }
    }
    getchar();

}

But it's repeating default twice. Why is this?

[swebonny]

[QUOTE=Anonim;33157535]The algorithm performs two sub-passes (the for-loops) over the array for every pass through the while-loop. During the first sub-pass it checks if A[i+1] is greater than A[i] for all i <= n - 2 and swaps if that's the case. During the second sub-pass, it checks if there are any remaining A[i+1] greater than A[i], and if there are, it needs to iterate again.

This will continue until it has been sorted (i.e. no A[i+1] are greater than A[i] for all i <= n - 2).

This algorithm seems to have a complexity of O(2*(n-1)^2) ~ O(n^2). Listen to Obama: Bubble sort is not the way to go![/QUOTE]

You're a fucking king man.

[calzoneman]

[QUOTE=Meatpuppet;33157539]Jookia helped me. Now, it's
-codesnip-
But it's repeating default twice. Why is this?[/QUOTE]
You have
[cpp]
default:
printf("Choice not valid...");
main();
break;
[/cpp]
The extra main() there is calling the main function all over again.
Change to
[cpp]
default:
printf("Choice not valid...");
break;
[/cpp]

Also if you're using while(true) then the valid_input bool is unnecessary.

[Meatpuppet]

[QUOTE=calzoneman;33157719]
Also if you're using while(true) then the valid_input bool is unnecessary.[/QUOTE]What?

Also, taking out the main() makes it go into a n infinite loop.

[calzoneman]

[QUOTE=R1Z3;33155365]

x = 1
y = 0
z = 0
for n in range(1, 9000):
	z = x
	x = x + y
	y = z
	print n, ": ", x
	if len(str(x)) == 1000:
		break

Doing a problem on project Euler. I have to find the first Fibonacci number to have 1000 digits. I came up with the code above but the site says it's wrong. I got 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816.[/QUOTE]
I think the question was asking for the index of the term which has 1000 digits. For example, fib[1] = 1, fib[2] = 1, fib[3] = 2, fib[4] = 3, ..., fib[n] = that huge ass number with 1000 digits, the problem wants you to find n.

[editline]6th November 2011[/editline]

[QUOTE=Meatpuppet;33157738]What?

Also, taking out the main() makes it go into a n infinite loop.[/QUOTE]
The whole point of adding the while loop was to prevent you from calling main() recursively. I get the sense you really don't understand what's going on, I would recommend you read a simpler tutorial to get a feel for how C works.

[Anonim]

[QUOTE=Swebonny;33157567]You're a fucking king man.[/QUOTE]

I also meant A[i] being greater than A[i+1] obviously, not vice versa. Dem typos.

[rzzi]

[QUOTE=calzoneman;33157802]I think the question was asking for the index of the term which has 1000 digits. For example, fib[1] = 1, fib[2] = 1, fib[3] = 2, fib[4] = 3, ..., fib[n] = that huge ass number with 1000 digits, the problem wants you to find n.[/QUOTE]

Ah, okay, got it. Thanks.

[pollyzoid]

[QUOTE=Swebonny;33157567]You're a fucking king man.[/QUOTE]

I'm not sure why that second pass is there, it could be simplified a bit by moving the invalidation to the first pass.

Algorithm bubblesort(A, n):
   Input: An array A storing n integers.
   Output: An array with the same integers in ascending order.
   isReady = false
   while not isReady
      isReady = true
      for i = 0 to n - 2
         if A[i] > A[i+1] then
            swap(A[i], A[i+1])
            isReady = false

[swebonny]

[QUOTE=raBBish;33158047]I'm not sure why that second pass is there, it could be simplified a bit by moving the invalidation to the first pass.

Algorithm bubblesort(A, n):
   Input: An array A storing n integers.
   Output: An array with the same integers in ascending order.
   isReady = false
   while not isReady
      isReady = true
      for i = 0 to n - 2
         if A[i] > A[i+1] then
            swap(A[i], A[i+1])
            isReady = false

[/QUOTE]

Yes that's why I was a bit confused. One of the questions were to determine the optimal performance, which should be O(n). But by adding that second pass it changes, I guess they wanted to make us think a little bit before using google(or FP and catch the people that are writing O(n)).

[mechanarchy]

[QUOTE=Anonim;33149864]I was just looking through the thread and saw this:
And I thought I'd practice my Python lambdas:

>>> from math import log10
>>> f = lambda x: sum([((n==0) and 1) or int(log10(abs(n)))+1 for n in range (1, x+1)])
>>> f(10)
11
>>> f(100)
192
>>> f(10**6)
5888896

Apparently, this logarithmic digit counting is pretty much just as fast as len(str(abs(n))).

>>> f2 = lambda x: sum([len(str(abs(n))) for n in range (1, x+1)])
>>> f(10**6)
5888896
>>> f2(10**6)
5888896
>>> from timeit import timeit
>>> timeit(repr(f(10**6)))
0.008955676209552621
>>> timeit(repr(f2(10**6)))
0.009411776069782718

Any way to make this a little more efficient while keeping it a short, unreadable one-liner?[/QUOTE]

By changing "range" to "xrange" you can usually make loops more efficient when dealing with a large scope. "range" generates all the numbers at the start, so if you're looping between one and one million you'd have one million numbers stored in memory at the very first call. "xrange" uses generator functions to generate the numbers on the fly and hence doesn't waste so much time shoving numbers into memory at the very start.

[Anonim]

[QUOTE=mechanarchy;33158881]By changing "range" to "xrange" you can usually make loops more efficient when dealing with a large scope. "range" generates all the numbers at the start, so if you're looping between one and one million you'd have one million numbers stored in memory at the very first call. "xrange" uses generator functions to generate the numbers on the fly and hence doesn't waste so much time shoving numbers into memory at the very start.[/QUOTE]

Right, I should've known this. My Python is getting rusty.

[backwardspy]

[QUOTE=Anonim;33163815]Right, I should've known this. My Python is getting rusty.[/QUOTE]
As soon as I read that, the image of your pet snake getting rusty popped into my head... 'twas a strange enough image, to say the least.

[Anonim]

[QUOTE=Swebonny;33158611]Yes that's why I was a bit confused. One of the questions were to determine the optimal performance, which should be O(n). But by adding that second pass it changes, I guess they wanted to make us think a little bit before using google(or FP and catch the people that are writing O(n)).[/QUOTE]

If I'm not mistaken, Bubble sort will only ever achieve O(n) (from 1 loop over n-1 comparisons and 0 swaps) in its single best case: When the array is already sorted. It'll just traverse the array, not swap anything and leave the "isReady" flag on.

But it can only approach O(n) in the best case. In general, it's going to average a horrid O(n^2). The math for this is tricky, but if we assume a constant n-1 passes and let the number of comparisons and swaps per pass vary, we get an average n/2 comparisons and n/4 swaps per pass, giving an average time of [img]http://latex.codecogs.com/gif.download?%5Cfrac{n^2}{2}-%5Cfrac{n}{2}+%5Cfrac{n^2}{4}-%5Cfrac{n}{4}&space;=&space;%5Cfrac{3}{4}n^2-%5Cfrac{3}{4}n[/img] = O(n^2).
Not only is it O(n^2), but its less efficient than most other O(n^2) sorting algorithms.

You could actually optimise it a bit (just for the effort) by keeping track of the largest index from which point the remaining subarray is already sorted, and then only iterating up to that point on each successive loop. It's still going to be O(n^2) though, but with better efficiency.

[editline]7th November 2011[/editline]

[QUOTE=Chris220;33163942]As soon as I read that, the image of your pet snake getting rusty popped into my head... 'twas a strange enough image, to say the least.[/QUOTE]

:ohdear:

[editline]7th November 2011[/editline]

Oh, you meant pet snake, not "pet snake". Never mind the ":ohdear:" then.

[mechanarchy]

[QUOTE=Anonim;33163815]Right, I should've known this. My Python is getting rusty.[/QUOTE]

I thought I'd give it a run myself with the xrange change and time it. "f" is your f, "f2" is your f2, "f3" is your f2 with xrange instead of range.

f(10**6)  = 0.012033939361572266
f(10**6)  = 0.011991024017333984
f2(10**6) = 0.011934995651245117
f2(10**6) = 0.012253999710083008
f3(10**6) = 0.011886119842529297
f3(10**6) = 0.012001991271972656

[editline]7th November 2011[/editline]

It doesn't end up making that much of a change, really. Though neither did f2 compared to f.

[Anonim]

[QUOTE=mechanarchy;33164386]I thought I'd give it a run myself with the xrange change and time it. "f" is your f, "f2" is your f2, "f3" is your f2 with xrange instead of range.

f(10**6)  = 0.012033939361572266
f(10**6)  = 0.011991024017333984
f2(10**6) = 0.011934995651245117
f2(10**6) = 0.012253999710083008
f3(10**6) = 0.011886119842529297
f3(10**6) = 0.012001991271972656

[editline]7th November 2011[/editline]

It doesn't end up making that much of a change, really. Though neither did f2 compared to f.[/QUOTE]

xrange generally doesn't help much with speed as far as I know. But I'd assume memory usage went down quite a bit.

[editline]7th November 2011[/editline]

And I'd assume xrange() would be faster than range() for extremely large values. While range() creates a list of all the desired elements, xrange() returns one yielded object at a time and stores practically nothing else. If you try this with sys.maxint iterations (assuming Python wouldn't run out of memory at this point with range(), which it probably would), I'd think that xrange() would be noticeably faster.

[mechanarchy]

[QUOTE=Anonim;33164610]xrange generally doesn't help much with speed as far as I know. But I'd assume memory usage went down quite a bit.

[editline]7th November 2011[/editline]

And I'd assume xrange() would be faster than range() for extremely large values. While range() creates a list of all the desired elements, xrange() returns one yielded object at a time and stores practically nothing else. If you try this with sys.maxint iterations (assuming Python wouldn't run out of memory at this point with range(), which it probably would), I'd think that xrange() would be noticeably faster.[/QUOTE]

I knew it would be more efficient in terms of reduced memory usage but I wasn't sure if it'd be any faster, so I thought I'd test it out. But as you can see, the results really aren't conclusive for a number on that scale.

[長門有希]

So I'm wondering about something:
Let's say I want to make something like a simple game where you're a some symbol in a maze:

$ - the player

##############
#  #   #   #
#    # # # # #
# # ## # # # #
# #  #   #   #
#$############

Now, I can figure out how to capture moves the player does, but I have no idea how to draw and update the maze. Just redraw it line by line each time there's a move?

[Catdaemon]

[QUOTE=Ezhik;33166532]So I'm wondering about something:
Let's say I want to make something like a simple game where you're a some symbol in a maze:

$ - the player

##############
#  #   #   #
#    # # # # #
# # ## # # # #
# #  #   #   #
#$############

Now, I can figure out how to capture moves the player does, but I have no idea how to draw and update the maze. Just redraw it line by line each time there's a move?[/QUOTE]

There are two options. Either you only draw the changed portions of the screen manually, or draw the whole lot again. Latter generally makes more sense, especially if the scene moves around.

[長門有希]

Hmm, how would I re-draw changed parts of the screen?

[Arfbarf]

I just started Visual Basic 2010 not too long ago for school.
I'm supposed to create an application that cycles through three background form colors that change every 2 seconds.
Do I have to create 3 different timers? Is it possible to reuse the same timer for each color?

I've tried using the three timers, but the background colors for the last two are only visible for a tiny fraction of a second before being overridden by the first color.
Any help?

[NovembrDobby]

[QUOTE=arfbarf;33167119]I just started Visual Basic 2010 not too long ago for school.
I'm supposed to create an application that cycles through three background form colors that change every 2 seconds.
Do I have to create 3 different timers? Is it possible to reuse the same timer for each color?

I've tried using the three timers, but the background colors for the last two are only visible for a tiny fraction of a second before being overridden by the first color.
Any help?[/QUOTE]

You could use one timer, and on every tick (2 seconds) check the colour of the form:

(pseudocode)

if(Form.BackColor == Green)
   Form.BackColor = Blue;
else if(Form.BackColor == Blue)
   Form.BackColor = Red;
else if(Form.BackColor == Red)
   Form.BackColo = Green;

[長門有希]

How do I clear the screen, change the cursor position and use colors in console programs in C++.
Windows has shit like "SetConsoleCursorPosition()", but I'm using Mac OS...

[BlkDucky]

[QUOTE=Ezhik;33168503]How do I clear the screen, change the cursor position and use colors in console programs in C++.
Windows has shit like "SetConsoleCursorPosition()", but I'm using Mac OS...[/QUOTE]

ncurses should work on Mac OS, I think.

It's a very nice library for doing this stuff.

[長門有希]

Alright, I'll try it.

[Philly c]

Does anybody know how to bounce 2 moving balls correctly? When I say correctly i'm not really looking for a proper physics simulation but just get the direction correct. I'm following this tutorial [URL]http://www.tonypa.pri.ee/vectors/tut11.html[/URL] (the section at the bottom of the page), but it just doesn't work properly. At first it seems to work but at an extreme angle it breaks down, for example:

[IMG]http://i.imgur.com/E9ejx.png[/IMG]
The green lines are directions, and the pink lines are bounces.

[Armandur]

I'm installing boost using an installer from boostpro. I got to the page where I should choose the default variants.
Which one/s should I choose? I'm running VS2010 on Win7.

[ROBO_DONUT]

[QUOTE=Philly c;33169186]Does anybody know how to bounce 2 moving balls correctly? When I say correctly i'm not really looking for a proper physics simulation but just get the direction correct. I'm following this tutorial [URL]http://www.tonypa.pri.ee/vectors/tut11.html[/URL] (the section at the bottom of the page), but it just doesn't work properly. At first it seems to work but at an extreme angle it breaks down, for example:

[IMG]http://i.imgur.com/E9ejx.png[/IMG]
The green lines are directions, and the pink lines are bounces.[/QUOTE]
Direction of impulse on p2:
d1 = norm(p2 - p1)
Direction of impulse on p1:
d2 = norm(p1 - p2) = -d1
The delta-v of each is going to be equal to the magnitude of their relative velocity
deltav = magnitude(v2 - v1)
So:
v1 = v1 + d1 * deltav = norm(p2 - p1) * magnitude(v2 - v1)
v2 = v2 + d2 * deltav = norm(p1 - p2) * magnitude(v2 - v1)

This will be unstable if the two spheres are moving apart but still colliding (which may or may not occur depending on how you handle collisions).

[Meatpuppet]

[QUOTE=calzoneman;33157802]

[editline]6th November 2011[/editline]

The whole point of adding the while loop was to prevent you from calling main() recursively. I get the sense you really don't understand what's going on, I would recommend you read a simpler tutorial to get a feel for how C works.[/QUOTE]I'm using http:\\[url]www.cprogramming.com[/url] right now; I'm having trouble understanding [url]http://www.cprogramming.com/tutorial/c/lesson6.html[/url], starting at "The function malloc" down, but other than that I think I understand it. If I could get a better tutorial that would be awesome.

[editline]7th November 2011[/editline]

Fuck. Everyone in this damn thread makes me feel like I'm an idiot. I see people learning this when they were 12, and they got it, and moved on to other languages. I can't even fucking learn C, and it's been about a month.

[swebonny]

[QUOTE=Meatpuppet;33172192]I'm using http:\\[url]www.cprogramming.com[/url] right now; I'm having trouble understanding [url]http://www.cprogramming.com/tutorial/c/lesson6.html[/url], starting at "The function malloc" down, but other than that I think I understand it. If I could get a better tutorial that would be awesome.

[editline]7th November 2011[/editline]

Fuck. Everyone in this damn thread makes me feel like I'm an idiot. I see people learning this when they were 12, and they got it, and moved on to other languages. I can't even fucking learn C, and it's been about a month.[/QUOTE]

Why are you learning C?

And you're not alone :v: