Примечание: если в приведенном коде встретился незнакомы метод или класс, то найти документацию можно из терминала с помощь утилиты 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 не все в порядке, есть маленькая деталька, которую можно улучшить - жду кто первым заметит =)
