Уменьшить массив целых до самого длинного общего префикса

Question

Я имею дело с почтовыми индексами и хочу получить значения «Начинается с» из списка почтовых индексов.

Например, массив

arr = [10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10009, 10010, 10011]

Должен производить массив:

out = [1000,10010,10011]

Любая помощь с благодарностью. Проблема становится все больше, чем больше я об этом думаю!

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

Мне нужен синтаксис «Начинается с», который обычно используется в почтовых сервисах. В основном, если у вас есть фиксированное число из 5 цифр (почтовые индексы США, без zip + 4), если охватывается весь диапазон, например, 11000-11999, то он может быть уменьшен до 11 при запуске с синтаксисом. Тем не менее, если в этом диапазоне есть число (или набор чисел), которое не включено. например, 11005, то синтаксис должен возвращать все числа для этого диапазона, пока снова не появится общее «начинается с». Таким образом, для этого примера это будет:

[ 11000, 11001, 11002, 11003, 11004, 11006, 11001, 11007, 11008, 11009, 1101, 1102, 1103, 1104, 1105, 1106, 1107, 1108, 1109, 111, 112, 113, 114, 115, 116, 117, 118, 119 ]

Таким образом, для 11000-11004 и 11006-11009 не существует общих «начинающихся с» чисел, поэтому необходимо добавить точные числа. А с 11010 до 11999 общие цифры можно уменьшить, как указано выше.

Включение букв в этот синтаксис было бы огромным бонусом, поскольку оно распространяется и на почтовые индексы Великобритании. Однако это сложнее, поскольку почтовые индексы в Великобритании не всегда последовательны, поэтому я не собирался заниматься этим. 5-значный почтовый индекс США.

Answer 1

Код

def doit(arr)
  a = arr.dup
  loop do
    size = a.size
    a = combine_by_last(a)
    break if a.size == size
  end
  a
end

def combine_by_last(a)
  b = []
  until a.empty?
    move_10 = a.first % 10 == 0 && a.size > 9 && a[9] == a.first + 9
    if move_10
      b << a.shift/10
      a.shift(9) # discard
    else
      b << a.shift
    end        
  end
  b
end

Пример

arr = [10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10009,
       10010, 10011] +
       (11000..11999).to_a +
       [12251, 12252] +
       (12340..12349).to_a

doit arr
  #=> [1000, 10010, 10011, 11, 12251, 12252, 1234] 

Пояснение

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

arr = (11000..11999).to_a

, то сначала оно будет уменьшено до:

(1100..1199).to_a

, а затем:

(110..119)

, а затем:

11

Мы можем изменить doit, чтобы показать это в действии.

def doit(arr)
  a = arr.dup
  loop do
    size = a.size
    a = combine_by_last(a)
    puts
    p a 
    break if a.size == size
  end
  a
end

doit arr
  #=> [1000, 10010, 10011, 11, 12251, 12252, 1234]  

[1000,
 10010, 10011,
 1100, 1101, 1102, 1103, 1104, 1105, 1106, 1107, 1108, 1109,
 1110, 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119,
 1120, 1121, 1122, 1123, 1124, 1125, 1126, 1127, 1128, 1129,
 1130, 1131, 1132, 1133, 1134, 1135, 1136, 1137, 1138, 1139,
 1140, 1141, 1142, 1143, 1144, 1145, 1146, 1147, 1148, 1149,
 1150, 1151, 1152, 1153, 1154, 1155, 1156, 1157, 1158, 1159,
 1160, 1161, 1162, 1163, 1164, 1165, 1166, 1167, 1168, 1169,
 1170, 1171, 1172, 1173, 1174, 1175, 1176, 1177, 1178, 1179,
 1180, 1181, 1182, 1183, 1184, 1185, 1186, 1187, 1188, 1189,
 1190, 1191, 1192, 1193, 1194, 1195, 1196, 1197, 1198, 1199,
 12251, 12252,
 1234]

[1000, 
 10010, 10011,
 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
 12251, 12252,
 1234]

[1000,
 10010, 10011,
 11,
 12251, 12252,
 1234]

Поскольку почтовые индексы уникальны и упорядочены, a[9] == a.first + 9 равно true тогда и только тогда, когда a[0], a[1], ..., a[9] являются последовательными значениями.

Выражение:

move_10 = a.first % 10 == 0 && a.size > 9 && a[9] == a.first + 9

можно упроститьto:

move_10 = a.first % 10 == 0 && a[9] == a.first + 9

, потому что если a.size <= 9, a[9] == a.first + 9 станет nil == a.first + 9, что приведет к возвращению условия false, как и должно быть. Это, однако, ухудшило бы читабельность.

Answer 2

Enumerable's group_by полезен для подобных задач, он группирует одинаковые почтовые индексы в хеш, используя какое-то общее свойство. В вашем случае мы бы хотели, чтобы это свойство было префиксом почтового индекса.

group_by принимает блок, который используется для сопоставления элемента в ключ, например:

animals = ['Cat', 'Dog', 'Donkey']

# Group each animal by their first letter
grouped_animals = animals.group_by {|animal| animal[0]} 

puts grouped_animals
# => {"C"=>["Cat"], "D"=>["Dog", "Donkey"]}

Чтобы сгруппировать почтовые индексы по их префиксам, мы можем разделить число на 10, чтобы отбросить последнюю цифру. Затем вы можете использовать hash.keys, чтобы получить только префиксы.

zipcodes = [10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10009, 10010, 10011]
grouped_zipcodes = zipcodes.group_by {|zipcode| zipcode / 10}

puts grouped_zipcodes
# => {1000=>[10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10009], 1001=>[10010, 10011]}

puts grouped_zipcodes.keys
# => [1000, 1001]

Это предполагает, что ваши почтовые индексы всегда состоят из 5 цифр, и что префиксы всегда будут первыми 4 цифрами, но по крайней мереТеперь проблема сводится к выяснению того, как вы хотите найти свой префикс!