screen = [
[9,9,4,7,4,8,9,9,9,9,2,5,6,7,8,9],
[1,2,3,9,9,6,7,8,9,9,9,9,9,9,9,9]
]
def find_8_9s(screen)
width = screen[0].length - 8 # no need to check if not enough #s left
(0..screen.length - 1).each do |row|
(0..width).each do |column|
return [row, column] if screen[row][column,8].all? {|pixel| pixel == 9}
end
end
false
end
find_8_9s(screen) => [1, 8]
screen[1].chunk {|pixel| pixel == 9}.each {|chunk| p chunk} =>
[false, [1, 2, 3]]
[true, [9, 9]]
[false, [6, 7, 8]]
[true, [9, 9, 9, 9, 9, 9, 9, 9]]
Refactorings
No refactoring yet !
Ants
June 28, 2011, June 28, 2011 00:13, permalink
Sounds like a string search problem. Have you looked at these for inspiration? http://en.wikipedia.org/wiki/String_searching_algorithm
Marc
June 28, 2011, June 28, 2011 00:37, permalink
screen1 = [ [9,9,4,7,4,8,9,9,9,9,2,5,6,7,8,9],
[1,2,3,9,9,6,7,8,9,9,9,9,9,9,9,9] ]
screen2 = [ [9,9,4,9,9,9,9,9,9,9,9,9,9,7,8,9],
[1,2,3,9,9,6,7,8,9,9,9,9,0,9,9,9] ]
def find_around(line, line_no, position, min_occurence, pattern, &block)
# checks current_position
return unless line[position] == pattern
# find first occurence
index = position
while(index >= 0 && line[index] == pattern) do
first = index
index -= 1
end
# find last occurence
index = position
while(index < line.length && line[index] == pattern) do
last = index
index += 1
end
yield line_no, first if(last - first >= min_occurence - 1)
end
def find_in_screen(screen, min_occurence = 8, pattern = 9)
# checks each line
screen.each_with_index do |line, line_no|
# Determine how many positions to check in each line (if there isn't a
# number 9 at position 0 and 9 than its useless to check in between)
checks = line.length / min_occurence
checks.times do |check|
position = check * min_occurence
# check around that position
find_around(line, line_no, position, min_occurence, pattern) do |l, i|
puts "Match found beginning line ##{ l } position ##{ i }"
end
end
end
end
find_in_screen(screen1) #=> Match found beginning line #1 position #8
find_in_screen(screen2) #=> Match found beginning line #0 position #3
Adam
June 28, 2011, June 28, 2011 11:23, permalink
def find_8_9s(screen)
match = screen.to_s.match(/9{8}/)
[ match.offset(0).first / screen.first.size, match.offset(0).first % screen.first.size ] if match
end
Ants
July 1, 2011, July 01, 2011 00:42, permalink
LOL! Kudos to Adam who took my "it sounds like a string search problem", and put together a solution that quite literally change the input arrays into a string and did a string search. :-)
slothbear
July 1, 2011, July 01, 2011 08:40, permalink
Thanks for all the ideas. Once I got to the array abstraction, it seemed like it could be generalized even more; string search sounds like the right idea. Marc -- lots of inspiration in your code, including the optimization of not checking every character.
And Adam, that kind of solution is why I love this site. Ideas turned inside out, then right side out again. The actual colors are numbers like -11589625, but I could reduce the array to binary (brown and not-brown). Then process as a "string". That's starting to sound like image processing again. I'm currently working with a Java BufferedImage, and thinking I should research the libraries. Hm, something called "Color Space Conversion" sounds promising. many thanks!
slothbear
July 1, 2011, July 01, 2011 08:41, permalink
Thanks for all the ideas. Once I got to the array abstraction, it seemed like it could be generalized even more; string search sounds like the right idea. Marc -- lots of inspiration in your code, including the optimization of not checking every character.
And Adam, that kind of solution is why I love this site. Ideas turned inside out, then right side out again. The actual colors are numbers like -11589625, but I could reduce the array to binary (brown and not-brown). Then process as a "string". That's starting to sound like image processing again. I'm currently working with a Java BufferedImage, and thinking I should research the libraries. Hm, something called "Color Space Conversion" sounds promising. many thanks!
Somewhere in an image, I know there is one horizontal brown line, 200 pixels long. My quest is to find it.
For the code below, I've abstracted all the image processing stuff. That reduces it to a problem of finding a sequence of consecutive values in an array. So instead of finding 200 consecutive brown pixels, this example looks for 8 consecutive 9s.
I've tried a couple of refactorings already. The best used Enumerable#chunk. But #chunk doesn't keep track of the position of each chunk. I can keep track of the position, but I felt like I was getting pretty far afield. I'm open to all ideas, including those who want to yell at my midstream return.