如何从字典中构建一个Plinko单词板比蛮力更好？

Question

如何从字典中构建一个Plinko单词板比蛮力更好？

考虑以下字母排列:

    B
   O A
  N R I
 D E N T

Run Code Online (Sandbox Code Playgroud)

从顶部字母开始,选择以下两个字母之一,Plinko风格,直到你到达底部.无论你选择什么样的路径,你都会创建一个四个字母的单词:BOND,BONE,BORE,BORN,BARE,BARN,BAIN或BAIT.DENT读到底部的事实只是一个很好的巧合.

我想帮助找出一个可以设计这种布局的算法,其中从顶部到底部的每条可能路径都会从(提供的)字典中生成一个不同的单词.程序的输入将是起始字母(在该示例中为B)和字长n(在该示例中为4).它将返回组成这种布局的字母,或者返回表示不可能的消息.它不一定是确定性的,因此它可能会生成具有相同输入的不同布局.

到目前为止,我还没有想到比蛮力方法更好的东西.也就是说,对于26^[(n+2)(n-1)/2]为布局底部选择字母的所有方法,检查所有可能的2^(n-1)路径是否给出字典中的单词.我考虑过某种前缀树,但路径可以交叉并分享与我混淆的字母.我对Python最熟悉,但至少我只是想要一个可以解决这个问题的算法或方法.谢谢.

Answer 1

גלע*_*רקן 6

假装V W X Y Z在底部这里实际上是完整的单词.

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

Run Code Online (Sandbox Code Playgroud)

我们可以用启发式扫描来实现一个非常严格的回溯搜索,似乎不太可能出现任何错误的路径.

n在如下的简单树中插入以相同字母开头的所有大小的单词.现在执行深度优先搜索,断言以下内容:每个连续级别需要一个额外的"共享"字母,意味着p(letter)它在该级别上的实例,另外要求他们的两个孩子是相同的字母(例如R括号中的两个s)在2级可能是一个"共享"字母,因为他们的孩子是相同的).

什么是p(letter)？帕斯卡的三角形当然!n choose r根据Plinko董事会的说法,这正是这棵简单树相关层面所需字母的实例数.在第3级,如果我们选择R和R,我们需要3 N秒和3 E秒至表达上该级别的"共享"的信件.并且3 Ns中的每一个必须具有相同的子字母(在这种情况下为W,X),并且3 Es中的每一个也必须(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

Run Code Online (Sandbox Code Playgroud)

UPDATE

出于好奇,这里有一些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

Run Code Online (Sandbox Code Playgroud)