#define private public - A subset of Ruby (16 Apr 2006)

topic end
<!--
   * Set TOPICTITLE = #define private public - A subset of Ruby (16 Apr 2006)
-->

<style type="text/css">
pre {background-color:#ffeecc;}
</style>

%STARTINCLUDE%
<a name="16"></a>

---+++ [[BlogOnSoftware20060416][A subset of Ruby]] (16 Apr 2006)

A programming language which inspires an author to write something like
[[http://poignantguide.net/ruby/][why's (poignant) guide to Ruby]] 
must be truly special. So I gave in readily to the temptation to try
the language, especially since Ruby's dynamic type system and
lambda-like expressions appeal to the Lisp programmer in me.

A while ago, I blogged about the [[BlogOnSoftware20060301][subset sum problem]],
and so writing a version of that algorithm in Ruby was an obvious choice.

<pre>
<font color="#008080">$solutions</font> = <font color="#ff00ff">0</font>
<font color="#008080">$numbers</font> = []
<font color="#008080">$flags</font> = []

<font color="#a020f0">def </font><font color="#008080">find_solutions</font>(k, target_sum)
  <font color="#804040"><b>if</b></font> target_sum == <font color="#ff00ff">0</font>
    <font color="#0000ff"># found a solution!</font>
    (<font color="#ff00ff">0</font>..<font color="#008080">$numbers</font>.length).each { |<font color="#008080">i</font>| <font color="#804040"><b>if</b></font> (<font color="#008080">$flags</font>[i]) <font color="#804040"><b>then</b></font> print <font color="#008080">$numbers</font>[i], <font color="#6a5acd">&quot;</font><font color="#ff00ff"> </font><font color="#6a5acd">&quot;</font>; <font color="#804040"><b>end</b></font> }
    print <font color="#6a5acd">&quot;</font><font color="#6a5acd">\n</font><font color="#6a5acd">&quot;</font>
    <font color="#008080">$solutions</font> = <font color="#008080">$solutions</font> + <font color="#ff00ff">1</font>
  <font color="#804040"><b>else</b></font>
    <font color="#804040"><b>if</b></font> k &lt; <font color="#008080">$numbers</font>.length
      <font color="#804040"><b>if</b></font> target_sum &gt;= <font color="#008080">$numbers</font>[k]
        <font color="#008080">$flags</font>[k] = <font color="#ff00ff">true</font>
        find_solutions k+<font color="#ff00ff">1</font>, target_sum-<font color="#008080">$numbers</font>[k]
        <font color="#008080">$flags</font>[k] = <font color="#ff00ff">false</font>
      <font color="#804040"><b>end</b></font>
      find_solutions k+<font color="#ff00ff">1</font>, target_sum
    <font color="#804040"><b>end</b></font>
  <font color="#804040"><b>end</b></font>
<font color="#a020f0">end</font>

<font color="#a020f0">def </font><font color="#008080">find_subset_sum</font>(target_sum)
  print <font color="#6a5acd">&quot;</font><font color="#6a5acd">\n</font><font color="#ff00ff">Now listing all subsets which sum up to </font><font color="#6a5acd">&quot;</font>, target_sum, <font color="#6a5acd">&quot;</font><font color="#ff00ff">:</font><font color="#6a5acd">\n</font><font color="#6a5acd">&quot;</font>
  <font color="#008080">$solutions</font> = <font color="#ff00ff">0</font>
  (<font color="#ff00ff">0</font>..<font color="#008080">$numbers</font>.length()).each { |<font color="#008080">i</font>| <font color="#008080">$flags</font>[i] = <font color="#ff00ff">false</font> }
  find_solutions <font color="#ff00ff">0</font>, target_sum
  print <font color="#6a5acd">&quot;</font><font color="#ff00ff">Found </font><font color="#6a5acd">&quot;</font>, <font color="#008080">$solutions</font>, <font color="#6a5acd">&quot;</font><font color="#ff00ff"> different solutions.</font><font color="#6a5acd">\n</font><font color="#6a5acd">&quot;</font>
<font color="#a020f0">end</font>

<font color="#a020f0">def </font><font color="#008080">subset_sum_test</font>(size)
  total = <font color="#ff00ff">0</font>
  target_sum = <font color="#ff00ff">0</font>
  (<font color="#ff00ff">0</font>..size).each { |<font color="#008080">i</font>| <font color="#008080">$numbers</font>[i] = rand(<font color="#ff00ff">1000</font>); total += <font color="#008080">$numbers</font>[i]; print <font color="#008080">$numbers</font>[i], <font color="#6a5acd">&quot;</font><font color="#ff00ff"> </font><font color="#6a5acd">&quot;</font> }
  target_sum = total/<font color="#ff00ff">2</font>
  find_subset_sum target_sum
<font color="#a020f0">end</font>

subset_sum_test <font color="#ff00ff">25</font>
</pre>

Comparing this to my [[OneSpaceModeling.MacroSubsetSum][other implementations in various languages]],
this solution is shorter than the Lisp version, and roughly the same length as
the VB code I wrote. I'm pretty sure that as I learn more about Ruby I will be able
to improve quite a bit on the above na&iuml;ve code, so it will probably become
even shorter.

But even after the first few minutes of coding in this language, I'm taking
away the impression that I can produce code which looks a lot cleaner than, say,
Perl code. Well, at least cleaner than the Perl code which _I_ usually write ... :D

---

%STOPINCLUDE%

%COMMENT{type="below" nonotify="on"}%

---
to top
End of topic
Skip to action links | Back to top
You are here: Blog > BlogOnSoftware20060416

r1.2 - 29 Jan 2007 - 21:01 - ClausBrod to top
Blog