daily pastebin goal
59%
SHARE
TWEET

Untitled

a guest Dec 10th, 2018 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /** Help the Christmas elves fetch presents in a magical labyrinth! **/
  2.  
  3. #include <iostream>
  4. #include <string>
  5. #include <vector>
  6. #include <queue>
  7. #include <unordered_map>
  8. #include <unordered_set>
  9. #include <cmath>
  10.  
  11. #define ROWS 7
  12. #define COLS 7
  13. #define DIRS 4
  14.  
  15. #define UP 0
  16. #define RIGHT 1
  17. #define DOWN 2
  18. #define LEFT 3
  19.  
  20. #define TURN_PUSH 0
  21. #define TURN_MOVE 1
  22.  
  23. #define LARGE_DISTANCE 1000
  24.  
  25.  
  26. const std::string directions[] = { "UP", "RIGHT", "DOWN", "LEFT" };
  27. const std::string turnNames[] = { "Push", "Move" };
  28.  
  29.  
  30. int getOppDir(int dir)
  31. {
  32.     switch (dir)
  33.     {
  34.     case UP:
  35.         return DOWN;
  36.     case DOWN:
  37.         return UP;
  38.     case RIGHT:
  39.         return LEFT;
  40.     case LEFT:
  41.         return RIGHT;
  42.     default:
  43.         throw "Unknown direction";
  44.         break;
  45.     }
  46. }
  47.  
  48. struct Cell
  49. {
  50.     int row;
  51.     int col;
  52.  
  53.     void set(int _row, int _col)
  54.     {
  55.         row = _row;
  56.         col = _col;
  57.     }
  58.  
  59.     int manhattan(const Cell& other) const
  60.     {
  61.         return abs(row - other.row) + abs(col - other.col);
  62.     }
  63.  
  64.     int toInt() const  // I use this as a key when storing a Cell in map or set
  65.     {
  66.         return row * COLS + col;
  67.     }
  68.  
  69.     bool operator==(const Cell& other) const
  70.     {
  71.         return row == other.row && col == other.col;
  72.     }
  73.  
  74.     Cell getNeighbor(int direction) const
  75.     {
  76.         Cell neighbor;
  77.         switch (direction)
  78.         {
  79.         case UP:
  80.             neighbor.set(row - 1, col);
  81.             break;
  82.         case DOWN:
  83.             neighbor.set(row + 1, col);
  84.             break;
  85.         case RIGHT:
  86.             neighbor.set(row, col + 1);
  87.             break;
  88.         case LEFT:
  89.             neighbor.set(row, col - 1);
  90.             break;
  91.         default:
  92.             throw "Unknown direction";
  93.             break;
  94.         }
  95.         return neighbor;
  96.     }
  97.  
  98.     bool inBounds() const
  99.     {
  100.         return row >= 0 && col >= 0 && row < ROWS && col < COLS;
  101.     }
  102.  
  103.     friend std::ostream& operator<<(std::ostream& os, const Cell& cell)
  104.     {
  105.         os << '[' << cell.row << ',' << cell.col << ']';
  106.         return os;
  107.     }
  108. };
  109.  
  110.  
  111. struct Player
  112. {
  113.     int numPlayerCards; // the total number of quests for a player (hidden and revealed)
  114.     Cell playerCell;
  115.     std::string playerTile;
  116.  
  117.     void set(int _numPlayerCards, int _playerX, int _playerY, const std::string& _playerTile)
  118.     {
  119.         numPlayerCards = _numPlayerCards;
  120.         playerCell.set(_playerY, _playerX);
  121.         playerTile = _playerTile;
  122.     }
  123.  
  124.     friend std::ostream& operator<<(std::ostream& os, const Player& player)
  125.     {
  126.         os << player.numPlayerCards << " cards; " << player.playerCell << " tile = " << player.playerTile;
  127.         return os;
  128.     }
  129. };
  130.  
  131. struct Item
  132. {
  133.     std::string itemName;
  134.     Cell itemCell;
  135.     int itemPlayerId;
  136.  
  137.     void set(const std::string& _itemName, int _itemX, int _itemY, int _itemPlayerId)
  138.     {
  139.         itemName = _itemName;
  140.         itemCell.set(_itemY, _itemX);
  141.         itemPlayerId = _itemPlayerId;
  142.     }
  143.  
  144.     friend std::ostream& operator<<(std::ostream& os, const Item& item)
  145.     {
  146.         os << item.itemName << ' ' << item.itemCell << " player-" << item.itemPlayerId;
  147.         return os;
  148.     }
  149. };
  150.  
  151. struct Quest
  152. {
  153.     std::string questItemName;
  154.     int questPlayerId;
  155.  
  156.     void set(const std::string& _questItemName, int _questPlayerId)
  157.     {
  158.         questItemName = _questItemName;
  159.         questPlayerId = _questPlayerId;
  160.     }
  161.  
  162.     friend std::ostream& operator<<(std::ostream& os, const Quest& quest)
  163.     {
  164.         os << quest.questItemName << " player-" << quest.questPlayerId;
  165.         return os;
  166.     }
  167. };
  168.  
  169.  
  170. class Node  // for Astar path search
  171. {
  172.  
  173. public:
  174.  
  175.     Cell position;
  176.     Node* parent;
  177.     int dirFromParentToChild;
  178.     int f;
  179.     int g;
  180.     int h;
  181.  
  182.     Node(const Cell& _position, Node* _parent, int _dirFromParentToChild, int _g, int _h)
  183.     {
  184.         position = _position;
  185.         parent = _parent;
  186.         dirFromParentToChild = _dirFromParentToChild;
  187.         g = _g;
  188.         h = _h;
  189.         f = g + h;
  190.     }
  191.  
  192.     bool operator<(const Node& other) const
  193.     {
  194.         return f < other.f;
  195.     }
  196. };
  197.  
  198. class mycomparison  // can be used to create q priority queue for path
  199. {
  200. public:
  201.     bool operator() (const Node* lhs, const Node* rhs) const
  202.     {
  203.         return lhs->operator<(*rhs);
  204.     }
  205. };
  206.  
  207.  
  208. int getPathAsNearAsPossible(
  209.     const std::string grid[ROWS][COLS], const Cell& startCell, const Cell& endCell, std::string& path)
  210. {
  211.     /*
  212.    
  213.     You may notice that the return value is int
  214.     Actually, it is the final distance (manhattan) from the nearest reachable
  215.     cell to the endCell; (it will be 0 if endCell is reachable from startCell)
  216.     the actual path is put in the passed-by-reference argument "path" (see last argument)
  217.    
  218.     *****
  219.    
  220.     Using Astar search,
  221.     I search path from startCell to endCell. As endCell may not be reachable,
  222.     I keep track of the nearest reached to end cell (by manhattan dist)
  223.    
  224.     */
  225. }
  226.  
  227. struct State
  228. {
  229.     int turnType;
  230.     std::string grid[ROWS][COLS];
  231.     Player players[2];
  232.     Player* me;  // this and the following are just aliases; for ease of use
  233.     Player* opp;
  234.     std::vector<Item> items;
  235.     std::vector<Quest> quests;
  236.  
  237.     State()
  238.     {
  239.         me = &players[0];  // now we can use me or players[0] for Player0
  240.         opp = &players[1];
  241.     }
  242.  
  243.     friend std::ostream& operator<<(std::ostream& os, const State& state)
  244.     {
  245.         os << "Turn type: " << turnNames[state.turnType] << std::endl;
  246.  
  247.         os << "Grid:" << std::endl;
  248.         for (int r = 0; r < ROWS; r++)
  249.         {
  250.             for (int c = 0; c < COLS; c++)
  251.                 os << state.grid[r][c] << " ";
  252.             os << std::endl;
  253.         }
  254.         os << "Players:" << std::endl;
  255.         for (int i = 0; i < 2; i++)
  256.             os << state.players[i] << std::endl;
  257.         os << "Items:" << std::endl;
  258.         for (const auto& item : state.items)
  259.             os << item << std::endl;
  260.         os << "Quests:" << std::endl;
  261.         for (const auto& quest : state.quests)
  262.             os << quest << std::endl;
  263.  
  264.         return os;
  265.     }
  266.  
  267.     // for the following two functions (pushing a row or column)
  268.     // it is better to see the referee code they shared (link in problem statement)
  269.     // I implemented it in a crude way
  270.     std::string pushRow(int row, int direction, const std::string &tileInPushersHand)
  271.     {
  272.         /*
  273.        
  274.         the return value is the pushed tile, i.e,
  275.         whenever a player pushes, the tile in player's hand gets inserted at
  276.         one end of the grid, and the tile at the other end of the grid comes out
  277.         into player's hand
  278.        
  279.         so, this is returned
  280.        
  281.         ********
  282.        
  283.         check if direction is one of LEFT and RIGHT
  284.        
  285.         (avoid using magic numbers as I used below, use words like COLS-1....)
  286.        
  287.         if LEFT
  288.             pushedTile = leftMost tile
  289.             for col = 0 to col = 5
  290.                 tile at col = tile at col+1
  291.             tile at col6 = tile in player's hand
  292.         else // RIGHT
  293.             pushedTile = rightMost tile
  294.             for col = 6 to col = 1
  295.                 tile at col = tile at col-1
  296.             tile at col0 = tile in player's hand
  297.        
  298.        
  299.         for each player
  300.             if player in in pushed row
  301.                 change column
  302.                 if goes out of bounds
  303.                     warp to the other side
  304.        
  305.        
  306.         for each item
  307.             if item in pushed row
  308.                 change column
  309.             else if item.col == -1  // implies it is in pusher's hand (assuming only p0 pushes)
  310.                 put it in appropriate place
  311.        
  312.        
  313.         return pushedTile
  314.        
  315.        
  316.         */
  317.     }
  318.  
  319.     std::string pushCol(int col, int direction, const std::string &tileInPushersHand)
  320.     {
  321.         /*
  322.         same as above but for pushing a column
  323.         */
  324.     }
  325. };
  326.  
  327. struct Agent
  328. {
  329.     State state;
  330.  
  331.     void read();
  332.     void act();
  333. };
  334.  
  335. void Agent::read()
  336. {
  337.     // read turn type
  338.     int turnType;
  339.     std::cin >> turnType; std::cin.ignore();
  340.     state.turnType = turnType;
  341.  
  342.     // read grid
  343.     for (int r = 0; r < ROWS; r++) {
  344.         for (int c = 0; c < COLS; c++) {
  345.             std::string tile;
  346.             std::cin >> tile; std::cin.ignore();
  347.             state.grid[r][c] = tile;
  348.         }
  349.     }
  350.  
  351.     // read player data
  352.     for (int i = 0; i < 2; i++) {
  353.         int numPlayerCards; // the total number of quests for a player (hidden and revealed)
  354.         int playerX;
  355.         int playerY;
  356.         std::string playerTile;
  357.         std::cin >> numPlayerCards >> playerX >> playerY >> playerTile; std::cin.ignore();
  358.         state.players[i].set(numPlayerCards, playerX, playerY, playerTile);
  359.     }
  360.  
  361.     // read items
  362.     state.items.clear();
  363.     int numItems; // the total number of items available on board and on player tiles
  364.     std::cin >> numItems; std::cin.ignore();
  365.     for (int i = 0; i < numItems; i++) {
  366.         std::string itemName;
  367.         int itemX;
  368.         int itemY;
  369.         int itemPlayerId;
  370.         std::cin >> itemName >> itemX >> itemY >> itemPlayerId; std::cin.ignore();
  371.         state.items.emplace_back();
  372.         state.items.back().set(itemName, itemX, itemY, itemPlayerId);
  373.     }
  374.  
  375.     // read quests
  376.     state.quests.clear();
  377.     int numQuests; // the total number of revealed quests for both players
  378.     std::cin >> numQuests; std::cin.ignore();
  379.     for (int i = 0; i < numQuests; i++) {
  380.         std::string questItemName;
  381.         int questPlayerId;
  382.         std::cin >> questItemName >> questPlayerId; std::cin.ignore();
  383.         state.quests.emplace_back();
  384.         state.quests.back().set(questItemName, questPlayerId);
  385.     }
  386. }
  387.  
  388. void Agent::act()
  389. {
  390.   Item* itemSought;
  391.  
  392.     /*
  393.     get the first of my quests from quests
  394.    
  395.     get the item corresponding to that quest from items, point itemSought to it
  396.     */
  397.    
  398.     if (state.turnType == TURN_PUSH)
  399.     {
  400.         if (itemSought->itemCell.row == -2)
  401.         {
  402.             std::cerr << "Item sought is with opponent - Pushing 0 Right for now" << std::endl;
  403.             std::cout << "PUSH 0 RIGHT" << std::endl;
  404.         }
  405.         else
  406.         {
  407.             std::string __path;
  408.  
  409.  
  410.             int bestNearestDistance = LARGE_DISTANCE;
  411.             int bestRowOrCol = ROWS;
  412.             int bestDir = DIRS;
  413.  
  414.             int rowDirs[] = { LEFT, RIGHT };
  415.             int colDirs[] = { UP, DOWN };
  416.  
  417.             for (int r = 0; r < ROWS; r++)
  418.             {
  419.                 for (auto d : rowDirs)
  420.                 {
  421.                     // push a row
  422.                     auto pushed = state.pushRow(r, d, state.me->playerTile);
  423.                     // get path as near as possible to the quest item
  424.                     int distance = LARGE_DISTANCE;
  425.                     if (itemSought->itemCell.inBounds() && state.me->playerCell.inBounds())
  426.                         distance = getPathAsNearAsPossible(state.grid, state.me->playerCell, itemSought->itemCell, __path);
  427.                     // push in opposite direction with the tile that got pushed out earlier
  428.                     state.pushRow(r, getOppDir(d), pushed);
  429.                    
  430.                     // keep track if it is the best
  431.                     if (distance < bestNearestDistance)
  432.                     {
  433.                         bestNearestDistance = distance;
  434.                         bestRowOrCol = r;
  435.                         bestDir = d;
  436.                     }
  437.                 }
  438.             }
  439.  
  440.             /*
  441.             do the same with col in outer loop and colDirs in inner loop
  442.             */
  443.            
  444.             std::cout << "PUSH " << bestRowOrCol << " " << directions[bestDir] << std::endl;
  445.         }
  446.     }
  447.     else
  448.     {
  449.         std::string path;
  450.         getPathAsNearAsPossible(state.grid, state.me->playerCell, itemSought->itemCell, path);
  451.         if (path.size() == 0)
  452.             std::cout << "PASS" << std::endl;
  453.         else
  454.             std::cout << "MOVE" << path << std::endl;
  455.     }
  456. }
  457.  
  458.  
  459. int main()
  460. {
  461.     Agent agent;
  462.    
  463.     // game loop
  464.     while (true) {
  465.  
  466.         agent.read();
  467.         std::cerr << agent.state << std::endl;
  468.         agent.act();
  469.     }
  470. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top