Archive for the ‘Tech’ Category

Combination Generation

Saturday, December 23rd, 2006

I ran across a wonderful article a while ago about a Combination / Permutation class that generated them as a stream.  It’s a great idea.  It makes unit testing pretty easy, as you can have the class make sure you hit all your test cases.  Sadly I wasn’t able to find the article again, at least I don’t think i was able to find it.

Anyway, I went a made my own combination generator.  For those wondering what a Combination is, its arranging K items from a set of N items, order doesn’t matter.  So given 5 items, and only taking 3 at a time you would get

0,1,2
0,1,3
0,1,4
0,2,3
0,2,4
0,3,4
1,2,3
1,2,4
1,3,4
2,3,4
The way this works is quite simple.  Each column has a min and max value that it can hold.  The first column goes from 0-2 (or 0 to (N-K) ), the last column goes from N-K to N-1.  You can easily generalize this into column C can hold a value from C to N-K+C.  The value of N-K can be precomputed.  Armed with this knowledge you can now make all your combinations.  First start with the identity (0,1,2,…,n).  To get the next combination, start at the right most item, and move left until you hit the first item that can be incremented, in other words, the value is between C and N-K+C.  Increment this value, then move back right and set each of these columns equal to 1 more than the item at its left (ie   c[i] = c[i-1]+1).

So given 0,3,4,  we start at the right (4).  4 is the max value for this column, so we move left.  3 is also the max value for this column, so we move left again.  0 is between 0 and 2, so we can still increment it.  We increment it to 1.  Now the array is 1,3,4.  Next we go back right and add set each column to one more than the column at its right, so we change the 3 into 1+1, which is 2.  We change the 4 into 2+1, which is 3.  This leaves us with the next combination of 1,2,3.

The last combination has the pattern of the first item equal to N-K (or 2 in our case).  When we reach this case we stop.

Ok, thats my little walk through on combinations. I’ll put something up about permutations next

n-jugs

Thursday, November 9th, 2006

Given a set of n jugs of different sizes, how would you dump water between them to get a specific amount? If you have ever watched Diehard III, you might have seen this with 2 jugs. In the movie they are given 4 and 5 gallon jugs and are asked to make 3 gallons.

I originally tried to write a program to solve this problem using a brute force method. Needless to say, this was very slow and almost never ran to completion. I thought about it for a while and finally figured it out. It boils down to just solving a graph of connected nodes. Since I wanted to learn ruby, I used this to learn the language.

The basic idea to solve this is:

Have we reach the end state (desired amount)?
Loop through each from jug (i)
Loop through each to jug (j)
Calculate the new state of the jugs (water level in each)
Have we seen this “state” before? If not, store the new state. If we have, then move on
If this is a new state, go to step 1 with new state
old state, continue looping

Obviously, this wont find the optimal solution, but it will find a solution. If you want to find the optimal, you will have to store the steps to get to a state, and see if you have found a quicker path to a state. If you want, I still have the ruby file to solve this.

If it aint broke, don’t fix it.

Saturday, October 14th, 2006

Ok, so a big woops on my part. I tried to update the server the other day. As you probably have guessed, I messed up. I miss typed a few things, left out a few things, and promptly rebooted the server. Whats wrong with rebooting you ask? Well, if the computer you are working on is located in a different state, behind locked doors, in a cabinet , then you might have a problem. Apparently the computer couldn’t find the right file to boot from, because i miss typed it. So it was just sitting there waiting for the “Any Key” to be pressed. I had to wait a whole day before someone could drive down there and manually restart the server for me.

So the lesson for today is, if it aint broke, don’t fix it. Maybe in a few months when I have more time to make sure I do everything correctly, I’ll try for an update.

osx x86 install guide

Wednesday, August 2nd, 2006

Looking around the net, its hard to find a good, complete guide for install osx86. I’ll try to make a complete one here. If there is anything missing, please feel free to comment.

Things you might need:

  • An Install DVD that works on intel hardware
  • A computer that supports at least SSE2
  • A USB mouse and keyboard (optional, but makes things easyer later)
  • A free 6.5GB (at least) partition or disk

The 1st thing you should do is make sure you can boot the install DVD. If you can’t get to the installer screen, this guide will do you no luck. Some things you might want to try to get it booted are as follows.

Press F8 to get to the boot option screen. You do this right when it says Loading Darwin

at the boot: prompt add -v to get a print out of what is going on. Some other options you can try are platform=ACPI or platform=X86PC. If you still can’t get it booted you should look around http://wiki.osx86project.org/ for help.
Now that you know you can boot into the installer you can contine.

Setting up Hard drive space:

As stated earlyer, you will need at least 6.5GB of free space. You can try to get away with less, but you wont be left with much free room. I would recommend you go with 10GB. There are two ways to setup the harddrive space. The first is in an empty partition. The second would be on an entire disk.

Setting up a Partition:

I recommend using Partition Magic to do this. There are a number of linux methods you can also use to resize partitions. Where the partition is on the drive doesn’t matter, as long as the partition is a primary partition. DO NOT make the partition as an extended partition. Do not format the partition. The partition type needs to be set to 0xAF (HFS), otherwise the installer complains. You can set the partition type using the installer DVD if you have trouble.

Using FDISK from DVD to set partition ID (0xAF):

It F8 to get to the boot menu and type -x -s -v (plus any addition options you might need to boot correctly). This will boot you into a command line. At the command line type

fdisk -e /dev/rdisk0

Mind you the rdisk0 part might be different depending on how your system is setup. rdisk0 is the first SATA disk in my system. If you are using IDE drives you might want to try /dev/disk0. If you did it correctly you see
fidsk: 1>

Type p to print out the partition table. You should see the partitions you setup. If not then you typed the wrong drive and need to quit (by typing q) and try another drive. If you see the partition you want to use for OSX type setpid followed by the number of the partition you would like edit. For example you would type setpid 2, if you want to set up OSX on your 2nd partition, and windows is on the first. Fdisk then ask you for a “Partion id”, type AF, and press enter. Type w to write your changes, then q to quit. Type reboot to restart the computer.

Setting up a whole Disk:

If you want to use a whole disk to install to there is nothing to setup. Just use the Disk Utility built into the installer to setup the drive.
The Install (what you were waiting for)

At this point, you should be able to boot into the graphical install, and have a partition or disk ready to install into. Boot up the installer and wait for the menu bar to show acrows the top. On the menu bar go to Utilities and select Disk Utility. Select the partition you want to install onto from the menu on the left. At the bottom of the screen it should show you all the information about it. If the format (partition ID) is not 0xAF (HFS or Mac OS Extended), you’ll have problems. If you close the disk utility and open up the terminal from the utitlities menu, you can change the id using fdisk, as explained above (go back to the section about using fdisk for an explanation.) Click on the tab labled ‘erase’ to format the disk. I recommend setting the volume format to “Mac OS Extended (Journaled). But you can use what you like. Click erase to format the drive. Once the drive is format close Disk Utility and contine the install.

Customize Install:

At one point in the install there will be a Customize option on the bottom left corner. DONT MISS THIS. If you miss this you will have an hour long install process. Customize the install by removing the languages and print drivers you do not need. If you DVD has patches on it, you might find them in here to. Install only the ones you need.

Contine with the install

Don’t believe the time remaining, it lies. It will take some time to finish the install. Go find something to do. Like take a 10 mile walk. Watch a movie. When it is done installing the computer will automaticly reboot.
The first boot:

This is where alot of problems happen. Even though the install went well, you 1st boot might not go well. You could get stuck at the grey apple screen for ever, or OSX wont see your mouse and keyboard, or you might be stuck in an reboot cycle. If it can’t see your keyboard and mouse, this is where the USB keyboard and mouse come in. Plug them in and OSX should see they ok. If you don’t have the USB see the section at the bottom about PS2 kext. If you have the other problems try the F8 trick and put in -v to see what is going on.

You should be in OSX after the initial register screen. But a few things might not be working, such as ethernet and sound. There might be a way to fix these depending on what you have.

Mouse not working, and other PS2 problems:

You need PS2 support for these to work. If you’re lucky these would have already been installed by the DVD, but probably not correctly if they aren’t working. If not, you have to find them. Look for ApplePS2Controller.kext on the internet. To fix them so they work, boot in safe mode by using F8 then -x -s, to get into Safe Mode. Now you need to remount your drive in read/write mode. The quickest is to just type

mount /

Next you need to fix the permissions on the extention. You can do this as follows.

cd /System/Library/Extensions
chmod -R 755 ApplePS2*

If you installed other extentions do the same for them, such as:

chmod -R 755 AppleAC97Audio.kext

You then need to remove the Extentions cache files:

rm /System/Library/Extentions/Extensions.kextcache
rm /System/Library/Extentions/Extensions.mkext

You can now reboot the system and your mouse, sound, or what ever should be working now.

Fixing the Network:

So you have what you think is a supported card, but it’s not working? Well it probably is supported, but OSX doesn’t know that. The following was derived from osx86project. You need to find the PnP device ID for your card. To do that boot into windows and open up the Device Manager. Find your Network card, open up the properties on it. Click on the Details tab. You should have “Device Instance Id” selected in the drop down. What you will see is something like PCI\VEN_12AB&DEV_12EF&SUBSYS… Now what you need is the numbers/letters following VEN and DEV. These are your vender and device ID numbers. You need to join them with the Device ID first. So in this example you would get 0x12EF12AB. Write this number down, as you’ll need it.

Boot up OSX and open up a terminal window. Type

sudo bash
cd /System/Library/Exensions/IONetworkingFamily.kext/Contents/PlugIns/
ls

Here you should see a list of apple supported cards. If you are luckly one simular to your hardware will be listed in here. The AppleIntel9245XEthernet.kext is for Gigabit internet cards, the other works on Intel Pro 100/VE cards. cd into the kext that you will use then into the Context subfolder. Open up the Info.plist file with the following command.
nano Info.plist

Now this is where it will differ depending on what version of OSX you are installing. If you are using 10.4.5, scroll down untill you find IOPCIMatch. If you look right below it you will see with a list of number in the format of 0xABCD1234. Other versions of OSX will have these numbers after were it says Device Name. These are a list of PnP device id, as you probably guessed. If you can’t find the above sections, scroll through the file until you can find a list of 8 digit numbers. Remeber that number you wrote down a little bit ago? Add it to the list. Each ID should be seperated by a space. Next remove your Extentions cache files.

rm /System/Library/Extentions/Extensions.kextcache
rm /System/Library/Extentions/Extensions.mkext

Reboot and your card should work now. If it doesn’t then you added your PnP id to the wrong kext. Undo what you did and try it with a different kext.Sound you say:

Getting sound to work is a little more involved then ethernet. Depending on what sound card you have there are many methods (to the madness) to get it to work. I had a RealTek ALC861. The thing about this card is that it uses an intel bus/hub. So I have to enter the ID’s for the card and the hub.First off you’ll need the right kext for your audio card. Mine happened to be the AppleAzaliaAudio.kext. Different cards might work with the AppleAC97Sound.kext (or something simular). What’s that you say? You don’t have these kext? You’ll have to google the internet for them then. I have heard there are torrents out there with these kext files, but havent ever looked or seen them.
Anyway, to get the RealTek card to work I followed the walk through found on here:

http://forum.osx86project.org/index.php?showtopic=1474&st=40

I had to do a little more mucking around because I had an ICH-7 intel bus insead of a 6. Where you have to edit this file:

/System/Library/Extensions/AppleAzaliaAudio.kext/Contents/PlugIns/AppleAzaliaController.kext/Contents/Info.plist

I put in a bunch of ID’s hopeing one would work. You find the section for the ICH-6 bus (yes i know its not ICH-7) and add your pnp ID in there right after IOPCIPrimaryMatch.

Now the bigest question I had when doing this was how to find my bus id. In windows I opened up device manager and wrote down ALL the id’s for the ICH-7 bus. Under ‘System devices’ in device manager, you see a buch of Intel® devices with a 4 digit number after then.. such as 244E or something. Somewhere in the list of Intel devices you’ll see one like UAA Audio something. This would be one you are looking for. Get the Dev ID for it (either by reading the 4 digit number next to it, or properties -> Details). Mine was 27DA for the UAA device. I also wrote down the ID for the PCI controller (27B9)..

I used these numbers to enter in for the IOPCIPrimaryMatch in the AppleAzaliaController.kext. ie i added 0x27DA8086 and 0x27b98086 onto the list. Removed my extentions cache files and rebooted.

My audio worked after this. I’m not sure which of the 2 above numbers i actauly needed but i figgured put both in and see if it worked. and it did.

VMware stuff:
If you are going to try to install in VMware, you will need a Virtual CD driver, as the built in ISO support in VMWare will not correctly read mac ISO’s. You also need to add paevm=”true” onto the end of the vmware machine configureation file. This enables PAE support. Your host CPU has to have this too. I’m not sure what VMware does if the hose CPU does have support.

Tsk, Tsk for tizzle

Monday, February 27th, 2006

Last week I ran across what looked like an interesting program (Tizzle Talk). It translates your IM for you. So I tried it, yeah i know bad idea. I couldnt quiet figgure out how to get it to work, and I mostly use trillion, so I uninstalled it, or so I thought.

I opened up my ‘My Documents’ folder today and noticed there were 40+ folders in it. Ones that I know I didnt put there. AppPatch, Microsoft.NET, WinSxS, Oracle, System32, Fonts, etc… If these wasn’t weird enough, some folders were listed multiple times. I didn’t know NTFS would allow a folder to contain files of the same name. A quick look at the dates on the folders showed they all were created the same date/time I installed Trizzle talked. A quick scan of my HD for all files on that date showed them in a bunch of folders. I had more of these ‘ghost’ folders in Windows, Windows\System32, Program Files, Program Files\Common Document Settings\\. I’m not sure what this has to do with trizzle, and why it created all of them, but each folder was empty. So point of warning to anyone who uses/used trizzle. You might have a bunch of extra files laying around.

Did i mention it’s been raining here for the last week… lots and lots of rain.