Lately I have posted an occasional coding challenge
and gotten responses.

This time, I thought I'd at least post my own
solution.

I'm sure someone can improve on the algorithm or
coding style or both.

Problem: Given a set of N (square) images, use a
subset of these to create a "collage" of pictures
in HTML.

Let the grid size be 8x8, but let it be reasonably
configurable.

Let image sizes be 4x4, 3x3, 2x2, and 1x1. (I assumed
64 pixels = 1 unit; and yes, I hardcoded it, and yes,
that's bad form). Let there be at least one 4x4; at
least two 3x3 if they'll fit; at least 5 2x2 if they'll
fit; and the rest 1x1.

Constraint: The edges of the pictures should
touch if possible! This depends on how well your
browser renders.

My solution prints out an ASCII version of the grid
and then outputs HTML.

A lot of the weirdness in the HTML is so that the
results will be "pretty"; and there are some specific
workarounds for IE bugs (where Konqueror rendered it
perfectly).

Comments welcome.


Cheers,
Hal


###################################

class Array

  def randomize!
    arr=self.dup
    result = arr.collect { arr.slice!(rand arr.length) }
    self.replace result
  end

end

class Range
  def rand
    self.to_a[Kernel.rand(self.size)]
  end
end

class Grid

  def initialize(pix,size)
    @pix = pix
    @size = size
    @grid = Array.new(@size)
    @grid.map! {|e| Array.new(@size) }
    @list = []
  end

  def [](x,y)
    @grid[x][y]
  end

  def []=(x,y,val)
    @grid[x][y] = val
  end

  def size
    @size
  end

  def inrange?(x,y,wide)
    (x + wide) <= @size and
    (y + wide) <= @size
  end

  def empty?(x,y,wide)
    return false if !inrange?(x,y,wide)
    x.upto(x+wide-1) do |i|
      y.upto(y+wide-1) do |j|
        return false if @grid[i][j]
      end
    end
    true
  end

  def place(x,y,wide,char)
    return false if !empty?(x,y,wide)
    x.upto(x+wide-1) do |i|
      y.upto(y+wide-1) do |j|
        @grid[i][j] = char
      end
    end
    @list << [x,y,wide]
    true
  end

  def inspect
    str = ""
    0.upto(@size-1) do |y|
      0.upto(@size-1) do |x|
        str << " #{self[x,y] || '-'}"
      end
      str << "\n"
    end
    str
  end

  def randxy(wide)
    xr = 0..(@size-wide)
    yr = 0..(@size-wide)
    [xr.rand,yr.rand]
  end

  def fit?(wide)
    0.upto(@size-wide) do |i|
      0.upto(@size-wide) do |j|
        return true if empty?(i,j,wide)
      end
    end
    false
  end

  def unused
    count = 0
    0.upto(@size-1) do |i|
      0.upto(@size-1) do |j|
        count += 1 if @grid[i][j]==nil
      end
    end
    count
  end

  def next_unused
    i = j = 0
    0.upto(@size-1) do |i|
      0.upto(@size-1) do |j|
        return [i,j] if @grid[i][j].nil?
      end
    end
    nil
  end

  def list
    @list.sort! {|x,y| x[1]*10+x[0] <=> y[1]*10+y[0] }
  end

  def rowcol
    rc = self.list.map {|x| [x[1], x[0], x[2]] }
    arr = Array.new(@size)
    arr.map! {|x| Array.new }
    rc.each {|e| arr[e[0]] << [e[1],e[2]] }
    arr
  end

  def html
    pic = -1
    puts "<html><body>"
    puts "<table border=0 cellpadding=0 cellspacing=0>"
    # Next three lines: Workaround for IE bug
    puts "<tr>"
    10.times { puts "<td><img src=white.jpg height=0 width=64
border=0></td>" }
    puts "</tr>"
    ###
    rowcol.each do |row|
      puts "<tr>"
      # Next line: Workaround for IE bug
      puts " <td><img src=white.jpg height=64 width=0 border=0></td>"
      # Note: Some of the weird formatting is so that spaces will not
      # appear between the images. This may not be an issue in some
      # browsers.
      row.each do |col,span|
        puts "<td colspan=#{span} rowspan=#{span}"
        puts "      cellpadding=0 cellspacing=0"
        puts "      align=center valign=center "
        puts "      border=0><img src=#{@pix[pic+=1]} "
        puts "                    width=#{span*64} height=#{span*64}"
        print "                   border=0></td>"
      end
      # Next line: Workaround for IE bug
      puts " <td><img src=white.jpg height=64 width=0 border=0></td>"
      puts "</tr>"
    end
    puts "</table>"
    puts "</body></html>"
  end

end

pix = %w[a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7]
pix.randomize!
pix.map! {|x| x + ".jpg" }

grid = Grid.new(pix,8)

ok = false
begin
  x,y = grid.randxy(4)
  ok = grid.place(x,y,4,"A")
end until ok


("B".."C").each do |code|
  ok = false
  begin
    if !grid.fit?(3)
      # puts "No fit! (3)"
      break
    end
    x,y = grid.randxy(3)
    ok = grid.place(x,y,3,code)
  end until ok
end



("D".."H").each do |code|
  ok = false
  begin
    if !grid.fit?(2)
      # puts "No fit! (2)"
      break
    end
    x,y = grid.randxy(2)
    ok = grid.place(x,y,2,code)
  end until ok
end


code = "a"
grid.unused.times do
  x,y = grid.next_unused
  grid.place(x,y,1,code.dup)
  code.succ!
end

p grid    # ASCII just to eyeball it...

puts

grid.html # Actual HTML

######################################