Найти самые короткие панграммы из списка слов

10

Панграмма является строкой , которая содержит все буквы a- zот английского алфавита, не чувствительны к регистру. (Это нормально, если панграмма содержит более одной копии буквы или если она содержит не буквенные символы в дополнение к буквам.)

Напишите программу или функцию, чьи входные данные представляют собой список строк и которые выводят одну или несколько строк, которые имеют следующие свойства:

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

Многие программы выберут вывод только одной строки; вы бы хотели вывести более одной строки, если бы вам пришлось написать дополнительный код для ограничения вывода.

Вы можете предположить, что входные данные не содержат непечатаемых символов или пробелов и что ни одно слово в нем не превышает (в 26 раз больше натурального логарифма длины списка) символов. (Однако вы не можете предполагать, что ввод содержит только буквы или только строчные буквы; знаки препинания и заглавные буквы вполне возможны.)

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

abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz

Вы должны включить образец результатов вашей программы вместе с вашим представлением. (Это может отличаться для разных людей в результате использования разных списков слов.)

Состояние победы

Это сложная задача . Победителем является самая короткая программа (в байтах), которая выполняется за полиномиальное время . (Резюме для людей, которые не знают, что это значит: если вы удвоите размер списка слов, программа должна стать медленнее не более чем на постоянный фактор. Однако рассматриваемый постоянный фактор может быть таким же большим, как вы Например, допустимо, чтобы он становился в четыре раза медленнее или в восемь раз медленнее, но не для того, чтобы он становился меньше в зависимости от длины списка слов; фактор, из-за которого он становится медленнее, должен быть ограничен.)


источник
При определении сложности можем ли мы использовать тот факт, что каждое слово имеет длину не более 26 букв? Что размер алфавита является константой 26?
xnor
Да. Я частично наложил это ограничение на входные данные, чтобы было проще определить / вычислить сложность.
Я думаю, что это сталкивается с техническими особенностями. Если вы игнорируете повторяющиеся входные слова, то существует не более 27 ^ 26 возможных входных слов и, следовательно, не более 2 ^ (27 ^ 26) возможных подмножеств из них в качестве возможных входных данных. Это огромный, но постоянный. Таким образом, любая программа в этом конечном наборе имеет постоянное время, причем константа - это максимальное количество шагов, предпринимаемых по всем возможным входам.
xnor
Я не говорил, что во входе нет повторяющихся слов. Я предполагаю, что вы могли бы запустить программу за «техническое» время O (n), отфильтровывая знаки препинания и сначала дедуплицируя ввод (хотя, или, скорее, O (n log n), который использовал бы намного меньше памяти, чем radix дедуплицировал бы). Затем вам придется вернуться от отфильтрованной версии к первоначальному списку слов. Вы не можете требовать рассматриваемого полиномиального времени, если вы не пройдете все эти шаги!
Я забыл про не-буквы. Можем ли мы предположить, что это ASCII или иным образом в некотором конечном множестве? Если так, то я думаю, что любой алгоритм, который начинается с дедупликации, может претендовать на полиномиальное время.
xnor

Ответы:

3

Рубин 159 (итеративный)

Рубин 227 220 229 227 221 (рекурсивный)

Новое итеративное решение (на основе алгоритма, описанного @Niel):

c={('A'..'Z').to_a=>""}
while l=gets
d=c.clone
c.map{|k,v|j=k-l.upcase.chars
w=v+" "+l.strip
d[j]=w if !c[j]||c[j].size<w.size}
c=d
end
x=c[[]]
p x[1..-1] if x

Старое рекурсивное решение:

W=[]
while l=gets
W<<l.strip
end
I=W.join(" ")+"!!"
C={[]=>""}
def o(r)if C[r]
C[r]
else
b=I
W.map{|x|s=r-x.upcase.chars
if s!=r
c=x+" "+o(s)
b=c if c.size<b.size
end}
C[r]=b
end
end
r=o ('A'..'Z').to_a
p r[0..-2] if r!=I

Измерение байтов основано на исключении последней строки в файле, что не имеет значения ruby 2.3.1p112. После исправления небольшой ошибки число байт снова увеличилось.downcase .upcase для нечувствительности к регистру, как того требует постановка задачи).

Вот более ранняя версия до сокращения идентификаторов и тому подобное:

#!/usr/bin/env ruby

$words = [];

while (line=gets)
  $words << line[0..-2];
end

$impossible = $words.join(" ")+"!!";

$cache = {};

def optimize(remaining)
  return $cache[remaining] if ($cache[remaining]);
  return "" if (remaining == []);

  best = $impossible;

  $words.each{|word|
    remaining2 = remaining - word.chars;
    if (remaining2 != remaining)
      curr = word + " " + optimize(remaining2);
      best = curr if (curr.length < best.length);
    end
  };

  $stderr.puts("optimize(#{remaining.inspect})=#{best.inspect}");

  return $cache[remaining] = best;
end

result = optimize(('a'..'z').to_a);

puts(result[0..-1]);

Как это работает? По сути, он поддерживает набор символов, которые все еще должны охватывать, и повторяется только в слове, если это уменьшит раскрытый набор. Кроме того, результаты рекурсии запоминаются. Каждое подмножество 2 ^ 26 соответствует записи в таблице памятки. Каждая такая запись рассчитывается во времени, пропорциональном размеру входного файла. Так что все дело в том O(N)(где Nразмер входного файла), хотя и с огромной константой.

DepressedDaniel
источник
1

JavaScript (ES6), 249 248 байт, возможно, конкурирующий

a=>a.map(w=>w.replace(/[a-z]/gi,c=>b|=1<<parseInt(c,36)-9,b=0,l=w.length)&&(m.get(b)||[])[0]<l||m.set(b,[l,w]),m=new Map)&&[...m].map(([b,[l,w]])=>m.forEach(([t,s],e)=>(m.get(e|=b)||[])[0]<=t+l||m.set(e,[t+l+1,s+' '+w])))&&(m.get(-2^-1<<27)||[])[1]

Объяснение: Преобразует массив путем преобразования букв в битовую маску, сохраняя только самое короткое слово для каждой битовой маски на карте. Затем перебирая копию карты, увеличивайте карту, добавляя каждую комбинированную битовую маску, если результирующая строка будет короче. Наконец, верните строку, сохраненную для растрового изображения, соответствующего панграмме. (Возвращает, undefinedесли такой строки не существует.)

Нил
источник
Интересно. Не могли бы вы рассказать подробнее о том, как это работает, и, если возможно, опубликовать неоплаченный код?
ДепрессияДаниэль
1
Это должна быть действительная / конкурирующая запись. Я думаю, что это на самом деле работает в O ( N журнала N ), на самом деле! (Карта имеет жесткое ограничение в 2²⁶ записей и, следовательно, не проявляется в сложности; таким образом, единственное время, затрачиваемое на чтение, - это время чтения ввода.)
Я просто перечитал описание и понял, как оно работает. Ухоженная. +1 ... Хм, когда он решает прекратить попытки дополнить карту, учитывая пары? Это должно продолжаться, пока никакие расслабления не возможны.
ДепрессияДаниэль
@DepressedDaniel Для каждой битовой маски, извлеченной из исходного списка слов, он проверяет все найденные частичные панграммы и определяет, создает ли добавление слова панграмму, которая короче той, которую он в настоящее время знает для комбинированной битовой маски.
Нил
@ ais523 Для больших вводов (> 1000 слов) большую часть времени тратится на обмен. Я попытался переключиться с карты на массив, и он стал еще медленнее!
Нил
-1

Python 3, 98 , 94 , 92 байта

print([s for s in input().split()if sum([1 for c in range(65,91)if chr(c)in s.upper()])>25])

Выполняет итерацию в алфавитном представлении ASCII и добавляет 1 в список, если в строке обнаружена буква. Если сумма в списке больше 25, он содержит все буквы алфавита и будет напечатан.

Erich
источник
Я думаю, что вы можете удалить пробел между (' ')и if. Вы также можете изменить ord(i) in range(65,91)на 91>x>=65. Кроме того, в чем сложность?
NoOneIsHere
1
В чем сложность этого решения? Он необходим для ответа , чтобы быть в полиномиальной сложности, в противном случае она не конкурирующая.
NoOneIsHere
Извините, я думаю, что это O (n), потому что длина входного списка может быть разной, но
Эрих
Извините, я думаю, что это O (n), потому что длина входного списка может быть разной, но второй цикл всегда идет от 65 до 90. Но я его не проверял.
Эрих
Не уверен, что это удовлетворяет: «Каждая строка вывода должна быть самой короткой или связана с самой короткой из всех строк с этими свойствами».
ДепрессияДаниэль