GDD2011用DevQuizのスライドパズルを(手抜きで)やってみたら4700問止まり

By Yoshichika

September 14, 2011

2011年のDevQuizお疲れ様でした。とりあえず、147点台でした。 GDD行けるかな? 最近遠出したいと思うと必ず悪天候に見舞われるんだよなー。。。 make -j4使ってインチキマルチコア稼働させてみたり。

全く誰の参考にならないけど、ちょっとは頑張った証ということで、ソースを晒してみる。

# g++ -O3 -o solveGDDQuiz -std=gnu++0x main.cpp SolutionNode.cpp solveQuiz.cpp
# g++ -O3 -o checkGDDQuiz solutionChecker.cpp
# mkdir ans
# mkdir left
# ./checkGDDQuiz < problem.txt > /dev/null
(Makefileのtimeoutコマンドの第1引数を10秒くらいに設定)
# make -j4 -k
(たぶん、この1回目で4200問は解けた。Corei5-2400+8GByteMemで1時間くらい)
# rm -f left/*
# ./checkGDDQuiz < problem.txt > result.txt
(Makefileのtimeoutコマンドの第1引数を30秒くらいに設定)
# make -j3 -k
(以下9～12行目を調整しながら気が済むまで繰り返し)

今になってソース見ると、どう見てもC++11の"unordered_map"が使いたかっただけです。本当に有難うござ(略)。まぁ、なんとか承認まで漕ぎ着けたということで。

アルゴリズムは、正直M.Hiroi先生のヒューリスティック探索をそのまま使っているだけです。本当にすいませんでした。 LL苦手だ。。。あと、自作stringもどっか参考にしたけど、場所忘れた。。。

DevQuiz期間中は『SUPER』や『ピラニア3D』とか観に行ったり、外出したり、正直に言うと動き始めたのが9/6くらいからだったので、もうこんなもんでいいや、と思って特に工夫する余裕もなし。マンハッタン距離くらいはもうちょっと工夫しても良かったんじゃないか、とは今になって思う。

main.cpp

#include <iostream>
#include <string>

using namespace std;

string solveQuiz(char xSize, char ySize, char* map);

int main(int argc, char* argv[])
{
    char mapWidth, mapHeight;
    string line;

    cin >> line;

    mapWidth = line.at(0)-'0';
    line.erase(0, 2);
    mapHeight = line.at(0)-'0';
    line.erase(0, 2);

    string ret = solveQuiz(mapWidth, mapHeight, (char*)line.c_str());

    cout << ret << endl;
}

SolutionNode.cpp

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>

#include <string.h>

#include "iString.h"
#include "SolutionNode.h"

using namespace std;

//MACRO
#define ABS(x)  (((x)>0)?(x):(-(x)))

//Static変数
int distanceMapArray[35][36];
int distanceMapArrayBackward[35][36];

bool boolAdjacentMap[36][4];

bool SolutionNode::operator>(const SolutionNode &amp;right) const {
    return cost > right.cost;
}


void SolutionNode_Init(SolutionNode&amp; current, int x, int y, char* mapArray, char zero, short mov, string movstr, void* prev, bool flgFwd){
    SolutionNode_width = x;
    SolutionNode_height = y;
    if(mapArray!=NULL)
        memcpy(current.map, mapArray, x*y);
    current.map[x*y] = '\0';
    current.posZero = zero;
    current.move = mov;
    current.moveStr = movstr;
    current.isOpen = true;
    current.isForward = flgFwd;

    current.cost = SolutionNode_calcCost(current, (SolutionNode*)prev);
}

void SolutionNode_printmap(SolutionNode current){
    if(current.isForward)
        cout << "sol.map FWD" << endl;
    else
        cout << "sol.map BWD" << endl;
    for(int i = 0 ; i< SolutionNode_height; ++i){
        for(int j = 0; j<SolutionNode_width ; ++j)
            cout << (int)current.map[i*SolutionNode_width+j] << " " ;
        cout << endl;
    }
}

short SolutionNode_calcCost(SolutionNode current, SolutionNode* prev)
{
    short ret = 0;

    if(prev==NULL){
        if(current.isForward)
            ret = current.move + SolutionNode_getDistance(current);
        else
            ret = current.move + SolutionNode_getDistanceBackward(current);
    }else{
        int p = current.map[prev->posZero];
        if(current.isForward){
            ret = prev->cost + 1 - distanceMapArray[p-1][current.posZero] + distanceMapArray[p-1][prev->posZero];
        }else{
            ret = prev->cost + 1 - distanceMapArrayBackward[p-1][current.posZero] + distanceMapArrayBackward[p-1][prev->posZero];
        }
    }
    return ret;
}

string SolutionNode_mapStr(SolutionNode current)
{
    char* tempStr;
    tempStr = new char[SolutionNode_width*SolutionNode_height + 1];
    for(int i=0;i<SolutionNode_width*SolutionNode_height;++i)
        tempStr[i] = '0' + current.map[i];
    tempStr[SolutionNode_width*SolutionNode_height]='\0';

    string retStr = tempStr;
    delete [] tempStr;
    return retStr;
}

iString SolutionNode_map_iString(SolutionNode current)
{
    iString retStr;
    string str;
    str = SolutionNode_mapStr(current);
    strcpy(retStr.str_, str.c_str());
    return retStr;
}

//manhattern distance
short SolutionNode_getDistance(SolutionNode current)
{
    short ret = 0;

    for(int i = 0;i<SolutionNode_width*SolutionNode_height;++i){
        if(current.map[i] != 0 &amp;&amp; current.map[i] != -1){
            ret+=distanceMapArray[current.map[i]-1][i];
        }
    }

    return ret;
}

//manhattern distance
short SolutionNode_getDistanceBackward(SolutionNode current)
{
    short ret = 0;

    for(int i = 0;i<SolutionNode_width*SolutionNode_height;++i){
        if(current.map[i] != 0 &amp;&amp; current.map[i] != -1){
            ret+=distanceMapArrayBackward[current.map[i]-1][i];
        }
    }

    return ret;
}

void Init_distanceMapArray(int xSize, int ySize)
{
    int posX, posY, cmpX, cmpY;
    for(int i = 0; i < xSize*ySize - 1 ; ++i){
        posX = i % xSize;
        posY = i / xSize;
        for(int j = 0; j < ySize*xSize ; ++j){
            cmpX = j % xSize;
            cmpY = j / xSize;
            distanceMapArray[i][j] = ABS(posX - cmpX) + ABS(posY - cmpY);
        }
    }
}

void Init_distanceMapArrayBackward(int xSize, int ySize, char* binAry)
{
    int posX, posY, cmpX, cmpY;
    memset(distanceMapArrayBackward, 0, 35*36);
    for(int i = 0; i < xSize*ySize - 1 ; ++i){
        if(binAry[i] <= 0)   continue;
        posX = i % xSize;
        posY = i / xSize;
        for(int j = 0; j < ySize*xSize ; ++j){
            cmpX = j % xSize;
            cmpY = j / xSize;
            distanceMapArrayBackward[binAry[i]-1][j] = ABS(posX - cmpX) + ABS(posY - cmpY);
        }
    }
}

void makeboolAdjacentMap(char xSize, char ySize, char* map)
{
    for(int iCount = 0;iCount < xSize*ySize; ++iCount){
        if(iCount/xSize == 0 || map[iCount - xSize] == '=')         boolAdjacentMap[iCount][0] = false; else    boolAdjacentMap[iCount][0] = true;
        if(iCount%xSize == 0 || map[iCount - 1    ] == '=')         boolAdjacentMap[iCount][1] = false; else    boolAdjacentMap[iCount][1] = true;
        if(iCount/xSize == ySize-1 || map[iCount + xSize] == '=')   boolAdjacentMap[iCount][2] = false; else    boolAdjacentMap[iCount][2] = true;
        if(iCount%xSize == xSize-1 || map[iCount + 1    ] == '=')   boolAdjacentMap[iCount][3] = false; else    boolAdjacentMap[iCount][3] = true;
    }
}

char SolutionNode_width;
char SolutionNode_height;

solveQuiz.cpp

#include <string>
#include <unordered_map>
#include <queue>

#include <string.h>

#include "iString.h"
#include "SolutionNode.h"

using namespace std;

// macro - compile switch
#define _ENABLE_DOUBLEWARD

// function
static string getAnswerMapString(SolutionNode startNode);
static void convCharArray2BinCharArray(char* dst, const char* org, char xSize, char ySize);
static void getGoalCharArray2BinCharArray(char* dst, const char* org, char xSize, char ySize);

string solveQuiz(char xSize, char ySize, char* mapArray)
{
    unordered_map<iString , SolutionNode, StringHash> hashList;
    priority_queue<SolutionNode, vector<SolutionNode>,greater<SolutionNode> > queNode;

    char zeroPos;
    char mapStart[6*6];
    convCharArray2BinCharArray(mapStart, mapArray, xSize, ySize);
    zeroPos = (char)strlen(mapStart);
    char moveULDR[4] = {0, -1, 0, +1};
    moveULDR[0] = -xSize;
    moveULDR[2] = +xSize;
    string moveULDRstr[4] = {"U", "L", "D", "R"};
    char moveULDRstrRev[4] = {'D', 'R', 'U', 'L'};

    Init_distanceMapArray(xSize, ySize);
    Init_distanceMapArrayBackward(xSize, ySize, mapStart);

    makeboolAdjacentMap(xSize, ySize, mapArray);

    SolutionNode startNode;
    SolutionNode_Init(startNode, xSize, ySize, mapStart, zeroPos, 0, "", NULL);
    hashList[SolutionNode_map_iString(startNode)] = startNode;
    queNode.push(startNode);

    string ans = getAnswerMapString(startNode);

#ifdef _ENABLE_DOUBLEWARD
    getGoalCharArray2BinCharArray(mapStart, ans.c_str(), xSize, ySize);
    SolutionNode endNode;
    SolutionNode_Init(endNode, xSize, ySize, mapStart, (char)strlen(mapStart), 0, "", NULL, false);
    hashList[SolutionNode_map_iString(endNode)] = endNode;
    queNode.push(endNode);
#endif

    SolutionNode a, b, tempNode;
    string retStr = "";
    string backStr;
    string::reverse_iterator rit;
    SolutionNode c;
    while(!queNode.empty()){
        a = queNode.top();
        queNode.pop();
        if(!a.isOpen)   continue;
        for(int iCount = 0;iCount<4;++iCount){
            if(boolAdjacentMap[a.posZero][iCount] &amp;&amp; (a.moveStr.empty() || *(a.moveStr.rbegin()) != moveULDRstrRev[iCount])){
                b = a;
                b.map[a.posZero] = b.map[a.posZero + moveULDR[iCount]];
                b.map[a.posZero + moveULDR[iCount]] = 0;
                b.posZero = a.posZero + moveULDR[iCount];
                b.moveStr+=moveULDRstr[iCount];
                ++b.move;
                if(hashList.find(SolutionNode_map_iString(b))!=hashList.end()){
                    tempNode = hashList[SolutionNode_map_iString(b)];
#ifdef _ENABLE_DOUBLEWARD
                    if(tempNode.isForward != b.isForward){
                        if(b.isForward){
                            retStr = b.moveStr;
                            backStr = tempNode.moveStr;
                        }else{
                            retStr = tempNode.moveStr;
                            backStr = b.moveStr;
                        }
                        for(rit=backStr.rbegin();rit!=backStr.rend();++rit){
                            if(*rit == 'U') retStr+="D";
                            else if(*rit == 'D')    retStr+="U";
                            else if(*rit == 'L')    retStr+="R";
                            else if(*rit == 'R')    retStr+="L";
                        }
                        return retStr;
                    }
#endif
                    if(tempNode.move > b.move){
                        if(tempNode.isOpen){
                            SolutionNode_Init(c, SolutionNode_width, SolutionNode_height, b.map, b.posZero, b.move, b.moveStr, &amp;a, b.isForward);
                            c.isOpen = false;
                            hashList[SolutionNode_map_iString(b)] = c;
                            queNode.push(c);
                        }else{
                            tempNode.cost += -tempNode.move + b.move;
                            tempNode.move = b.move;
                            tempNode.isOpen = true;
                            queNode.push(tempNode);
                        }
                    }
                }else{
#ifndef _ENABLE_DOUBLEWARD

                    if(SolutionNode_mapStr(b) == ans){
                        return b.moveStr;
                    }
#endif
                    SolutionNode_Init(c, SolutionNode_width, SolutionNode_height, b.map, b.posZero, b.move, b.moveStr, &amp;a, b.isForward);
                    queNode.push(c);
                    hashList[SolutionNode_map_iString(c)] = c;
                }
            }
        }
    }

    return "";
}

string getAnswerMapString(SolutionNode startNode)
{
    char* tempStr;
    tempStr = new char[SolutionNode_width*SolutionNode_height+1];
    for(int i = 0; i< SolutionNode_width*SolutionNode_height-1;++i){
        if(startNode.map[i]!=-1)    tempStr[i] = 0x31 + i;
        else                        tempStr[i] = 0x2F;
    }
    tempStr[SolutionNode_width*SolutionNode_height-1] = '0';
    tempStr[SolutionNode_width*SolutionNode_height  ] = '\0';
    string retStr = tempStr;
    delete [] tempStr;
    return retStr;
}

void convCharArray2BinCharArray(char* dst, const char* org, char xSize, char ySize)
{
    for(int i = 0; i<xSize*ySize;++i){
        if(org[i] == '=')
            dst[i] = -1;
        else if(org[i]>='0' &amp;&amp; org[i] <='9')
            dst[i] = org[i]-'0';
        else if(org[i]>='A' &amp;&amp; org[i] <='Z')
            dst[i] = org[i]-'A'+10;
    }
}

void getGoalCharArray2BinCharArray(char* dst, const char* org, char xSize, char ySize)
{
    for(int i = 0; i<xSize*ySize;++i){
        if(org[i] == '/')
            dst[i] = -1;
        else
            dst[i] = org[i]-'0';
    }
}

iString.h

#pragma once

#include <functional>
#include <string.h>

inline void hash_combine(std::size_t&amp; seed, const char* v);

struct iString{
    char str_[36+1];

    bool operator==(const iString &amp;rhs) const {
        return strcmp(str_, rhs.str_) == 0;
    }
};

class StringHash {
public:
    std::size_t operator()(const iString &amp;str) const {
        std::size_t a = 0;
        hash_combine(a, str.str_);
        return a;
    }

};

inline void hash_combine(std::size_t&amp; seed, const char* v)
{
    for(int iCount = 0;iCount<strlen(v);++iCount){
        std::size_t localSeed = std::hash<char>()(v[iCount]);
        seed ^= localSeed + 0x9e3779b9 + (seed<<6)+(seed>>2);
    }
}

SolutionNode.h

#pragma once

using namespace std;

extern char SolutionNode_width;
extern char SolutionNode_height;

struct SolutionNode{
    char map[36+1];
    char posZero;
    unsigned char move;
    string moveStr;
    unsigned char cost;
    bool isOpen;
    bool isForward;

    bool operator>(const SolutionNode &amp;right) const;
};

//Static Variable
extern int distanceMapArray[35][36];
extern int distanceMapArrayBackward[35][36];

extern bool boolAdjacentMap[36][4];

//functions
void Init_distanceMapArray(int xSize, int ySize);
void Init_distanceMapArrayBackward(int xSize, int ySize, char* binAry);

void makeboolAdjacentMap(char xSize, char ySize, char* map);

void SolutionNode_printmap(SolutionNode current);
short SolutionNode_calcCost(SolutionNode current, SolutionNode* prev);
string SolutionNode_mapStr(SolutionNode current);
iString SolutionNode_map_iString(SolutionNode current);
short SolutionNode_getDistance(SolutionNode current);
short SolutionNode_getDistanceBackward(SolutionNode current);
void SolutionNode_Init(SolutionNode&amp; current, int x, int y, char* mapArray, char zero, short mov, string movstr, void* prev, bool flgFwd = true);

solutionChecker.cpp

#include <string.h>
#include <memory.h>
#include <iostream>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <sstream>

using namespace std;

bool searchZeroPosition(char xSize, char ySize, char* map, char&amp; xpos_zero, char&amp; ypos_zero);
bool isValidSolutionSlidePuzzle(char xSize, char ySize, char* map, char posx, char posy, char* solutionStr, char* strCorrectAnswer);
bool processMoveString(char xSize, char ySize, char* map, char&amp; posx, char&amp; posy, char* solutionStr, char* resultMap);
bool isValidCursorMove(char xSize, char ySize, char* map, char xpos_zero, char ypos_zero, char direction);
string convAnswerFromString(char xSize, char ySize, const char* map);
void outputProblemTextfile(int problemNo, string problemStr);

int main(int ac, char** av)
{
    int a1, a2, a3, a4;
    int num;

    cin >> a1 >> a2 >> a3 >> a4;

    cerr << a1 << ", " << a2 << ", " << a3 << ", " << a4 << endl;

    cin >> num;
    cerr << num << endl;

    int spaceCount = 0;
    for(int iCount=0;iCount<num;++iCount){
        char posx, posy;
        char mapWidth, mapHeight;

        string line, orgStr;
        cin >> line;
        orgStr = line;

        mapWidth = line.at(0)-'0';
        line.erase(0, 2);
        mapHeight = line.at(0)-'0';
        line.erase(0, 2);

        string ans = convAnswerFromString(mapWidth, mapHeight, line.c_str());
        ostringstream strStream;
        strStream << "ans/problem" << iCount+1 << ".txt" ;
        std::ifstream inputStream(strStream.str().c_str());
        if(!inputStream.fail()){
            string solution;
            inputStream >> solution;
            if(solution != ""){
                searchZeroPosition(mapWidth, mapHeight, (char*)line.c_str(), posx, posy);
                if(isValidSolutionSlidePuzzle(mapWidth, mapHeight, (char*)line.c_str(), posx, posy, (char*)solution.c_str(), (char*)ans.c_str()))
                    cout << solution << endl;
                else{
                    cerr << "Solution" << iCount+1 << " is Invalid." << endl;
                    ++spaceCount;
                    cout << endl;
                    outputProblemTextfile(iCount+1, orgStr);
                }
            }else{
                ++spaceCount;
                cout << endl;
                outputProblemTextfile(iCount+1, orgStr);
            }
        }else{
            ++spaceCount;
            cout << endl;
            outputProblemTextfile(iCount+1, orgStr);
        }
    }
    cerr << "No Answer: " << spaceCount << endl;
    cerr << "Point: " << (num-spaceCount)*0.01 << endl;
    return 0;
}

bool searchZeroPosition(char xSize, char ySize, char* map, char&amp; xpos_zero, char&amp; ypos_zero)
{
    char index = -1;
    for(int iCount = 0;iCount < xSize*ySize; ++iCount)
        if(map[iCount] == '0'){
            index = iCount;
        }

        if(index != -1){
            xpos_zero = index % xSize;
            ypos_zero = index / xSize;
            return true;
        }

        return false;
}

bool isValidSolutionSlidePuzzle(char xSize, char ySize, char* map, char posx, char posy, char* solutionStr, char* strCorrectAnswer)
{
    char* resultMap;
    bool ret;

    if(map[posy*xSize+posx]!='0')   return false;

    resultMap = new char[xSize*ySize+1];

    ret = processMoveString(xSize, ySize, map, posx, posy, solutionStr, resultMap);
    if(ret &amp;&amp; strcmp(resultMap, strCorrectAnswer) == 0) ret = true;

    delete [] resultMap;

    return ret;
}

bool processMoveString(char xSize, char ySize, char* map, char&amp; posx, char&amp; posy, char* solutionStr, char* resultMap)
{
    strcpy(resultMap, map);
    int cursorSolution=0;

    while(solutionStr[cursorSolution]){
        if(!isValidCursorMove(xSize, ySize, resultMap, posx, posy, solutionStr[cursorSolution])){
            return false;
        }
        switch(solutionStr[cursorSolution]){
        case 'U':
            resultMap[xSize*(posy  )+posx] = resultMap[xSize*(posy-1)+posx];
            resultMap[xSize*(posy-1)+posx] = '0';
            --posy;
            break;
        case 'D':
            resultMap[xSize*(posy  )+posx] = resultMap[xSize*(posy+1)+posx];
            resultMap[xSize*(posy+1)+posx] = '0';
            ++posy;
            break;
        case 'L':
            resultMap[xSize*posy+(posx  )] = resultMap[xSize*posy+(posx-1)];
            resultMap[xSize*posy+(posx-1)] = '0';
            --posx;
            break;
        case 'R':
            resultMap[xSize*posy+(posx  )] = resultMap[xSize*posy+(posx+1)];
            resultMap[xSize*posy+(posx+1)] = '0';
            ++posx;
            break;
        }
        ++cursorSolution;
    }
    return true;
}

bool isValidCursorMove(char xSize, char ySize, char* map, char xpos_zero, char ypos_zero, char direction)
{
    if(map[ypos_zero*xSize+xpos_zero] != '0')   return false;

    switch(direction){
    case 'U':
        if(ypos_zero <= 0         || map[xSize*(ypos_zero-1)+xpos_zero] == '=')  return false;
        break;
    case 'D':
        if(ypos_zero >= ySize - 1 || map[xSize*(ypos_zero+1)+xpos_zero] == '=')  return false;
        break;
    case 'L':
        if(xpos_zero <= 0         || map[xSize*ypos_zero+(xpos_zero-1)] == '=')  return false;
        break;
    case 'R':
        if(xpos_zero >= xSize - 1 || map[xSize*ypos_zero+(xpos_zero+1)] == '=')  return false;
        break;
    }
    return true;
}

string convAnswerFromString(char xSize, char ySize, const char* map)
{
    const char* orgMap = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    string retStr = "";
    for(int iCount = 0;iCount<xSize*ySize-1;++iCount){
        if(map[iCount]!='=')
            retStr += orgMap[iCount];
        else
            retStr += '=';
    }
    retStr+="0";

    return retStr;
}

void outputProblemTextfile(int problemNo, string problemStr)
{
    ostringstream strOutputFile;
    strOutputFile << "left/problem" << problemNo << ".txt" ;
    std::ofstream outputStream(strOutputFile.str().c_str());
    outputStream << problemStr << endl;
}

Makefile

SRC = ./left
DST = ./ans

PROGRAM=/home/yoshichika/GDDQuizDir/solveGDDQuiz

LS = ls -A

PROBLEM_LST = $(shell $(LS) $(SRC))

all : $(addprefix $(DST)/,$(addsuffix .txt,$(basename $(PROBLEM_LST))))

.PHONY : all

$(DST)/%.txt:$(SRC)/%.txt
timeout 240 $(PROGRAM) < $< > $@

未分類