魔方吧·中文魔方俱乐部

标题: 叹为观止的程序 [打印本页]

作者: aubell 时间: 2010-1-20 19:30:39 标题: 叹为观止的程序

#include <string>
#include <iostream>
using namespace std;

string data = "2#6'&78)5+1/AT[NJ_PERLQO@IAHPNSMBJCKLRMSDHEJNPOQFKGIQLSNF@DBROPMAGCEMPOACSRQDF";
char inva [48], b [48], cur_phase, search_mode, history_idx, history_mov [48], history_rpt [48], depth_to_go[5 << 20], hash_table [48][6912];

struct Cubelet { char pos, twi ;} cubelet [48];

void rot(char cur_phase ){
if ( cur_phase < 4)
for (int i = -1; ++ i < 25%21 ;)
cubelet[64^data[20+cur_phase*8+i ]].twi =
(cubelet[64^data[20+cur_phase*8+i ]].twi + 2 - i%2) % 3, cubelet[64^data[20+cur_phase*8+i +4 ]].twi ^= cur_phase < 2;
for (int i = -1; ++ i < 28%21 ;)
swap(cubelet[64^data[20+cur_phase*8+i +(i!=3) ]], cubelet[64^data[20+cur_phase*8+i ]] );
;}

int hashf( ){
int ret = 0;
switch(cur_phase ){
case 0:
  for (int i = -1; ++ i < 32%21 ;) ret += ret + cubelet [i ]. twi;
  return ret;

case 1:
  for (int i = -1; ++ i < 49%21 ;) ret = ret*3 + cubelet [i +12]. twi;
  for (int i = -1; ++ i < 53%21 ;) ret += ret + (cubelet [i ]. pos > 7 );
  return ret-7;

case 2:
  for (int i = -1; ++ i < 71%21 ;)
if ( cubelet [i +12]. pos<16) inva[cubelet [i +12]. pos&3] = ret++; else b [i -ret] = cubelet [i +12]. pos&3;
for (int i = -1; ++ i < 91%21 ;) ret += ret + (cubelet [i ]. pos > 3 );
for (int i = -1; ++ i < 91%21 ;) ret += ret + (cubelet [i +12]. pos > 15 );
  return ret*54 + (inva[b[0 ]] ^inva[b[ 1 ]] )*2 + ((inva[b[0 ]] ^inva[b[ 2 ]] ) > (inva[b[0 ]] ^inva[b[ 3 ]] )) - 3587708;
  }

for (int i = -1; ++ i < 110%21 ;) {
ret *= 24; int cur_phase;
for (cur_phase = -1; ++ cur_phase < 4 ;) for (int k = -1; ++ k < cur_phase ;)
if ( cubelet [i *4+cur_phase].pos < cubelet [i *4+k].pos) ret += cur_phase << cur_phase/3 ;
}
return ret/2;
}

int do_search(int dpt ){
int h = hashf(), q = cur_phase/2*19+8 << 7;
if ( (dpt < hash_table[cur_phase ][h%q] | dpt < hash_table[cur_phase+4][h/q]) ^ search_mode ){
if ( search_mode)
if ( dpt <= depth_to_go[h]) return !h;
else depth_to_go[h] = dpt;

hash_table[cur_phase ][h%q] <?= dpt;
hash_table[cur_phase+4][h/q] <?= dpt;

for (int k = -1; ++ k < 6 ;)
for (int i = -1; ++ i < 130%21 ;) {
rot(k );
if ( k < cur_phase*2 & i != 1 || i > 2) continue;
history_mov[history_idx] = k;
history_rpt[history_idx++] = i;
if ( do_search(dpt-search_mode*2+1)) return 1;
history_idx--;
}
}
return 0;
}

int main(int, char** arg ){
memset(hash_table, 6, sizeof(hash_table) );
for (int i = -1; ++ i < 146%21 ;) cubelet [i ]. pos = i ;
for (cur_phase = -1; ++ cur_phase < 4 ;) do_search(0 );
for (int i = -1; ++ i < 146%21 ;) {
  string s = arg [i +1] + string("!" );
  cubelet [i ]. pos = data.find(s[0] ^ s[1] ^ s[2] );
  int x = min(s.find(85), s.find(68) );
  cubelet [i ]. twi = ~x ? x : s[0]>70;
}

for (int i = -1; ++ i < 152%21 ;)
  swap(cubelet[64^data[20+cur_phase*8+i +16 ]], cubelet[64^data[20+cur_phase*8+i +21 ]] );

search_mode = 1;

for (cur_phase = -1; ++ cur_phase < 4 ;)
  for (int i = -1; ++ i < 167%21 ;) if ( do_search(i)) break;
for (int k = -1; ++ k < history_idx ;)
  cout << "FBRLUD"[history_mov[k ]] << history_rpt[k]+1 << " ";
return 0;
}

作者: aubell 时间: 2010-1-20 19:32:06

程序来源：http://tomas.rokicki.com/cubecontest/winners.html
这里面第一名的程序就是了。
原来的程序是用宏写的，比较难读点。我已经用g++展开了，还是如天书一般。

编译用g++

调用时按照如下顺序
UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
输入

[ 本帖最后由 aubell 于 2010-1-20 19:38 编辑 ]

作者: yaorendechong 时间: 2010-1-20 19:37:26

没看懂？？？？？？？？？？？？？？

作者: kang1994 时间: 2010-1-20 19:38:21

看不懂啊.................

作者: Paracel_007 时间: 2010-1-20 19:39:42

怎么不给个下载？代码看着晕…

作者: wwd_meng 时间: 2010-1-20 19:42:31

不知道是什么啊……
本人还没学习过计算机编程啦

作者: wzj_xp 时间: 2010-1-20 19:48:21

看不懂。。
变成汗语了

作者: Paracel_007 时间: 2010-1-20 19:57:13

才看到2楼~
不过，干什么用的？手机党，不明白

作者: aubell 时间: 2010-1-20 20:04:30

测试了许多状态，一般都在30步左右。
最难得的是用如此简短的程序实现了状态集转换法！
而且运行速度相当快，并且不使用外部的表。

作者: aubell 时间: 2010-1-20 20:10:57 标题: 回复 8# 的帖子

当然是解魔方用的。
例如打乱用 F- U+ F- D- L- D- F- U- L2 D- ，按照上面的顺序，就输入
progname RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU

Aubell所作下一版的RCube将集成这个程序，作为内置的状态集转换法。实在钦佩原作者。

作者: oyyq99999 时间: 2010-1-20 20:31:42

貌似是stefan pochmann写的

作者: raka 时间: 2010-1-20 21:33:07

好像用C＋＋就能读懂了…… 再看看

作者: aubell 时间: 2010-1-20 22:27:56 标题: 回复 11# 的帖子

这个是 Tomas Sirgedas写的, Ann Arbor, MI, USA 874
pochmann的那个是第二名

作者: aubell 时间: 2010-1-22 11:55:50

观止啊，观止！顶顶，让更多的人欣赏一下如此强悍的程序。

作者: 爱如潮水 时间: 2010-1-22 15:26:00

楼主是来晕我们的~~

作者: noski 时间: 2010-1-22 15:57:51

顶一下，那个程序的本来面目被谁发在水木上了，很强大。。

修改了一下那个奇怪的运算符"<?="，原来a<?=b相当于a=min(a,b)。
修改了一下min函数，在VC++中可以编译了。
另外，可读性变好了一点。。
附件是编辑结果，可以试着算一算。。

[ 本帖最后由 noski 于 2010-1-22 18:03 编辑 ]

附件: rubik_cpp.rar (2010-1-22 18:03:45, 7.12 KB) / 下载次数 99
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=ODY1ODN8MGFmZDVmZjJ8MTczNDQ5MzE5MnwwfDA%3D

作者: aubell 时间: 2010-1-23 22:38:10

noski排版的很漂亮啊！大家快来下。
期待高手分析这个代码。

作者: rjhabc 时间: 2010-7-25 17:53:58

怎么用上面的改过的程序算出来的结果不能还原啊

作者: aa65535 时间: 2010-12-9 20:58:03

完全看不懂

作者: L08 时间: 2010-12-23 08:47:33

果然叹为观止！完全看不懂。不过应该是好东东。

作者: lyy00000001 时间: 2010-12-26 16:30:14

啊这到底是什么东东完全看不懂

作者: aubell 时间: 2011-3-14 20:13:04 标题: 回复 18# 的帖子

这个跟编译器和平台有关。gcc里的min是一个宏，
在VC下，定义min函数，你要把min函数的返回值和参数都改成unsigned型才可以。
非常抱歉这么久了才回复你。
因为我一直用原始的程序编译的，没有发现这个问题。

作者: aubell 时间: 2011-3-14 20:30:07 标题: 回复 16# 的帖子

noski,不知道那个min是否引入了bug。在我的电脑上确实解不出。
把min的参数和返回值改成unsigned类型才可以。
你如果看到，能否测试一下？

作者: ダ跳跳♂糖 时间: 2011-3-25 21:24:53

我只会VB和FP编程······

作者: Manted 时间: 2011-5-26 16:35:19

试用了一下上面贴的C++代码，发现所有块的位置都能复原，但方向不能复原，请问是什么情况？
原代码可以完美复原么？

作者: 丁云龙521 时间: 2011-6-9 21:57:52

这是使用VB编的吧！！！
但我还是看不明白啊！求高手指点一二！

作者: jinxian 时间: 2011-6-13 17:02:35

　　
　　

回楼上的，人家是用 C 、C++ 等写的。
　　
　　
　　

作者: jshyhzj 时间: 2011-6-27 21:02:39 标题: 人类不容易看懂的程序不是好程序

资深开发人员评价，不要羡慕别人的程序写的多么神奇，简洁易读的程序才是好程序

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)