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

Amazing ruby

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

Одна строчка в консоли:

ruby -e "puts ENV['PATH'].split(';').sort"

(; - так как действие проиходило в windows)
и он обладатель читабельного приятного списка. Удивительно, но данный пример поразил его настолько, что он наконец признал, что в руби есть что-то очень хорошее =)))


Также сегодня перевел код знакомого из:

r = []; a.each { |x| b.each { |y| r << [x,y] } };

в

(a*b.size).zip(b*a.size)

Демонстрация,

a, b = [1,2,3], [:a, :b]
p (a*b.size).zip(b*a.size) # => [[1, :a], [2, :b], [3, :a], [1, :b], [2, :a], [3, :b]]

Интересно, потянет на http://www.novemberain.com/tags/TiaBWTDI ? =))

stderr for `cmd`

Порой, программируя на ruby, нужно получить не только стандартный вывод для консольной команды, но и перехватить сообщения об ошибках. Для этого можно прямо использовать Open3, но для простых операций можно использовать обертку:

# extensions.rb

def `(cmd)
 Open3.popen3(cmd) do |stdin, stdout, stderr|
   out, err = [stdout, stderr].map &:readlines
   {:short_out => out[0], :short_err => err[0], :out => out, :err => err, :all => out + err}
 end
end

Примечание: для того, чтобы работала сокращенная форма

[stdout, stderr].map &:readlines

Необходимо, чтобы был определен метод to_proc для Symbol:

class Symbol
 def to_proc
   Proc.new { |obj, *args| obj.send(self, *args) }
 end
end

Теперь можно работать с консольными командами следующим образом:

require 'extensions'

status = `rm non-existent-file`
p status[:short_err] # => "rm: non-existent-file: No such file or directory\n"
p status[:out]       # => []

Или сразу вытаскивать нужные потоки:

out = `rm existent-file`[:out]
err = `rm non-existent-file`[:err]
all = `rm any-file`[:all]

Или, если использовать модифицированный хэш-аксессор из предыдущего поста:

short_out, full_out = `ln -s`[:short_out, :out]
out, err = `rm any-file`[:out, :short_err]

Также есть простой способ, с помощью которого без Open3 можно получить объединенный вывод для stderr и stdout. Для этого просто нужно указать в конце системного вызова 2>&1 - то есть дописать в стандартный вывод все полученные сообщения об ошибках.
Пример:

p `rm non-existent-file 2>&1` # >> "rm: non-existent-file: No such file or directory\n"