Как построить доску Plinko слов из словаря лучше, чем грубая сила?

Вопрос задан: 1 год назад Последняя активность: 1 год назад
up 13 down

Рассмотрим следующий расположение букв:

    B
   O A
  N R I
 D E N T

Начало в верхних буквах и выбрать одну из двух букв ниже, Plinko стиля, пока не достигнет дна. Независимо от того, какой путь вы выбираете вы создать четыре-письма слово: BOND, КОСТЬ, расточные, Борн, обнажены, Амбар, Bain, или наживку. Тот факт, чт.д.НТ читает через дно просто хорошее совпадение.

Я хотел бы помочь выяснить алгоритм, который может спроектировать такую ​​планировку, где каждый возможный путь от верха до низа создает отчетливое слово из (прилагается) словаря. Входы в программе будет начальное письмо (B, в этом примере) и длина слова п (4, в этом примере). Он вернется либо буквы, которые составляют такую ​​компоновку, или сообщение о том, что это не возможно. Он не должен быть детерминированным, так что, возможно, создавать различные макеты с тем же входом.

Я не думал, что ничего лучше, чем грубой силы подход до сих пор. То есть, для всех 26^[(n+2)(n-1)/2] способы выбора букв для нижней части макета, чтобы проверить, если это вообще возможно 2^(n-1) пути дают слова, которые в словаре. Я рассматривал какой-то префикс дерева, но тот факт, что пути могут пересекать и обмениваться письмами перепутались со мной. Я наиболее комфортно в Python, но, как минимум, я бы так же, как идея для алгоритма или подхода, который будет работать для этой проблемы. Благодарю.

2 ответа

Возможно, для Вашего проекта будут необходимы бесплатные векторные карты. На нашем сайте представлены карты для всех стран.

Реклама

up 6 down

притвориться V W X Y Z на дне здесь на самом деле полные словах.

    B
   A O
  I R N
 T N E D
V W X Y Z

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

Вставить все n размера слова, которые начинаются с той же буквы в простом дереве, как показано ниже. Теперь выполните глубины первого поиска, утверждая следующее: каждый последующий уровень необходим один дополнительный «общий» письмо, смысл p(letter) экземпляры этого на этом уровне, с дополнительным требованием, чтобы их двое детьми являются одними и теми же буквами (например, два Rs в скобках на уровне 2 может быть «общим» письмо, потому что их дети одинаковы).

Что такое p(letter)? треугольник Паскаля, конечно! n choose r именно количество экземпляров письма, необходимое на соответствующем уровне этого простого дерева, в соответствии с доской Plinko. На уровне 3, если мы выбрали R а также R, Нам понадобится 3 Nс и 3 Es выражать «общие» буквы на этом уровне. И каждый из 3 Nы должны иметь одни и те же буквы дети (W, X в данном случае), и каждый из 3 Eы должны также (X, Y).

                     B
            /                 \
          A                     O
      /       \             /       \   
     I        (R)         (R)        N
    / \       / \         / \       / \
   T  (N)   (N)  E      (N)  E     E   D
  V W W X   W X X Y     W X X Y   X Y Y Z

4 W's, 6 X's, 4 Y's 

ОБНОВИТЬ

Из любопытства, вот некоторые код Python :)

from itertools import combinations
from copy import deepcopy

# assumes words all start
# with the same letter and
# are of the same length
def insert(word, i, tree):
  if i == len(word):
    return
  if word[i] in tree:
    insert(word, i + 1, tree[word[i]])
  else:
    tree[word[i]] = {}
    insert(word, i + 1, tree[word[i]])

# Pascal's triangle
def get_next_needed(needed):
  next_needed = [[1, None, 0]] + [None] * (len(needed) - 1) + [[1, None, 0]]

  for i, _ in enumerate(needed):
    if i == len(needed) - 1:
      next_needed[i + 1] = [1, None, 0]
    else:
      next_needed[i + 1] = [needed[i][0] + needed[i+1][0], None, 0]
  return next_needed

def get_candidates(next_needed, chosen, parents):
  global log
  if log:
    print "get_candidates: parents: %s" % parents
  # For each chosen node we need two children.
  # The corners have only one shared node, while
  # the others in each group are identical AND
  # must have all have a pair of children identical
  # to the others' in the group. Additionally, the
  # share sequence matches at the ends of each group.
  #    I       (R)     (R)      N
  #   / \      / \     / \     / \
  #  T  (N)  (N)  E  (N)  E   E   D

  # Iterate over the parents, choosing
  # two nodes for each one
  def g(cs, s, seq, i, h):
    if log:
      print "cs, seq, s, i, h: %s, %s, %s, %s, %s" % (cs, s, seq, i, h)

    # Base case, we've achieved a candidate sequence
    if i == len(parents):
      return [(cs, s, seq)]
    # The left character in the corner is
    # arbitrary; the next one, shared.
    # Left corner:
    if i == 0:
      candidates = []
      for (l, r) in combinations(chosen[0].keys(), 2):
        _cs = deepcopy(cs)
        _cs[0] = [1, l, 1]
        _cs[1][1] = r
        _cs[1][2] = 1
        _s = s[:]
        _s.extend([chosen[0][l], chosen[0][r]])
        _h = deepcopy(h)
        # save the indexes in cs of the
        # nodes chosen for the parent 
        _h[parents[1]] = [1, 2]
        candidates.extend(g(_cs, _s, l+r, 1, _h))
        _cs = deepcopy(cs)
        _cs[0] = [1, r, 1]
        _cs[1][1] = l
        _cs[1][2] = 1
        _s = s[:]
        _s.extend([chosen[0][r], chosen[0][l]])
        _h = deepcopy(h)
        # save the indexes in cs of the
        # nodes chosen for the parent
        _h[parents[1]] = [1, 2]
        candidates.extend(g(_cs, _s, r+l, 1, _h))
      if log:
        print "returning candidates: %s" % candidates
      return candidates
    # The right character is arbitrary but the
    # character before it must match the previous one.
    if i == len(parents)-1:
      l = cs[len(cs)-2][1]
      if log:
        print "rightmost_char: %s" % l
      if len(chosen[i]) < 2 or (not l in chosen[i]):
        if log:
          print "match not found: len(chosen[i]) < 2 or (not l in chosen[i])"
        return []
      else:
        result = []
        for r in [x for x in chosen[i].keys() if x != l]:
          _cs = deepcopy(cs)
          _cs[len(cs)-2][2] = _cs[len(cs)-2][2] + 1
          _cs[len(cs)-1] = [1, r, 1]
          _s = s[:] + [chosen[i][l], chosen[i][r]]
          result.append((_cs, _s, seq + l + r))
        return result

    parent = parents[i]
    if log:
      print "get_candidates: g: parent, i: %s, %s" % (parent, i)
    _h = deepcopy(h)
    if not parent in _h:
      prev = _h[parents[i-1]]
      _h[parent] = [prev[0] + 1, prev[1] + 1]
    # parent left and right children
    pl, pr = _h[parent]
    if log:
      print "pl, pr: %s, %s" % (pl, pr)
    l = cs[pl][1]
    if log:
      print "rightmost_char: %s" % l
    if len(chosen[i]) < 2 or (not l in chosen[i]):
      if log:
        print "match not found: len(chosen[i]) < 2 or (not l in chosen[i])"
      return []
    else:
      # "Base case," parent nodes have been filled
      # so this is a duplicate character on the same
      # row, which needs a new assignment
      if cs[pl][0] == cs[pl][2] and cs[pr][0] == cs[pr][2]:
        if log:
          print "TODO"
        return []
      # Case 2, right child is not assigned
      if not cs[pr][1]:
        candidates = []
        for r in [x for x in chosen[i].keys() if x != l]:
          _cs = deepcopy(cs)
          _cs[pl][2] += 1
          _cs[pr][1] = r
          _cs[pr][2] = 1
          _s = s[:]
          _s.extend([chosen[i][l], chosen[i][r]])
          # save the indexes in cs of the
          # nodes chosen for the parent
          candidates.extend(g(_cs, _s, seq+l+r, i+1, _h))
        return candidates
      # Case 3, right child is already assigned
      elif cs[pr][1]:
        r = cs[pr][1]
        if not r in chosen[i]:
          if log:
            print "match not found: r ('%s') not in chosen[i]" % r
          return []
        else:
          _cs = deepcopy(cs)
          _cs[pl][2] += 1
          _cs[pr][2] += 1
          _s = s[:]
          _s.extend([chosen[i][l], chosen[i][r]])
          # save the indexes in cs of the
          # nodes chosen for the parent
          return g(_cs, _s, seq+l+r, i+1, _h)
    # Otherwise, fail 
    return []

  return g(next_needed, [], "", 0, {})

def f(words, n):
  global log
  tree = {}
  for w in words:
    insert(w, 0, tree)

  stack = []
  root = tree[words[0][0]]
  head = words[0][0]
  for (l, r) in combinations(root.keys(), 2):
    # (shared-chars-needed, chosen-nodes, board)
    stack.append(([[1, None, 0],[1, None, 0]], [root[l], root[r]], [head, l + r], [head, l + r]))

  while stack:
    needed, chosen, seqs, board = stack.pop()
    if log:
      print "chosen: %s" % chosen
      print "board: %s" % board
    # Return early for demonstration
    if len(board) == n:
      # [y for x in chosen for y in x[1]]
      return board

    next_needed = get_next_needed(needed)
    candidates = get_candidates(next_needed, chosen, seqs[-1])
    for cs, s, seq in candidates:
      if log:
        print "  cs: %s" % cs
        print "  s: %s" % s
        print "  seq: %s" % seq
      _board = board[:]
      _board.append("".join([x[1] for x in cs]))
      _seqs = seqs[:]
      _seqs.append(seq)
      stack.append((cs, s, _seqs, _board))

"""
    B
   A O
  I R N
 T N E D
Z Y X W V
"""
words = [
  "BONDV",
  "BONDW",
  "BONEW",
  "BONEX",
  "BOREW",
  "BOREX",
  "BAREW",
  "BAREX",
  "BORNX",
  "BORNY",
  "BARNX",
  "BARNY",
  "BAINX",
  "BAINY",
  "BAITY",
  "BAITZ"]
N = 5
log = True

import time
start_time = time.time()
solution = f(list(words), N)
print ""
print ""
print("--- %s seconds ---" % (time.time() - start_time))
print "solution: %s" % solution
print ""
if solution:
  for i, row in enumerate(solution):
    print " " * (N - 1 - i) + " ".join(row)
  print ""
print "words: %s" % words
up 3 down accepted

Я считаю это довольно интересной проблемой.

Первая попытка была случайным решателем; другими словами, он просто заполняет треугольник с буквами, а затем подсчитывает, сколько «ошибок» присутствуют (слова не в словаре). Затем пониженная осуществляется путем изменения одного или более письма случайным образом и, видя, если ошибка улучшается; если ошибка остается тем же, что изменения все еще принимаются (так делают блуждания на плато областях).

Удивительно достаточно это может решить в разумные сроки неочевидным проблемы, как 5-буквенные слова, начинающиеся с «B»:

    b
   a u
  l n r
 l d g s
o y s a e

Затем я попробовал полный поиск подход, чтобы быть в состоянии ответить также «без решения» часть и идея состояла в том, чтобы написать рекурсивный поиск:

Первый шаг

Просто запишите все допустимые слова на левой стороне; например

    b
   a ?
  l ? ?
 l ? ? ?
o ? ? ? ?

и называть рекурсивно, пока мы не найдем приемлемое решение или не

Шаг 2

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

    b
   a u
  l ? r
 l ? ? k
o ? ? ? e

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

Другие шаги

В общем случае первый знак вопроса заменяется все буквы в алфавите, если все слова, которые используют выбранный знак вопроса либо

  1. слово не имеет знаки вопроса и в словаре, или
  2. есть слова в словаре, которые совместимы (все символы, кроме вопросительных знаков являются матчем)

Если решение не будет найдено для конкретного знака вопроса выбранного нет смысла в хранении поиска так False возвращается. Возможно использовать некоторые эвристики для выбора которых знак вопроса для заполнения первой бы ускорить поиск, я не исследовал эту возможность.

Для случая 2 (поиск, если есть совместимые слова) Я создаю 26*(N-1) наборы слов, которые имеют заданный символ в определенной позиции (позиция 1 не считается), и я использую пересечение множеств на всех не-знак вопроса.

Такой подход может сказать примерно 30 секунд (PyPy), что нет решения для 5-буквенных слов начиная с w (Есть 468 слов в словаре с этой начальной буквой).

Код для реализации этого можно увидеть на

https://gist.github.com/6502/26552858e93ce4d4ec3a8ef46100df79

(Программа ожидает файл с именем words_alpha.txt содержащий все действительные слова, а затем должны быть вызваны specifiying начальной буквы и размера; как словарь я использовал файл из https://github.com/dwyl/english-words)

Ошибка 505

Что-то пошло не так

Попробуйте воспользоваться поиском