# Subset Counter
# 
# Finds how many subsets within a set satisfy the condition
#
# "The first n-1 elements sum to the nth element"
#
# Does so by:
#
# 1. Reading in set s.
# 2. Generating all subsets of set s. (writes them out at this point)
# 3. Iterating over all subsets, storing results. (writes found sets to file)
# 4. Displays number of matching subsets found.
#
# The means of generating all subsets is:
#
# Count from 0 to 2^size of set s, and use the bits of each number to 
# determine set population. 
#
# For example,"001000110" would include 3 elements of a set with 9 members. 
# The next umber would be "001000111" and would include a set of 4 elements,
# the successive set. All of these are saved for ease of recalculation in the
# chance that something goes wrong during the counting step.
#
# 
# Written because the people at Greplin put a programming problem up on their
# website, by Wyatt Carss, on Sunday October 10th, 2010. (10/10/10 woo)
#
# If you have any questions or comments (particularly, a better algorithm that
# doesn't require 2^sizeof(s) * sizeof(s) steps would be pretty cool.
#
# Thanks for reading!
#



# Reads integers from a file of the format "1, 2, 3, 4, 5"
# 
def get_whole_set_from(filename)
  f = File.open("test_subs")

  g = f.gets
  f.close

  g[g.size-1] = ""
  elements = g.split(',').map {|e| e.to_i }
end


# Utility function which accompanies 'to_binary'
#
def convert_small_binary(num)
  if num.class == Fixnum then
    if num < 0 or num > 1 then
      "error"
    else
      num.to_s
    end
  end
end


# Converts a given number to binary.
#
def to_binary(num)
  str = ""

  if num < 2 then
    convert_small_binary(num)
  else
    str += to_binary(num/2).to_s
    str += convert_small_binary(num - (num/2 * 2))
  end
end


# Pads a number to a specific length by stuffing leading 0's
#
# somewhat obviously, returns the number as a string.
#
def pad(num, length)
  while num.to_s.length < length do 
    num = "0" + num.to_s
  end

  #print "Padded num is #{num}"
  num
end


# Returns bit i of a num of length length
#
def get_bit(i, num, length=num.to_s.size)
  # This value is padded out to a given size by supplying leading zeroes.
  bit_value = pad(to_binary(num), length)[i].to_i - 0x30
  
  # What the heck is going on there?
  #
  # A given number is converted to binary in "to_binary(num)", and it is
  # padded out to a specified length by "pad(num, length)", which returns
  # a string-representation of the number.
  #
  # We then index position i of that string, and subtract hex-30, yielding
  # the literal value 1 or 0 for that number.
  #
  # Note that 'bit i' is i spots into a bitstring of the /length specified/.
  #
  
  #puts ", and a is #{bit_value}"

  bit_value
end

# Given a sorted array of integers representing a set, calculates
# all 2^elements.size subsets for it.
# 
def generate_subsets_out_of(elements)
  subsetlist = []

  for num in 0 .. (2**elements.size)-1 do
    subset = []

    elements.each_index do |i|
      if get_bit(i, num, elements.size) == 1 then
        subset << elements[i]
      end
    end

    subsetlist << subset
    puts "number #{num} yields subset #{subset}"
  end

  subsetlist
end


# Given an array of sets of sorted, ascending ints, calculates 
# how many of those sets satisfy the condition:
#
# "The first n-1 elements sum to the nth element"
#
# Then returns an array of all matching sets.
#
def count_sets_in(subsetlist)
  count = 0
  list_tracker = 0
  found_list = []

  subsetlist.each do |subset|
    sum = 0

    subset.each_with_index do |e, i|
      if i == subset.size-1 then
        if sum == e then
          count += 1
	  puts "Subset #{list_tracker} is in."
	  found_list << subset
        else
	  puts "Subset #{list_tracker} is out."
        end
      else
        sum += e
      end
    end

    list_tracker += 1
  end

  found_list
end


# Writes an array of arrays of numbers to a file.
#
# ex. [[1, 2, 3, 5], [1], [2, 5], [3, 6]]
#
# file 'output':
#
# 1 2 3 5
# 1
# 2 5
# 3 6
#
def write_out(list_of_numbers, outputfile="output")
  f = File.open(outputfile, "w")

  list_of_numbers.each do |list|
    list.each do |element|
      f.print "#{element} "
    end
    f.print "\n"
  end

  f.close()
end


# Filenames for this run
filename = "test_subs"
outfile = "test_big"
resultsfile = "test_results"

# Generate a list of all subsets for a given (sorted, ascending) set, then
# find all subsets for which the first n-l elements sum to the nth element.

whole_set = get_whole_set_from filename

all_subsets = generate_subsets_out_of whole_set
write_out all_subsets, outfile 

found_list = count_sets_in all_subsets 
write_out found_list, resultsfile 

puts "I found #{found_list.size} subsets!"