Sunday, May 30, 2010

145 Puzzle

I've just started reading a blog Praxis that features programming problems to solve and shows their solutions typically in scheme. You're encouraged to submit your own solutions there to for others to look examine. The ones that come from Bonsai Code in Haskell are nothing short of amazing in their brevity.

Anyway, one I've solved is the 145 puzzle. Here's the description from Praxis ...
Form all the arithmetic expressions that consist of the digits one through nine, in order, with a plus-sign, a times-sign, or a null character interpolated between each pair of digits; for instance, 12+34*56+7*89 is a valid expression that evaluates to 2539. What number is the most frequent result of evaluating all possible arithmetic expressions formed as described above? How many times does it occur? What are the expressions that evaluate to that result?
.

So here's my solution in Ruby:


#
# Consider this math puzzle:

# Form all the arithmetic expressions that consist of the digits one through
# nine, in order, with a plus-sign, a times-sign, or a null character
# interpolated between each pair of digits; for instance, 12+34*56+7*89 is a
# valid expression that evaluates to 2539. What number is the most frequent
# result of evaluating all possible arithmetic expressions formed as
# described above? How many times does it occur? What are the expressions
# that evaluate to that result?
#
# Your task is to answer the three questions. When you are finished, you are
# welcome to read or run a suggested solution, or to post your own solution or
# discuss the exercise in the comments below.

# Multi-combination. Takes the elements to combine, a "level" (how many ways
# will we do the combination), the current multi-combination, and a block that
# we'll yield to.
def mc(elements, level, current=[], &block)
elements.each do | e |
if level == 1 then
yield current << e
else
mc(elements, level-1, current << e, &block)
end
current.pop
end
end

# Main program.
digits = ['1', '2', '3', '4', '5', '6', '7', '8', '9']

# DON'T initialize the hash with "[]" (as I initially did). You'll end up with
# the same array in every hash position.
results = Hash.new()

# Generate each multi-combination in the 8 spots (between each of the digits.
mc(['*', '+', ''], 8) do | operators |

# Initialize the string to evaluate.
eval_string = ''

# Add the digits and operators to the eval_string.
0.upto(digits.length-2) { |i| eval_string << digits[i] << operators[i] }

# Add teh final digit.
eval_string << digits.last

# Evaluate the string and save the result in the hash. Create a new array
# if one doesn't exist at this position.
(results[eval(eval_string)] ||= []) << eval_string
end

# Get the results that occur the most times.
m = results.max { |a, b| a[1].length <=> b[1].length }

# Print out the answer.
puts "Most evaluated number = #{m[0]} Number of times evaluated = #{m[1].length} values = #{m[1]}"


Let me know if you have questions and take some time to explore Praxis and solve some of the problems yourself.

Thursday, May 27, 2010

Installing Ubuntu, Ruby, Ramaze, Sequel, Vim, and More on an HP dm3-1130us

Sorry for not posting recently. My trusty Sony VAIO passed away and I've been getting my new box, an HP dm3-1130us running Linux with all the tools that I normally use. I thought I'd document it in case anyone else needed to do it. To be honest, most of this should work on any system not just mine or even an HP. Here are the steps:
  • Create boot disks. Use the Recovery Manager.
  • Use http://unetbootin.sourceforge.net/ to create a bootable USB device.
  • Plug the USB drive in, reboot, and hit ESC (multiple times).
  • Select the USB device to boot
  • Ubuntu should load. Pick your name, language keyboard, time zone, and password (I think these are all that are asked for)
  • Install flash - sudo apt-get install flashplugin-nonfree
  • Add the following add ons to Firefox (you may have different favorites)- Colorful Tabs, Faviconize, Vimperator
  • Install Ruby 1.9 - sudo apt-get install ruby1.9.1-full (will load executable ruby1.9.1)
  • Create a symbolic link for ruby - sudo ln -s /usr/bin/ruby1.9.1 /usr/bin/ruby
    Install 7zip - sudo apt-get install p7zip
  • Install gvim - sudo apt-get install vim-gnome; Create an application launcher
  • Name-gvim Location-/usr/bin/gvim Change the icon to /usr/share/pixmaps/vim.svg
  • Install Ruby gems - sudo apt-get install rubygems1.9.1
  • Install mailit mail package for ruby - sudo gem install mailit
    Install gemcutter (A replacement for SourceForge and gethub as gem repositories) - sudo gem install gemcutter
  • Install sequel - sudo gem install sequel
  • Install sqlite3 - sudo apt-get install sqlite3 libsqlite3-dev
  • Install sqlite3-ruby gem - sudo gem install sqlite3-ruby
  • Install ramaze - sudo gem install ramaze
  • Put sequel into /usr/bin - sudo ln -s /var/lib/gems/1.9.1/bin/sequel /usr/bin
  • Put ramaze in /usr/bin - sudo ln -s /var/lib/gems/1.9.1/bin/ramaze /usr/bin
  • Add the sqlite manager to Firefox - https://addons.mozilla.org/en-US/firefox/addon/5817/
  • Download snipmate.vim - http://www.vim.org/scripts/script.php?script_id=2540
  • Unzip snipmate.zip from ~/Downloads - unzip snipMate.zip -d ~/.vim
  • Install irb *and* removed unused packages - sudo apt-get install irb1.9; sudo apt-get autoremove
  • Be able to use matchit (match ruby do/end etc.) in vim (may want to look at vim-addons for Debian/Ubuntu) - set rtp+=/usr/share/vim/addons/ (in the .vimrc file)
Vimperator is a Firefox add-on that if you use vim, you absolutely need. It makes Firefox behave like vim ("j" scrolls down, "k" scrolls up, etc.). For vim itself, you need to look at snipmate. It provides snippets (similar to TextMate I believe) and it will make your Ruby programming life much easier. The final step, for matchit, is a bit of a hack and you probably want to investigate the vim-addons tool which from my quick glance, looked like a gem type thing for vim add ons.

I'm keeping a list of everything I do system wise on this machine. I discovered that for the most part I had a ton of stuff that I wasn't using and sometimes had no idea what it was.

So, let me know if you have any questions or comments.

Wednesday, April 21, 2010

Passing Classes as Parameters

I've been playing around with genetic algorithms again and I'll post my work a bit later. But, I did realize something while I was doing it that I thought was interesting and completely makes sense, but I hadn't seen discussed anywhere before (that I remember anyway). You can actually pass Classes as parameters to methods, including initializers. Why's this interesting? It allows you to create factories and then pass those factories to other classes. Here's a very simple example, using my genetic algorithm terminology of Organisms.

# Create a basic organism.
class Organism
def speak
puts "I'm a basic organism"
end
end

# Derive an organism that modifies the speak method.
class OrganismOther < Organism
def speak
puts "I'm another organism"
end
end

# Create a "factory" that take a Class as a parameter and can
# generate organisms of that class.
class OrganismFactory
def initialize(organism_class)
@organism_class = organism_class
end

def generate_organism
@organism_class.new
end
end

if __FILE__ == $PROGRAM_NAME

# Create a basic and other factory for the two types of organisms.
organism_factory_basic = OrganismFactory.new(Organism)
organism_factory_other = OrganismFactory.new(OrganismOther)

# Generate an organism of each type.
organism = organism_factory_basic.generate_organism
organism_other = organism_factory_other.generate_organism

# Let them speak.
organism.speak
organism_other.speak
end



You can see that we create a basic Organism and then subclass it to get a slightly different organism. There's nothing too awfully interesting there. Next is the OrganismFactory where we show off our new technique. The initialize() method takes a Class as a parameter and saves it away in the @organism_class variable. We also have a method generate_organism() that will return an object of the type that was passed in. Finally, we have the main program that creates a couple of factories, one of each type, and then uses them to create objects of each type. Finally, we make sure they work by having them "speak".

Let me know if you have questions or comments on this.

Monday, March 22, 2010

Metaprogramming Ruby - Review

I wrote a review of Metaprogramming Ruby by Paolo Perrotta and much to my surprise, Slashdot published it. You can find it here. Feel free to post comments and thoughts.

Wednesday, February 17, 2010

Ruby and Simple Dynamic Programming V

I've been reading Paolo Perrotta's new book "Metaprogramming Ruby" recently and enjoying it thoroughly. In the first chapter, he talks about Monkey Patching, the ability to add methods to classes at runtime. This combined with a need recently for an iterator through an array that returns both the index and the value led me to come up with the following code:

# Open the Array class and add a new method "each_with_index".
# This will loop through the array using the each_index method
# and yeild the index and the value of the array at that index.
class Array
def each_with_index
self.each_index do | i |
yield i, self[i]
end
end
end

if __FILE__ == $PROGRAM_NAME

# Create a simple array
x = [ "hello", "world", 42, 3.14159, ["test", "an", "array"] ]

# Go through the array and print each index and value in the
# array.
x.each_with_index do | i, v |
puts "index = #{i} value = #{v}"
end


end



The code is pretty simple. We open the Arrary class, define the new method, and then close the class. There's a bit of test code after that to show that everything works as expected.

Even though I'm only through the first chapter, I can recommend Perrotta's book. It's an easy read (so far anyway) and clearly shows the concepts that it discusses. The form it takes is conversational and the narrative is that you're a programmer, new to Ruby, who is paired with a senior developer Bill. This format may not be for everyone, especially if you're looking for more "formality", but I think it works well here and it's not overdone.

Let me know if you have questions or comments.

Wednesday, February 10, 2010

Beginning a Program

A young friend (YF) of mine was having a problem with a programming assignment from a large local university (LLU) and gave me a call the other day for some help. We spent a couple of hours together going through the piece that he was having issues with and finally got everything pretty much working. This episode though showed me that we don't necessarily teach the right things in college concerning how approach a program. I thought I'd take a few posts and show how I might tackle a problem like this. Not everyone will find this way of doing things appropriate and I wouldn't use it in certain cases, but it may help some of you in some cases.

Here's the problem as given:


Assignment Details
Homework 1 - Non-GUI Tower Defender
Players start with a fixed amount of money, in less they are a returning player. In that case, they are to start with the money they ended up with, or they can start over, if they wish.

Towers:There are to be 4 types of towers. Each has a different capability - you get to decide. Each has a different price - that you decide. A player starts the game by deciding which towers they want and where they are to be put. Given that the path for Creeps is only from left to right, towers can be above, or below, the path. The player gets to decide that, and the "x-direction" for the tower location.

Since this first assignment is not graphical - only command line - the Creep path is straight from left to right. You are to use keyboard characters as your graphics to display what is happening - tower location, and Creep location.

Creeps:Creeps may move one, or more, squares, from left to right each "turn". You get to decide how big squares are. Too big, and Creeps will easily get to the base - which is on the right side of the window. Creeps start from the left side of the display window. You are to have three (3) types of Creeps. Their behavior is up to you, but just moving faster, or slower, does not qualify as a different Creep type. Each Creep is worth a different amount of money - depending on how hard they are to kill.

Statistics: You are to track the number of Creeps killed (for each Creep type), the total number of times this player has played, the total amount of money they have spent, and the total amount of money they have earned. You may choose to have additional statistics.


There are a few things here that are worth noting. First the requirements are pretty loose. You have some options for doing things how you like (this may be good or bad depending on your temperament. Second there are a couple of things that don't make sense. We have the "x-direction" for the tower location. I'm pretty sure that what's meant is the "x-position", but if I were doing this for a grade at LLU, I'd check with the prof. I checked with YF and it sounds like since the towers don't move, the x-position is what is meant.

As a first cut, I'd spend my time working on the "logistics" of the program. What do I mean by that? Well, we'll have a main program that loops getting input from a player. We're going to have to create a player, give her some money, be able to save her totals when she quits, and on initialization, we're going to have to check if she's played before and if so if she'd like to resume or start a new game.

With that out of the way, here's what I came up with (this is in Ruby, YF for LLU had to write this in Java).

# Assignment Details Homework 1 - Non-GUI Tower Defender Players start with a
# fixed amount of money, in less they are a returning player. In that case,
# they are to start with the money they ended up with, or they can start over,
# if they wish.
#
# Towers: There are to be 4 types of towers. Each has a different capability -
# you get to decide. Each has a different price - that you decide. A player
# starts the game by deciding which towers they want and where they are to be
# put. Given that the path for Creeps is only from left to right, towers can be
# above, or below, the path. The player gets to decide that, and the
# "x-direction" for the tower location.
#
# Since this first assignment is not graphical - only command line - the Creep
# path is straight from left to right. You are to use keyboard characters as
# your graphics to display what is happening - tower location, and Creep
# location.
#
# Creeps: Creeps may move one, or more, squares, from left to right each "turn".
# You get to decide how big squares are. Too big, and Creeps will easily get to
# the base - which is on the right side of the window. Creeps start from the
# left side of the display window. You are to have three (3) types of Creeps.
# Their behavior is up to you, but just moving faster, or slower, does not
# qualify as a different Creep type. Each Creep is worth a different amount of
# money - depending on how hard they are to kill.
#
# Statistics: You are to track the number of Creeps killed (for each Creep
# type), the total number of times this player has played, the total amount of
# money they have spent, and the total amount of money they have earned. You
# may choose to have additional statistics.
#

class Tower
end

class Creep
end

class Game
end

class Player

# Initialize a player.
def initialize(name)
@name = name
@dollars = 100
@file_name = "#{@name}.txt"

if File.exist?(@file_name)
print "Welcome back #{@name}. Would you like to resume(r) or start a new game(n)?"
command = gets.chomp
case command
when "r"
puts "Resuming from #{@file_name}"
File.open(@file_name, "r") do |player_file|
line = player_file.gets
if line != nil
name_f, @dollars = line.split(",")
puts "Resume: #{name_f}: Dollars" #{dollars_f}"
else
puts "Could not read line"
end
end
when "n"
puts "Starting new game"
end
end

end

# Save the players and stats to a file.
def save
player_file = File.new(@file_name, "w+")
player_file.puts "#{@name}, #{@dollars}"
player_file.close
end

# Convenience funtion to get the player and their current
# stats.
def to_s
"name: #{@name}, dollars: #{@dollars}"
end

end

if __FILE__ == $PROGRAM_NAME

# Get the player name
print "Name: "
name = gets.chomp

# Create a new player
player = Player.new(name)
puts "#{player}"

# Do forever (or until a 'q' command anyway)
while true do

# Get the command
print "Command: "
command = gets.chomp

# Check the command and execute it.
case command
when "q"
# Quit so go ahead and save the player then break out
# of the loop.
player.save
break
end
end
end



You can see that I put the requirements at the top so they're pretty much always available for checking (you obviously can't do this with really big requirements, but when you can, it's not a bad idea). There are place holders for the classes that I think we'll have, but those may change. The one that's filled out, the Player class, has just three methods. initialize(), sets the player up and checks if the do/don't already have a saved game, save() saves the players current data, and to_s() let's us print out their data in a readable format. As we go along, these may (really will) change and get refactored, but for now, they'll suffice. The main program asks the user for their name and creates a player. We then start the main loop that just gets a command (here only the quit command) and processes it. Quit simply saves the players data and breaks out of the loop which then exits.

This would probably take less than 1/2 an hour for someone who knows the language they're working in fairly well. What is does though is provide us with places to hang major pieces of the game going forward.

Let me know if you have questions or comments and look for the next edition where we'll add in a bit more functionality to the program.

Wednesday, January 20, 2010

Ruby and Simple Dynamic Programming IV

After my last post, Gregory Brown, the author of Ruby Best Practices wrote in to note that not only was eval evil, it was not ever really necessary. He suggested that the attr_r, attr_w, and attr_rw could be better implemented by using define_method, instance_variable_get, and instance_variable_set. So, as I like to do after someone smart shows me a better way of doing things, I reimplemented our last piece of code using these methods. It's really pretty straightforward so there's not much to really talk about, so here it is:

# Open the class Class and add three new access methods, access_r, access_w, access_rw.
# These are really just reimplementations for attr_reader, attr_writer, attr_accessor.
# This version will use define_method, instance_variable_get,
# and instance_variable_set to do this (based on a recommendation from Gregory Brown.
class Class

# Provide read access only. Take a list of symbols and create a
# method that will all the user to access each symbol.
def access_r(*symbols)
symbols.each do |symbol|
define_method(symbol) do
instance_variable_get("@#{symbol}")
end
end
end

# Provide write access only. Take a list of symbols and create a
# method that will all the user to write each symbol.
def access_w(*symbols)
symbols.each do |symbol|
define_method("#{symbol}=") do |val|
instance_variable_set("@#{symbol}", val)
end
end
end

# Provide read/write access. Take a list of symbols and create two
# methods that will all the user to read and write each symbol.
def access_rw(*symbols)
symbols.each do |symbol|
define_method(symbol) do
instance_variable_get("@#{symbol}")
end

define_method("#{symbol}=") do |val|
instance_variable_set("@#{symbol}", val)
end
end
end

end

if __FILE__ == $PROGRAM_NAME

# Using the new attribute accessor methods.
class Foo
access_r :bar
access_w :qux
access_rw :baz, :quux

# Since bar is read only from the outside, we'll just initialize
# it here.
def initialize(bar)
@bar = bar
end

# Since qux is write only, we'll create a method that lets us view
# it.
def show_qux
puts "qux = #{@qux}"
end

end


# Create a new foo and initialize bar (read only) with goodbye.
# Show that we can then access it.
foo = Foo.new ("goodbye")
puts "foo.bar = #{foo.bar}"


# Set and then access the two variables we set to
# read/write.
foo.baz = "hello"
puts "foo.baz = #{foo.baz}"

foo.quux = "world"
puts "foo.quux = #{foo.quux}"

# Set the write only field and then display it using the show_qux
# method.
foo.qux = "test"
foo.show_qux

# Try to access the write only field for reading. This should
# fail with an undefined method.
puts foo.qux

end



Like I said, it's all pretty straightforward. Also, here's a link to someone who's done something very similar using the same technique (there's some other good posts in there, so take some time and read a bit of it).

As always, let me know if you have questions or comments and thanks to Gregory Brown for starting me down this path.