Adrian Bravo's tumblr

I decided to do kick off learning Haskell again (via http://learnyouahaskell.com/). Personally, I feel that jumping right into utilization of a language is the best way for me to learn it, so I solved a few Project Euler problems in Haskell.

Problem #1

{-
  http://projecteuler.net/index.php?section=problems&id=1

  If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9.
  The sum of these multiples is 23.
  Find the sum of all the multiples of 3 or 5 below 1000.
-}

solution = sum ([
    x | 
    x <- [3..999],
    x `mod` 3 == 0 || x `mod` 5 == 0
  ])

Problem #2

{-
  http://projecteuler.net/index.php?section=problems&id=2

  Each new term in the Fibonacci sequence is generated by adding the previous two terms.
  By starting with 1 and 2, the first 10 terms will be:
      1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
  Find the sum of all the even-valued terms in the sequence which do not exceed four million.
-}

solution = sum [ x | x <- fibonacci 0 1 4000000, even x ]
    
fibonacci :: Integer -> Integer -> Integer -> [Integer]
fibonacci x y m =
  if x + y <= m then x:(fibonacci y (x+y) m) else [x,y]

I think this is a bit sloppy/inelegant. Here’s a different way to pull fibonacci numbers, yet infinitely:

fibonacci :: [Integer]
fibonacci = fib 0 1

fib :: Integer -> Integer -> [Integer]
fib x y = x:(fib y (x+y))

Problem #3

{-
  http://projecteuler.net/index.php?section=problems&id=3

  The prime factors of 13195 are 5, 7, 13 and 29.
  What is the largest prime factor of the number 600851475143 ?
-}

maxFactor :: Integer -> Integer
maxFactor x = (floor (sqrt (fromIntegral x)))

factors :: Integer -> [Integer]
factors x = [ y | y <- [1..(maxFactor x)], x `mod` y == 0, y /= 1, null (factors y) ]

solution = factors 600851475143

I really love the factors function, although it could be named prime_factors more accurately. That null (factors y) part makes me want to marry Haskell.

Problem #4

{-
  http://projecteuler.net/index.php?section=problems&id=4

  A palindromic number reads the same both ways.
  The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.
  Find the largest palindrome made from the product of two 3-digit numbers.
-}

import Data.List -- for the sort function

digit_to_char :: Int -> Char
digit_to_char x = "0123456789" !! x

number_to_string :: Int -> [Char]
number_to_string x =
  if x == 0 then ['0']
  else
    if x < 0 then '-' : number_to_string (x * (-1))
    else
      if x >= 10 then number_to_string (floor (fromIntegral (x `div` 10))) ++ [digit_to_char (x `mod` 10)]
      else [digit_to_char(x)]

is_palindrome :: [Char] -> Bool
is_palindrome x =
  if length x <= 1 then True
  else
    if head x /= last x then False
    else is_palindrome (tail (init x))

-- sort and reverse to start with the highest numbers in the list
-- and return the first without moving forward using call to head
solution = head [ z | z <- (reverse (sort ([ x * y | x <- [100..999], y <- [x..999] ]))), is_palindrome (number_to_string z) ]

Problem #5

{-
  http://projecteuler.net/index.php?section=problems&id=5

  2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
  What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
-}

2
3
2,2 
5
2,3
7 
2,2,2
3,3 
2,5   
11    
2,2,3
13
2,7
3,5
2,2,2,2
17  
2,3,3
19
2,2,5

2*2*2*2*3*3*5*7*11*13*17*19

So I didn’t really solve this one with Haskell, but why bother? I just took the prime factors of the whole numbers (or the number itself if it is prime) from 2 to 20 and multiplied them together without redundancy (i.e. while 16 = 2*2*2*2 and 8 = 2*2*2, I need not compound them as 16 is divisible by 8).

First, if you are unaware of vagrant, it is described as “a tool for building and distributing virtualized development environments.” It’s an extremely useful piece of software for developers who insist on making their development environment mimic their production environment without fumbling over different installations of software on their local machine. You can read more about it at http://vagrantup.com/.

Also, these instructions are being written using vagrant version 0.3.4. It is beta software, so many underlying concepts may change. Feel free to contact me if anything seems off. I based a good deal of my instructions on what I learned from vagrant’s documentation on base boxes in the first place. However, some of my instructions are customized due to errors I found along the way (especially my change to /etc/sudoers due to Ubuntu’s default secure_path behavior).

What you’ll need

• VirtualBox (http://www.virtualbox.org/wiki/Downloads)
• disk image of an Ubuntu server installer (http://www.ubuntu.com/desktop/get-ubuntu/alternative-download)
• a working installation of ruby, rubygems, the vagrant gem and any other required gems

Note: It is important that you are using a server installation of Ubuntu rather than desktop as base boxes should be relatively small in size.

Set up a new virtual machine

In VirtualBox, start a new machine. You’ll probably want to name it something descriptive in terms of the operating system and architecture. I’ve named mine ubuntu_9.10_64. Choose Linux as your Operating System and the proper Version or distribution—Ubuntu or Ubuntu (64 bit). In my case, I chose the latter.

Next, set the base memory size. It’s recommended that the default of 384 MB is used. However, this can be changed easily when launching individual vms with vagrant.

Now you need to set up a new hard disk. The default settings should be fine, and you’ll definitely want to make the disk use the Dynamically expanding storage type. I made my disk 40.00 GB in size. This should be more than enough for most projects. Just use your good judgment. Not the bad one. Right.

Anyway, your virtual machine’s basic set up should be complete.

Toggle some settings

Right-click on your virtual machine and select Settings. Go to the Audio tab and unset Enable Audio. Next, go to the Ports tab and unset Enable USB Controller. These are likely unnecessary to your development environment. Finally, go to the Network tab and make sure it is enabled and attached to NAT.

Install Ubuntu

Start up your virtual machine. You should be prompted with a First Run Wizard, which will ask you to choose an installation media. This is where your disk image is going to be put to use. If you’ve already attached it to VirtualBox, just select it from the list of Media Sources. If not, click the icon next to the select menu. This will pop up the Virtual Media Manager. Select Add and browse to your disk image to add it to the list. Then select it and move on to the next step.

Your virtual machine should start up with the Ubuntu installation options. The personal stuff like keyboard layout is up to your discretion. However, be careful to set the hostname, username and password appropriately, so pay attention to the installation prompts.

Hostname

Like the virtual box name, you’ll probably want to be descriptive here. Vagrant’s documentation suggests vagrant-[os-name], e.g. vagrant-debian-lenny. I’ve named mine vagrant-ubuntu-910-64.

Disk Partitioning

I chose Guided - use entire disk. I’m unsure of what LVM will do to a base box nor what purpose it will serve for my projects, so I haven’t bothered trying it. But don’t let that discourage you.

Full name, Username, Password

I set these to vagrant, vagrant, and vagrant, respectively. While full name should be changeable to whatever you like, I’ve chosen vagrant to make it more appropriate for use on machines other than my own. Again, this one’s up to you. However, your username and password should both be vagrant to follow vagrant’s suggested conventions. 

Moving on

I chose not to encrypt my home directory, left my http proxy blank, and selected No automatic updates.

Finally, for software to install, I simply chose OpenSSH server.

That should be it for the ubuntu installation. Here comes the fun part.

Configure the base box

Log in to the virtual machine, which should have restarted itself after the installation.

Modify sudoers

Let’s make sudo work without prompting for passwords. Vagrant needs this. Run the following command:

sudo visudo

Find and change the line that says %admin ALL=(ALL) ALL to %admin ALL=NOPASSWD: ALL

Save and exit the editor and run this command:

echo 'echo $PATH' | sudo sh

You should see something like this:

/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/X11R6/bin

Copy the output down run sudo visudo once again. Now change this line:

Defaults env_reset

to this (using output from the previous results to set the secure_path):

Defaults env_reset, secure_path="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/X11R6/bin:/var/lib/gems/1.8/bin"

If it’s unclear, we’re making it such that the secure_path recognizes our rubygems’ bin directory so that it may run executables created by rubygems. This is crucial for vagrant to be able to run chef commands for provisioning.

Note: The rubygems’ bin directory may change dependent on your system. After rubygems is installed, you can check where this is by running gem environment. It will be listed in the output as EXECUTABLE DIRECTORY.

There are other possible solutions to this problem with executables. You may consider symbolically linking each executable to one of the already-working bin directories. However, such a solution may not prove effective when executables are added in the future.

Install and remove basic packages

Let’s install and remove some stuff with apt. You may want to customize a bit here. For instance, I doubt irb is necessary for all users, but I like to have it as part of my base boxes, no matter what. Just keep in mind that vagrant uses chef for provisioning, so for the same reason we did not choose more than OpenSSH server for software packages while installing Ubuntu, we don’t need much beyond these packages. Run the following commands:

sudo apt-get update
sudo apt-get upgrade -y
sudo apt-get remove apparmor -y
sudo apt-get install linux-headers-$(uname -r) build-essential ruby-dev libopenssl-ruby rake rubygems irb -y
sudo apt-get clean

Modify gemrc

Open up /etc/gemrc, which likely does not exist, and add the following line. We do this to conserve space by preventing any gem installations from adding documentation—keeping the base box as small as possible.

gem: --no-rdoc --no-ri

Install chef

Hopefully, you will be using chef solo or chef server as a provisioner for your project. Run the following to install chef [and right_aws]:

sudo gem install chef right_aws

Guest additions

This is necessary for running vagrant ssh as well as utilizing the VirtualBox folder sharing feature. Both are integral parts of vagrant. The specifics may change between versions of VirtualBox, and I am currently using version 3.1.8 r61349.

From your VirtualBox GUI (while your virtual machine is running), go to Devices and select Install Guest Additions. And then mount the drive and run the installation script (I am using the -amd64.run suffix, but if you’re working with a 32-bit installation of Ubuntu, use -x86.run):

sudo mount /media/cdrom
sudo sh /cdrom/VBoxLinuxAdditions-amd64.run

Don’t worry about the “Window System drivers” error you’ll receive. This only occurs because we chose to forego any desktop environments for a smaller box.

SSH Authentication

If you want to set up ssh for a private box, you should use your own custom keys for this section. However, if you’re distributing this as a ‘public’ box, you can use keys provided by vagrant.

mkdir ~/.ssh/
cd ~/.ssh
wget http://github.com/mitchellh/vagrant/raw/master/keys/vagrant
wget http://github.com/mitchellh/vagrant/raw/master/keys/vagrant.pub
mv vagrant.pub authorized_keys

Package and add the box

I shut down my my virtual machine for this part, although I do not know if it’s absolutely necessary. In its own folder, create and edit a file named Vagrantfile, containing:

Vagrant::Config.run do |config|
config.ssh.forwarded_port_key = "ssh"
config.vm.forward_port("ssh", 22, 2222)
end

From inside the same folder, run the following:

vagrant package --base ubuntu_9.10_64 package.box
vagrant box add ubuntu_9.10_64 package.box

The first bolded statement is what I named my virtual machine earlier. This should match whatever you named your virtual machine for the base box. The second bolded statement is what I am naming the base box when I import it into vagrant. It can be whatever you want, although being descriptive is usually smart.

Note: Technically, you can skip the Vagrantfile step. I just find it useful to set up the port forwarding for all projects. When you work with individual projects (rather than the base box), you can specify port forwarding again. This is useful if you’re running multiple vms at once, as you will not want the ports to all converge and collide at 2222,

Using your new box

Well, that’s pretty much it. Now you can use your box like any other. In a project, run vagrant init and then edit your Vagrantfile, setting config.vm.box = “ubuntu_9.10_64” or whatever you named your box.

Earlier today, I needed to move a mysql database from one server to another on EC2. The mysql data was mostly in a folder that was mounted from an attached EBS volume, so the basic move was relatively easy (just removing the attached volume and placing it on the new server).

However, the server also had several slaves. I made sure to copy the appropriate my.cnf file to the new server as well as all of the binary logs, which are used for the slaves to keep in track with the master (in layman’s terms). As such, on each slave, I had to do this:

change master to master_host='xxx.xxx.xxx.xxx', master_log_file='mysql-bin.yyyyyy', master_log_pos=z;

Obviously, the strings of x’s, y’s and z’s denote numbers that will change. The important thing here is that the switch was much easier than I’d thought it would be. I copied over the binary logs after switching off slaving on each slave. I checked the slaves to make sure they were all positioned at the same point on the binary log, and when switching their master, I specified that same log file and log position (otherwise mysql would pick something erroneous on its own). After restarting the slaves, they were caught up perfectly.

def eulers_sieve(max)
  range = (2..max).to_a
  (2..(max ** 0.5).floor).each do |n|
    next if range[n-2].nil?
    to_delete = []

    (n..(max/n).floor).each do |m|
      next if range[m-2].nil?
      to_delete << (n * m) - 2
    end

    to_delete.each do |d| { range[d] = nil }
  end
  return range.compact
end

This is a ruby-implementation of Euler’s Sieve I wrote while working on a problem from Project Euler. It’s speedy.