For Crying Out Loud

http://ismerbrails.com/ :D

Redefining unary operators

Developers song by Steve Ballmer

Разбор решений для задачи про календарные промежутки

Время для разбора решений для задачи про календарные промежутки =)

Примечание: если в приведенном коде встретился незнакомы метод или класс, то найти документацию можно из терминала с помощь утилиты ri или на сайтах http://gotapi.com, http://noobkit.com. Также можно использовать http://ru.wikibooks.org/wiki/Rubyдля русскоязычной документации по часто-употребительным методам встроенных классов. 

Само задание не представляет ничего сложного. У нас есть массив со строками, представляющими разные даты. Даты могут повторяться и массив не упорядочен. Требуется выделить из этих дат непрерывные временные диапазоны (то есть найти все последовательности дат, которые идут по календарю подряд)).

Сама постановка задачи предлагает решение - убрать все повторяющиеся даты, отсортировать их и выделить в отдельные группы даты, идущие друг за другом.  

Удаление дубликатов и сортировка делаются в одну строчку: 

dates.sort!.uniq!

Теперь остается реализовать метод для разделения идущие подряд даты на группы.

Посмотрим, как реализовали этот метод участники в своих решениях:


Версия Кирилла:

date_dzn_start=[]
date_dzn_end=[]
i=0
dates.length.times do
  a=dates[i].split("-")
  d=Date.new(a[0].to_i ,a[1].to_i,a[2].to_i)
  if (d - 1).to_s != dates[i-1] then
    date_dzn_start.push(d)
  end
  if (d + 1).to_s != dates[i+1] then
    date_dzn_end.push(d)
  end
  i+=1
end
i=0

date_dzn_end.length.times do
  if(date_dzn_start[i]!=date_dzn_end[i]) then
    puts date_dzn_start[i]..date_dzn_end[i]
  else
    puts date_dzn_start[i]
  end
  i+=1
end

Каждый элемент массива сравнивается с соседними элементами, причем если текущий элемент не является следующей датой в календаре для левого элемента, или предыдущей датой - для правого, тогда мы его добавляем в массив с начальными датами диапазонов или конечными соответственно. 

Но при таком алгоритме мы делаем в два раза больше проверок, чем необходимо (предположим, что n - текущий индекс элемента массива, тогда мы должны сравнить n-элемент массива с (n-1)-элементом и (n+1)- 
элементом, но мы уже сравнивали n-элемент и (n-1)-элемент, когда (n-1) было текущим индексом).

Конечно, сам код можно сделать более рубиновым, к примеру, если не вручную поддерживать счетчик, а использовать автоматический предоставляемый методом times, и заменить условные конструкции их сокращенными формами. Вот, что получится, если учесть сказанное и заменить times более подходящими в данном случае методами each и each_with_index :

dates.each_with_index do |date, index|
  date = Date.parse(date)
  start_dates.push date if (date-1).to_s != dates[index-1]
  end_dates.push date if (date+1).to_s != dates[index+1]
end

start_dates.zip(end_dates) do |start_date, end_date|
  puts start_date == end_date ? start_date : start_date..end_date
end

Теперь перейдем к версии kaineer'a:

SEC_PER_HOUR = 3600
DAY_AND_HALF = ( 24 + 12 ) * SEC_PER_HOUR

def more_than_day( s1, s2 )
  d1 = Time.mktime( *s1.scan( /\d+/ ) )
  d2 = Time.mktime( *s2.scan( /\d+/ ) )

  ( d2 - d1 ) > DAY_AND_HALF
end

result = dates.inject( [] ) { |arr, str|
  if arr.empty? || more_than_day( arr.last.last, str )
    arr << [ str, str ]
  else
    arr.last[ 1 ] = str
  end

  arr
}.map{|arr|( arr.first )..( arr.last )}

puts result.inspect

здесь выбран правильный подход, когда каждый элемент сравнивается только с предыдущим элементом, и в зависимости от результатов проверки добавляется либо в последний временной диапазон, либо в новый. Но несмотря на это в решении все равно используется в два раза больше проверок, чем требуется, и все из-за лишних проверок на начальное состояние.

Еще пара мелких замечаний: нам не нужно при создании нового временного диапазона дважды добавлять текущий элемент и для выражения "puts object.inspect" есть альтернативный лаконичный синтаксис "p object". Ну, и опять же в этом решении не использовался класс Date, его метод parse и метод next объектов класса Date, что придало объема программе.

Устранив лишние сравнения и использовав Date.parse, мы получили довольно симпатичный вариант, хоть и не конечный:

result = dates.inject([[ Date.parse(dates.shift) ]]) do |ranges, date|
  if (date = Date.parse(date)) == ranges.last.last.next
    ranges.last[1] = date
    ranges
  else
    ranges << [date]
  end
end

p result.map {|it| "#{it.first}..#{it.last}" }

Нужно всегда выделять более универсальные алгоритмы, с целью их повторного использования. Поэтому выделим в отдельный метод Array#group_by_range разбивку на группы идущих подряд элементов:

class Array
 def group_by_range
   inject([[shift]]) do |result, it|
     result << [] unless it == result.last.last.next
     result.last << it
     result
   end
 end
end

puts dates.group_by_range.map {|it| "#{it.first}..#{it.last}"}

Этот метод потом можно будет применить к любому массиву, главное чтобы его элементы поддерживали метод next. То есть в случае с массивом dates нужно всего лишь привести его элементы к классу Date:

dates.map! {|it| Date.parse it }

Ну и напоследок пользуясь случаем приведу пример (хоть и немного притянутый за уши) использования метода Object#tap:

class Object
 def tap
   yield self; self
 end
end

Для этого мы незначительно модифицируем предыдущую версию и получим:

class Array
 def group_by_range
   inject([[shift]]) do |result, it|
     result << [] unless it == result.last.last.next
     result.tap {|array| array.last << it }
   end
 end
end

puts dates.group_by_range.map {|it| "#{it.first}..#{it.last}"}

Как видно с помощью Object#tap можно сделать несколько модификаций перед возвращением объекта из метода и тем самым немного улучшить его вид.

P.S.
Вместо последовательного использование методов uniq и sort было бы конечно лучше использовать что-то вроде sort_uniq (когда сортировка проводится с одновременным отбросом повторяющихся значений), потому что это было бы эффективнее, чем два прохода сначала для отсева повторяющихся значений, а потом сортировки. Главное то, что руби со своим набором готовых алгоритмических и дизайнерских решений позволяет быстро создать рабочий прототип
программы и учит главному правилу программирования - "откладывай оптимизацию на потом". Это позволяет проводить оптимизацию только действительно узких мест, а не всего подряд, что дает значительный прирост продуктивности разработчиков.

P.P.S.
В методе group_by_range не все в порядке, есть маленькая деталька, которую можно улучшить - жду кто первым заметит =)

Новая google-группа: Знакомство с ruby и ruby on rails

Группа создана для помощи в решении вопросов, связанных с руби и ориентирована прежде всего на начинающих, для прошаренных существует ror2ru. 

Не стесняйтесь задавать простые вопросы - помните 
"имидж ничто, жажда познания все", 
"глупых вопросов не бывает, хотя иногда бывают глупые ответы".

(from http://groups.google.com/group/learnrb/about)

Кроме того в этой группе я буду регулярно публиковать небольшие задачки разных уровней сложности. Надеюсь, это поможет осознать насколько руби может быть удобен. 

Первая простенькая задачка.

Polaroid thumbnails

Хотите быть способным преобразовывать так картинки на лету?

Я реализовал у себя в одном rails приложении генерацию подобных thumbnails при отправке пользователем картинки с помощью следующего кода:

  def after_save 
   thumbnail   = Magick::Image.read(image_path).first
   cols, rows  = thumbnail.columns, thumbnail.rows
  
   thumbnail.crop_resized!(400,300)
   thumbnail[:caption] = "\n  #{pet.breed.animal.kind}, #{pet.breed.title}, #{pet.name}\n  Cost: #{pet.price}$"
  
   thumbnail = thumbnail.polaroid(5 - rand(10)) do 
     self.gravity      = Magick::CenterGravity
     self.shadow_color = "black"
     self.align        = Magick::LeftAlign
     self.pointsize    = 30
     self.font_family  = 'comic sans ms'
   end
  
   thumbnail.change_geometry!("#{cols}x#{rows}") do |ncols, nrows, img|
     img.resize!(ncols, nrows)
   end
  
   thumbnail.resize!(200,150)
   thumbnail.write(thumbnail_path)
 end

Требуется наличие RMagick.

Примечание: делается двойной resize - до и после полароид-эффекта, для более четкого изображения.

YAML-конфиги

Поработав некоторое время с конфигурационным файлами в формате YAML, вы заметите, что встроенного простого метода для синхронизации изменений нет. Чтобы каждый раз не расписывать однородные конструкции для записи изменений, я написал маленькое расширение:

module YAML
  def self.set_connection(path)
    data = load_file(path).symbolize_keys
    class << data
      attr_accessor :path
      def sync
        File.open(@path, 'w+') { |file| file.puts(self.stringify_keys.to_yaml) }
      end
    end
    data.path = path
    data
  end
end

Заметьте, что я также автоматом применяю symbolize_keys, когда вытаскиваю данные из yaml, и stringify_keys, когда отправляю обратно изменения. Все это сделано по простой причине, что у меня на верхнем уровне конфига всегда находится хэш (со строками в качестве ключей, так как они смотрятся более органично в yaml чем символы, на моей взгляд), а в коде уже удобнее работать с символами для доступа к отдельным разделам конфига. Можно было, конечно, проверять является ли хэшем выгружаемая информация и, в случае, положительного ответа, применять эти функции, но кто захочет - сам сделает, а для моих целей этого достаточно.

Пример из скрипта, который я использую для управления рейлс приложениями:

$config = YAML.set_connection('config.yaml'.in_current_dir)
#...
mode 'config' do
  keyword('repository', 'r') do
    default $config[:repository]
    #...
  end
  
  keyword('rails_apps') do
    default $config[:rails_apps]
    #...
  end
  
  def run
    #...
    %w(repository rails_apps).each { |setting| $config[setting.to_sym] = params[setting].value }
    $config.sync 
  end
end