An algorithm that simulates a quad tree to group similar values on a grid

quadtree.rb

def printTree tree
  puts tree.map{|a|a.map{|b|(b[0] != 0 ? b[1] : '.')}.join}.join("\n")
end

def createTree str
  # split up the grid and give node each value a scale of 1
  # 2^(n-1) will represent dimension of a node, so scale 1 is size 1x1, 3 is 4x4..
  grid = str.split("\n").map{|a|a.chars.map{|b|[1,b]}}
  size = [grid.length, grid[0].length].max

  greatestDimension = [grid.length, grid.map(&:length).max].max
  # get the next greatest power of 2
  depth = [(Math.log(greatestDimension) / Math.log(2)).ceil, 6].min

  # start at 2nd depth (we aren't merging halves)
  2.upto(depth) do |i|
    # pow is used for finding the next potential parent
    pow = 2**(i-1)
    # pow2 is used for comparing adjacent children
    pow2 = 2**(i-2)

    0.step(size-1, pow) do |y|
      0.step(size-1, pow) do |x|

        begin
          cell = grid[y][x]
        rescue
          # the row doesn't exist
          next
        end

        # the cell doesn't exist
        next unless cell

        value = cell[1]
        currDepth = cell[0]

        # ignore if it's not at the depth we're comparing (it's too small to merge)
        next if currDepth != i - 1

        merge = true
        
        # check all 4 children to see if they are the appropriate resolution and same value
        (0...4).each do |j|
          child = grid[y + (j % 2) * pow2][x + (j/2) * pow2]

          if !child || child[1] != value || child[0] != currDepth
            merge = false
            break
          end
        end

        # make all the children but the top left empty
        if merge
          (0...4).each do |j|
            grid[y + (j % 2) * pow2][x + (j/2) * pow2] = [0]
          end

          # top left keeps value and has a new size
          grid[y][x] = [i, value]
        end

      end
    end
  end

  printTree grid
  return grid
end

createTree """
00001101
00001011
00001100
00001100
11110011
11110011
00000011
00000011
""".strip


"""
It will print this out:
0...1101
....1011
....1.0.
........
1.1.0.1.
........
0.0.0.1.
........
"""