Defrag Time

2 07 2010

Hmm, maybe this has something to do with my desktop has been running slow…

I have reached nearly 60% file fragmentation! I think that’s a new personal record.





Hidden Window Update

19 06 2010

No new information on my mystery hidden Chinese window. The computer was scanned with Avast, Windows Defender, and SpyBot Search and Destroy with all negative results. I also spent some time going through my Firefox plugins and anything in services.msc and msconfig. If it’s a virus or some sort of spywear, it’s a damn stealthy one. Maybe it’s just some sort of random window title that happens to be mostly Chinese characters… Odd that none of my other computers display the same behavior though.





Hidden Windows Scare me

18 06 2010

So I was messing around with twapi on my laptop and noticed an oddly named window. It was filled with question marks, like the encoding wasn’t working. Then I ran twapi::show_window on it (and all other hidden windows), and the result was some sort of hidden window filled with Chinese text.

Upon further experimentation I found it only shows up when I log into gmail, either via my ASU account or normal gmail accounts.

Meh… virus? I tested it on other machines and didn’t find the window. Looks like something hooked into Firefox and is launching whenever I view my email… joy.





Back to Slack?

16 11 2009

Well, after hearing and seeing horrible things with the new Ubuntu release, I decided to try good old stable Slackware on my new 320GB drive along side Windows 7. The install was… well, you know how Linux goes.

First off, LILO refused to boot into Windows 7. When I tried to edit the lilo.conf and then run lilo -v to update it, I got the error, Fatal Error: Partition entry not found. The partition from which an other operating system should be booted isn’t listed in the specified partition table. The only thing I could find online said,

This either means that an incorrect partition table has been specified or that you’re trying to boot from a logical partition. The latter usually doesn’t work. – Linux Bible

Well, I am trying to boot Windows from a logical partition. Why doesn’t this work? Don’t know….

I put my Windows 7 install disk in, restored the MBR with “bootsect /nt60 c: /mbr” inside the repair command prompt. Will update this when I have some more time to make it work. I’ll try and just install Lilo/Grub to the same partition as Slackware’s on and then point the Windows 7 bootloader to it. Either that or I’ll try Grub instead of Lilo.





Microsoft Visio for UML Review

11 10 2009

I recently got MSDN access and decided to do some UML modeling for a class project in Microsoft Visio. I have to say, unlike most Microsoft Office tools, this is one where the Open Source community certainly wins. Adding a class, methods to the class, and arguments to those methods to a class diagram, requires so many menus, clicks, and scrolls, that half way through your UML diagram you’ll be wishing you had done it in Powerpoint instead.The slow and difficult to use interface is the main downside. The program was designed to do diagrams, schematics, and just too many things. It does a lot of things, but it doesn’t do them well. To add to that, it doesn’t even have templates for any of the Java datatypes, just C++, C#, and Visual Basic.

The major Open Source alternatives, StarUML or ArgoUML, are a lot faster to use and have all the same major features for UML diagrams.

For Outlook vs Sunbird or Microsoft Excel vs OpenOffice Calc I MIGHT go for the Microsoft version if I can get either for free, but in the case of Visio, I’m going back to the Open Source tools.





Internship Coming Along

9 07 2009

Just a random post to let people know I’m still alive, and this blog may actually be updated every now and then. I’m currently doing a summer internship at Emerson Network Power, which is keeping me rather busy (40 hours a week). The details I can’t really go into, but it can best be summed up as automation scripts in a bunch of languages no one has ever heard of, for software most people haven’t heard of, on an interesting project that I’d have to kill you if I told you about.

In another news, I’ve ordered an AVR Butterfly to play around with in my spare time and learn some C programming for embedded microcontrollers. It should be coming in the mail today (woot). That should provide some useful rambles about hacking and programming to put here.





Project Euler Problem #15

20 03 2009

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

p_015

How many routes are there through a 20×20 grid?

First off, let me say I’ve never taken a combinatorics course, and before this problem had never seen the words “n choose k”. If you’ve taken a combinatorics course, you’ll probably figure out this problem in about 3 seconds, realizing it’s simply 40 choose 20 (which Google calculator will gladly output). Due to my lack of combinatorics, I was forced to take a very long route to get to the answer, but challenged myself a lot more in the process.

First off, I thought to myself, there must be some function f(n) for an n x n grid that will give me the result, and I just need to find it. In order to simplify things, I changed the grid to a set of equally spaced points in a plane. For a 2×2 grid, there would be 9 points (2+1)(2+1). Then I traced through the grid again, looking for some simple pattern. I quickly noticed that once you hit the bottom or right edge, you must go straight to the end point using a single path (along the edge). Otherwise, you have two choices (down or right). In my diagram below, I drew arrows on the points that I had a choice, and simply put a line through the points on the edges that had no choice. I also took note that for an n x n grid, there would be n movements in the right direction, n movements in the down direction, and 2n movements total.

paths2I was also on the bus at the time, so no access to a computer, which explains the badly scribbled diagrams.

The only pattern I could deduce from this, is that because there is 2n number of moves, all of which n must be down and n must be right, I could do something like this.

Down = 0

Right = 1

Paths to end in my 2×2 grid (from left to right, top to bottom in the diagram): 1100, 1001, 1010, 0011, 0101, 0110.

Nifty, but how do I make an algorithm to actually create these numbers? I could simply check using a brute force method, generating all the binary numbers from 0 to 15, and then checking if they meet the requirements. To solve the problem though, I would need to generate all the numbers from 0 to 2^(40). That’s a lot of numbers to check. 1,099,511,627,776 of them to be exact. I found the result of the 3×3 grid by hand, through painful searching. There’s 20 of them, so I don’t bother to show the result. If anyone finds an easy algorithm to use this method, I’d be interested in seeing it.

As things were, I hadn’t gotten far, and decided to take another approach. After staring at 1’s and 0’s for so long, I was ready to stare at something more graphical, and decided to represent the 3×3 grid paths as a binary tree, in the back of my mind thinking I could use a linked list in C to actually make such a structure and maybe get somewhere. First off, I put all the points into an array (in my head anyway) so I could easily keep track of them. P11, P12, P13, P21, etc for labels. Then, for a down branch, go left on the tree, and for a right branch, go right.

pathtreeThen I spent quite some time trying to make out patterns. First off, I began noting the paths from a point down to the bottom, which you can see in the small numbers on the lines and under the points. Then I noticed the tree diagrams for a 1×1 (red) and 2×2 (blue) grid were actually inside the 3×3 (green) grid. Nifty! Closer I thought I was, to finding a simple recursive function to find the answer I seek. Unfortunately, I couldn’t devise a simple function to generate the number of paths from the next tree diagram. Then, it came to me, looking at the path lengths.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

20

Eureka! It’s Pascal’s  triangle up-side-down! The result I seek for a n x n grid is the middle number of the 2*n’th row of pascal’s triangle. Not only that, but this is also the sum of the terms squared of the n’th row (one of many odd patterns in the triangle). Finally all I had to do was write a program to calculate the first 20 lines of Pascal’s triangle, and then square the terms of that last row and add them together.

to calculate the triangle,

#include 

#define ROWS 21
#define COLS 21

int main() {
        int triangle[ROWS][COLS];
        int i, j;

        for (i = 0; i < ROWS; i++) {
                for (j = 0; j <= i; j++) {
                        triangle[i][j] = 0;
                        if (i == j || j == 0) {
                                triangle[i][j] = 1;
                        } else {
                                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
                        }
                        printf("%d ", triangle[i][j]);
                }
                printf("\n");
        }
}

Resulting in,

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1

Taking all the elements of the last row, squaring them, and adding them,

1^2 + 20^2 + 190^2…. = 137,846,528,820 paths to the end in a 20×20 grid. That’s a lot of paths, I’m glad I didn’t have to resort to a pure brute force approach, it would have taken quite a long time.