# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1430500327 18000
# Node ID b71457723bed41c6b4b5516b3b1e868df5cde8df
# Parent  129caa02df95d3a4b57d2ef1c295a8be572d17f5
Added the two sum problem and a solution in Perl.

diff -r 129caa02df95 -r b71457723bed two_sum/nums1
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/two_sum/nums1	Fri May 01 12:12:07 2015 -0500
@@ -0,0 +1,10 @@
+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
diff -r 129caa02df95 -r b71457723bed two_sum/nums2
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/two_sum/nums2	Fri May 01 12:12:07 2015 -0500
@@ -0,0 +1,10 @@
+9
+8
+7
+6
+5
+4
+3
+2
+1
+0
diff -r 129caa02df95 -r b71457723bed two_sum/two_sum.pl
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/two_sum/two_sum.pl	Fri May 01 12:12:07 2015 -0500
@@ -0,0 +1,39 @@
+#!/bin/env perl
+
+use strict;
+use warnings;
+use Data::Dumper;
+
+# Problem: given an input array of numbers, and a target value, find two numbers
+# in the input which sum to the target value.  Do so with worst case performance
+# of O(N).
+
+# Solution: add the input numbers to a hash as they are read, with the number
+# as the hash key, and it's index position in the input as the hash value.
+
+# At each step we can do an O(1) lookup in the hash to see if target - num has
+# already been added to the hash.  If it has, we terminate processing and print
+# the two numbers (along with their indices).  Otherwise we add num to the hash
+# and loop back to read the next input number.
+
+# Usage: Pass the target value as a command line option, and the number array as
+# values on stdin, one item per line.
+
+my $target = $ARGV[0];
+my $lookfor;
+my $num;
+my $i = 0;
+my %h;
+while (<STDIN>) {
+    $num = $_;
+    chomp($num);
+    $lookfor = $target - $num;
+    if ( exists $h{$lookfor} ) {
+        print "$num $lookfor (indices $i, ".$h{$lookfor}.")\n";
+        exit(0);
+    }
+    $h{$num} = $i;
+    $i++;
+}
+exit(1);
+