Forum

Post 12.10.2012   # 1
Subject practice problem RotateMaze won't compile

Hi Guys,

First of all thanks for this great site! It helped me get back into programming and I like it a lot. I'm working in C++ and have done the first three practice problems in round 1 without a hitch. Now I thought let's throw in some neat classes in problem 4 (RotateMaze).

The solution works fine on my own machine, but somehow the compiler does not give any results or errors when I send it in. It just keeps saying "compiling". If I click "compile & test", all testcases return "error" and "compile errors". I read all the relevant forum posts and even split my solution, which was all subclasses to one master class at first into multiple classes. It still does not compile. Any hints would be much appreciated.

here's the code:

 

<code>

 

#include

#include

using namespace std;

struct possibilities

{

    bool direction[4];

    possibilities()

    {

        direction[0] = false;

        direction[1] = false;

        direction[2] = false;

        direction[3] = false;

    }

}; // possibilities

struct coordinate

{

    int x, y, orientation;

    coordinate(int const xvalue, int const yvalue, int const orientationvalue = 0)

    {

        x=xvalue;

        y=yvalue;

        orientation = orientationvalue;

    }

    coordinate()

    {

        x=0;

        y=0;

        orientation = 0;

    }

    bool operator==(const coordinate &right) const

  {

    return (x == right.x) && (y == right.y) && (orientation == right.orientation);

    }

    bool operator!=(const coordinate &right) const

  {

    return (x != right.x) || (y != right.y) || (orientation != right.orientation);

    }

    bool operator <(const coordinate &right) const

  {

    return (x < right.x) || (y < right.y);

    }

    bool operator >(const coordinate &right) const

  {

    return (x > right.x) || (y > right.y);

    }

}; // coordinate

struct mapSquare

{

    intdistance = 0;

    possibilities possibleOrientations;

    possibilities possibleMoves[4];

    bool isWall = false, isTreasure = false;

    mapSquare()

    {

    }

    ~mapSquare()

    {

    }

}; // mapSquare

int mod (int const a, int const b)

{

    if(b < 0)

        return mod(-a, -b);

    int ret = a % b;

    if(ret < 0)

        ret+=b;

    return ret;

}

coordinate getMoveCoordinate (coordinate current, int direction)

{

    switch (direction) {

        case 0: // left

            current.x--;

            break;

        case 1: // right

            current.x++;

            break;

        case 2: // up

            current.y--;

            break;

        case 3: // down

            current.y++;

            break;

    }

    return current;

}

coordinate getTurnCoordinate (coordinate current, int direction)

{

    switch (direction) {

        case 0: // Clockwise

            current.orientation = mod(++current.orientation, 4);

            break;

        case 1: // Counterclockwise

            current.orientation = mod(--current.orientation, 4);

            break;

    }

    return current;

}

int getOppositeDirection (int direction)

{

    switch (direction) {

        case 0: // left

            return 1;

            break;

        case 1: // right

            return 0;

            break;

        case 2: // up

            return 3;

            break;

        case 3: // down

            return 2;

            break;

    }

    return -1;

}

class elementStructure

{

public:

    void add(coordinate current)

    {

        element.push_back(current);

    }

    void addCenter(coordinate current)

    {

        if (size()>0) {

            add(element[0]);

            element[0] = current;

        }

        else {

            add(current);

        }

    }

    void jump(coordinate newCenter)

    // moves all parts of element to a new location with the center at position newCenter

    // including the correct orientation

    {

        int offsetX = element[0].x - newCenter.x, offsetY = element[0].y - newCenter.y;

        while (element[0].orientation != newCenter.orientation) {

            rotateCW();

        }

        for (int i=0;i

            element<span style=""font-style: italic;">.x -= offsetX;</span>

            element<span style=""font-style: italic;">.y -= offsetY;</span>

        }

    }

    void rotateCW()

    //turns element clockwise (CW) without checking

    {

        int offsetX, offsetY;

        int centerX = element[0].x, centerY = element[0].y;

        for (int i=0;i

            offsetX = element<span style=""font-style: italic;">.x - centerX;</span>

            offsetY = element<span style=""font-style: italic;">.y - centerY;</span>

            element<span style=""font-style: italic;">.x= centerX - offsetY;</span>

            element<span style=""font-style: italic;">.y= centerY + offsetX;</span>

        }

        element[0].orientation = mod((element[0].orientation + 1), 4);

    }

    void rotateCCW() // debug

    // turns element counterclockwise (CCW) without checking

    {

        int offsetX, offsetY;

        int centerX = element[0].x, centerY = element[0].y;

        for (int i=0;i

            offsetX = element<span style=""font-style: italic;">.x - centerX;</span>

            offsetY = element<span style=""font-style: italic;">.y - centerY;</span>

            element<span style=""font-style: italic;">.x= centerX + offsetY;</span>

            element<span style=""font-style: italic;">.y= centerY - offsetX;</span>

        }

        element[0].orientation = mod((element[0].orientation + 1), 4);

    }

    int getOrientation() const

    {

        return element[0].orientation;

    }

    coordinate getCoordinate (int index = 0) const

    {

        return element[index];

    }

    coordinate getCenter() const

    {

        return getCoordinate(0);

    }

    void clear()

    {

        element.clear();

    }

    int size() const

    {

        return (int) element.size();

    }

private:

    vector element;

}; // elementStructure

class mapStructure

{

public:

    /*        void outputMap (vector const map) const //debug

     {

     for (int i=0;i

     std::cout << ' ' << map<span style=""font-style: italic;"> << endl;</span>

     }

     std::cout << endl << endl;

     }

     vector
getUpdatedMap (vector map, elementStructure object) const //debug

     // outputs map with a newly positioned element (assumes readMap has been called before)

     {

     vector result = map;

     coordinate center = object.getCenter();

     coordinate current;

     result[center.y][center.x] = 'O';

     for (int i=1;i

     current = object.getCoordinate(i);

     result[current.y][current.x] = '*';

     }

     return result;

     }

     void outputPossibleMoves() const //debug

     {

     bool currentMove = false;

     coordinate currentPosition;

     for (int orientation=0;orientation<4;orientation++){

     std::cout << endl;

     std::cout << "orientation: " << orientation << endl;

     for (int i=0;i

     for (int j=0;j

     currentPosition = coordinate (j, i, orientation);

     currentMove = possibleMove (currentPosition, 3); //return all possible down moves (down = 3)

     if (currentMove) {

     std::cout << ',' ;

     }

     else {

     std::cout << '.' ;

     }

     }

     std::cout << endl;

     }

     }

     std::cout << endl << endl;

     }

     */

    void setWall(coordinate const current)

    {

        map[current.y][current.x].isWall = true;

    }

    bool isWall(coordinate const current) const

    {

        if (outOfBounds(current)) {

            return true;

        }

        else {

            return map[current.y][current.x].isWall;

        }

    }

    void setTreasure(coordinate const current)

    {

        map[current.y][current.x].isTreasure = true;

    }

    bool isTreasure(coordinate const current) const

    {

        if (outOfBounds(current)) {

            return false;

        }

        else {

            return map[current.y][current.x].isTreasure;

        }

    }

    void setPossibleOrientation(coordinate const current)

    {

        map[current.y][current.x].possibleOrientations.direction[current.orientation] = true;

    }

    bool orientationPossible(coordinate const current) const

    {

        return map[current.y][current.x].possibleOrientations.direction[current.orientation];

    }

    void setPossibleMoves(elementStructure element, coordinate const current)

    {

        mapSquare temp;

        coordinate neighbourPosition;

        int opposite;

        for (int i=0;i<4;i++){

            if ((getNeighbour(current, i, temp)) && !(temp.isWall)) {

               neighbourPosition = coordinate(getMoveCoordinate(current, i));

                if (fits(element, neighbourPosition)) {

                    map[current.y][current.x].possibleMoves[current.orientation].direction<span style=""font-style: italic;"> </span>

                    = true;

                }

                // also be sure to set the opposite direction

                opposite = getOppositeDirection(i);

                if (!temp.possibleMoves[current.orientation].direction[opposite]

                    && !outOfBounds(neighbourPosition)

          && fits(element, neighbourPosition)) {

          map[neighbourPosition.y][neighbourPosition.x].possibleMoves[current.orientation].direction[opposite] = true;

                }

            }

        }

    }

    bool possibleMove (coordinate const current, int direction) const

    {

        if (outOfBounds(current)) {

            return false;

        }

        else {

            return map[current.y][current.x].possibleMoves[current.orientation].direction[direction];

        }

    }

    bool getNeighbour(coordinate current, int direction, mapSquare &result) const

  {

    coordinate neighbourPosition = getMoveCoordinate(current, direction);

        if (outOfBounds(neighbourPosition)) {

            return false;

        }

        else {

            result = map[neighbourPosition.y][neighbourPosition.x];

            return true;

        }

    }

    bool fits(elementStructure element, coordinate newCenter) const

    // check whether element fits into the map at coordinate newCenter

    {

        if (map[newCenter.y][newCenter.x].possibleOrientations.direction[newCenter.orientation]){

            return true;

        }

        else {

            element.jump(newCenter);

            for (int i=0;i

                if (isWall(element.getCoordinate(i))){

                    return false;

                }

            }

            return true;

        }

    }

    bool findPath(vector
const map, elementStructure object, coordinate const current, vector const trail) //map only needed for debug purposes

    // Finds all paths to the treasure, sets the shortest path length

    // returns -1 if treasure is unreachable

    // assumes that analyseMap() has been correctly executed and that findPath() is initially

    // called with the position and orientation of the center of the object to traverse the maze.

    {

        bool success = false;

        vector nextTrail;

        object.jump(current);

        //            outputMap(getUpdatedMap(map, object)); //debug

        //            cout << ' ' << trail.size() - 1 << endl << endl; //debug

        if (treasureFound(object)){

            if ((shortestPath == -1)

                || ((int) trail.size() - 1 < shortestPath)){

                shortestPath = (int)trail.size() - 1;

                return true;

            }

            else {

                return true;

            }

        }

        else {

            for (int direction=0;direction<6 && ((shortestPath == -1)||(trail.size() <= shortestPath));direction++){

                if (moveOption (current, trail, direction)) {

                    nextTrail = trail;

                    nextTrail.push_back(getNextMove(current, direction));

                    success = findPath(map, object, getNextMove (current, direction), nextTrail);

                }

            }

        }

        return success;

    }

    bool moveOption (coordinate const current, vector const trail, int newDirection) const

    {

        if ((newDirection < 4) && possibleMove(current, newDirection)

      && !inTrail(trail, getMoveCoordinate(current, newDirection))){

      return true;

        }

        else if ((newDirection == 4) && orientationPossible(getTurnCoordinate(current, 0))

        && !inTrail (trail, getTurnCoordinate(current, 0))){

      return true;

        }

        else if ((newDirection == 5) && orientationPossible(getTurnCoordinate(current, 1))

        && !inTrail (trail, getTurnCoordinate(current, 1))){

      return true;

        }

        return false;

    }

    coordinate getNextMove (coordinate const current, int const direction) const

    {

        if (direction < 4){

            return getMoveCoordinate(current, direction);

        }

        else {

            return getTurnCoordinate(current, direction-4);

        }

    }

    int getShortestPathLength ()

    {

        return shortestPath;

    }

    /*

     bool flip (coordinate const current, coordinate const next) const

     // returns true if moving from position current to position next would constitute

     // a impossible flip (i.e. a 180 degree turn) in a too narrow spot

     // NOTE: does not check whether the move would actually be valid

     // assumes that analyseMap() has been executed correctly.

     {

     if (next.orientation == mod(current.orientation + 2, 4)){

     return (orientationPossible(getTurnCoordinate(current, 0))

     || orientationPossible(getTurnCoordinate(current, 1)));

     }

     return false;

     }

     */

    bool inTrail (vector const trail, coordinate const current) const

    // returns true if current coordinate is found in trail, searching from the back

    {

        if (!trail.empty()){

            for (int i=(int)trail.size()-1;i>=0;i--) {

                if (trail<span style=""font-style: italic;"> == current) {</span>

                    return true;

                }

            }

        }

        return false;

    }

    int height() const

    {

        return (int) map.size();

    }

    int width() const

    {

        return (int) map[0].size();

    }

    bool outOfBounds(coordinate current) const

    {

        return (current.x < 0) || (current.y < 0) || (current.x >= map.size()) || (current.y >= map.size());

    }

    bool treasureFound (elementStructure const object) const

    {

        for (int i=0;i

            if (isTreasure(object.getCoordinate(i))){

                return true;

            }

        }

        return false;

    }

    mapStructure(int const width, int const height)

    {

        mapSquare tempSquare;

        vector
tempVector;

        tempVector.assign(width, tempSquare);

        map.assign(height, tempVector);

    }

    mapStructure ()

    {

    }

    ~mapStructure ()

    {

    }

private:

    vector< vector
> map;

    int shortestPath = -1;

}; //mapStructure

class RotateMaze

{

public:

    int find(vector map)

    // reads map and checks all possible moves and positions for element

    // as specified in problem specification (see above)

    {

        vector trail;

        readMap(map);

        analyseMap();

        //        distanceMap.outputPossibleMoves(); //debug

        trail.push_back(object.getCenter());

        distanceMap.findPath(map, object, object.getCenter(), trail);

        return distanceMap.getShortestPathLength();

    }

private:

    // private member variables of RotateMaze

    elementStructure object;

    mapStructure distanceMap;

    // private member functions of RotateMaze

    void readMap(vector &map)

  // find all parts of element and store the coordinates of the center at position [0]

  // also strips the parts of element from map for easier output later as a debug measure

  // assumes map is a vector of strings that are of equal length

  {

      mapStructure tempDistanceMap ((int) map[0].size(), (int) map.size());

        distanceMap = tempDistanceMap;

        object.clear();

        for (int i=0;i

            for (int j=0;j

                // read the entire map, skipping the borders

                if (map<span style=""font-style: italic;">[j] == '#'){</span>

                    distanceMap.setWall(coordinate(j,i));

                }

                else if (map<span style=""font-style: italic;">[j] == '*'){</span>

                    // part of object

                    object.add(coordinate(j,i));

                    //                    map <span style=""font-style: italic;">[j] = ' '; //debug</span>

                }

                else if (map<span style=""font-style: italic;">[j] == 'O') {</span>

                    // center of object, store as such

                    object.addCenter(coordinate(j,i));

                    //                    map <span style=""font-style: italic;">[j] = ' '; //debug</span>

                }

                else if (map<span style=""font-style: italic;">[j] == 'X') {</span>

                    // treasure, store as such

                    distanceMap.setTreasure(coordinate(j,i));

                }

            }

        }

    }

    void analyseMap ()

    // looks at all possible positions for element and saves those that fit in the maze

    // the same goes for all possible orientations of element

    // returns false if maze is unsolvable

    {

        elementStructure testElement = object;

        coordinate currentPosition;

        for (int orientation=0;orientation<4;orientation++){

            // try all orientations of testElement

            while (testElement.getOrientation()!= orientation){

                testElement.rotateCW();

            }

            for (int i=0;i

                for (int j=0;j

                    //check all map squares and see whether element would fit there

                    currentPosition = coordinate(j,i, orientation);

                    if (distanceMap.fits (testElement, currentPosition)){

                        distanceMap.setPossibleOrientation (currentPosition);

                        distanceMap.setPossibleMoves (testElement, currentPosition);

                    }

                }

            }

        }

    }

}; // RotateMaze

</code>

 

Somehow pasting the code inserts extra lines. Sorry for that. 

titusn is offline Reply
Post 14.10.2012   # 2

It seems that you were using some improper characters as whitespaces in your code. I've just stripped them out, fixed some initializations in the structures (due to iso C++ rules), and I got the solution compiled. However, I got wrong answers

Anyway, I edited your code in the practice section, it should be OK now for you too. In the future, be careful with the editor and what characters it inserts inside your code.

hsilomedus is offline Reply
Post 20.10.2012   # 3

Hey Thanks a lot!

I was using XCode. Could you venture a guess as to what kind of whitespace characters were inserted? And of course you're absolutely right, one should always initialize all variables. Thanks for reminding me. I probably did too much code golfing the past few months and got sloppy

I had the right answers for the first few testcases, so I was looking forward to debugging for the other testcases. Thank you for enabling me to do that.

titusn is offline Reply
Post 26.10.2012   # 4

Ah, I found the source of my predicament (pun intended).

I had used copy paste from XCode, including the formatting. Stupid but true. Once I used paste plain text (on Apple Shift+Cmd+V) the problem melted away.

titusn is offline Reply

Please login to post reply.