Showing posts with label C. Show all posts
Showing posts with label C. Show all posts
Thursday, March 22, 2012
Wednesday, March 14, 2012
A reminder about character array sizes
char *charpointer = "iameight\0";
char array[9] = "iameight\0";
The strlen size of charpointer is: 8
The strlen size of array is: 8
The sizeof size of charpointer is: 4
The sizeof size of array is: 9
The above is the result of a small "sanity check" program I keep around. It's super helpful.
char array[9] = "iameight\0";
The strlen size of charpointer is: 8
The strlen size of array is: 8
The sizeof size of charpointer is: 4
The sizeof size of array is: 9
The above is the result of a small "sanity check" program I keep around. It's super helpful.
Sunday, March 4, 2012
Project Euler progress on GitHub
I'm unifying my Project Euler progress, and I'm going to use this opportunity to learn more about Git and GitHub.
I thought a good deal on where to do the actual work (Windows, OS X, Linux) and settled on Linux since Windows has a bizarre Git implementation, and OS X would let me cheat by using a front end for Git and keep me away from the command line (which I need to be stronger at).
Git is sort of easy to learn. I feel like I'm doing things the hard way sometimes. I had assumed it would just "know" when I add a new file to the project, for example, but it didn't. I have to really be mindful of what I'm doing (in hindsight an obvious sentiment).
https://github.com/cheydrick/Project-Euler
The first go at it is just the foundation. I'll make functional the ability to choose which project to run at the command line next, and then continue adding the projects I have already finished. I'm looking forward to this, and I hope I'll have the chance to learn more about Git and proper source control practices. Maybe I can get someone to fork my repository and make a change so that I can learn how to merge changes into the master branch (or is it clone and pull... woof with the terminology).
I thought a good deal on where to do the actual work (Windows, OS X, Linux) and settled on Linux since Windows has a bizarre Git implementation, and OS X would let me cheat by using a front end for Git and keep me away from the command line (which I need to be stronger at).
Git is sort of easy to learn. I feel like I'm doing things the hard way sometimes. I had assumed it would just "know" when I add a new file to the project, for example, but it didn't. I have to really be mindful of what I'm doing (in hindsight an obvious sentiment).
https://github.com/cheydrick/Project-Euler
The first go at it is just the foundation. I'll make functional the ability to choose which project to run at the command line next, and then continue adding the projects I have already finished. I'm looking forward to this, and I hope I'll have the chance to learn more about Git and proper source control practices. Maybe I can get someone to fork my repository and make a change so that I can learn how to merge changes into the master branch (or is it clone and pull... woof with the terminology).
Saturday, January 21, 2012
Monday, January 2, 2012
Linked List
I have been trying to stick to this rule where I'll never use a pre-made implementation of an advanced programming concept without first creating my own version of it. The Objective-C stuff I've been working on has me frequently using the Foundation version of a linked list (NSArray and NSMutableArray). I've never created my own linked list implementation so this morning I sat down and hashed out the creation, adding of things, and deletion of a doubly linked list of character pointers. To make it complete I'll have to include insertion and deletion of nodes at any arbitrary point, but that shouldn't be too hard.
Here is what I came up with. My notes of what went right and wrong and some questions to address later are below.
DLinkedList.h
DLinkedList.c
main.c
What went right is that it seems to work. I'd like to add a list traversal function that prints out all the data in the node (node address, head pointer, tail pointer, and data) so that I can verify it's doing exactly what I think it's doing.
What went wrong is that I'm not sure if my AddWord() function is following the best practice for shuffling around variables. I'm always worried that I will treat pointers as special and not do the same thing I'd do if it was an integer. A new node being created in that function is always addressed "through" the node that preceded it. I should have created a temporary node pointer to hold the address of the newly created node and then assign the next/previous/data from that. The weirdness came from literally translating my hand-written notes to code.
What's left is to do the verification, stress test it, and add in some safety checks for all the malloc() calls. Then I can move on to adding in the insert and delete node functions and think of something clever to do with all of it.
I made the nodes rather specifically hold pointers to strings in memory. The next iteration of this needs to make it hold anything. I think I can do this by (in the event of strings) allocating the space, doing strcpy(), and then casting the pointer to void to store in the node. Getting the data back out means needing to re-cast, probably. I messed around with going to and from void a while back and I don't recall having any difficulty.
The list struct which holds the head and tail of the list is so that it's quick to find the last node. Otherwise I would have had to always have the last node's "next" pointer be NULL.
Right, so I think I can give this little side-project another run through in a few days and then I'll feel good about using fancier canned library versions of it!
Here is what I came up with. My notes of what went right and wrong and some questions to address later are below.
DLinkedList.h
DLinkedList.c
main.c
What went right is that it seems to work. I'd like to add a list traversal function that prints out all the data in the node (node address, head pointer, tail pointer, and data) so that I can verify it's doing exactly what I think it's doing.
What went wrong is that I'm not sure if my AddWord() function is following the best practice for shuffling around variables. I'm always worried that I will treat pointers as special and not do the same thing I'd do if it was an integer. A new node being created in that function is always addressed "through" the node that preceded it. I should have created a temporary node pointer to hold the address of the newly created node and then assign the next/previous/data from that. The weirdness came from literally translating my hand-written notes to code.
What's left is to do the verification, stress test it, and add in some safety checks for all the malloc() calls. Then I can move on to adding in the insert and delete node functions and think of something clever to do with all of it.
I made the nodes rather specifically hold pointers to strings in memory. The next iteration of this needs to make it hold anything. I think I can do this by (in the event of strings) allocating the space, doing strcpy(), and then casting the pointer to void to store in the node. Getting the data back out means needing to re-cast, probably. I messed around with going to and from void a while back and I don't recall having any difficulty.
The list struct which holds the head and tail of the list is so that it's quick to find the last node. Otherwise I would have had to always have the last node's "next" pointer be NULL.
Right, so I think I can give this little side-project another run through in a few days and then I'll feel good about using fancier canned library versions of it!
Wednesday, December 7, 2011
Don't work harder, work smarter
10 minutes of code saved me an hour of copying and pasting repetitive lines in a script.
EDIT: Oof, bad newbie - no treat. Forgot to close the file. Leaving it up as a shameful reminder.
EDIT: Oof, bad newbie - no treat. Forgot to close the file. Leaving it up as a shameful reminder.
Tuesday, November 29, 2011
Project Euler 12 Solution
Some quick lunchtime coding:
http://projecteuler.net/problem=12
It took about 18 minutes to run. The biggest speed fix I could make is to change the divisor counter to only check up to the square root of the number entered. Another one is to not start from scratch every time I want to make a new triangle number. I should store the last result and then add the next number.
I read somewhere to optimize only after things are working since optimizing on the fly can be tricky. Also, I didn't want to spend too long on this since I had a sandwich to focus on, too.
http://projecteuler.net/problem=12
It took about 18 minutes to run. The biggest speed fix I could make is to change the divisor counter to only check up to the square root of the number entered. Another one is to not start from scratch every time I want to make a new triangle number. I should store the last result and then add the next number.
I read somewhere to optimize only after things are working since optimizing on the fly can be tricky. Also, I didn't want to spend too long on this since I had a sandwich to focus on, too.
Sunday, November 27, 2011
A pointer blunder I made today
Every time I think I'm getting half-decent at recreational-level C programming I do something dumb that knocks me down a few pegs. In my last post I mentioned using malloc() and free() to run some very simple tests. The tests turned out fine but I ran into an error that took me a few minutes to resolve.
This illustrates what I tried to do, and what I actually meant to do:
Basically I tried to alter where ptr was pointing, instead of filling in the reserved space ptr pointed to. The error happened when I tried to free the location of x instead of my malloc() allocated location.
I consider myself pointer-competent but I still make really dumb errors. The difference between now and a year ago is that I'd have had to write a post about how I was stuck on an error I couldn't figure out!
This illustrates what I tried to do, and what I actually meant to do:
Basically I tried to alter where ptr was pointing, instead of filling in the reserved space ptr pointed to. The error happened when I tried to free the location of x instead of my malloc() allocated location.
I consider myself pointer-competent but I still make really dumb errors. The difference between now and a year ago is that I'd have had to write a post about how I was stuck on an error I couldn't figure out!
The trouble for newbs with Objective-C, Cocoa, and XCode
I've been working much more with Objective-C: The Big Nerd Ranch Guide than I have been with Programming in Objective-C (3rd edition) lately. I decided to pop back over to the PiO-C book to see how much the other book had already covered (and see if it didn't cover anything since PiO-C is supposed to be the more in-depth book) and I discovered something I should have noticed before.
At some point XCode started using either a different compiler (Clang/LLVM instead of GCC) or a different way of handling memory allocation called Automatic Reference Counting (ARC). A pretty big change happened in the default way new projects are created that really makes it tough to learn from older books (if August 2011 is considered old!).
What it comes down to for the newbie is basically this:
Old way new projects were generated:
New way new projects are generated:
This wouldn't be a super big deal except that the old way where you explicitly handle the NSAutoreleasePool isn't legit in newly generated projects. Going back and forth requires really mucking with the project settings to get it to not use ARC. If I was brand new at learning programming and decided to use Objective-C with XCode as a first language/environment it wouldn't take long to get exasperated. I'm already pretty irked that a new book I bought is obsolete!
I need to track down a step-by-step guide to editing the project settings to go back and forth from the old way and the new way in case I want to use any examples in the old book to learn something. If there was a way to tell it which to use at the start of the new project then that would be great.
I understand the benefit of the new way on a superficial level (just as superficial as I understood what the old way was doing). Coming from C I'm not afraid of doing my own memory management, but I get that it's something you don't want to mess with once you start working on larger frameworks. Even GDK/GTK did a lot of stuff for you (similar to "new" in C++).
For kicks I threw in a few malloc() and free() assignments inside and outside the @autoreleasepool block and I didn't get any complaints. That's a relief - I take very seriously the claim that you can always revert back to straight C and Obj-C is just a strict superset of features that doesn't change any of the known rules.
I just found a placeholder for the 4th edition (releases in a month or so) of PiO-C on Amazon that specifically mentions in the description coverage of XCode 4.2, ARC, and iOS 5. If TBNRG doesn't cover everything then I'll have to drop $30 on the latest edition of a book I already own. Well... that's the game isn't it?
Maybe in a few weeks I'll follow up this post with instructions on reverting to pre-ARC compiler options, but for now I'll stick with TBNRG.
One big disappointment is that although TBNRG or PiO-C goes into some depth about what NSAutoreleasePool or @autoreleasepool{} are really doing, I don't think it discusses much of when to use it. I've seen snippets of code that have multiple groups of @autoreleasepool{} blocks (and in the older book multiple NSAutoreleasePool allocations) but it's not super obvious when to use them. In comparison malloc() and free() look downright friendly.
It's horribly ironic. I started this journey as an almost spiteful motion to clear up my ignorance of pointers and memory. I got to a certain competence in C and now I'm hitting a roadblock with an entirely new flavor of memory management.
Maybe I should ditch XCode and do some AVR/PIC stuff.
At some point XCode started using either a different compiler (Clang/LLVM instead of GCC) or a different way of handling memory allocation called Automatic Reference Counting (ARC). A pretty big change happened in the default way new projects are created that really makes it tough to learn from older books (if August 2011 is considered old!).
What it comes down to for the newbie is basically this:
Old way new projects were generated:
New way new projects are generated:
This wouldn't be a super big deal except that the old way where you explicitly handle the NSAutoreleasePool isn't legit in newly generated projects. Going back and forth requires really mucking with the project settings to get it to not use ARC. If I was brand new at learning programming and decided to use Objective-C with XCode as a first language/environment it wouldn't take long to get exasperated. I'm already pretty irked that a new book I bought is obsolete!
I need to track down a step-by-step guide to editing the project settings to go back and forth from the old way and the new way in case I want to use any examples in the old book to learn something. If there was a way to tell it which to use at the start of the new project then that would be great.
I understand the benefit of the new way on a superficial level (just as superficial as I understood what the old way was doing). Coming from C I'm not afraid of doing my own memory management, but I get that it's something you don't want to mess with once you start working on larger frameworks. Even GDK/GTK did a lot of stuff for you (similar to "new" in C++).
For kicks I threw in a few malloc() and free() assignments inside and outside the @autoreleasepool block and I didn't get any complaints. That's a relief - I take very seriously the claim that you can always revert back to straight C and Obj-C is just a strict superset of features that doesn't change any of the known rules.
I just found a placeholder for the 4th edition (releases in a month or so) of PiO-C on Amazon that specifically mentions in the description coverage of XCode 4.2, ARC, and iOS 5. If TBNRG doesn't cover everything then I'll have to drop $30 on the latest edition of a book I already own. Well... that's the game isn't it?
Maybe in a few weeks I'll follow up this post with instructions on reverting to pre-ARC compiler options, but for now I'll stick with TBNRG.
One big disappointment is that although TBNRG or PiO-C goes into some depth about what NSAutoreleasePool or @autoreleasepool{} are really doing, I don't think it discusses much of when to use it. I've seen snippets of code that have multiple groups of @autoreleasepool{} blocks (and in the older book multiple NSAutoreleasePool allocations) but it's not super obvious when to use them. In comparison malloc() and free() look downright friendly.
It's horribly ironic. I started this journey as an almost spiteful motion to clear up my ignorance of pointers and memory. I got to a certain competence in C and now I'm hitting a roadblock with an entirely new flavor of memory management.
Maybe I should ditch XCode and do some AVR/PIC stuff.
Friday, November 25, 2011
Back on the horse
I'm getting through some more of the Big Nerd Ranch Objective-C book today. It took the free time of the Thanksgiving holiday and some gentle prodding from my wife to do it (she preferes that I indulge my more productive hobbies rather than play Skyrim all day).
It's been a while so I'm having to play catch-up. A quick note to self about Objective-C class organization:
Class header file:
Class implementation (.m) file:
main.m:
The new Blogger interface doesn't take well to the Pastebin inserts. I'm working on it.
It's been a while so I'm having to play catch-up. A quick note to self about Objective-C class organization:
Class header file:
Class implementation (.m) file:
main.m:
The new Blogger interface doesn't take well to the Pastebin inserts. I'm working on it.
Thursday, October 20, 2011
Come and Git it.
I started reading the first few chapters of Advanced Mac OS X Programming: The Big Nerd Ranch Guide and so far it's been super enlightening. There are a lot of things I don't understand about C that aren't really about C at all and are compiler or platform specific, like what's available to you in the pre-processor. The book has a great super clear explanation of how to use all those fancy #define and #ifdef bits work. That's the kind of stuff that I'm not abundantly familiar with that's preventing me from moving on beyond being a beginner C programmer to an intermediate C programmer. I had no idea you could set #define information in the GCC command line, either. Where do people learn this stuff? I feel super fortunate that I came across this book because I'd still be in the dark otherwise.
I thumbed through Programming in Objective-C and realized I can probably skip the first nine or so chapters since it covers basic C stuff like data types and control structures. The juicy bits are how classes are implemented.
Someone on Reddit posted a link to a site that has the full text (.pdf) of Michael Abrash's Graphics Programming Black Book. I didn't realize that it was legit released for free online. I just picked a chapter and page at random and had my mind blown. He's a really good writer.
This morning I made a GitHub account and did the quick tutorial on making a repository and pushing a file up. At this point I'm just following directions because I have no idea what any of the stuff I'm typing in does. I'm kind of irked because it has a great walk-through on creating a repository, making a new file, and commiting it, but it doesn't say what to do after you edit the file. I can't tell if the commands in the tutorial were only for new files or for any file. I don't plan on using Git or any source control for every quick program I write (unless I feel like I need the practice) but it will help make the case for trying to work on more long term projects.
EDIT: Also a good (free) read: C Elements of Style
I thumbed through Programming in Objective-C and realized I can probably skip the first nine or so chapters since it covers basic C stuff like data types and control structures. The juicy bits are how classes are implemented.
Someone on Reddit posted a link to a site that has the full text (.pdf) of Michael Abrash's Graphics Programming Black Book. I didn't realize that it was legit released for free online. I just picked a chapter and page at random and had my mind blown. He's a really good writer.
This morning I made a GitHub account and did the quick tutorial on making a repository and pushing a file up. At this point I'm just following directions because I have no idea what any of the stuff I'm typing in does. I'm kind of irked because it has a great walk-through on creating a repository, making a new file, and commiting it, but it doesn't say what to do after you edit the file. I can't tell if the commands in the tutorial were only for new files or for any file. I don't plan on using Git or any source control for every quick program I write (unless I feel like I need the practice) but it will help make the case for trying to work on more long term projects.
EDIT: Also a good (free) read: C Elements of Style
Friday, October 14, 2011
Compiling GTK 3.0 programs in CodeBlocks
I spent some free time installing Ubuntu 11.10 in a VirtualBox session hosted by OS X. The trials involved with getting that to work may be the subject of another post. The punchline? VirtualBox and Unity 3d don't get along. Install the host drivers, update, then log in with Unity 2d selected. Doing those first two steps is tricky when the desktop windows don't redraw unless you go to the desktop switcher. Wowie. This was true in 11.04 and 11.10 beta 2.
My motivation for moving to 11.10 from 10.10 was so that I could get a handle on GTK 3.0. A few weekends ago I really beat myself into a pulp trying to make a basic "hello world" sort of program using Cairo in GTK and failed. A lot of the issues I had were with the basic initialization and packing a Cairo window into a GTK container. I also couldn't hash out the relationship between Cairo and GTK pixbuffs. That functionality seems to have changed a lot in GTK 3.0 and I want to try again.
I use CodeBlocks out of habit. Eclipse has a weird project organization that rubbed me the wrong way, and Anjuta was just plain hard to use. I don't know of any other popular IDEs in Linux (emacs and vim worry me).
Installing CodeBlocks and Synaptic Package Manager (to get the GTK 3.0 development files) was easy enough through the Ubuntu Software Center. No problems there, although I was very surprised that Synaptic wasn't pre-installed like in 10.10.
Expecting the default GTK program (the code that is generated when you start a new GTK project) to compile the first time was naive of me (well... it worked for GTK 2.0). The errors were about not being able to find the header files. I went error to error and added the paths to the headers in the compiler search options (Project->Build Options->Search directories->Compiler tab). Once all the missing files errors went away I got a bunch of new errors about how all the functions weren't defined. This basically means the libraries it needed to link against couldn't be found. Hooray.
I sat and thought about it and realized that if I were to compile this in the terminal I'd use pkg-config. pkg-config is a tool that looks at some different file (.pc files?) for all the compiler flags you'd need to use a certain package, like GTK.
If I type into the terminal: pkg-config --cflags gtk+-3.0
I get this out:
-pthread -DGSEAL_ENABLE -I/usr/include/atk-1.0 -I/usr/include/cairo -I/usr/include/gdk-pixbuf-2.0 -I/usr/include/pango-1.0 -I/usr/include/gio-unix-2.0/ -I/usr/include/glib-2.0 -I/usr/lib/i386-linux-gnu/glib-2.0/include -I/usr/include/pixman-1 -I/usr/include/freetype2 -I/usr/include/libpng12 -I/usr/include/gtk-3.0
Similarly, if I type in: pkg-config --cflags gtk+-3.0
I get this:
-pthread -lgtk-3 -lgdk-3 -latk-1.0 -lcairo-gobject -lgio-2.0 -lpangoft2-1.0 -lpangocairo-1.0 -lgdk_pixbuf-2.0 -lcairo -lpango-1.0 -lfreetype -lfontconfig -lgobject-2.0 -lgmodule-2.0 -lgthread-2.0 -lrt -lglib-2.0
GCC has this neat feature (or maybe it's a Linux thing?) where you can embed commands with text output into the GCC options when you run it if you surround the command with these: ''
So the compile command would look like this:
gcc program.c -o program`pkg-config --cflags --libs gtk+-2.0`
And you'd get all of those extra instructions into the gcc command. Pretty neat, right?
Ok, so I got real excited and found precedent for using pkg-config in CodeBlocks via StackOverflow in a question very similar to my own:
http://stackoverflow.com/questions/5921460/how-to-setup-gtk-to-develop-with-codeblocks-on-ubuntu-linux
However, when I did this (add the pkg-config lines to the compiler/linker "Other options") the error message I got said there was no input file. It's the same error you get if you just run gcc in the terminal.
As a last resort I simply copied the output of "pkg-config --cflags gtk+-2.0" into the compiler "Other options" and the output of "pkg-config --libs gtk+-2.0" into the linker "Other options" and now everything works just fine. This seems like a bit of a hack but I can't argue with the results.
I'm glad I finally have a functional development environment, but this raises a lot of questions. Why did it automagically work with GTK 2.0 in Ubuntu 10.10? Why did implementing the solution in the StackOverflow thread not work? Is this how everyone else has to do it?
This is a pretty strong argument in favor of avoiding IDEs for everything but editing. I should either learn Make or create a shell script that runs gcc with the pkg-config lines that takes in the .c file as an argument.
My motivation for moving to 11.10 from 10.10 was so that I could get a handle on GTK 3.0. A few weekends ago I really beat myself into a pulp trying to make a basic "hello world" sort of program using Cairo in GTK and failed. A lot of the issues I had were with the basic initialization and packing a Cairo window into a GTK container. I also couldn't hash out the relationship between Cairo and GTK pixbuffs. That functionality seems to have changed a lot in GTK 3.0 and I want to try again.
I use CodeBlocks out of habit. Eclipse has a weird project organization that rubbed me the wrong way, and Anjuta was just plain hard to use. I don't know of any other popular IDEs in Linux (emacs and vim worry me).
Installing CodeBlocks and Synaptic Package Manager (to get the GTK 3.0 development files) was easy enough through the Ubuntu Software Center. No problems there, although I was very surprised that Synaptic wasn't pre-installed like in 10.10.
Expecting the default GTK program (the code that is generated when you start a new GTK project) to compile the first time was naive of me (well... it worked for GTK 2.0). The errors were about not being able to find the header files. I went error to error and added the paths to the headers in the compiler search options (Project->Build Options->Search directories->Compiler tab). Once all the missing files errors went away I got a bunch of new errors about how all the functions weren't defined. This basically means the libraries it needed to link against couldn't be found. Hooray.
I sat and thought about it and realized that if I were to compile this in the terminal I'd use pkg-config. pkg-config is a tool that looks at some different file (.pc files?) for all the compiler flags you'd need to use a certain package, like GTK.
If I type into the terminal: pkg-config --cflags gtk+-3.0
I get this out:
-pthread -DGSEAL_ENABLE -I/usr/include/atk-1.0 -I/usr/include/cairo -I/usr/include/gdk-pixbuf-2.0 -I/usr/include/pango-1.0 -I/usr/include/gio-unix-2.0/ -I/usr/include/glib-2.0 -I/usr/lib/i386-linux-gnu/glib-2.0/include -I/usr/include/pixman-1 -I/usr/include/freetype2 -I/usr/include/libpng12 -I/usr/include/gtk-3.0
Similarly, if I type in: pkg-config --cflags gtk+-3.0
I get this:
-pthread -lgtk-3 -lgdk-3 -latk-1.0 -lcairo-gobject -lgio-2.0 -lpangoft2-1.0 -lpangocairo-1.0 -lgdk_pixbuf-2.0 -lcairo -lpango-1.0 -lfreetype -lfontconfig -lgobject-2.0 -lgmodule-2.0 -lgthread-2.0 -lrt -lglib-2.0
GCC has this neat feature (or maybe it's a Linux thing?) where you can embed commands with text output into the GCC options when you run it if you surround the command with these: ''
So the compile command would look like this:
gcc program.c -o program`pkg-config --cflags --libs gtk+-2.0`
And you'd get all of those extra instructions into the gcc command. Pretty neat, right?
Ok, so I got real excited and found precedent for using pkg-config in CodeBlocks via StackOverflow in a question very similar to my own:
http://stackoverflow.com/questions/5921460/how-to-setup-gtk-to-develop-with-codeblocks-on-ubuntu-linux
However, when I did this (add the pkg-config lines to the compiler/linker "Other options") the error message I got said there was no input file. It's the same error you get if you just run gcc in the terminal.
As a last resort I simply copied the output of "pkg-config --cflags gtk+-2.0" into the compiler "Other options" and the output of "pkg-config --libs gtk+-2.0" into the linker "Other options" and now everything works just fine. This seems like a bit of a hack but I can't argue with the results.
I'm glad I finally have a functional development environment, but this raises a lot of questions. Why did it automagically work with GTK 2.0 in Ubuntu 10.10? Why did implementing the solution in the StackOverflow thread not work? Is this how everyone else has to do it?
This is a pretty strong argument in favor of avoiding IDEs for everything but editing. I should either learn Make or create a shell script that runs gcc with the pkg-config lines that takes in the .c file as an argument.
Monday, October 10, 2011
deep
http://www.slideshare.net/olvemaudal/deep-c
Long, but pretty sweet dialog on what a deeper meaning of c/c++ means.
Long, but pretty sweet dialog on what a deeper meaning of c/c++ means.
Sunday, September 25, 2011
Notes on divisors
Project Euler 12 requires counting how many divisors a number has. It only wants positive divisors, and 1 and the number itself count. So, the number 12 has six divisors: 1, 2, 3, 4, 6, and 12.
You're trying to find the first triangle number that has 500 divisors. Well, I'd like to not bother calculating triangle numbers that aren't going to have anywhere near 500 divisors so I want to know how high numbers have to get before they start approaching having 500 divisors.
I wrote this program to loop from 1 to a high number, count how many divisors each number has (and dump it to a text file), report which number had the highest number of divisors, and the number of divisors it had.
I had hoped to graph it out see it generally rise and maybe guess about where it would hit the 500 mark, but I ran it from 1 to a million and it only got to around 200.
The program would eventually get me the answer I want but once the numbers get high my CountDivisors() function starts really slowing down. Now I'm researching faster options using recursion.
This exercise is also revealing how much basic math I've lost over the years. Like the difference between divisors and factors. Divisors will divide a number with no remainder and factors will multiply into the number (which can be broken down into a set of prime numbers). Terminology, woof. I need a fifth grade math book on hand.
EDIT: I set the upper limit of numbers to get divisors from to 3 million. I started it this morning and it's still going. I'm about to head out for the afternoon so I'll leave it running. I think I'll stop it tomorrow morning if it isn't done yet. I got rid of the printf statements since they do indeed slow down the process but now I'm not sure where it's at in the loop.
You're trying to find the first triangle number that has 500 divisors. Well, I'd like to not bother calculating triangle numbers that aren't going to have anywhere near 500 divisors so I want to know how high numbers have to get before they start approaching having 500 divisors.
I wrote this program to loop from 1 to a high number, count how many divisors each number has (and dump it to a text file), report which number had the highest number of divisors, and the number of divisors it had.
I had hoped to graph it out see it generally rise and maybe guess about where it would hit the 500 mark, but I ran it from 1 to a million and it only got to around 200.
The program would eventually get me the answer I want but once the numbers get high my CountDivisors() function starts really slowing down. Now I'm researching faster options using recursion.
This exercise is also revealing how much basic math I've lost over the years. Like the difference between divisors and factors. Divisors will divide a number with no remainder and factors will multiply into the number (which can be broken down into a set of prime numbers). Terminology, woof. I need a fifth grade math book on hand.
EDIT: I set the upper limit of numbers to get divisors from to 3 million. I started it this morning and it's still going. I'm about to head out for the afternoon so I'll leave it running. I think I'll stop it tomorrow morning if it isn't done yet. I got rid of the printf statements since they do indeed slow down the process but now I'm not sure where it's at in the loop.
Wednesday, September 21, 2011
Project Euler 11 Solution
This one wasn't so hard. The difficulty was resisting the urge to make it sleeker.
A better way to do this (ah, hindsight) would be to have one loop and at each position in the 2d array do all the horizontal/vertical/diagonal math right then. It would have been a bit tricky to keep up with all the "are there enough numbers available to do this" checks that would have been needed.
This problem reminded me of the some time I was reading about object oriented programming - specifically about why the methodology is used. I had read that a class should contain a set of data and all the operations you would want to perform on that set. I could rewrite this program such that an initialized class would load up the relevant array and then the methods of that class would get each of the different products I'd need.
EDIT: I looked at the solutions other people created and it seems that this brute force method is very popular.
Project Euler 11 WIP
It's not pretty code, but so far so good.
I have the horizontal and vertical sets functional. The diagonal ones shouldn't be too much more difficult but I need to sit and pencil/paper it out before I take time on it.
This is one of those programs I worry about not because it's tricky but because someone more familiar with the language could probably do it in a quarter of the lines.
I have the horizontal and vertical sets functional. The diagonal ones shouldn't be too much more difficult but I need to sit and pencil/paper it out before I take time on it.
This is one of those programs I worry about not because it's tricky but because someone more familiar with the language could probably do it in a quarter of the lines.
Friday, September 16, 2011
2d array sanity check
This wasn't to hard to figure out - noodling about with 2d arrays is something I've always had an easy time doing (that is to say nested for loops don't scare me).
Ok - good sanity check. Hopefully this will make the rest of PE11 a bit less stressful.
Monday, September 12, 2011
Project Euler 10 Solution
This was annoying. I got the program right but the formatting of the eventual answer wrong. The acceptable format characters vary dramatically from compiler to compiler and the warnings (or lack of) can't always be trusted.
For reference (if I get around to optimizing this program) it took 8.5 minutes to run. OH and all the other stuff in the program for generating the list of primes under 2,000,000 to a text file was just for fun.
EDIT: I worked out on paper how to do the prime test faster. The next time I need it I'll implement it. I bounce between doing these problems on Linux, OS X, and Windows so that I can be exposed to the variety of platform and compiler differences that come up even in simple problems (such as this one). It's been a real learning experience but the big downside is that all my code is scattered between three machines. I did once make a fast prime finder but I have no idea where it is and my file organization for my programs is not very good. I'm considering using Dropbox.
For reference (if I get around to optimizing this program) it took 8.5 minutes to run. OH and all the other stuff in the program for generating the list of primes under 2,000,000 to a text file was just for fun.
EDIT: I worked out on paper how to do the prime test faster. The next time I need it I'll implement it. I bounce between doing these problems on Linux, OS X, and Windows so that I can be exposed to the variety of platform and compiler differences that come up even in simple problems (such as this one). It's been a real learning experience but the big downside is that all my code is scattered between three machines. I did once make a fast prime finder but I have no idea where it is and my file organization for my programs is not very good. I'm considering using Dropbox.
Subscribe to:
Posts (Atom)