Получите самый длинный префикс в массивах Ruby

Question

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

m = [
  ["A", "97455589955", "97455589920", "97455589921"],
  ["B", "2348045101518", "2348090001559"]
]

Я ожидаю вывод, подобный следующему:

n = [
  ["A", "974555899"],
  ["B", "2348045101518", "2348090001559"]
]

Для первого подмассива в m самый длинный префикс равен "974555899" длины девять.

974555899-55
974555899-20
974555899-21

Для второго подмассива самый длинный префикс - "23480" длины пять, и он меньше восьми.В этом случае второй подмассив остается без изменений.

23480-45101518
23480-90001559

Для этого ввода:

m = [
  ["A", "2491250873330", "249111222333", "2491250872214", "2491250872213"],
  ["B", "221709900000"],
  ["C", "6590247968", "6590247969", "6598540040", "65985400217"]
]

Вывод должен быть таким:

[
  ["A", "2491250873330", "249111222333", "249125087221"],
  ["B", "221709900000"],
  ["C", "659024796", "65985400"]
]

Для array m[0] между его четырьмя числами нет достаточно длинного префикса, но есть префикс 249125087221 длиной двенадцать между m[0][2] и m[0][3].Для array m[2] существует префикс "659024796" длины девять между m[2][0] и m[2][1], и есть другой префикс "65985400" длины восемь между m[2][2] и m[2][3].

Iпостроил код ниже:

m.map{|x, *y|
  [x, y.map{|z| z[0..7]}.uniq].flatten
}

С моим кодом с первым вводом, я получаю этот вывод.

[
  ["A", "97455589"],
  ["B", "23480451", "23480900"]
]

Я застрял на том, как динамически получить общий префикс без установкификсированная длина.

Answer 1

Код

def doit(arr, min_common_length)
  arr.map do |label, *values|
    [label, values.group_by { |s| s[0, min_common_length] }.
      map { |_,a| a.first[0, nbr_common_digits(a, min_common_length)] }]
  end
end

def nbr_common_digits(a, min_common_length)
  max_digits = a.map(&:size).min
  return max_digits if max_digits == min_common_length + 1
  (min_common_length..max_digits).find { |i|
    a.map { |s| s[i] }.uniq.size > 1 } || max_digits
end

Пример

arr = [["A","2491250873330","249111222333","2491250872214","2491250872213"],
       ["B","221709900000"],
       ["C","6590247968","6590247969","6598540040","65985400217"]]

doit(arr, 8)
  #=> [["A", ["249125087", "249111222333"]],
  #    ["B", ["221709900000"]],
  #    ["C", ["659024796", "65985400"]]]

Объяснение

Давайте сначаларассмотрим вспомогательный метод, nbr_common_digits.Предположим, что

a = ["123467", "12345", "1234789"]
min_common_length = 2

, тогда шаги следующие:

max_digits = a.map(&:size).min
  #=> 5 (the length of "12345")
max_digits == min_common_length + 1
  #=> 5 == 2 + 1
  #=> false, so do not return max_digits
b = (min_common_length..max_digits).find { |i| a.map { |s| s[i] }.uniq.size > 1 }
  #=> (2..5).find { |i| a.map { |s| s[i] }.uniq.size > 1 }
  #=> 4

На этом этапе мы должны рассмотреть возможность того, что b будет равно nil, что происходит, когда первый 5 символов всех строк равны.В этом случае мы должны вернуть max_digits, поэтому нам требуется следующее.

b || max_digits
  #=> 4

В doit шаги следующие:

min_common_length = 8

Во-первых, мы используем Enumerable # group_by для группировки значений по их первым min_common_length цифрам.

arr.map { |label, *values| [label,
  values.group_by { |s| s[0, min_common_length] }] }
  #=> [["A", {"24912508"=>["2491250873330", "2491250872214", "2491250872213"],
  #           "24911122"=>["249111222333"]}],
  #    ["B", {"22170990"=>["221709900000"]}],
  #    ["C", {"65902479"=>["6590247968", "6590247969"],
  #           "65985400"=>["6598540040", "65985400217"]}]]

Второй шаг - вычисление самых длинных общих длин и замена значений при необходимости.

arr.map do |label, *values| [label,
  values.group_by { |s| s[0, min_common_length] }.
         map { |_,a| a.first[0, nbr_common_digits(a, min_common_length)] }]
end
  #=> [["A", ["249125087", "249111222333"]],
  #    ["B", ["221709900000"]],
  #    ["C", ["659024796", "65985400"]]]

Первая переменная блока во втором блоке map (значение которого равно строке с nbr_common_length символами - критерий группировки group_by) представлена ​​подчеркиванием (допустимой локальной переменной) дляозначает, что он не используется в расчете блока.

Answer 2

Это интересная проблема.Вот мое решение:

def lcn(lim, *arr)
  # compute all substrings of lengths >= lim and build a lookup by length
  lookup = lcn_explode(lim, arr)

  # first pass: look for largest common number among all elements
  res, = lcn_filter(arr, lookup) { |size| size == arr.size }

  return res unless res.empty?

  # second pass: look for largest common number among some elements
  res, rem = lcn_filter(arr, lookup) { |size| size > 1 }

  # append remaining candidates with no matches
  res.concat(rem)
end

def lcn_explode(lim, arr)
  memo = Hash.new { |h, k| h[k] = Array.new }

  arr.uniq.each do |n|
    lim.upto([n.size, lim].max) do |i|
      memo[i] << [n[0, i], n]
    end
  end

  memo
end

def lcn_filter(arr, lookup)
  memo = []

  lookup.keys.sort!.reverse_each do |i|
    break if arr.empty?

    matches = Hash.new { |h, k| h[k] = Array.new }
    lookup[i].each do |m, n|
      matches[m] << n if arr.include?(n)
    end

    matches.each_pair do |m, v|
      next unless yield v.size

      memo << m

      # remove elements from input array so they won't be reused
      arr -= v
    end
  end

  return memo, arr
end

Вы используете его так:

p lcn(8, "97455589955", "97455589920", "97455589921") => ["974555899"]

Или:

m.each do |key, *arr|
  p [key, *lcn(8, *arr)]
end

Какие отпечатки:

["A", "249125087221", "2491250873330", "249111222333"]
["B", "221709900000"]
["C", "659024796", "65985400"]

Answer 3

Ваша задача может быть разделена на две части: вычисление наибольшего общего числа и изменение исходного массива.

Максимальное общее число работает с массивами, поэтому следует использовать метод Array.

После вычисленияLCN, вы можете просто сравнить его длину с пределом (т.е. 8).

class Array
  def lcn
    first.length.times do |index|
      numb = first[0..index]
      return numb unless self[1..-1].all? { |n| n.start_with?(numb) }
    end

    first
  end
end

def task(m, limit = 8)
  m.map { |i,*n| [i, n.lcn.length >= limit ? n.lcn : n].flatten }
end

task(m) # => [["A", "9745558995"], ["B", "2348045101518", "2348090001559"]]

В вашем решении вы фактически не реализуете поиск и фильтрацию lcn.