Well a friend of mine found a new game, and, cheap ass that he is its a freebie.
Actually turns out its a pretty fun. Like, mindless Counter-strike fun, only more mindless. And less polished.
The game is called Combat Arms by Nexon. It's a free-to-play fps with a level system that unlocks new toys and an in-game currency that you use to rent items for a time to play with. Overall I'm having a lot of fun with the game. Started an 8v8 with my friend on Cold Seed and it was 1v1 for awhile. And then someone joined, so it was 1v2. Me, a sniper, against two with assault rifles. And I was kicking ass (considering the sniper is one-shot, one-kill). And then another joined, and it was 2v2.
Overall I'm enjoying myself.
If you're interested... www.nexon.net
Saturday, August 2, 2008
Saturday, June 21, 2008
Recursion continued
A friend of mine likes Palindromes, and was trying to figure out a way of seeing which sentences are Palindromes from a list of combinations of words. I don't exactly know how the combination maker works, but that part is recursive.
The part of his code that checks for a Palindrome is iterative, however. It checks the String from its beginning and its end, and makes comparisons based on those. If a letter pair doesn't match, it terminates. Otherwise it returns true.
It's pretty fast.
My recursive method, on the other hand, takes a String and splits it into two halves, and reverses the second half (so that ecar = race), and then does comparisons based on that.
It's pretty slow. But its also turning up an extra Palindrome or two every now and then. Which I think has to do with how its doing its calculations.
If I could somehow optimize my recursion to break if it knows its false i could probably speed it up greatly.
Which one's better? I don't know.
Also, for if tests, especially when calling a method in a return line, I think I found a pretty nifty way of indenting my code.
take
i think this is a lot better than
With the former, you can easily tell that it's returning a number and then calling itself. With the latter, you have to take in both as one step. This isn't so bad at first, but when you have something like
Where the return statements get a little long winded, it can be quite nice to break them up into smaller pieces. Of course, all the indention can get a little long winded, but, indenting has always been a sign that you're going a little bit deeper into the logic of an operation (nested if tests, nested loops, etc)
Since recursion breaks down a problem into its subproblems, and then returns a combined result, I believe this way makes sense, too. When you break a problem into a smaller part, you're going further into the logic... When you're done, you're coming out.
The part of his code that checks for a Palindrome is iterative, however. It checks the String from its beginning and its end, and makes comparisons based on those. If a letter pair doesn't match, it terminates. Otherwise it returns true.
It's pretty fast.
My recursive method, on the other hand, takes a String and splits it into two halves, and reverses the second half (so that ecar = race), and then does comparisons based on that.
It's pretty slow. But its also turning up an extra Palindrome or two every now and then. Which I think has to do with how its doing its calculations.
If I could somehow optimize my recursion to break if it knows its false i could probably speed it up greatly.
Which one's better? I don't know.
Also, for if tests, especially when calling a method in a return line, I think I found a pretty nifty way of indenting my code.
take
function foo (int num) {
if (num == 0) {
return 1;
}
else {
return
1
+ foo(num--);
}
}
i think this is a lot better than
function bar(int num) {
if (num == 0)
return 1;
else return 1 + bar(num--);
}
With the former, you can easily tell that it's returning a number and then calling itself. With the latter, you have to take in both as one step. This isn't so bad at first, but when you have something like
public String flip(String word) {
if (word.length() ==1) {
return
word.substring(word.length() - 1, word.length());
}
else {
return
word.substring(word.length() - 1, word.length())
+ flip(word.substring(0, word.length() - 1));
}
}
Where the return statements get a little long winded, it can be quite nice to break them up into smaller pieces. Of course, all the indention can get a little long winded, but, indenting has always been a sign that you're going a little bit deeper into the logic of an operation (nested if tests, nested loops, etc)
Since recursion breaks down a problem into its subproblems, and then returns a combined result, I believe this way makes sense, too. When you break a problem into a smaller part, you're going further into the logic... When you're done, you're coming out.
Thursday, June 19, 2008
Recursion is recursion is recursion is recursion is recursion . . .
So, bought a book the other day, called "Introduction to Algorithms", which is a heavy, thick book that covers well, algorithms in computing, makes a case for them as a technology (it is not enough to have fast hardware, the instruction set must be efficient, as well), and goes on and on with tons of heavy calculus that I don't well, understand all that well. So far I've read up on insertion sort and merge sort, and, while I actually did make (read: copy) an insertion sort algorithm and make it work (correctly), I never did a merge sort.
See, the problem with recursion is that, its not very easy to see where its going. Yet, for some problems, recursion is the way to go. Take the game Portal and its view of looking through portals like in a mirror (It's really something better shown than explained... but the next time you see two mirrors directly opposite each other, its like that). They explain in the commentary that this is done recursively. And it makes sense. I couldn't see how it'd be doing using iterations.
Except... recursion is a type of loop. But a special type of loop. One that is actually very elegant and beautiful. It is also not all that verbose, compared to that of say a for loop or while loop.
// sorry about the lack of indents. Blogger doesn't like lots of spaces for some reason
Consider . . . (in Java syntax, at least. Well, I think this is correct. Merge sort isn't working but this is from the book)
where the method merge (A, p, r) calls itself several times, breaks its problem down through both halves of the array and then reassembles the list in sorted order, which is what the last method does. At least, this is how I understand it.
Merge sort I do not actually have working. I have something, and by something I mean it sort of sorts an array and loses a huge chunk of data by the time its done. And why I don't know.
This is a lot more elegant than, say, the insertion sort with its for loop and while loop, although a bit harder to grasp. Merge sort, however, is quite efficient for large arrays.
Where was I going with this? Well, I just built a word-counter program that solves counting words line by line recursively. It reads in a line, takes out the first word, and calls itself with the new sentence. It's exit condition is satisfied when the line it is working with no longer contains a space.
It isn't perfect by any means. A long trail of spaces, or, say, a blank line will up the word count per space or per line. Putting in the wrong file name will terminate the program without any explanation as to why. That I need to fix. Maybe I could throw some other checks in there to make sure that the line doesn't contain nothing or doesn't count extra spaces. I mean, maybe that would be easy. But it means more steps, too.
But then computers are fast, anyway. No, I mean, seriously fast.
See, the problem with recursion is that, its not very easy to see where its going. Yet, for some problems, recursion is the way to go. Take the game Portal and its view of looking through portals like in a mirror (It's really something better shown than explained... but the next time you see two mirrors directly opposite each other, its like that). They explain in the commentary that this is done recursively. And it makes sense. I couldn't see how it'd be doing using iterations.
Except... recursion is a type of loop. But a special type of loop. One that is actually very elegant and beautiful. It is also not all that verbose, compared to that of say a for loop or while loop.
// sorry about the lack of indents. Blogger doesn't like lots of spaces for some reason
Consider . . . (in Java syntax, at least. Well, I think this is correct. Merge sort isn't working but this is from the book)
merge (A, p, r) {
if p < r) {
q = (p + r) / 2;
merge (A, p, q);
merge (A, q + 1, r);
merge (A, p, q, r);
}
}
where the method merge (A, p, r) calls itself several times, breaks its problem down through both halves of the array and then reassembles the list in sorted order, which is what the last method does. At least, this is how I understand it.
Merge sort I do not actually have working. I have something, and by something I mean it sort of sorts an array and loses a huge chunk of data by the time its done. And why I don't know.
This is a lot more elegant than, say, the insertion sort with its for loop and while loop, although a bit harder to grasp. Merge sort, however, is quite efficient for large arrays.
Where was I going with this? Well, I just built a word-counter program that solves counting words line by line recursively. It reads in a line, takes out the first word, and calls itself with the new sentence. It's exit condition is satisfied when the line it is working with no longer contains a space.
It isn't perfect by any means. A long trail of spaces, or, say, a blank line will up the word count per space or per line. Putting in the wrong file name will terminate the program without any explanation as to why. That I need to fix. Maybe I could throw some other checks in there to make sure that the line doesn't contain nothing or doesn't count extra spaces. I mean, maybe that would be easy. But it means more steps, too.
But then computers are fast, anyway. No, I mean, seriously fast.
Friday, May 30, 2008
Top coder competition
www.topcoder.com
Basically an outsourcing site where you can (supposedly) win money by competing to build software components on demand, or do algorithm contests for fun and some money.
I did a competition the other day, even though I knew they'd be hard. I mean, you know, worst case scenario is I had no idea how to solve it and I just go and move on to something else. But it turns out the problem wasn't all that hard (except for the third one), and they were all related to eachother.
So once I figure out problem 1 I just copy some code over for problem 2, make some changes, get in the top 7 after the coding phase is done and am feeling pretty good about myself. Well, the challenge phase comes along and my second program fails.
The reason? Time. TopCoder wants their programs to run, but run fast. Any algorithm that will take longer than 2 seconds will fail. I think the weakness here, for me at least, is my lack of math skill. I looked at source of some of the competitors and it seemed that the ones that did well were based in math.
Oh well. Lesson learned, plus, it was fun.
Basically an outsourcing site where you can (supposedly) win money by competing to build software components on demand, or do algorithm contests for fun and some money.
I did a competition the other day, even though I knew they'd be hard. I mean, you know, worst case scenario is I had no idea how to solve it and I just go and move on to something else. But it turns out the problem wasn't all that hard (except for the third one), and they were all related to eachother.
So once I figure out problem 1 I just copy some code over for problem 2, make some changes, get in the top 7 after the coding phase is done and am feeling pretty good about myself. Well, the challenge phase comes along and my second program fails.
The reason? Time. TopCoder wants their programs to run, but run fast. Any algorithm that will take longer than 2 seconds will fail. I think the weakness here, for me at least, is my lack of math skill. I looked at source of some of the competitors and it seemed that the ones that did well were based in math.
Oh well. Lesson learned, plus, it was fun.
Tuesday, April 29, 2008
Words cannot describe the atrocites I've committed
So, I'm working on making Mastermind as a way to learn more about programming with graphical user interfaces in mind. The core logic for checking this and that took maybe 2-3 hours of programming, tops, to build. Plus a day or two to think of how to solve a really tough part (Which, to my knowledge, works correctly now, but I suck at Mastermind so I can't tell 100%. but it seems to be correct).
While I developed the game from the console first with the concept of switching over to a graphical user interface later, I quickly found that I didn't structure my code well enough for the changeover and, well, what started as a project that should take a few days and be somewhat elegant (as I try to be... well, elegant isn't the right word... I just mean like... not using more lines than needed) into something that's bogged me down and forced me to give up a feature I had planned (Just as well... I can't manipulate AutoCad like I used to anyway).
Once frustration set in I stopped caring about code elegance and just started bulldozing whatever wasn't finished (It's a decision based on time spent on coming up with a good solution vs. time spent forcing the solution into place which a computer can still solve pretty fast... whichever saves me more time I pick) because I'm just getting frustrated with it all.
Oh, don't get me wrong. It's almost finished (I just need to refactor a few things). Well, single player anyway.
Then comes two-player support and computer play. Yeah, making an AI will be real fun.
I think after this I'll go make Battleship.
While I developed the game from the console first with the concept of switching over to a graphical user interface later, I quickly found that I didn't structure my code well enough for the changeover and, well, what started as a project that should take a few days and be somewhat elegant (as I try to be... well, elegant isn't the right word... I just mean like... not using more lines than needed) into something that's bogged me down and forced me to give up a feature I had planned (Just as well... I can't manipulate AutoCad like I used to anyway).
Once frustration set in I stopped caring about code elegance and just started bulldozing whatever wasn't finished (It's a decision based on time spent on coming up with a good solution vs. time spent forcing the solution into place which a computer can still solve pretty fast... whichever saves me more time I pick) because I'm just getting frustrated with it all.
Oh, don't get me wrong. It's almost finished (I just need to refactor a few things). Well, single player anyway.
Then comes two-player support and computer play. Yeah, making an AI will be real fun.
I think after this I'll go make Battleship.
Sunday, January 20, 2008
Opening really large text files
So I have this problem. I have a 500MB text file filled with prime numbers.
I'm not entirely sure how it got to be so big or how it was even made without the JVM crashing in protest (I guess file access for programs other than the end-user don't use RAM) like it did when I tried holding stuff in arrays, bt suffice it to say I'm not going to be able to open this file with any basic program (I know because opening a 4MB program in notepad takes about 1-2 hrs). Yet my programming teacher keeps talking about how stuff like this is always handled as a string (Primitive data types are so limited in that they can go up to 64 bit at most), so I got to thinking and googled "opening really large text files", thinking that there was probably some top-secret technology that only the super computer gurus had.
Turns out that I'm not the only one with this problem, and the solution seems to be a little program called TextPad (www.textpad.com). Even the evaluation copy is powerful enough to open files larger than 500MB in a little over ten seconds. OpenOffice exited after it tried, and wordpad struggled (it opened part of it then froze... well not froze, it was still working but was unresponsive).
I'm not sure why it works so fast while others struggle or even just crash outright. I wish I knew, because I think it'd be nice to write a text editor one day (among a whole slew of other things, of course), and knowing that this is a problem that can crop up from time to time (usually when trying to read files from mySQL servers, apparently)
I'm not entirely sure how it got to be so big or how it was even made without the JVM crashing in protest (I guess file access for programs other than the end-user don't use RAM) like it did when I tried holding stuff in arrays, bt suffice it to say I'm not going to be able to open this file with any basic program (I know because opening a 4MB program in notepad takes about 1-2 hrs). Yet my programming teacher keeps talking about how stuff like this is always handled as a string (Primitive data types are so limited in that they can go up to 64 bit at most), so I got to thinking and googled "opening really large text files", thinking that there was probably some top-secret technology that only the super computer gurus had.
Turns out that I'm not the only one with this problem, and the solution seems to be a little program called TextPad (www.textpad.com). Even the evaluation copy is powerful enough to open files larger than 500MB in a little over ten seconds. OpenOffice exited after it tried, and wordpad struggled (it opened part of it then froze... well not froze, it was still working but was unresponsive).
I'm not sure why it works so fast while others struggle or even just crash outright. I wish I knew, because I think it'd be nice to write a text editor one day (among a whole slew of other things, of course), and knowing that this is a problem that can crop up from time to time (usually when trying to read files from mySQL servers, apparently)
Wednesday, December 26, 2007
Calculating Big (really really really really really MONSTEROUSLY BIG) numbers
The curious thing about programming and mathematics is that I'm not at all a good mathematician (C in Algebra 1, B in Geometry, D in Algebra 2), except when it comes to the computer, and the thing that has intrigued me most so far is the concept of computers being able to calculate extremely large numbers. Pi has been found to some odd billion digits, prime numbers (as far as we know) have been found using computers up to and beyond the 10 millionth digit (www.mersenne.org), and computers are used for other mathematical purposes as well (Seti, folding@Home, protein formations, etc).
The list is quite endless, I'm sure.
So as a novice programmer I also wanted to do something with higher math. Simply squaring numbers and all that is a little boring, yet the fibonacci sequence fascinated me, so I wrote a program to calculate that.
But it died after runs through the sequence. The 64 bits of data become clogged after about 19 digits, and fibonacci has been calculated to 10 million with some god-awful C++ code that was several lines long. So I asked the gods at www.javaranch.com, and they helped. The program no longer died after 91 runs through.
But then I realized that with an output to screen I couldn't retrieve the information, at all (what's the use of calculating a really really really big number if you can't get to it), which meant I had to solve another problem.
So I went searching, went on a journey, tried a bunch of things, looked at the hard-to-decipher-if-you-try-to-read-deep-in java docs, and then realized that the solution was right under my nose. The BigInteger class used to represent numbers larger than 64 bit (that is, 19 digits long or so) is an object. Every object has a toString method (returns it as a series of text). Text is savable to a file. My teacher went on about how these really big ass numbers are just strings of text..............
CLICK!
The only problem now is processing. The only solution for that is time.
Guess I'll be leaving something on overnight. Hey, fibonacci is already to the 100,000th digit :)
The list is quite endless, I'm sure.
So as a novice programmer I also wanted to do something with higher math. Simply squaring numbers and all that is a little boring, yet the fibonacci sequence fascinated me, so I wrote a program to calculate that.
But it died after runs through the sequence. The 64 bits of data become clogged after about 19 digits, and fibonacci has been calculated to 10 million with some god-awful C++ code that was several lines long. So I asked the gods at www.javaranch.com, and they helped. The program no longer died after 91 runs through.
But then I realized that with an output to screen I couldn't retrieve the information, at all (what's the use of calculating a really really really big number if you can't get to it), which meant I had to solve another problem.
So I went searching, went on a journey, tried a bunch of things, looked at the hard-to-decipher-if-you-try-to-read-deep-in java docs, and then realized that the solution was right under my nose. The BigInteger class used to represent numbers larger than 64 bit (that is, 19 digits long or so) is an object. Every object has a toString method (returns it as a series of text). Text is savable to a file. My teacher went on about how these really big ass numbers are just strings of text..............
CLICK!
The only problem now is processing. The only solution for that is time.
Guess I'll be leaving something on overnight. Hey, fibonacci is already to the 100,000th digit :)
Subscribe to:
Posts (Atom)