如何开始打造“无裂墙”？问题

发布于 2024-09-06 12:35:21 字数 673 浏览 3 评论 0原文

这是问题陈述：

考虑用 2x1 和 3x1 砖块（水平×垂直尺寸）建造一堵墙的问题，这样，为了获得额外的强度，水平相邻砖块之间的间隙永远不会在连续层中对齐，即永远不会形成“连续裂缝” ”。
形成无裂缝 9x3 墙的方法有八种，写作 W(9,3) = 8。
计算 W(32,10)。 <将其推广到 W(x,y) >
http://www.careercup.com/question?id=67814& ;form=评论

上面的链接提供了一些解决方案，但我无法理解它们背后的逻辑。我正在尝试用 Perl 编写此代码，并且到目前为止已经完成：

input : W(x,y)
find all possible i's and j's such that x == 3(i) + 2(j);
for each pair (i,j) ,
find n = (i+j)C(j)            # C:combinations

添加所有这些 n 应该给出所有可能组合的计数。但我不知道如何找到一行的真正组合以及如何进一步进行。

原文

Here's the problem statement:

Consider the problem of building a wall out of 2x1 and 3x1 bricks (horizontal×vertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".
There are eight ways of forming a crack-free 9x3 wall, written W(9,3) = 8.
Calculate W(32,10). < Generalize it to W(x,y) >
http://www.careercup.com/question?id=67814&form=comments

The above link gives a few solutions, but I'm unable to understand the logic behind them. I'm trying to code this in Perl and have done so far:

input : W(x,y)
find all possible i's and j's such that x == 3(i) + 2(j);
for each pair (i,j) ,
find n = (i+j)C(j)            # C:combinations

Adding all these n's should give the count of all possible combinations. But I have no idea on how to find the real combinations for one row and how to proceed further.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

若水微香 2024-09-13 12:35:21

基于 W(9,3)=8 的说法，我推断“连续裂缝”是指任何高度为 2 或更高的连续垂直裂缝。在解决所提出的二维问题之前，我想讨论一个类似的一维问题及其解决方案。我希望这将使人们更清楚如何将二维问题视为一维问题并最终得到解决。

假设您想要计算长度为 40 的列表的数量，这些列表的符号来自相当小的集合，例如五个符号 {a,b,c,d,e}。当然有 5^40 个这样的列表。如果我们添加一个额外的约束，即任何字母不能连续出现两次，数学解决方案仍然很简单：有 5*4^39 个没有重复字符的列表。然而，如果我们反而希望禁止诸如 bc、cb、bd 等辅音组合，那么事情就更困难了。当然，我们想计算选择第一个字符、第二个字符等的方法数，然后相乘，但是选择第二个字符的方法数取决于第一个字符的选择，依此类推。这个新问题很难说明正确的技术。（虽然还没有困难到完全无法抵抗数学方法！）

为了解决长度为 40 且没有辅音组合的列表问题（我们称之为 f(40)），我们可以想象使用递归。你能根据 f(39) 计算 f(40) 吗？不，因为长度为 39 的列表有些以辅音结尾，有些以元音结尾，而我们不知道每种类型有多少个。因此，我们不是对每个长度 n<=40 f(n) 进行计算，而是对每个 n 和每个字符 k f(n,k) 计算以 k 结尾的长度为 n 的列表的数量。虽然 f(40) 不能
仅根据 f(39) 计算，f(40,a) 可以根据 f(30,a)、f(39,b) 等计算。

上述策略可用于解决您的二维问题。您拥有长度为 32（或 x）的整个水平砖行，而不是字符。您有 10（或 y），而不是 40。您拥有无相邻裂纹约束，而不是无辅音组合约束。

您特别询问如何枚举给定长度的所有砖行，您是对的，这是必要的，至少对于这种方法而言。首先，决定如何表示一行。显然，指定 3 块砖的位置就足够了，并且由于每个砖块都有明确定义的中心，因此给出 3 块砖的中心位置列表似乎很自然。例如，当墙长为 15 时，序列 (1,8,11) 将描述如下所示的行：(ooo|oo|oo|ooo|ooo|oo)。该列表必须满足一些自然约束：

初始位置和最终位置不能是 3 块砖的中心。上面的 0 和 14 是无效条目。
序列中数字之间的连续差异必须是奇数，且至少为三个。
第一个条目的位置必须是奇数。
最后一个条目与列表长度之间的差异也必须是奇数。

有多种方法可以计算和存储所有此类列表，但概念上最简单的方法是对墙的长度进行递归，忽略条件 4，直到完成为止。手动生成长度为 2、3 和 4 的墙的所有列表的表格，然后对于每个 n，从先前的值推导出描述长度为 n 的墙的所有列表的表格。完成后施加条件 4，因为它不适用于递归。

给定任何砖排 S，您还需要一种方法来快速描述可以合法位于其下方的所有砖排 S'。为简单起见，我们假设墙的长度为 32。稍微思考一下，您就会相信

S' 必须满足与上面的 S 相同的约束。
当且仅当 1 不在 S 中时，1 在 S' 中。
当且仅当 30 不在 S 中时，30 在 S' 中。
对于 S 中的每个条目 q，S' 必须有一个对应的条目 q+1 或 q- 1，相反，对于 S 中的某个元素 q，S' 的每个元素都必须是 q-1 或 q+1。

例如，列表 (1,8,11) 可以合法地放置在 (7,10,30 )、(7,12,30) 或 (9,12,30)，但不是 (9,10,30)，因为这不满足“至少三个”条件。根据此描述，编写一个计算给定行的可能后继的循环并不困难。

现在我们将所有内容放在一起：

首先，对于固定的 x，制作一个包含长度为 x 的所有合法行的表。接下来，编写一个函数W(y,S)，该函数用于（递归地）计算宽度x、高度y和顶行S的墙的数量。对于y=1，W(y,S)=1。否则，W(y,S) 是可与上述 S 相关的所有 S' 值 W(y-1,S') 的总和。

该解决方案足够有效地解决问题 W(32,10)，但对于较大的 x 会失败。例如，按照我所描述的方式计算 W(100,10) 几乎肯定是不可行的。如果 x 很大但 y 很小，我们就会打破所有合理的砌砖惯例，并认为墙是从左到右而不是从下到上建造的。这需要对墙的有效柱进行描述。例如，列描述可以是一个列表，其长度为墙的高度，其条目为五个符号，分别表示“2x1 砖块的第一个正方形”、“2x1 砖块的第二个正方形”、“2x1 砖块的第一个正方形”。 3x1 砖”等。当然，每个柱的描述以及描述连续柱之间关系的约束都会有限制，但与上面相同的方法也可以这样工作，并且更适合长墙、短墙。

Based on the claim that W(9,3)=8, I'm inferring that a "running crack" means any continuous vertical crack of height two or more. Before addressing the two-dimensional problem as posed, I want to discuss an analogous one-dimensional problem and its solution. I hope this will make it more clear how the two-dimensional problem is thought of as one-dimensional and eventually solved.

Suppose you want to count the number of lists of length, say, 40, whose symbols come from a reasonably small set of, say, the five symbols {a,b,c,d,e}. Certainly there are 5^40 such lists. If we add an additional constraint that no letter can appear twice in a row, the mathematical solution is still easy: There are 5*4^39 lists without repeated characters. If, however, we instead wish to outlaw consonant combinations such as bc, cb, bd, etc., then things are more difficult. Of course we would like to count the number of ways to choose the first character, the second, etc., and multiply, but the number of ways to choose the second character depends on the choice of the first, and so on. This new problem is difficult enough to illustrate the right technique. (though not difficult enough to make it completely resistant to mathematical methods!)

To solve the problem of lists of length 40 without consonant combinations (let's call this f(40)), we might imagine using recursion. Can you calculate f(40) in terms of f(39)? No, because some of the lists of length 39 end with consonants and some end with vowels, and we don't know how many of each type we have. So instead of computing, for each length n<=40, f(n), we compute, for each n and for each character k, f(n,k), the number of lists of length n ending with k. Although f(40) cannot be
calculated from f(39) alone, f(40,a) can be calculated in terms of f(30,a), f(39,b), etc.

The strategy described above can be used to solve your two-dimensional problem. Instead of characters, you have entire horizontal brick-rows of length 32 (or x). Instead of 40, you have 10 (or y). Instead of a no-consonant-combinations constraint, you have the no-adjacent-cracks constraint.

You specifically ask how to enumerate all the brick-rows of a given length, and you're right that this is necessary, at least for this approach. First, decide how a row will be represented. Clearly it suffices to specify the locations of the 3-bricks, and since each has a well-defined center, it seems natural to give a list of locations of the centers of the 3-bricks. For example, with a wall length of 15, the sequence (1,8,11) would describe a row like this: (ooo|oo|oo|ooo|ooo|oo). This list must satisfy some natural constraints:

The initial and final positions cannot be the centers of a 3-brick. Above, 0 and 14 are invalid entries.
Consecutive differences between numbers in the sequence must be odd, and at least three.
The position of the first entry must be odd.
The difference between the last entry and the length of the list must also be odd.

There are various ways to compute and store all such lists, but the conceptually easiest is a recursion on the length of the wall, ignoring condition 4 until you're done. Generate a table of all lists for walls of length 2, 3, and 4 manually, then for each n, deduce a table of all lists describing walls of length n from the previous values. Impose condition 4 when you're finished, because it doesn't play nice with recursion.

You'll also need a way, given any brick-row S, to quickly describe all brick-rows S' which can legally lie beneath it. For simplicity, let's assume the length of the wall is 32. A little thought should convince you that

S' must satisfy the same constraints as S, above.
1 is in S' if and only if 1 is not in S.
30 is in S' if and only if 30 is not in S.
For each entry q in S, S' must have a corresponding entry q+1 or q-1, and conversely every element of S' must be q-1 or q+1 for some element q in S.

For example, the list (1,8,11) can legally be placed on top of (7,10,30), (7,12,30), or (9,12,30), but not (9,10,30) since this doesn't satisfy the "at least three" condition. Based on this description, it's not hard to write a loop which calculates the possible successors of a given row.

Now we put everything together:

First, for fixed x, make a table of all legal rows of length x. Next, write a function W(y,S), which is to calculate (recursively) the number of walls of width x, height y, and top row S. For y=1, W(y,S)=1. Otherwise, W(y,S) is the sum over all S' which can be related to S as above, of the values W(y-1,S').

This solution is efficient enough to solve the problem W(32,10), but would fail for large x. For example, W(100,10) would almost certainly be infeasible to calculate as I've described. If x were large but y were small, we would break all sensible brick-laying conventions and consider the wall as being built up from left-to-right instead of bottom-to-top. This would require a description of a valid column of the wall. For example, a column description could be a list whose length is the height of the wall and whose entries are among five symbols, representing "first square of a 2x1 brick", "second square of a 2x1 brick", "first square of a 3x1 brick", etc. Of course there would be constraints on each column description and constraints describing the relationship between consecutive columns, but the same approach as above would work this way as well, and would be more appropriate for long, short walls.

回复收藏 0 原文

小帐篷 2024-09-13 12:35:21

我在网上这里找到了这个Python代码，它运行快速且正确。我不明白这一切是如何运作的。我可以让我的 C++ 到达最后一步（计算解决方案的总数），但无法使其正常工作。

def brickwall(w,h):
    # generate single brick layer of width w (by recursion)
    def gen_layers(w):
        if w in (0,1,2,3):
            return {0:[], 1:[], 2:[[2]], 3:[[3]]}[w]
        return [(layer + [2]) for layer in gen_layers(w-2)] + \
               [(layer + [3]) for layer in gen_layers(w-3)]
    # precompute info about whether pairs of layers are compatible
    def gen_conflict_mat(layers, nlayers, w):
        # precompute internal brick positions for easy comparison
        def get_internal_positions(layer, w):
            acc = 0; intpos = set()
            for brick in layer:
                acc += brick; intpos.add(acc)
            intpos.remove(w)
            return intpos
        intpos = [get_internal_positions(layer, w) for layer in layers]        
        mat = []
        for i in range(nlayers):
            mat.append([j for j in range(nlayers) \
                              if intpos[i].isdisjoint(intpos[j])])
        return mat
    layers = gen_layers(w)
    nlayers = len(layers)
    mat = gen_conflict_mat(layers, nlayers, w)
    # dynamic programming to recursively compute wall counts
    nwalls = nlayers*[1]
    for i in range(1,h):
        nwalls = [sum(nwalls[k] for k in mat[j]) for j in range(nlayers)]
    return sum(nwalls)

print(brickwall(9,3))   #8
print(brickwall(9,4))   #10
print(brickwall(18,5))  #7958
print(brickwall(32,10)) #806844323190414

I found this python code online here and it works fast and correctly. I do not understand how it all works though. I could get my C++ to the last step (count the total number of solutions) and could not get it to work correctly.

def brickwall(w,h):
    # generate single brick layer of width w (by recursion)
    def gen_layers(w):
        if w in (0,1,2,3):
            return {0:[], 1:[], 2:[[2]], 3:[[3]]}[w]
        return [(layer + [2]) for layer in gen_layers(w-2)] + \
               [(layer + [3]) for layer in gen_layers(w-3)]
    # precompute info about whether pairs of layers are compatible
    def gen_conflict_mat(layers, nlayers, w):
        # precompute internal brick positions for easy comparison
        def get_internal_positions(layer, w):
            acc = 0; intpos = set()
            for brick in layer:
                acc += brick; intpos.add(acc)
            intpos.remove(w)
            return intpos
        intpos = [get_internal_positions(layer, w) for layer in layers]        
        mat = []
        for i in range(nlayers):
            mat.append([j for j in range(nlayers) \
                              if intpos[i].isdisjoint(intpos[j])])
        return mat
    layers = gen_layers(w)
    nlayers = len(layers)
    mat = gen_conflict_mat(layers, nlayers, w)
    # dynamic programming to recursively compute wall counts
    nwalls = nlayers*[1]
    for i in range(1,h):
        nwalls = [sum(nwalls[k] for k in mat[j]) for j in range(nlayers)]
    return sum(nwalls)

print(brickwall(9,3))   #8
print(brickwall(9,4))   #10
print(brickwall(18,5))  #7958
print(brickwall(32,10)) #806844323190414

回复收藏 0 原文

~没有更多了~