From: Yohanes Santoso <ysantoso-rubytalk@...>
Date: 2006-07-09T04:34:24+09:00
Subject: Re: Algorithm searched ...

--=-=-=

Meino Christian Cramer <Meino.Cramer@gmx.de> writes:

>  It may be that this is equivalent to the "backpacker's problem" --

This problem is known as the binary (0/1) knapsack problem.
There is a program called ``bestfit``
(http://oskarsapps.mine.nu/bestfit.html) that would find the optimal
solution.

I do not use that because I prefer similarly named files to be put in
a media. So, I wrote my own implementation (attached) that solved that
using greedy approximation. You can choose whether to group by name or
by size.

For my files, the grouping produced by the greedy approximation (both
by name or size) is about 90% close to the optimum grouping. It is      
acceptable for me. You may find it useful.


YS.



--=-=-=
Content-Type: text/x-ruby
Content-Disposition: inline; filename=bestfit.rb

#!ruby

=begin
**see how many cd80 discs needed for all files
./bestfit.rb -a -m cd80 -f size  *

**move files to various subdirs in ++isodir. each subdir is cd80 size.
./bestfit.rb -a -m cd80 -f size -i *

**use this after burning
sudo mount /cdrom; a=`ls -1 /cdrom`; a=${a%%/}; sudo umount /cdrom; echo $a; dic -c "" add $a; eject /cdrom
=end

module MediaBlockSize
  CD80 = 359800 # block, each block is 2048 bytes
  CD74 = 332800 
  DVD5 = 2297888 


  def self.collection_size_in_blocks(files, block_size=2048)
    files.inject(0) {|sum, file| sum + size_in_blocks(file, block_size)}
  end
  
  def self.size_in_blocks(file, block_size=2048)
    actual_size = FileTest.size(file)
    result = actual_size / 2048 + 1
  end
end



class GreedyFit
  attr_reader :files, :options
  def initialize(files, fit_method, media_size)
    @files = files
    @selection_method = {
      :file_size => method(:descending_file_sizes), 
      :file_name => method(:ascending_file_names)
    }[fit_method]
    @media_size = media_size
  end

  # try to fit as many into a media with block_count blocks
  def fit(block_count=@media_size)
    remaining_blocks = block_count
    file_list = []
    @selection_method.call {|file, size|
      if size > block_count 
        fail "The file: #{file} has a size larger than the media size: #{block_count} blocks"
      elsif remaining_blocks - size < 0
        next
      else
        file_list << file
        remaining_blocks -= size
        @files.delete(file)
      end
    }
    file_list
  end


  private
  # descending_file_sizes{|file, size| ....}
  def descending_file_sizes
    file_sizes = {}
    @files.each{|x|
      size = MediaBlockSize.size_in_blocks(x)
      file_sizes[size] ||= []
      file_sizes[size] << x
    }
   file_sizes.keys.sort{|x,y| -1 * (x <=> y)}.each{|size|
      file_sizes[size].each{|file|
        yield file, size
      }
    }
  end

  # ascending_file_names{|file, size| ....}
  def ascending_file_names
    @files.sort_by{|x| x.downcase}.each{|file|
      yield file, MediaBlockSize.size_in_blocks(file)
    }
  end
end



require 'optparse'
require 'ostruct'
require 'fileutils'
require 'time'
class Main
  attr_reader :discs
  def initialize(args)
    @options = init_options(args)
    files = init_files(args)
    fitter = GreedyFit.new(files, @options.fit_method, @options.media_size)
    @discs = find_fit(fitter)
  end

  def run
    if @options.move_into_dirs 
      move_files
    else
      print_out
    end
  end

  def move_files
    @discs.each_with_index{|file_list, i|
      output_disc_content(i)
      dir = "++isodir/#{Time.now.iso8601}-#{i}"
      begin FileUtils.mkdir_p(dir) rescue Errno::EEXIST end
      FileUtils.mv(file_list, dir)
    }
  end
  
  def print_out
    @discs.each_with_index{|file_list, i|
      output_disc_content(i)
    }
  end

  
    

  def output_disc_content(disc_index)
    content = @discs[disc_index]
    if @options.verbose
      col_size = MediaBlockSize.collection_size_in_blocks(content)
      media_size = @options.media_size
      $stderr.puts "-"*80
      $stderr.puts "Disc: #{disc_index}. Usage allocation: #{col_size}/#{media_size} (#{"%.2f"%(100.0*col_size/media_size)}%)"
    end
    if @options.null_separated_name 
      puts content.join("\0")
    else
      puts content.join("\n")
    end
  end
  
  private
  def find_fit(fitter)
    discs = []
    while not (file_list = fitter.fit).empty?
      discs << file_list
      if not @options.all_files
        break
      end
    end
    discs
  end

  def init_files(args)
    args.select{|x| FileTest.file?(x)}
  end

  def init_options(args)
    options = OpenStruct.new
    options.fit_method = :file_size
    options.media_size = MediaBlockSize::DVD5
    options.verbose = true
    options.all_files = false
    options.null_separated_name = false
    options.move_into_dirs = false

    opts = OptionParser.new do |opts|
      opts.banner = "Usage: #{$0} [options]"
      opts.separator ""
      opts.separator "Specific options:"
      
      opts.on("-a", "--all-files", "Fit all files into many medium. Default: only fit enough for one media.") do |t|
        options.all_files = true
      end

      opts.on("-i", "--iso-dir", "Move files into directories suitable for burning. Implies -a. Default: just print out file listing.") do |t|
        options.move_into_dirs = true
        options.all_files = true
      end

      opts.on("-m", "--media [TYPE]", [:cd80, :cd74, :dvd5],
              "Select media size (cd80, cd74, dvd5). Default: dvd5") do |t|
        t = t.to_s.upcase
        options.media_size = MediaBlockSize.const_get(t)
      end
      
      opts.on("-f", "--fit [TYPE]", [:name, :size],
              "Fitment method (name, size). Default: size") do |t|
        options.fit_method = ("file_"+t.to_s).intern # :file_size or :file_name
      end

      opts.on("-0", "Separate file names with NUL char. Default: with \\n") do |t|
        options.null_separated_name = true
      end

      # Boolean switch.
      opts.on("-v", "--[no-]verbose", "Run verbosely. Default: true") do |v|
        options.verbose = v
      end
      
      opts.on_tail("-h", "--help", "Show this message") do
        $stderr.puts opts
        exit
      end
    end
    opts.parse!(args)
    options
  end
end


if __FILE__ == $0
  Main.new(ARGV).run
end

--=-=-=--