One of my favorite classic programming exercises is the Subset Sum problem. I'm (trying) to learn Ada and it's the first thing I wanted to implement, even before a Hello World.
The Subset Sum problem aims to find within a set of numbers, if a specified sum can be found by combining any number of elements from the set. For example, {2, 8, 4}
has subset sums of 2
, 8
, 4
, 10
(2+8), 6
(2+4), 12
(8+4), and 14
(2+8+4). The goal of this algorithm is to feed it a set and a sum and determine if the sum is a subset sum or not.
Here's my code:
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Command_line; use Ada.Command_Line;
procedure Subset_Sum is
-- a set of numbers to find subset sum on
type Set is array(0..4) of Integer;
Arr : Set;
-- find if subset sum exists in a set
-- @param Arr - the set to check
-- @param S - the sum to check against Arr
-- @param N - for iteration; equals Arr.length
-- @returns - truth value on whether subset sum exists
function Find_Subset (Arr : in Set; S, N : in Integer) return Boolean is
begin
-- a sum of zero is always possible
if S = 0 then
return True;
-- base case, if surpassed all elements of Set
elsif N = 0 then
return False;
end if;
-- if last is bigger than sum, ignore and go deeper
if (Arr(N-1)) > S then
return Find_Subset(Arr, S, N-1);
end if;
-- check including the last
-- and excluding the last
return Find_Subset(Arr, S, N-1)
or else Find_Subset(Arr, S-Arr(N-1), N-1);
end Find_Subset;
-- verifies arguments are correct before continuing
-- @returns - truth value on whether args valid
function Verify_Args return Boolean is
begin
-- only six arguments allowed
-- one for sum, five for set
if Argument_Count /= 6 then
-- instruct user how to use args
Put("Invalid arguments."); New_Line;
Put("Use arguments '<arg1> <args2>'."); New_Line;
Put("<arg1> is the sum to find, <args2> is space delimited list of 5 numbers.");
return False;
end if;
return True;
end Verify_Args;
begin
-- if valid arguments
if Verify_Args then
Put("{");
-- populate Arr with arguments
for i in 0..4 loop
Arr(i) := Integer'value(Argument(i+2));
Put(Integer'Image(Arr(i)));
if i /= 4 then
Put(", ");
end if;
end loop;
Put("} ");
-- determine if a subset sum exists
if Find_Subset(Arr, Integer'Value(Argument(1)), Arr'Length) = False then
Put("does not contain subset sum " & Argument(1));
else
Put("contains subset sum " & Argument(1));
end if;
end if;
end Subset_Sum;
You can run the code like so:
# save as subset_sum.adb
$ gnatmake subset_sum.adb -o sss
$ ./sss <arg1> <args2>
# <arg1> is the sum to find
# <args2> is space delimited list of numbers of size 5
# eg. ./sss 12 2 8 4 1 5
An example execution and output:
$ ./sss 11 2 8 4 9 1
$ {2, 8, 4, 9, 1} contains subset sum 11
This is the naive approach. In my experience, Subset Sum Problem is studied as part of a unit on dynamic programming. My next step is to implement that but in the interim I wanted to get the handle of Ada.
or
withor else
? If that still compiles, it will make your code a bit faster. Theor
operator always evaluates both of its operands. The same would apply toand
being replaced withand then
, if your code contained it. \$\endgroup\$false
? \$\endgroup\$Arr'Length) = False then -- ' fix highlighting on Stack Overflow
. I've done that regularly when I wrote Perl code, which also confuses most editors. \$\endgroup\$(5, 5, 3, 2, 1)
); and even then, doesn’t it only check consecutive subsequences? \$\endgroup\$