-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- The three rules of Ruby Quiz: 1. Please do not post any solutions or spoiler discussion for this quiz until 48 hours have elapsed from the time this message was sent. 2. Support Ruby Quiz by submitting ideas and responses as often as you can! Visit: http://rubyquiz.strd6.com/suggestions 3. Enjoy! Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone on Ruby Talk follow the discussion. Please reply to the original quiz message, if you can. RSS Feed: http://rubyquiz.strd6.com/quizzes.rss -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ## Plot the Shape (#211) Kvetha Rubyists, This week's quiz was submitted by Alan at http://rubyquiz.strd6.com/suggestions Somewhere on a 10x20 grid is a 10 block shape. The shape parts are all adjacent, either horizontally, vertically or diagonally. Write a simple algorithm that will list the co-ordinates of the 10 parts of the shape. Try to minimize lookups to the grid. Here is an example shape to get started (you may need to copy into a monospaced font): 0123456789ABCDEFGHIJ 0.................... 1.................... 2.........@@......... 3........@........... 4........@@@@@....... 5.............@...... 6............@....... 7.................... 8.................... 9.................... Have Fun! -- -Daniel http://rubyquiz.strd6.com P.S. Submitting quiz ideas is fun and easy. Visit http://rubyquiz.strd6.com/suggestions to find out more!

on 2009-06-26 21:31

on 2009-06-29 01:43

Hello, Here's my solution, it works also with grid with different sizes but it does not check the adjacency of the shape parts. http://github.com/sandropaganotti/Ruby-Quiz-Reposi... Sandro

on 2009-06-29 03:45

> ## Plot the Shape (#211) > > Somewhere on a 10x20 grid is a 10 block shape. The shape parts are all > adjacent, either horizontally, vertically or diagonally. > > Write a simple algorithm that will list the co-ordinates of the 10 > parts of the shape. Try to minimize lookups to the grid. Six little methods. The first two started with some simplifying assumptions: * The grid is stored in a "convenient" data-structure * The grid only contains one shape * The shape doesn't violate any of the rules The third dispenses with the convenient structure and simply brute-force scans the whole grid. The last three build on each other until the sixth iteration attempts to follow the part adjacency rules and minimize lookups (and is super-super-ugly-code :-). #!/usr/bin/env ruby $input = <<-EO .................... .................... .........@@......... ........@........... ........@@@@@....... .............@...... ............@....... .................... .................... .................... EO def foo1 # assuming the grid is stored hash-like, keyed on coordinate grid = {} $input.split.each_with_index{|line, y| line.split(//).each_with_index{|char, x| grid[[x,y]] = char } } # reject by value and return the keys grid.reject{|k,v| v != "@"}.keys end def foo2 # assuming the grid is stored hash-like, keyed on value grid = {} $input.split.each_with_index{|line, y| line.split(//).each_with_index{|char, x| (grid[char] ||= []) << [x,y] } } # return the value grid['@'] end def foo3 # grid is stored nested-array-liked, indexed by row then column grid = $input.split rows, cols, parts = grid.size, grid[0].size, [] # :-( my 'clever' duck is defeated by 1.8's String#[] rows.times{|r| cols.times{|c| parts << [c,r] if grid[r][c] == 64 }} parts end def foo4 # grid is stored nested-array-liked, indexed by row then column grid = $input.split rows, cols, parts, checked = grid.size, grid[0].size, [], {} until (parts.size == 10) # pick a random spot r, c = rand(rows), rand(cols) next if checked[[r,c]] # skip if we've already checked this one checked[[r,c]] = true next unless grid[r][c] == 64 # skip if this one isn't a part parts << [c,r] # store if it is a part end parts end def foo5 # grid is stored nested-array-liked, indexed by row then column grid = $input.split rows, cols, parts, checked = grid.size, grid[0].size, [], {} until (parts.size == 10) # pick a random spot r, c = rand(rows), rand(cols) next if checked[[r,c]] # skip if we've already checked this one checked[[r,c]] = true next unless grid[r][c] == 64 # skip if this one isn't a part parts << [c,r] # store if it is a part # check the current parts neighbors (-1..1).each do |dc| (-1..1).each do |dr| cprime = (c + dc).abs rprime = (r + dr).abs next if checked[[rprime,cprime]] # skip if we've already checked this one checked[[rprime,cprime]] = true next unless grid[rprime][cprime] == 64 # skip if this one isn't a part parts << [cprime,rprime] # store if it is a part end end end parts end def foo6 # grid is stored nested-array-liked, indexed by row then column grid = $input.split rows, cols, parts, checked = grid.size, grid[0].size, [], {} l = lambda {|r, c, parts, checked| # check the current parts neighbors (-1..1).each do |dc| (-1..1).each do |dr| cprime = (c + dc).abs rprime = (r + dr).abs next if checked[[rprime,cprime]] # skip if we've already checked this one checked[[rprime,cprime]] = true next unless grid[rprime][cprime] == 64 # skip if this one isn't a part parts << [cprime,rprime] # store if it is a part l.call(rprime, cprime, parts, checked) # recurse to check more neighbors end end } loop do # pick a random starting spot r, c = rand(rows), rand(cols) next if checked[[r,c]] # skip if we've already checked this one checked[[r,c]] = true next unless grid[r][c] == 64 # skip if this one isn't a part parts << [c,r] # store if it is a part l.call(r, c, parts, checked) break end parts end p foo1.sort p foo2.sort p foo3.sort p foo4.sort p foo5.sort p foo6.sort #(ruby 1.8.6)=> [[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4], [12, 6], [13, 5]] [[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4], [12, 6], [13, 5]] [[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4], [12, 6], [13, 5]] [[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4], [12, 6], [13, 5]] [[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4], [12, 6], [13, 5]] [[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4], [12, 6], [13, 5]]

on 2009-06-29 17:21

Here's the first solution that came to my mind. Nothing tricky or efficient really. Just gets the job done. It uses recursion to search adjacent squares so as to meet the requirement/suggestion to avoid merely doing a linear search of the whole game board (at least, that's what I read into it). This supports boards of arbitrary size and can be configured via constants to support a different maximum number of characters to search for (and specific character to search for). It assumes the board, if provided, is rectangular. http://snipt.org/kmnm (Just noticed I left in a hard-coded regex using the '@' character; otherwise this supports searching for a different character)

on 2009-06-29 21:57

My solution is in two parts: -divide and conquerer until a '@' is found -use a recursive backtracker starting from the seed coord. found in step 1. I am not positive about my worst-case analysis on lookups. -C $map = File.new(ARGV[0]).inject([]){|a,line| a << line.split("")} #vertical line m = lambda {|x| (1..10).detect{|y| $map[y][x] == '@'}} #horizontal line n = lambda {|y| (1..20).detect{|x| $map[y][x] == '@'}} #find a coordinate with an '@'; worst case 118 lookups seed = [[n.call(5),5],[n.call(6),6],[10,m.call(10)],[6,m.call(6)],[3,m.call(3)],[8,m.call(8)],\ [16,m.call(16)],[13,m.call(13)],[18,m.call(18)]].detect{|a| a[1] != nil and a[0] != nil} #recursive maze solver; worst case 80 lookups $visits = {} def m_solver(a,found) x,y = a[0],a[1] return if found >= 10 if $visits["#{y},#{x}"] == nil puts "#{x-1 > 9 ? (x-1+55).chr : (x-1)},#{y-1}" found += 1;$visits["#{y},#{x}"] = true end #vertical or horizontal m_solver([x,y-1],found) if y-1 >= 1 and $map[y-1][x] == '@' and $visits["#{y-1},#{x}"] == nil m_solver([x,y+1],found) if y+1 <= 10 and $map[y+1][x] == '@' and $visits["#{y+1},#{x}"] == nil m_solver([x-1,y],found) if x-1 >= 1 and $map[y][x-1] == '@' and $visits["#{y},#{x-1}"] == nil m_solver([x+1,y],found) if x+1 <= 20 and $map[y][x+1] == '@' and $visits["#{y},#{x+1}"] == nil #diagonal m_solver([x-1,y-1],found) if y-1 >= 1 and x-1 >= 1 and $map[y-1][x-1] == '@' and $visits["#{y-1},#{x-1}"] == nil m_solver([x-1,y+1],found) if y+1 <= 10 and x-1 >= 1 and $map[y+1][x-1] == '@' and $visits["#{y+1},#{x-1}"] == nil m_solver([x+1,y-1],found) if x+1 <= 20 and y-1 >= 1 and $map[y-1][x+1] == '@' and $visits["#{y-1},#{x+1}"] == nil m_solver([x+1,y+1],found) if x+1 <= 20 and y+1 <= 10 and $map[y+1][x+1] == '@' and $visits["#{y+1},#{x+1}"] == nil end #worst case 198 lookups m_solver(seed,0)

on 2009-07-01 18:38

Here is my solution. On average, for a 10x10 grid with a 10 sized shape, it will plot the shape in about 31.7 guesses. If you change the neighbors definition to exclude diagonals, it does it in around 24 guesses. Worst case scenario is of course the size of the grid. I spent a fair amount of effort trying to collect statistical information about the shapes I am generating, but experiments have shown that even though there is a certain amount of non-uniformity in the distribution across the board, it is not enough to gain a significant advantage in the total number of guesses (probably less than a half a guess.) --Chris # The Shape class accomplishes a couple of things. # First, it randomly generates shapes and provides some # accounting, keeping track of how many lookups one does. # Next, it acts as a kind of geometry manager for the board. # (each, each_neighbors, get_neighbors. Changing the definition # of each_neighbors can change the rules for what it means for # squares to be adjacent. # Finally, it keeps track of occupancy statistics for the board # over successive regenerations of the shape. class Shape attr_reader :h,:w,:l,:count def initialize(hh = 10, ww = 10, ll = 10) @h,@w,@l=hh,ww,ll #height,width, shape size @regens = @count = 0 #number of times shape generated, times dereferenced @stats = [] #used to count frequency of occupancy # seed the stats array with all 1s. h.times { |y| @stats[y] = [ 1 ] * w } @regens = h*w/(1.0 * l) rebuild end def each_neighbors(xxx,yyy=nil) if xxx.kind_of?( Array ) then x,y = xxx[0],xxx[1] else x,y = xxx,yyy end lowx,hix = [x-1,0].max, [x+1,w-1].min lowy,hiy = [y-1,0].max, [y+1,h-1].min (lowy..hiy).each do |yy| (lowx..hix).each do |xx| yield([xx,yy]) unless x==xx and y==yy end end end def get_neighbors(x,y=nil) result = [] each_neighbors(x,y) do |coords| result.push(coords) end return result end def each h.times { |y| w.times { |x| yield [x,y] } } end def rebuild() @regens += 1 #increment the build count @count = 0 #clear the deref count #initialize board to contain only spaces @board=[] h.times { |y| @board[y] = [" "] * w } neighbors = [] shape = [] l.times do if neighbors.length == 0 then # first piece - place it anywhere x,y = [w,h].map {|z| (rand*z).to_i} else # subsequent pieces - pick a random neighbor x,y = neighbors[ (rand * neighbors.length).to_i ] end @board[y][x] = "@" #mark occupancy @stats[y][x] += 1 #track occupancy shape |= [ [x,y] ] # add choice to list of shape coords # update neigbors neighbors -= [[x,y]] neighbors |= get_neighbors(x,y) - shape end return self end def to_s return @board.map { |x| x.join "" }.join("\n") + "\nTotal Lookups: #{@count}\n" end def [](xx,yy=nil) if xx.kind_of?(Array) then x,y = xx[0],xx[1] else x,y = xx,yy end @count += 1 return @board[y][x] end def stats norm_stats = [] h.times do |y| norm_stats[y] = [] w.times do |x| # correct stats for rotation and reflection symmetry norm_stats[y][x] = (@stats[y][x] + @stats[-y-1][x] + @stats[-y-1][-x-1] + @stats[y][-x-1] + @stats[x][y] + @stats[-x-1][y] + @stats[-x-1][-y-1] + @stats[x][-y-1])/(8.0*@regens) end end return norm_stats end def statstring return stats.map { |y| y.map { |x| "%0.3f" % x}.join(" ") }.join("\n") end end class ShapePlot def initialize(r = Shape.new, c=0) @shape = r c.times {@shape.rebuild} @stats = @shape.stats @plays = 0 @count = 0 reset end def reset @guesses = [] @members = [] @neighbors = [] @choices = [] @shape.each { |coords| @choices << coords } end def to_s board = [] @shape.each { |x,y| @shape.h.times { |y| board[y] = [ " " ] * @shape.w }} @neighbors.each { |x,y| board[y][x] = "." } @guesses.each { |x,y| board[y][x] = "x" } @members.each { |x,y| board[y][x] = "@" } header = "+" + ("-"*(@shape.w*2-1)) + "+\n" return header + "|" + board.map{|x| x.join(" ")}.join("|\n|") + "|\n" + header end def choose_random(p_list) sum = 0 #choose from among the choices, probibilistiacally, weighted by #the occupation probabilities p_list.each { |p,c| sum += p } r = rand * sum p_list.each do |p,c| r -= p return c if r <= 0 end # shouldnt ever be here, but return the last one anyway puts "BAAAAD" puts p_list puts @shape return p_list[-1][1] end def build_weighted(list) return list.map {|x| [ @stats[x[1]][x[0]], x ]} end def guess_none_known return choose_random( build_weighted( @choices ) ) end def guess_some_known choices = @neighbors - @guesses return choose_random( build_weighted( choices ) ) end def found_a_hit(coords) # update the members of the shape @members += [ coords ] x,y=coords # calculate the neigbors of the new piece @neighbors += @shape.get_neighbors(x,y) # the intersection of @members and @neighbors should be empty, but # we are subtracting out @guesses, which includes all @members when # we go to pick a choice list anyway... end def guess #choose a square to look at # if we know some part of the shape is known, restrict guesses # to neighbors of the stuff we know #if we dont know any of them yet, choose from the whole board x,y = coords = (@members.length > 0 ? guess_some_known : guess_none_known) @guesses += [coords] @choices -= [coords] if @shape[x,y]=="@" then found_a_hit(coords) end end def play( draw = false) reset # upldate statistics before we update the shape @stats = @shape.stats @shape.rebuild while @members.length < @shape.l guess puts self if draw end @plays +=1 @count += @shape.count return @shape.count end def report mean = @count / (1.0 * @plays) puts "After #{@plays} plays, the mean score is: #{mean}" end end q = ShapePlot.new q.play(true) 999.times { q.play } q.report

on 2009-07-06 00:37

There were many good solutions to this week's quiz, but Chris Howe's solution stands out as the best. Chris's solution consists of two parts: a `Shape` class that handles creating the shape and tracking lookups to the grid and a `ShapePlot` class that handles the guesses. Chris also provides a mode that draws the board as it is searched. The '@' characters represent the parts of the shape that have been discovered so far, the 'x' characters represent misses, and the '.' characters represent neighbors to the discovered shapes: the places that the program will search next. <pre> +-------------------+ | x | | | | | | | | . x x . | |x x x @ @ . | |x @ @ @ x . | |x x @ x x | | . x . x | | x | +-------------------+ </pre> As you can see the two 'x's off to the side are random choices that missed. The program continues to guess randomly a location with part of the shape is found. A piece of the shape was then discovered near the bottom left and the program began searching the neighbors of the already discovered pieces to find the rest of it. The default output of the program is to display one game in drawing mode, and then run 999 more games to generate the statistics for the average number of lookups. After 1000 plays the average number of lookups is around 31.7. Thank you Brabuhr, Chris Cacciatore, Chris Howe, Kendal Gifford, and Sandro Paganotti for your solutions this week!