Сколько мез начинается с данной строки?

11

Назовем непустой список строк мезой, если выполняются следующие условия:

  1. Каждая указанная строка непуста и использует только символы, которые встречаются в первой строке.
  2. Каждая последующая строка ровно на один символ длиннее предыдущей строки.
  3. Ни одна строка в списке не является подпоследовательностью любой другой строки в списке.

Термин «меза» происходит от такой визуализации (где xсимволы должны быть различными):

    xx..x
    xx..xx
    xx..xxx
    .
    .
    .
    xx..xxx..x

NB: Это математический факт, что только конечное число мез начинается с заданной строки. Обратите внимание на различие между подпоследовательностью и подстрокой ; например, «анна» является подпоследовательностью (но не подстрокой) «банана».

Вызов:

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

Вход (стандартный):

  • Любая непустая буквенно-цифровая строка.

Выход (стандартный вывод):

  • Количество мез, которые начинаются с входной строки.

Подсчет очков:

  • Победителем становится программа с наименьшим количеством байтов.

Пример мезы

Только одна меза начинается с a:

a

Только одна меза начинается с aa:

aa

Многие мезы начинаются с ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
code-golf Рез
источник
Как определяется уникальность мезы? Например, я мог бы ab, bbbкак меза, просто остановиться на втором семестре. Это действительно? Или они всегда должны быть сделаны как можно дольше? Кроме того , если имеется несколько возможных перестановки в nthперспективе (например baa, aba, aab), не все они учитываются как отдельные Месасы , а также ( при условии , конечно , все они следуют правилам)?
mellamokb
@mellamokb - это разные мезы, если они вообще отличаются. Например, ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaaразные Mesas.
Res
@mellamokb - ты поднимаешь другие хорошие вопросы; например, сколько мез максимальной длины начинается с данной строки, и какова эта максимальная длина. Другие версии этих вопросов фиксировали бы алфавит заданного размера (размер алфавита был бы входным) и рассматривали бы все мезы (переопределенные без условия # 1), которые используют только буквы из данного алфавита - опять же, их только конечное число.
Res

Ответы:

2

Рубин, 142 персонажа

m=->l{[*l[0].chars].repeated_permutation(l[-1].size+1).reduce(1){|s,x|l.any?{|y|x*''=~/#{[*y.chars]*'.*'}/}?s:s+m[l+[x*'']]}}
p m[[gets.chop]]

Этот алгоритм является конструктивным, то есть он строит все возможные мезы для входной строки и считает их. Это делает программу очень, очень медленной - но эй, это Codegolf.

Пример работы:

> a
1
> aa
1
> ab
43
Говард
источник
Я надеялся, что все мезы, начинающиеся с некоторых нетривиальных двоичных строк длины 3 (например aab), имеют допустимую длину, но я не уверен - ваша программа работала около часа для этого примера. NB. Не будет осуществимого вывода для любого ввода, включающего более двух различных букв; например, некоторые из мез, начинающихся с, abcимеют длину, превышающую 7000-е число Аккермана .
Res
Я построил оптимизированную версию в C #, и после того, как я сгенерировал 300,000записи с помощью, aabя все еще видел, что первые 10 или около того терминов были идентичными. Поэтому я думаю, что это может быть неосуществимо для чего-то большего, чем два персонажа. По крайней мере, не без интеллектуальных и эвристических расчетов.
mellamokb