操纵栅格！
操纵栅格！
提问于 2016-11-14 07:31:16
简报会
你是一个机器人，在一个二维网格中，向北、南、东和西无限延伸。当给出一个数字时，你必须移动机器人，这样你才能到达目标号码。
下面是网格的工作方式：
你可以朝四个方向移动:北、南、东或西。一旦你离开了一个单元格，你就不允许再次回到那个单元格(非常有效，它已经从地图上删除了)。
有一个“计数器”，上面写着1234567890 (所以它从1到2.一直到9，再到0，再回到1 )，每次移动都会发生变化。
您还有一个"value"，它从0开始。
一旦你朝任何方向移动，数学运算就会发生，这取决于你移动的方向：
- 北方:您的价值是通过计数器(
value += counter)增加的。 - 东方:您的值由计数器(
value -= counter)递减。 - 南方:您的值乘以计数器(
value *= counter)。 - 韦斯特:你的价值除以计数器(
value /= counter)。- 除法是整数除法，所以是
5/2 -> 2。 - 你不允许被
0除法。
- 除法是整数除法，所以是
示例：
如果机器人向北移动3次：
- 第一个“北方”移动将计数器增加到
1，并将其添加到值(现在为1)中。 - 第二个“北方”移动将计数器增加到
2，并将其添加到值(现在为3)中。 - 第三个“北方”移动将计数器增加到
3，并将其添加到值(现在是6)中。
最后一个值是6。
向北移动，然后再向南移动：
- 第一个“北方”移动将计数器增加到
1，并将其添加到值(现在为1)中。 - 第二个“南”移动错误，因为机器人试图移动的单元被移除(从第一个移动)。
没有最终值，因为机器人出错了。
挑战
您的挑战是，当给定一个数字时，编写一个程序，为机器人生成合适的进入方向，以便bot的最终值等于该数字。
因此，如果数字是6，则有效的解决方案是：
nnn(机器人连续三次向北移动)。
您的测试值是：
49445094, 71259604, 78284689, 163586986, 171769219, 211267178, 222235492, 249062828, 252588742, 263068669, 265657839, 328787447, 344081398, 363100288, 363644732, 372642304, 374776630, 377945535, 407245889, 467229432, 480714605, 491955034, 522126455, 532351066, 542740616, 560336635, 563636122, 606291383, 621761054, 648274119, 738259135, 738287367, 748624287, 753996071, 788868538, 801184363, 807723631, 824127368, 824182796, 833123975, 849666906, 854952292, 879834610, 890418072, 917604533, 932425141, 956158605, 957816726, 981534928, 987717553(这是50个随机数，从10亿到10亿。)
你的分数是为所有50个数字所做的移动总数-移动越少，越好。在平手的情况下，先前提交代码的人获胜。
规范
- 您保证接收一个正整数作为输入。
- 对于生成的路径，您的
value变量不能在2^31-1或-2^31以下的任何一点上运行。 - 您的最终程序必须符合一个答案(所以，
< 30,000字节)。 - 你只能硬编码10个号码。
- 对于任何测试用例，程序必须在合理的膝上型计算机上运行5分钟。
- 每次对每个数字运行程序时，结果都必须相同。
回答 3
Code Golf用户
回答已采纳
发布于 2016-11-14 12:30:21
C++：得分= 453,324,048
好的，需要一些时间来重做这个，但这是我解决它的方法。
在研究了解决方案空间之后，我决定我的策略是：
- 使用南部步骤以接近目标号码。
- 如果目标为正，请遵循以下路径: nnnesssssessssssss
- 如果目标为负值，请遵循以下路径: esssssssseessssss c.如果目标介于0到20之间，请按“旧方式”求解(对所有可能的路径进行跟踪和错误，直到我们到达它)。
- 一旦我们有了“最好的地方”(接近目标，而不是“越过”)，我们就可以通过乘以2或3来接近目标；所以向东走0到9步，然后向南走一步。保持最接近目标的路径。
- “跑”北，或东边，直到我们距离目标在45分以内(每往北10步，往北加45分，如wise，每10步往东，减少45分)。
- 朝同一个方向再走几步，直到我们到达目标的10点以内。
- 从这个意义上讲，做“旧时尚之路”，现在应该没那么难了。
我的结果是:总分是453324048
以及道路：
0) to reach 49445094, it takes 1311037 steps, by doing: nnnesssssesssssseeeeese(n * 1311010)enen
1) to reach 71259604, it takes 1320313 steps, by doing: nnnesssssesssssseeeeeese(n * 1320280)nnnnnneee
2) to reach 78284689, it takes 1956998 steps, by doing: nnnesssssesssssseeeeeees(e * 1956970)eeee
3) to reach 163586986, it takes 2483885 steps, by doing: nnnesssssessssssse(n * 2483860)nnnnnnn
4) to reach 171769219, it takes 4302163 steps, by doing: nnnesssssessssssse(n * 4302130)nnnnnnnnnnennnn
5) to reach 211267178, it takes 13079485 steps, by doing: nnnesssssessssssse(n * 13079460)nnnnnen
6) to reach 222235492, it takes 15516886 steps, by doing: nnnesssssessssssse(n * 15516860)nnnnnnnn
7) to reach 249062828, it takes 12390325 steps, by doing: nnnesssssessssssseeees(e * 12390290)eeeeenenneene
8) to reach 252588742, it takes 11606785 steps, by doing: nnnesssssessssssseeees(e * 11606760)een
9) to reach 263068669, it takes 9277915 steps, by doing: nnnesssssessssssseeees(e * 9277880)eeeeenennneee
10) to reach 265657839, it takes 8702543 steps, by doing: nnnesssssessssssseeees(e * 8702510)eeeeenennee
11) to reach 328787447, it takes 5326312 steps, by doing: nnnesssssessssssseeeese(n * 5326280)nnnnennnn
12) to reach 344081398, it takes 8724966 steps, by doing: nnnesssssessssssseeeese(n * 8724940)enn
13) to reach 363100288, it takes 12951386 steps, by doing: nnnesssssessssssseeeese(n * 12951360)enn
14) to reach 363644732, it takes 13072373 steps, by doing: nnnesssssessssssseeeese(n * 13072340)nnnnnnnnen
15) to reach 372642304, it takes 15071833 steps, by doing: nnnesssssessssssseeeese(n * 15071800)nnnnnnnenn
16) to reach 374776630, it takes 15546133 steps, by doing: nnnesssssessssssseeeese(n * 15546100)nnnnnenene
17) to reach 377945535, it takes 16250331 steps, by doing: nnnesssssessssssseeeese(n * 16250300)nnnnennn
18) to reach 407245889, it takes 11107325 steps, by doing: nnnesssssessssssseeeees(e * 11107300)ne
19) to reach 467229432, it takes 2222403 steps, by doing: nnnesssssessssssseeeeese(n * 2222370)nnnnnnnee
20) to reach 480714605, it takes 5219109 steps, by doing: nnnesssssessssssseeeeese(n * 5219080)neenn
21) to reach 491955034, it takes 7716983 steps, by doing: nnnesssssessssssseeeeese(n * 7716950)nnnnennnn
22) to reach 522126455, it takes 14421745 steps, by doing: nnnesssssessssssseeeeese(n * 14421710)nnnnnneneee
23) to reach 532351066, it takes 16693875 steps, by doing: nnnesssssessssssseeeeese(n * 16693850)n
24) to reach 542740616, it takes 14866179 steps, by doing: nnnesssssessssssseeeeees(e * 14866150)eeeen
25) to reach 560336635, it takes 10955953 steps, by doing: nnnesssssessssssseeeeees(e * 10955920)eeeeennen
26) to reach 563636122, it takes 10222731 steps, by doing: nnnesssssessssssseeeeees(e * 10222700)eeeeene
27) to reach 606291383, it takes 743785 steps, by doing: nnnesssssessssssseeeeees(e * 743760)e
28) to reach 621761054, it takes 2693968 steps, by doing: nnnesssssessssssseeeeeese(n * 2693940)nnn
29) to reach 648274119, it takes 8585761 steps, by doing: nnnesssssessssssseeeeeese(n * 8585730)nnnnnn
30) to reach 738259135, it takes 5286413 steps, by doing: nnnesssssessssssseeeeeees(e * 5286380)eeneneee
31) to reach 738287367, it takes 5280141 steps, by doing: nnnesssssessssssseeeeeees(e * 5280110)nneenn
32) to reach 748624287, it takes 2983042 steps, by doing: nnnesssssessssssseeeeeees(e * 2983010)eeeenee
33) to reach 753996071, it takes 1789313 steps, by doing: nnnesssssessssssseeeeeees(e * 1789280)eeeennee
34) to reach 788868538, it takes 5960183 steps, by doing: nnnesssssessssssseeeeeeese(n * 5960150)nnenene
35) to reach 801184363, it takes 8697033 steps, by doing: nnnesssssessssssseeeeeeese(n * 8697000)nnenene
36) to reach 807723631, it takes 10150197 steps, by doing: nnnesssssessssssseeeeeeese(n * 10150170)n
37) to reach 824127368, it takes 13795475 steps, by doing: nnnesssssessssssseeeeeeese(n * 13795440)nnnnnnnne
38) to reach 824182796, it takes 13807795 steps, by doing: nnnesssssessssssseeeeeeese(n * 13807760)nnnnnenee
39) to reach 833123975, it takes 15794722 steps, by doing: nnnesssssessssssseeeeeeese(n * 15794690)nennnn
40) to reach 849666906, it takes 14397917 steps, by doing: nnnesssssessssssseeeeeeees(e * 14397880)eeeeeeeenee
41) to reach 854952292, it takes 13223389 steps, by doing: nnnesssssessssssseeeeeeees(e * 13223350)eeeeeeeeneeen
42) to reach 879834610, it takes 7693981 steps, by doing: nnnesssssessssssseeeeeeees(e * 7693950)eeenn
43) to reach 890418072, it takes 5342102 steps, by doing: nnnesssssessssssseeeeeeees(e * 5342070)eeennn
44) to reach 917604533, it takes 699395 steps, by doing: nnnesssssessssssseeeeeeeese(n * 699360)nnnneene
45) to reach 932425141, it takes 3992863 steps, by doing: nnnesssssessssssseeeeeeeese(n * 3992830)nennnn
46) to reach 956158605, it takes 9266963 steps, by doing: nnnesssssessssssseeeeeeeese(n * 9266930)nnnnen
47) to reach 957816726, it takes 9635434 steps, by doing: nnnesssssessssssseeeeeeeese(n * 9635400)nnnennn
48) to reach 981534928, it takes 14906145 steps, by doing: nnnesssssessssssseeeeeeeese(n * 14906110)nnnnnnnn
49) to reach 987717553, it takes 16280059 steps, by doing: nnnesssssessssssseeeeeeeese(n * 16280030)nn我确信有一种方法可以通过做一些“南/西”动作(除以4，乘以5，例如)来改进这一点；但是编写代码，并确保你不超过圈或被困住，是很棘手的。
另一种解决方案，可能是尝试从目标返回到“合理”的数字，然后，只需找到一条通向较小数目的路径；但您必须将其“瞄准”正确，以便步数与之匹配。很棘手，但可能是解决这个问题的最好方法。
总之，这是我的代码：
#include <stdio.h>
#include <vector>
#include <queue>;
using namespace std;
long long upperLimit;
long long lowerLimit;
bool bDebugInfo = false;
//bool bDebugInfo = true;
// a point struct (x and y)
struct point
{
int x;
int y;
point():x(0),y(0)
{
}
bool operator ==(const point& other)
{
return (x==other.x) && (y==other.y);
}
void ApplyDirection(char direction)
{
switch (direction)
{
case 'n':
y++;
break;
case 'w':
x--;
break;
case 'e':
x++;
break;
case 's':
y--;
break;
}
}
};
// each state is of this formate
struct botState
{
int nStep;
long long number;
vector<char> path;
botState()
:nStep(0),
number(0)
{
}
botState* clone()
{
botState* tmp = new botState();
tmp->nStep = nStep;
tmp->number = number;
tmp->path = path;
return tmp;
}
void clone(botState* other)
{
nStep = other->nStep;
number = other->number;
path = other->path;
}
};
bool changeNumberWithDirection(long long &number, char direction, int step)
{
switch (direction)
{
case 'n':
number += (step%10);
break;
case 'w':
if (step%10)
number /= (step%10);
else
return false;
break;
case 'e':
number -= (step%10);
break;
case 's':
number *= (step%10);
break;
default:
return false;
}
return true;
}
bool tryToAddStep(queue<botState*>& queueOfStates, const botState* pState, char direction, char cStarDirection)
{
botState* pTmpState;
long long newNumber;
int newStep = pState->nStep+1;
newNumber = pState->number;
if (!changeNumberWithDirection(newNumber, direction, newStep))
return false;
if (newNumber > upperLimit)
return false;
if (newNumber < lowerLimit)
return false;
if ((newNumber == 0) && (newStep%10 == 0))
return false; // no need to return back to 0 after 10 or more steps, we already have better ways to do this.
// build the x,y points of the path up to this point
point tmpPoint;
vector<point> pointsInPath;
pointsInPath.push_back(tmpPoint);
for (int i=0; i<pState->path.size(); i++)
{
if (pState->path.at(i) == '*')
{
for (int j=0; j<100; j++)
{
tmpPoint.ApplyDirection(cStarDirection);
pointsInPath.push_back(tmpPoint);
}
}
else
{
tmpPoint.ApplyDirection(pState->path.at(i));
pointsInPath.push_back(tmpPoint);
}
}
tmpPoint.ApplyDirection(direction);
// check for over lap
for (int i=0; i<pointsInPath.size(); i++)
{
if (tmpPoint == (pointsInPath.at(i)))
return false;
}
pTmpState = new botState();
pTmpState->nStep = newStep;
pTmpState->number= newNumber;
pTmpState->path = pState->path;
pTmpState->path.push_back(direction);
queueOfStates.push(pTmpState);
return true;
}
bool isBetterNum(long long newNum, long long oldBest, long long target)
{
long long newDiff = (newNum > target) ? newNum - target : target - newNum ;
long long oldDiff = (oldBest > target) ? oldBest - target : target - oldBest;
return (newDiff < oldDiff);
}
bool tryToJumpDown(long long num, botState* pState, int& nTimes)
{
// if where the bot is, we have a clear path to go as far east as we could ever want, we can just do as many sets of eeeeeeeeee (e*10) as needed, til we are close enough to the target
point tmpPoint;
vector<point> pointsInPath;
pointsInPath.push_back(tmpPoint);
for (int i=0; i<pState->nStep; i++)
{
tmpPoint.ApplyDirection(pState->path.at(i));
pointsInPath.push_back(tmpPoint);
}
for (int i=0; i<pointsInPath.size(); i++)
{
if ((pointsInPath.at(i).x > tmpPoint.x) && (pointsInPath.at(i).y == tmpPoint.y))
return false; // we have a point blocking our path up!
}
long long tmpTimes = (pState->number - num)/45;
if ((tmpTimes>1) && (tmpTimes<upperLimit))
{
tmpTimes--;
tmpTimes*=10;
nTimes = (int)tmpTimes;
pState->nStep+=nTimes;
pState->number-=(tmpTimes/10)*45;
pState->path.push_back('*');
return true;
}
return false;
}
bool tryToJumpUp(long long num, botState* pState, int& nTimes)
{
// if where the bot is, we have a clear path to go as far north as we could ever want, we can just do as many sets of nnnnnnnnnn (n*10) as needed, til we are close enough to the target
point tmpPoint;
vector<point> pointsInPath;
pointsInPath.push_back(tmpPoint);
for (int i=0; i<pState->nStep; i++)
{
tmpPoint.ApplyDirection(pState->path.at(i));
pointsInPath.push_back(tmpPoint);
}
for (int i=0; i<pointsInPath.size(); i++)
{
if ((pointsInPath.at(i).x == tmpPoint.x) && (pointsInPath.at(i).y > tmpPoint.y))
return false; // we have a point blocking our path up!
}
long long tmpTimes = (num - pState->number)/45;
if ((tmpTimes>1) && (tmpTimes<upperLimit))
{
tmpTimes--;
tmpTimes*=10;
nTimes = (int)tmpTimes;
pState->nStep+=nTimes;
pState->number+=(tmpTimes/10)*45;
pState->path.push_back('*');
return true;
}
return false;
}
typedef char* PChar;
bool buildPath(long long num, PChar& str, int& nLen, int& nScore, botState* startState, int nTimes)
{
long long nBest = 0;
int nMaxSteps = 0;
long long nMax = 0;
long long nMin = 0;
int nCleanUpOnStep= 12;
long long nFromLastCleanUp = 0;
bool bInCleanUp = false;
char cDirection = ' ';
if (nTimes>0)
cDirection = 'n';
else if (nTimes<0)
{
cDirection = 'e';
nTimes*=-1;
}
if (startState->nStep >= nCleanUpOnStep)
nCleanUpOnStep= startState->nStep+10;
str = NULL;
nLen = 0;
botState* bestState = new botState();
bestState->clone(startState);
queue<botState*> queueOfStates;
queueOfStates.push(bestState); // put the starting state into the queue
while (!queueOfStates.empty()) // while we still have states in the queue, process them
{
botState* pState = queueOfStates.front();
queueOfStates.pop(); // take a state out of the queue
if (!str) // no solution yet
{
if (pState->number == num) // check if this is a solution
{
// we solved it!
int nOffset=0;
nLen = pState->nStep - nTimes + 17;
str = new char[nLen+1];
if (bDebugInfo)
printf("solved!\n");
nScore = pState->nStep;
for (int i=0; i<pState->path.size(); i++)
{
if (pState->path.at(i)=='*')
{
sprintf(str+i, "(%c * %11d)", cDirection, nTimes);
if (bDebugInfo)
printf("(%c * %11d)", cDirection, nTimes);
nOffset=16;
}
else
{
str[i+nOffset] = pState->path.at(i);
if (bDebugInfo)
printf("%c", str[i+nOffset]);// print solution while making the string
}
}
if (bDebugInfo)
printf("\n");
str[nLen]='\0';
}
else
{ // no solution yet, we need to go deeper
if (pState->number < nMin)
nMin = pState->number;
if (pState->number > nMax)
nMax = pState->number;
if ((!bInCleanUp) && (queueOfStates.size()>1000000))
{
nCleanUpOnStep=nMaxSteps+10;
bInCleanUp = true;
}
if (pState->nStep > nMaxSteps)
{ // a little tracing, so we can see progress
nMaxSteps = pState->nStep;
// printf("current states have %d steps, reached a max of %lld, and a min of %lld\n", nMaxSteps, nMax, nMin);
if (nMaxSteps >= nCleanUpOnStep)
{
nCleanUpOnStep+=10;
bInCleanUp = true;
}
}
if (isBetterNum(pState->number, nBest, num))
{ // a little tracing, so we can see progress
nBest = pState->number;
if (bDebugInfo)
printf("Got closer to the target, %lld, with %d steps (target is %lld, diff is %lld)\n", nBest, pState->nStep, num, num-nBest);
if (bestState != pState)
delete bestState;
bestState = pState;
}
if (!bInCleanUp)
{
tryToAddStep(queueOfStates, pState, 'n', cDirection);
tryToAddStep(queueOfStates, pState, 'e', cDirection);
if (!nTimes) // once we did the "long walk in one direction" don't do the west or south moves any more
{
tryToAddStep(queueOfStates, pState, 'w', cDirection);
tryToAddStep(queueOfStates, pState, 's', cDirection);
}
}
}
}
if (pState!=bestState)
delete pState; // this is not java, we need to keep the memory clear.
if ((bInCleanUp) && (queueOfStates.empty()))
{
queueOfStates.push(bestState); // put the starting state into the queue
bInCleanUp = false;
long long diff = nFromLastCleanUp-bestState->number;
if (!nTimes)
{
if ((diff>0) && (diff<100))
if (tryToJumpDown(num, bestState, nTimes))
cDirection = 'e';
if ((diff<0) && (diff>-100))
if (tryToJumpUp(num, bestState, nTimes))
cDirection = 'n';
if (nTimes)
nCleanUpOnStep = bestState->nStep;
}
nFromLastCleanUp = bestState->number;
}
}
delete bestState; // this is not java, we need to keep the memory clear.
return str!=NULL;
}
char* positiveSpine = "nnnesssssessssssss";
char* negativeSpine = "esssssssseessssss";
bool canReachNumber(long long num, PChar& str, int& nLen, int& nScore)
{
int nTimes = 0;
botState tmpState;
if ((num>=0) && (num<=20))
return buildPath(num, str, nLen, nScore, &tmpState, nTimes);
botState bestState;
bestState.clone(&tmpState);
char* spine = NULL;
if (num>0)
{
spine = positiveSpine;
}
else
{
spine = negativeSpine;
}
for (int i=0; spine[i]; i++)
{
tmpState.nStep++;
tmpState.path.push_back(spine[i]);
if (!changeNumberWithDirection(tmpState.number, spine[i], tmpState.nStep))
return false;
if ((num>0) && (tmpState.number<num))
{
bestState.clone(&tmpState);
}
else if ((num<0) && (tmpState.number>num))
{
bestState.clone(&tmpState);
}
}
if (bestState.number == num)
return buildPath(num, str, nLen, nScore, &bestState, nTimes);
botState tryPath;
tmpState.clone(&bestState);
for (int i=0; i<9; i++)
{
tryPath.clone(&tmpState);
bool pathOK = true;
for (int j=0; j<i; j++)
{
tryPath.nStep++;
tryPath.path.push_back('e');
if (!changeNumberWithDirection(tryPath.number, 'e', tryPath.nStep))
{
pathOK = false;
break;
}
}
tryPath.nStep++;
tryPath.path.push_back('s');
if (!changeNumberWithDirection(tryPath.number, 's', tryPath.nStep))
{
pathOK = false;
break;
}
if ((pathOK) && (isBetterNum(tryPath.number, bestState.number, num)))
{
bestState.clone(&tryPath);
}
}
// in case we'll need to add, but last step was south, move one to the east.
if ((bestState.path.at(bestState.path.size()-1) == 's') && (bestState.number<num))
{
bestState.nStep++;
bestState.path.push_back('e');
if (!changeNumberWithDirection(bestState.number, 'e', bestState.nStep))
return false;
}
if (bestState.number<num)
{
long long diff = num - bestState.number;
diff/=45;
nTimes = (int)diff*10;
bestState.nStep += nTimes;
bestState.path.push_back('*');
bestState.number += 45*diff;
while (num - bestState.number > 10)
{
bestState.nStep++;
bestState.path.push_back('n');
if (!changeNumberWithDirection(bestState.number, 'n', bestState.nStep))
return false;
}
return buildPath(num, str, nLen, nScore, &bestState, nTimes);
}
else
{
long long diff = bestState.number - num;
diff/=45;
nTimes = (int)diff*10;
bestState.nStep += nTimes;
bestState.path.push_back('*');
bestState.number -= 45*diff;
while (bestState.number - num > 10)
{
bestState.nStep++;
bestState.path.push_back('e');
if (!changeNumberWithDirection(bestState.number, 'e', bestState.nStep))
return false;
}
return buildPath(num, str, nLen, nScore, &bestState, -nTimes);
}
return false;
}
long long aVals[] = {49445094, 71259604, 78284689, 163586986, 171769219, 211267178, 222235492, 249062828, 252588742, 263068669, 265657839, 328787447, 344081398, 363100288, 363644732, 372642304, 374776630, 377945535, 407245889, 467229432, 480714605, 491955034, 522126455, 532351066, 542740616, 560336635, 563636122, 606291383, 621761054, 648274119, 738259135, 738287367, 748624287, 753996071, 788868538, 801184363, 807723631, 824127368, 824182796, 833123975, 849666906, 854952292, 879834610, 890418072, 917604533, 932425141, 956158605, 957816726, 981534928, 987717553};
void main(void)
{
upperLimit = 2147483647; // 2^31 - 1
lowerLimit =-1; // -2^31
lowerLimit *=2147483648; // -2^31
long long num=0;
char* str=NULL;
int nLen = 0;
int nItems = sizeof(aVals)/sizeof(aVals[0]);
int nScore = 0;
long long nTotalScore = 0;
// nItems=1;
for(int i=0; i<nItems; i++)
{
if (canReachNumber(aVals[i], str, nLen, nScore)) //try to reach it
{
printf("%3d) to reach %10lld, it takes %9d steps, by doing: %s\n", i, aVals[i], nScore, str);
nTotalScore+=nScore;
delete str;
}
else
{
if (aVals[i]>0)
printf("Failed to reach %lld, use nenenenenenen..... ('n', followed by %lld pairs of 'en')\n", aVals[i], aVals[i]-1);
else
printf("Failed to reach %lld, use enenenenenene..... ('e', followed by %lld pairs of 'ne')\n", aVals[i], aVals[i]-1);
nTotalScore+=2*aVals[i]-1;
}
}
printf("done, total score is %lld\n", nTotalScore);
return;
}Code Golf用户
发布于 2016-11-14 11:08:24
Python，得分= 56068747912
def move(n):
print("n" + "en" * (n - 1))只需为每个数字打印nenenenenenenen...。
稍后会添加一个解释。
Code Golf用户
发布于 2018-07-23 21:04:06
生锈，score = 1758 (在没有西边的路径中最佳)
使用双向搜索，总共运行50个数字，时间约为7秒。
use std::collections::HashSet;
use std::io::{self, prelude::*};
#[derive(Debug, Eq, Clone, Copy, Hash, Ord, PartialEq, PartialOrd)]
enum Dir {
N,
E,
S,
}
use Dir::{E, N, S};
fn dir_char(dir: Dir) -> char {
match dir {
N => 'n',
E => 'e',
S => 's',
}
}
#[derive(Debug, Eq, Clone, Hash, Ord, PartialEq, PartialOrd)]
struct State {
counter: i32,
value: i32,
next: Dir,
}
fn step(s: &State) -> impl Iterator<Item = State> {
let (values, nexts): (_, &[Dir]) = match s.next {
N => (s.value.checked_add(s.counter), &[N, E]),
E => (s.value.checked_sub(s.counter), &[N, E, S]),
S => (
if s.counter != 0 {
s.value.checked_mul(s.counter)
} else {
None
},
&[E, S],
),
};
let counter = (s.counter + 1) % 10;
values.into_iter().flat_map(move |value| {
nexts.iter().map(move |&next| State {
counter,
value,
next,
})
})
}
fn unstep(s: &State) -> impl Iterator<Item = State> {
let counter = (s.counter + 9) % 10;
(match s.next {
N | E => s.value.checked_sub(counter).map(|value| State {
counter,
value,
next: N,
}),
_ => None,
}).into_iter()
.chain(s.value.checked_add(counter).map(|value| State {
counter,
value,
next: E,
}))
.chain(match s.next {
E | S if counter != 0 && s.value % counter == 0 => {
s.value.checked_div(counter).map(|value| State {
counter,
value,
next: S,
})
}
_ => None,
})
}
fn search(value: i32) -> String {
let mut lefts: Vec<HashSet<State>> = Vec::new();
let mut left = [N, E, S]
.iter()
.map(|&next| State {
counter: 1,
value: 0,
next,
})
.collect::<HashSet<_>>();
let mut rights: Vec<HashSet<State>> = Vec::new();
let mut right = (0..10)
.map(|counter| State {
counter,
value,
next: E,
})
.collect::<HashSet<_>>();
loop {
if let Some(mid) = left.intersection(&right).min() {
let mut path = Vec::new();
let mut mid1 = mid.clone();
for left in lefts.into_iter().rev() {
let mid2 = unstep(&mid1)
.filter(|mid2| left.contains(mid2))
.next()
.unwrap();
mid1 = mid2;
path.push(mid1.next);
}
path.reverse();
let mut mid1 = mid.clone();
for right in rights.into_iter().rev() {
let mid2 = step(&mid1)
.filter(|mid2| right.contains(mid2))
.next()
.unwrap();
path.push(mid1.next);
mid1 = mid2;
}
return path.into_iter().map(dir_char).collect::<String>();
}
if left.len() <= right.len() {
let left1 = left.iter().flat_map(step).collect::<HashSet<_>>();
lefts.push(left);
left = left1;
} else {
let right1 = right.iter().flat_map(unstep).collect::<HashSet<_>>();
rights.push(right);
right = right1;
}
}
}
fn main() {
let stdin = io::stdin();
let values = stdin
.lock()
.lines()
.flat_map(|line| {
line.unwrap()
.split(", ")
.map(|s| s.parse().unwrap())
.collect::<Vec<i32>>()
})
.collect::<Vec<_>>();
for value in values {
println!("{} {}", value, search(value));
}
}输出
49445094 nennesseseenenesseseeseseeeeseess
71259604 nnnnnnessennnessseeesssenesenesses
78284689 ennnesssseeeneenesenesssseeesese
163586986 ennnesesseneeeeessennesseeseseeneesen
171769219 ennnessenessssessseesesseeseenesee
211267178 sennnnneseeenessssenessssenenneseseee
222235492 ennnnnesseeeneseesseeesseseneesseesee
249062828 nnnnnesseneneseesssenennesseenesse
252588742 nennnessenneeeessesesesseseeseseeseee
263068669 nennnesseessseeessseesseeenesesssen
265657839 nnnesssseneesesssennneenesseeeses
328787447 eennnesssenesseesssesennnneeseenese
344081398 sennnnesennnesesessesesssseeseennnn
363100288 sennnnesseeneseesssenneesessennenee
363644732 nnnesssenneessesseeesseseseesenees
372642304 nnnnesseneseneseesseneneesssennesese
374776630 sennnnesseseesseneseeeseseessenesen
377945535 nnnesssseneeennesseesseeessseeses
407245889 nnnesseneesessseseseeeeessessenenee
467229432 nnnnesesennnnnesessesessesseeneess
480714605 nnnnessennneseesssenenesenesseesesen
491955034 nnnnnessseeneeeessseeeseenesseseeee
522126455 nnnnesssseeneeesesseesesseeeenese
532351066 nennnessenneeenesesesesessessesenesen
542740616 sennnnesseeneenesssesseenesseesesesen
560336635 nnnesssesesesssseeennessseseeneee
563636122 sennnnnesennneseseennesesssesenesenes
606291383 nnnessssenneeeseseseeseseeeeseesese
621761054 nnnessseennessesssenneeseseseess
648274119 nnnnessseneesseseeseenessseeneseeese
738259135 eennnnnesenennnesseneessssssennnees
738287367 nnnessesseessseseseneeesesseennen
748624287 nennnesseesseeenneseessseseeseneseseese
753996071 nnnnessseneeeseesssenesesenennnesesen
788868538 nnnessesseeseeeneeseesesseesseseeseee
801184363 ennnesseseeseeeeseseeeeseeseseessse
807723631 nnnessessessssesseennnnesssen
824127368 nnnnessesenessseseennnessseesesennnnn
824182796 nnnnessesenesssseenesssesssenesee
833123975 ennnnnneseeeennnessesssessseennnneeesse
849666906 sennnessseeeeseesesesssenesseneeeesen
854952292 nnnnnnesenenesssseeneeessessseseeeeeeee
879834610 nennnnesseessseneeseeesessseseneee
890418072 nnnesssennnnessesesennnesessennnnees
917604533 ennnnesseneeseeesesenennesesseeneesse
932425141 ennnnesssesseesesenesssessseeneesen
956158605 nnnnesseseeeeesesssennneseseenesseee
957816726 enennnesseseeseesseessessssenesss
981534928 eennnessennessseesseesessseenessseenn
987717553 nnnessseeneeesssesseesssesennessee页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/99717
复制相关文章
相似问题
腾讯云开发者
