Leaving some notes for myself here

I'd like to get this code to compile:

http://zetcode.com/tutorials/cairographicstutorial/basicdrawing/

I have a fun idea for a program but I can't do it unless I get a handle on embedding a cairo-based drawing in a GTK window.

http://developer.gnome.org/gdk/stable/gdk-Cairo-Interaction.html

quick detour

I took a brief lull in activity at work to knock out another important piece of code in my case analysis program (not so much analysis right now - mostly just parsing).

Python lacks a #define statement so I can't alias words to numbers. I had really hoped to do this to pair column names (human readable) to numbers (parser readable).

Instead of:

#define OPENDATE 0
#define CLOSEDATE 1
#define NOTES 2

I am faced with just making them proper variables:

OPENDATE = 0
CLOSEDATE = 1
NOTES = 2

and so on.

I stumbled across a different solution I like in example 3.20: http://diveintopython.org/native_data_types/declaring_variables.html#odbchelper.multiassign

I'll flip a coin to decide which is more readable and then put it in. The code for returning a specific column is already in place. Took me longer than it should have - I've forgotten too much about Python in the past few months.

More divisor function thoughts

I had some time to sit down with a pen and paper to figure out a better way of getting all the divisors out of a number.

I don't think there are any clever tricks using recursion I can use. I went down that path because it worked for something else but I don't think it will work here.

This makes sense in hindsight (and it's a testament to how poor at basic arithmetic I am) that I only need to test to half the number.

For example, the number 90 has 10 divisors: 1, 2, 3, 5, 9, 10, 18, 30, 45, 90. Obviously I don't need to test beyond half the number (which holds true for odd numbers, too).

I might have even stumbled upon a way of detecting square numbers.

64's divisors are 1, 2, 8, 16, 32, 64. If you see the symmetry in both 90 and 64's divisors you can see a pattern.

90: 1,2,3,5,9,10,18,30,45,90
Taking the outer numbers and working out way pairwise inward we have:
(1,90)(2,45)(3,30)(5,18)(9,10)
These are factors of 90.

64:1,2,4,8,16,32,64
Doing the same thing we find a slight difference - there are an odd number of divisors.
(1,64)(2,32)(4,16)(8,?)
We of course know that 8*8 is 64. This makes me wonder if all squares have an odd number of divisors, or if there are number with an odd number of divisors that
aren't squares.

25 is a square and has an odd number: 1,5,25

So, just some thoughts. I could quickly spin off my program to test for stuff like that.

Anyways I can quickly change my program to only loop n mod x and test for 0 such that x only goes to half of n instead of all the way up to n.

New GTK+

http://www.webupd8.org/2011/09/gtk-32-released-with-html5-allows.html

You know... I'm not really taking advantage of all that VirtualBox allows me to do. I'm still running Ubuntu 10.10 because I'm scared of the big UI refit that 11+ added. There's no reason for me not to just make another VM and test the waters.

Win32

One of my (ex) coworkers had to get up to speed on Windows programming and learned enough of the Win32 API (not MFC, or not much of MFC if I recall) to get the job done.

I spent last night perusing some Win32 tutorials and it doesn't look that hard. It has its own special weird things you have to do "just because", and the event handling is called message handling but other than that it looks rather analogous such that it wouldn't be too tough to get familiar in a hurry if I had a free weekend.

The way it handles messages is (at first glance) organized different than how GTK does it. In GTK you explicitly list all the signals you want to catch and pair it with a callback function. In Win32 you have one callback function paired to a window and in that callback function you use a big switch statement to handle any incoming messages.

The reason I mention this is that I'm still really fuzzy on all these Windows programming options. I know that .net is a framework and MFC is sort of the C++ option for Win32 (right?) but I have no idea what WPF or COM or any of those other TLA mean (beyond a quick Google search anyways).

As an amateur level hobbyist programmer that wants to evolve beyond simple ~100 line console programs to useful GUI-based programs that do interesting things I feel very nervous about hitching my wagon to one particular OS-specific framework. I picked GTK because it has decent cross-platform support (excluding OS X unfortunately) but it concerns me I almost never see programs for Windows written in GTK.

I'm just being paranoid about spending time learning something that isn't useful in a lot of situations. That being said I'm happy that the time spent with GTK at least allowed me to understand the Win32 API on a superficial level.

Divisor count results for 3 million

The number between 1 and 3 million with the largest number of divisors is 2882880 with 336 divisors.

Execution time was over six hours.

The actual output of the program (with CodeBlocks' own time counting):

---

The largest is 2882880 with 336 divisors

Process returned 0 (0x0) execution time : 23027.710 s
Press any key to continue.

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.

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.

fixed 2d array program

I fixed some big naming errors (I swapped rows and columns).

My Everest

A ray tracer would be my Everest. It requires competency at two things I desperately want to be good at: programming and math.

Someday there will be a Chris Learns Math journal. I'll probably start with pre-calculus algebra as a review. I actually excelled at that kind of thing and I recall doing very well on the SAT IIC which tested for algebra/geometry/trig. I'd rather focus after that on linear algebra and maybe calculus (which I still maintain a deep well earned fear of). It wouldn't kill me to do some statistics as well - another subject I was good at although the course I took was not statistics for engineers.

off topic

I've been playing Minecraft again now that another big update has come out and it makes me think of two things.

1) One of the game's big features is that it's very retro (for lack of a better word). It employs the use of "pixel art" (the quotes are because all digital art is pixel art but nevermind) and it gives off an 8-bit vibe like it would have been our favorite game on the original Nintendo had it been capable of 3d graphics. What occurs to me is that in another decade or so perhaps the blocky 3d graphics of the 90s (like the original Quake) will be used for some popular retro-looking game - probably once games start trying to do real-time ray tracing or something. Minecraft by virtue of not setting out to be a realistic looking game can get away with having low system requirements and have a massive map size.

2) I really wish I had a few more years of programming experience before Minecraft came out. I think of neat ideas for utilities or mods and I'm kind of just stuck still doing simple Project Euler problems. I know that in time I'll reach the next plateau but I feel like a kid that can't wait to grow up.

On the second point I have been having a hard time motivating myself to program. I'm at a point where everything is just grunt work like plowing through the GTK book or banging my head over the PE problems. Yes they are indeed extremely important but it's starting to become a chore. I need a pet project like a ray tracer or game mod or something that has neat flashy results that would improve over time with me.

Rethinking my smart phone choice

I had no idea Android phones could run Python.

This Reddit post is of a time lapse video - the OP put the code on GitHub.

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.

Project Euler 11 WIP

Project Euler Problem 11 is a pretty dramatic departure from the prior 10 problems (except maybe with the exception of problem 8).

I wrote out a smaller (6 x 6) version on paper and realized that it's not as hard as it initially looks. I'll have to brush up on my 2d array initialization.

The plan is at each element of the array to check if there are four numbers to the right, down, diagonal left, and diagonal right. That SHOULD handle every case of where there are four numbers lined up according to the rules of the problem. For example I don't need to check the diagonal to the upper left on element (6,5) because it was already handled by the diagonal lower right of element (3,2).

Traversing rows for checking or multiplying is easy. At element (3,2) the other three elements I need for the lower right diagonal are (4,3)(5,4)(6,5) - basically I just add +1 to the x and y three times. Similar rules apply for the other rows I need. I can likely combine the test of whether or not an element exists with the multiplying - if I try to add or subtract from an x or y point such that it falls out of bounds of the array I can simply not store the result and move on.

If I was feeling really fancy I'd do this in GTK and visualize the array and highlight the numbers I'm currently checking. It might be a good excuse to learn some Cairo.

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.

Project Euler 10

PE10 asks you to sum all the primes below 2 million. I've written the program with my old prime finder function but it's apparent I'll need a smarter primer finder. I can sum all the primes below 1 million in a reasonable amount of time (under a minute) but I left it running for the 2 million sum for a while and it's taking too long and really heating up my laptop.

There is a good prime finding solution using recursion I was shown once that I need to figure out for myself. Time get a pencil and paper.

Project Euler 9 Solution

Today's lesson is twofold. 1) Read the problem twice before diving in with both feet. 2) Wikipedia is your friend (and I have Matt to thank for that tip).

I completely misread the problem, but in my defense it's a poorly written problem. Thankfully Euclid gave us a handy way of generating Pythagorean Triples and the rest was easy.

wait now

I think I misread the problem and that square root test isn't necessary. Hm.

the fix for OSX

I had to change the square root test to:


if ((int)(sqrt(n) * (int)sqrt(n) == n))

This takes the square root of n and truncates everything after the decimal via cast to integer before multiplying against itself. There are many intricacies of number types that fall into the category of "not really important until it suddenly is".

one foot in front of the other

The next Project Euler problem I'm working on requires testing if a number is a square. There are some very complicated solutions for this but the one I'm going to try isn't very complicated at all which makes me wonder if I'm doing something wrong.

Basically if I have a number X I'm taking the square root of that number, multiplying it by itself and testing to see if I get the original X back out again. Usually that would result in all numbers passing (says my calculator), but for reasons I don't completely understand yet my implementation works. I thought that I would have to take the result of the square root (which would be returned as a float), cast it to an integer, and then square and compare. This isn't the case for some reason. I need to read up on what sqrt() is actually doing.



EDIT: On a hunch I built this program on my Mac and it totally doesn't work right. I got lucky on Windows.

EDIT 2: For the life of me I can't find the implementation of that function anywhere. That's ok. I'll just be really explicit about casting and I should get the results I want.

long weekend

I haven't been doing much programming the past week. I spent a few frustrating hours trying to find information on making XCode 4 work with SDL but didn't have any luck. There was also some reviewing of my old code to remember what I was up to and to make sure I could still read it. Luckily my Python code I was doing for work is well documented else I'd be totally lost. For whatever reason C is like riding a bike but Python is like trying to remember the plot to Mission Impossible 2.

comforting

I'ts nice to know Linus Torvalds has similar structure to his programs (which he admits this was done while learning GTK at the same time). At the least it's nice to have my bracket style validated.

https://github.com/torvalds/diveclog