Commit c7ffa03

@@ -35,37 +35,37 @@ DOC
 
 describe "triplet sum" do
   def triplet_sum(target, items)
-    sorted = items.sort
+    sorted = items.sort.find_all { |x| x < target }
     head = 0
     tail = sorted.size - 1
 
-    until head == sorted.size || head == tail
-      result = (sorted[head] + sorted[tail] + sorted[head + 1])
-      return true if target == result
-
-      result = (sorted[head] + sorted[tail] + sorted[tail - 1])
-      return true if target == result
-
-      head += 1 if result > target
-      tail -= 1 if result < target
+    until head == sorted.size || head == tail || head + 1 == tail || tail < 0
+      if sorted[tail] > target
+        tail -= 1
+        next
+      end
+      result = sorted[head] + sorted[head + 1] + sorted[tail]
+      return true if result == target
+      if result > target
+        tail -= 1
+      else
+        head += 1
+      end
     end
-
     false
   end
 
   def triplet_sum(target, items)
     sorted = items.sort
-    head = 0
-    tail = items.size - 1
-
-    until head == sorted.size || head == tail || tail < 0
-      result = sorted[head] + sorted[head + 1] + sorted[tail]
-      return true if result == target
-
-      if result > target
-        tail =- 1
-      else
-        head += 1
+    n = sorted.size
+    n.times do |i|
+      head = sorted[i]
+      (i+1).upto(n - 1) do |j|
+        middle = sorted[j]
+        (j+1).upto(n - 1) do |k|
+          tail = sorted[k]
+          return true if target == head + middle + tail
+        end
       end
     end
     false
@@ -87,6 +87,7 @@ describe "triplet sum" do
     [468, [335, 501, 170, 725, 479, 359, 963, 465, 706, 146, 282, 828, 962, 492, 996, 943, 828, 437, 392, 605, 903, 154, 293, 383, 422, 717, 719, 896, 448, 727, 772, 539, 870, 913, 668, 300, 36, 895, 704, 812, 323, 334], false],
     [165, [142, 712, 254, 869, 548, 645, 663, 758, 38, 860, 724, 742, 530, 779, 317, 36, 191, 843, 289, 107, 41, 943, 265, 649, 447, 806, 891, 730, 371, 351, 7, 102, 394, 549, 630, 624, 85, 955, 757, 841, 967, 377, 932, 309, 945, 440, 627, 324, 538, 539, 119, 83, 930, 542, 834, 116, 640, 659, 705, 931, 978, 307, 674, 387, 22, 746, 925, 73, 271, 830, 778, 574, 98, 513], true],
     [1291, [162, 637, 356, 768, 656, 575, 32, 53, 351, 151, 942, 725, 967, 431, 108, 192, 8, 338, 458, 288, 754, 384, 946, 910, 210, 759, 222, 589, 423, 947, 507, 31, 414, 169, 901, 592, 763, 656, 411, 360, 625, 538, 549, 484, 596, 42, 603, 351, 292, 837, 375, 21, 597, 22, 349, 200, 669, 485, 282, 735, 54, 1000, 419, 939, 901, 789, 128, 468, 729, 894, 649, 484, 808, 422, 311, 618, 814, 515, 310, 617, 936, 452, 601, 250, 520, 557, 799, 304, 225, 9, 845, 610, 990, 703, 196, 486, 94, 344, 524, 588, 315, 504, 449, 201, 459, 619, 581, 797, 799, 282, 590, 799, 10, 158, 473, 623, 539, 293, 39, 180, 191, 658, 959, 192, 816, 889, 157, 512, 203, 635, 273, 56, 329, 647, 363, 887, 876, 434, 870, 143, 845, 417, 882, 999, 323, 652, 22, 700, 558, 477, 893, 390, 76, 713, 601, 511, 4, 870, 862, 689, 402, 790, 256, 424, 3, 586, 183, 286, 89, 427, 618, 758, 833, 933, 170, 155, 722, 190, 977, 330, 369, 693, 426, 556, 435, 550, 442], true],
+    # 19, 24, 103
     [146, [61, 719, 754, 140, 424, 280, 997, 688, 530, 550, 438, 867, 950, 194, 196, 298, 417, 287, 106, 489, 283, 456, 735, 115, 702, 317, 672, 787, 264, 314, 356, 186, 54, 913, 809, 833, 946, 314, 757, 322, 559, 647, 983, 482, 145, 197, 223, 130, 162, 536, 451, 174, 467, 45, 660, 293, 440, 254, 25, 155, 511, 746, 650, 187, 314, 475, 23, 169, 19, 788, 906, 959, 392, 203, 626, 478, 415, 315, 825, 335, 875, 373, 160, 834, 71, 488, 298, 519, 178, 774, 271, 764, 669, 193, 986, 103, 481, 214, 628, 803, 100, 528, 626, 544, 925, 24, 973, 62, 182, 4, 433, 506, 594], true],
     [1032, [493, 143, 223, 287, 65, 901, 188, 361, 414, 975, 271, 171, 236, 834, 712, 761, 897, 668, 286, 551, 141, 695, 696, 625, 20, 126, 577, 695, 659, 303, 372, 467, 679, 594, 852, 485, 19, 465, 120, 153, 801, 88, 61, 927, 11, 758, 171, 316, 577, 228, 44, 759, 165, 110, 883, 87, 566, 488, 578, 475, 626, 628, 630, 929, 424, 521, 903, 963, 124, 597, 738, 262, 196, 526, 265, 261, 203, 117, 31, 327, 12, 772, 412, 548, 154, 521, 791, 925, 189, 764, 941, 852, 663, 830, 901, 714, 959, 579, 366, 8, 478, 201, 59, 440, 304, 761, 358, 325, 478, 109, 114, 888, 802, 851, 461, 429, 994, 385, 406, 541, 112, 705, 836, 357, 73, 351], true],
     [13, [1, 4, 45, 6, 10, 8], true],