Ruby 求助 - 拼图游戏,性能,ruby&c

jay_li · 2014年10月21日 · 最后由 heliang7 回复于 2014年11月05日 · 2688 次阅读

游戏规则:

  1. 拼图的单位为 [积木块]
  2. [积木条] 由 5 个 [积木块] 组成,每个 [积木块] 面与面相贴 (二维界面),可组合成任何可以组成的 [积木形状]
  3. [积木条] 放在 [拼盘] 中无间隙放满 ([积木条] 形状类型不同重复) 即成功,[拼盘] 长宽为 3x20(单位 [积木块])

游戏起因:

上周五,在会议室吃午餐时,同事 (其实是前辈,临时待在上海) 说他小女儿有个课余作业,需要他帮助,就是上面的拼图游戏,

他就用程序员最拿手的方式把这个问题给解决,不过他是使用 c 语言解决出来的,使用 1 分钟多点。

我感觉很好玩,就使用 ruby 试写一下,使用 3x5,3x10 做测试,分别使用 1s,46s 左右跑出结果来,但计算 3x20 时跑不出结果来 (1 小时以上).

当前困惑:

我认为是代码(没有使用 ruby 最合适的用法)或算法(多使用递归,可能使用不得当)写的不好,所以才有此救助贴。

下面我会把代码的解法思路,认为的瓶颈简单描述一下。

游戏思路:

  1. 5 个 [积木块] 可以拼成 12 种 [积木条] 形状类型,每个形状类型旋转、翻转等可以组成 63 种 [积木条] 形状。 (由于 [拼盘] 深度为 3,过滤一下只有 50 种 [积木条] 形状)
  2. 递归尝试每一个 [积木条] 形状

    1 [积木条] 形状深度大于 3,直接跳过 2 使用一个 [积木条] 形状后,把该 [积木条] 类型的所有形状都标记一下,下次遇到直接跳过 3 递归遍历 [拼盘] 中所有连续的空白块 (感觉此处代码有很大优化空间),数量都应该除 5 余 0,否则跳过 4 [积木条] 形状在 [拼盘] 上找不到放置,跳过 5 把 [积木条] 形状放置到 [拼盘] 上 6 是否拼满了

    1 yes 打印 2 no,继续尝试下一个 [积木条] 形状

其中为了便于区分 [积木条] 形状,有对每种 [积木条] 类型对应一个符号,要不然,打印出来,全是 1,同时也为了 uniq 一下。

相关说明:

上周五晚上就把 3x5 的测试跑出来了,但需要 28s,这几天一直在优化代码 (现在需要 1s),但还是跑不出 3x20 的结果。

其中尝试对 3x5 的结果再操作,最终实现 3x20,这条路不行的,3x5 的结果集包含的 [积木条] 类型是互斥的,经计算只能两两组合,实现 3x10.

对于写出的代码跳不出结果来,感觉很无奈...压箱底不管,还不如发个贴,救助学习一下。

代码文件:

https://github.com/jay16/phantom/tree/master/bricks

util.rb - 通用代码(复制对象,打印等) shapes.rb - 处理 [积木条] 形状 adapter.rb - 处理 [积木条] 形状与 [拼盘] 位置 bricks.rb - 调用上面三个文件 _test.rb - 测试代码

可以针对解法逻辑、代码风格、命令规范、测试规范进行批评。 (当前状态感觉自己的代码很丑陋)

贴一下电脑配置,

编辑中的树状列表如何排版?

全部解还是一个解。。。

@Kabie 目前的状态,能出一个解也不错。可以说一下思路吗?

提高这种算法的效率在于对某些条件下的分支限制,也叫做"剪枝"。比如说在拼盘的边缘部分,就可以限制积木的种类。

@heliang7 有道理,谢谢

@heliang7

all_slutions.select { |s| s.is_ok }.each do |s|
  ....
end
all_solutions.each do |s| 
  next if not s.is_ok
  ....
end

对这种算法,上面两种用法,前者算"剪枝"吗?

是俄罗斯方块游戏的延伸吧?给你固定的积木条,去填充棋盘,唯一不同的是 Tetris 是用 4 块积木组成的积木条,而你这个问题是用 5 块积木。

@quakewang 对的,是同事女儿的课外作业。

更难了,5 块积木可以拼成 12 种类型,3x20 就可以放 12 种个积木条(要求不重复),所以必须遍历所有类型的积木去尝试。

俄罗斯方块游戏生成不同形状的规则或顺序也不知道是怎么定义的。

希望我没理解错这个题目的意思。

觉得可以换个思路,就是把 bricks(积木) 往上面填。 代码在这, https://gist.github.com/yfractal/9fd567789ec0ef1534d0

结果看起来还不错,但我只检查第一个解。。。

有很多可重构的点,但觉得都是些小的改动。没时间,你先凑合着看吧。。。(Bricks 换个存储结构比较好些)

关键点有两个,一个是,尝试着创建积木,一个是递归。

选择创建积木的原因是,你在可能的积木中挑的话,然后在看是否合适,复杂度太高了,而且应该和创建的方法是等价的。但这是我猜的,没试着证明,也没看过你的代码。。。

不建议 “动” 拼盘 里面的东西,动的话,会带来很高的复杂度。直接 copy 一份其实也没什么

这个问题也没用多少空间,而且随着拼盘被填满,做的尝试会越来越少,而且才 10 几秒就停了。所以就没考虑优化的问题。

@jay_li 我想问问你朋友小女儿是多小?这题有难度的哟!

@hiveer 没有问,这只是课外作业,可能主要是来培养小朋友发散性思维吧。

#6 楼 @jay_li 没有详细看算法,个人认为这个的确缩小了继续运算的范围,就算” 剪枝 “了。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号