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.