public
Last active

[05/10/13] Challenge #122 [Hard] Subset Sum Insanity

  • Download Gist
challenge_input.txt
1 2
8 8 8
-7 0 -10 -4 -1 -9 4 3 -9 -1 2 4 -6 3 3 -9 9 0 -7 3 -7 -10 -9 4 -6 1 5 -1 -8 9 1 -9 6 -1 1 -8 -6 -5 -3 5 10 6 -1 2 -2 -7 4 -4 5 2 -10 -8 9 7 7 9 -7 2 2 9 2 6 6 -3 8 -4 -6 0 -2 -8 6 3 8 10 -5 8 8 8 8 0 -1 4 -5 9 -7 -10 1 -7 6 1 -10 8 8 -8 -9 6 -3 -3 -9 1 4 -9 2 5 -2 -10 8 3 3 -1 0 -2 4 -5 -2 8 -8 9 2 7 9 -10 4 9 10 -6 5 -3 -5 5 1 -1 -3 2 3 2 -8 -9 10 4 10 -4 2 -5 0 -4 4 6 -1 9 1 3 -7 6 -3 -3 -9 6 10 8 -3 -5 5 2 6 -1 2 5 10 1 -3 3 -10 6 -6 9 -3 -9 9 -10 6 7 7 10 -6 0 6 8 -10 6 4 -4 -1 7 4 -9 -3 -10 0 -6 7 10 1 -9 1 9 5 7 -2 9 -8 10 -8 -7 0 -10 -7 5 3 2 0 0 -1 10 3 3 -7 8 7 5 9 -7 3 10 7 10 0 -10 10 7 5 6 -6 6 -9 -1 -8 9 -2 8 -7 -6 -8 5 -2 1 -9 -8 2 9 -9 3 3 -8 1 -3 9 1 3 6 -6 9 -2 5 8 2 -6 -9 -9 1 1 -9 5 -4 -9 6 -10 10 -1 8 -2 -6 8 -9 9 0 8 0 4 8 -7 -9 5 -4 0 -9 -8 2 -1 5 -6 -5 5 9 -8 3 8 -3 -1 -10 10 -9 -10 3 -1 1 -1 5 -7 -8 -5 -10 1 7 -3 -6 5 5 2 6 3 -8 9 1 -5 8 5 1 4 -8 7 1 3 -5 10 -9 -2 4 -5 -7 8 8 -8 -7 9 1 6 6 3 4 5 6 -3 -7 2 -2 7 -1 2 2 2 5 10 0 9 6 10 -4 9 7 -10 -9 -6 0 -1 9 -3 -9 -7 0 8 -5 -7 -10 10 4 4 7 3 -5 3 7 6 3 -1 9 -5 4 -9 -8 -2 7 10 -1 -10 -10 -3 4 -7 5 -5 -3 9 7 -3 10 -8 -9 3 9 3 10 -10 -8 6 0 0 8 1 -7 -8 -6 7 8 -1 -4 0 -1 1 -4 4 9 0 1 -6 -5 2 5 -1 2 7 -8 5 -7 7 -7 9 -8 -10 -4 10 6 -1 -4 -5 0 -2 -3 1 -1 -3 4 -4 -6 4 5 7 5 -6 -6 4 -10 -3 -4 -4 -2 6 0 1 2 1 -7
main.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
$sumToCheck = 0
$inputFileName = "challenge_input.txt"
$results = Array.new()
 
def terminate(condition)
if condition
puts "Invalid Input."
exit
end
end
 
 
inputStuff = Array.new()
inputFile = File.new($inputFileName)
inputFile.each_line {|line| inputStuff << line}
terminate(inputStuff.length != 2)
 
dimensions = inputStuff[0]
dimensions = dimensions.split
terminate(dimensions.length != 3)
 
U = dimensions[0].to_i
V = dimensions[1].to_i
W = dimensions[2].to_i
 
 
numInput = inputStuff[1]
numInput = numInput.split
terminate(numInput.length != (U*V*W))
 
matrix = Array.new(U) { Array.new(V) { Array.new(W) }}
numInput.each_index { |x|
matrix[x % U][(((x - (x % U)) / U) % V)][((x - (x % (U*V))) / (U*V))] = numInput[x].to_i
}
 
#takes a line from the matrix as input and updates the results array if an appropriate subsum exists
def checkSum(sumArray)
checkRange = 1
while checkRange <= sumArray.length
i = 0
while i < sumArray.length - checkRange
sum = 0
j = 0
while j <= checkRange
sum += sumArray[(i+j)]
j += 1
end
if sum == $sumToCheck
newResult = Array.new()
k = 0
while k <= checkRange
newResult << sumArray[(i+k)]
k += 1
end
$results << newResult
end
i += 1
end
checkRange += 1
end
end
 
##Check individual values:
numInput.each{|x| $results << [x.to_i] unless x.to_i != 0}
 
## Check all X-dim lines:
j = 0
while j < V
k = 0
while k < W
subsum = Array.new()
i = 0
while i < U
subsum << matrix[i][j][k]
i += 1
end
#execute function on here subsum to check for matches
checkSum(subsum)
k += 1
end
j += 1
end
 
## Check all Y-dim lines:
j = 0
while j < U
k = 0
while k < W
subsum = Array.new()
i = 0
while i < V
subsum << matrix[j][i][k]
i += 1
end
#execute function on here subsum to check for matches
checkSum(subsum)
k += 1
end
j += 1
end
 
## Check all Z-dim lines:
j = 0
while j < U
k = 0
while k < V
subsum = Array.new()
i = 0
while i < W
subsum << matrix[j][k][i]
i += 1
end
#execute function on here subsum to check for matches
checkSum(subsum)
k += 1
end
j += 1
end
 
#print results
if $results.length == 0
puts "No subsets sum to #{$sumToCheck}"
else
$results.each do |x|
x.each {|y| print y, " "}
puts''
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.