The Big Programming Thread - Page 930

x = items[0]
OPT[x['A']][x['B']][x['C']][x['D']][0] = True

for i in range(1, len(items)):
  iA, iB, iC, iD = items[i]['A'], items[i]['B'], items[i]['C'], items[i]['D']
  OPT[iA][iB][iC][iD][n] = True
  for a in range(minA, maxA):
    for b in range(minB, maxB):
      for c in range(minC, maxC):
        for d in range(minD, maxD):
          if OPT[a][b][c][d][n-1] or OPT[a-iA][b-iB][c-iC][d-iD]:
            OPT[a][b][c][d][n] = True

items = [
  { a: 0, b: 10, c: 0, d: 0 },
  { a: 0, b: -15, c: 0, d: 0 },
  { a: 0, b: -5, c: 0, d: 0 },
  { a: 5, b: 5, c: 0, d: 0 }
]
target = { a: 0, b: 5, c: 0, d: 0 }

def solve(items, target)
    # check if any single one can solve it
  results = items.select { |item| item == target }

  # if we found any matches, we can just return them
  if results.any?
    puts results.inspect
    return
  end
  
  # otherwise we have to do the hard work
  return parse(items, target)
end

def parse(items, target)
  min = 0
  max = items.length
  result = []
  
  (min..max - 1).each do |x|
    (1..max - x).each do |y|
      chosen = items.slice(x, y)
      intermediate = total(chosen)
      
      if intermediate == target
        result = chosen if result.empty? || chosen.length < result.length
      end
      
      if y > 2
        (1..y).each do |sub_x|
          (1..y - sub_x).each do |sub_y|
            chosen_skip = [chosen[0]] + chosen.slice(sub_x, sub_y)
              intermediate = total(chosen_skip)
              
              if intermediate == target
                result = chosen_skip if result.empty? || chosen_skip.length < result.length
              end
          end
        end
      end
    end
  end
  
  result
end

def total(items)
  items.inject({ a: 0, b: 0, c: 0, d: 0 }) { |result, item|
    item.each do |key, value|
      result[key] += value
    end

    result 
  }
end

puts solve(items, target).inspect

@items = [
  { a: 0, b: 10, c: 0, d: 0 },
  { a: 0, b: -15, c: 0, d: 0 },
  { a: 0, b: -5, c: 0, d: 0 },
  { a: 5, b: 0, c: 0, d: 0 },
  { a: 2, b: 0, c: 0, d: 0 },
  { a: 1, b: 2, c: -5, d: -128 },
  { a: -1, b: 3, c: 5, d: 128 }
]
@target = { a: 0, b: 5, c: 0, d: 0 }
@results = []

def solve
  # check if any single one can solve it
  @results = @items.select { |item| item == @target }

  # if we found any matches, we can just return them
  return @results if @results.any?

  # otherwise we have to do the hard work
  check_for_matches(0, 2)

  # no matches found
  return @results if @results.empty?

  # drop duplicates
  @results = @results.uniq
  
  # check for shortest
  len = @results.min { |x, y| x.length <=> y.length }.length

  @results.select { |result| result.length == len }
end

def check_for_matches(x, y)
  return if x == @items.length

  chosen = @items.slice(x, y)
  check_result(chosen)
  check_subsequent(chosen, 2, 1) if y > 2

  return check_for_matches(x, y + 1) if y < @items.length - x

  check_for_matches(x + 1, 2)
end

def check_subsequent(chosen, x, y)
  return if x == chosen.length

  check_result([chosen[0]] + chosen.slice(x, y))
  
  return check_subsequent(chosen, x, y + 1) if x + y < chosen.length
  
  check_subsequent(chosen, x + 1, 1)
end

def check_result(chosen)
  return if total(chosen) != @target

  @results << chosen
end

def total(items)
  items.inject({ a: 0, b: 0, c: 0, d: 0 }) { |result, item|
    item.each do |key, value|
      result[key] += value
    end

    result 
  }
end

puts solve.inspect

# => 
[
  [
    { :a=>0, :b=>10, :c=>0, :d=>0 },
    { :a=>0, :b=>-5, :c=>0, :d=>0 }
  ],
  [
    { :a=>1, :b=>2, :c=>-5, :d=>-128 },
    { :a=>-1, :b=>3, :c=>5, :d=>128 }
  ]
]