// SnakeAI.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
int main( )
{
std:: cout << "Hello World!\n " ;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
#define ARENA_SIZE 13 * 13
#define ARENA_HEIGHT 13
#define ARENA_WIDTH 13
int tourToNumber[ ARENA_SIZE] ;
/* Take an x,y coordinate, and turn it into an index in the tour */
int getPathNumber( int x, int y) {
return tourToNumber[ x + ARENA_WIDTH * y] ;
}
int path_distance( int a, int b) {
if ( a < b)
return b - a - 1 ;
return b - a - 1 + ARENA_SIZE;
}
struct Maze {
struct Node {
bool visited : 1 ;
bool canGoRight : 1 ;
bool canGoDown : 1 ;
} ;
Node nodes[ ARENA_SIZE / 4 ] ;
void markVisited( int x, int y) {
nodes[ x + y * ARENA_WIDTH / 2 ] .visited = true ;
}
void markCanGoRight( int x, int y) {
nodes[ x + y * ARENA_WIDTH / 2 ] .canGoRight = true ;
}
void markCanGoDown( int x, int y) {
nodes[ x + y * ARENA_WIDTH / 2 ] .canGoDown = true ;
}
bool canGoRight( int x, int y) {
return nodes[ x + y * ARENA_WIDTH / 2 ] .canGoRight ;;
}
bool canGoDown( int x, int y) {
return nodes[ x + y * ARENA_WIDTH / 2 ] .canGoDown ;
}
bool canGoLeft( int x, int y) {
if ( x == 0 ) return false ;
return nodes[ ( x - 1 ) + y * ARENA_WIDTH / 2 ] .canGoRight ;
}
bool canGoUp( int x, int y) {
if ( y == 0 ) return false ;
return nodes[ x + ( y - 1 ) * ARENA_WIDTH / 2 ] .canGoDown ;
}
bool isVisited( int x, int y) {
return nodes[ x + y * ARENA_WIDTH / 2 ] .visited ;
}
void generate( ) {
memset ( nodes, 0 , sizeof ( nodes) ) ;
generate_r( - 1 , - 1 , 0 , 0 ) ;
generateTourNumber( ) ;
#ifdef LOG_TO_FILE
writeMazeToFile( ) ;
writeTourToFile( ) ;
#endif
}
void generate_r( int fromx, int fromy, int x, int y) {
if ( x < 0 || y < 0 || x >= ARENA_WIDTH / 2 || y >= ARENA_HEIGHT / 2 )
return ;
if ( isVisited( x, y) )
return ;
markVisited( x, y) ;
if ( fromx ! = - 1 ) {
if ( fromx < x)
markCanGoRight( fromx, fromy) ;
else if ( fromx > x)
markCanGoRight( x, y) ;
else if ( fromy < y)
markCanGoDown( fromx, fromy) ;
else if ( fromy > y)
markCanGoDown( x, y) ;
//Remove wall between fromx and fromy
}
/* We want to visit the four connected nodes randomly,
* so we just visit two randomly (maybe already visited)
* then just visit them all non-randomly. It's okay to
* visit the same node twice */
for ( int i = 0 ; i < 2 ; i++ ) {
int r = rand ( ) % 4 ;
switch ( r) {
case 0 : generate_r( x, y, x - 1 , y) ; break ;
case 1 : generate_r( x, y, x + 1 , y) ; break ;
case 2 : generate_r( x, y, x, y - 1 ) ; break ;
case 3 : generate_r( x, y, x, y + 1 ) ; break ;
}
}
generate_r( x, y, x - 1 , y) ;
generate_r( x, y, x + 1 , y) ;
generate_r( x, y, x, y + 1 ) ;
generate_r( x, y, x, y - 1 ) ;
}
SnakeDirection findNextDir( int x, int y, SnakeDirection dir) {
if ( dir == Right) {
if ( canGoUp( x, y) )
return Up;
if ( canGoRight( x, y) )
return Right;
if ( canGoDown( x, y) )
return Down;
return Left;
}
else if ( dir == Down) {
if ( canGoRight( x, y) )
return Right;
if ( canGoDown( x, y) )
return Down;
if ( canGoLeft( x, y) )
return Left;
return Up;
}
else if ( dir == Left) {
if ( canGoDown( x, y) )
return Down;
if ( canGoLeft( x, y) )
return Left;
if ( canGoUp( x, y) )
return Up;
return Right;
}
else if ( dir == Up) {
if ( canGoLeft( x, y) )
return Left;
if ( canGoUp( x, y) )
return Up;
if ( canGoRight( x, y) )
return Right;
return Down;
}
return ( SnakeDirection) - 1 ; //Unreachable
}
void setTourNumber( int x, int y, int number) {
if ( getPathNumber( x, y) ! = 0 )
return ; /* Back to the starting node */
tourToNumber[ x + ARENA_WIDTH * y] = number;
}
void generateTourNumber( ) {
const int start_x = 0 ;
const int start_y = 0 ;
int x = start_x;
int y = start_y;
const SnakeDirection start_dir = canGoDown( x, y) ? Up : Left;
SnakeDirection dir = start_dir;
int number = 0 ;
do {
SnakeDirection nextDir = findNextDir( x, y, dir) ;
switch ( dir) {
case Right:
setTourNumber( x * 2 , y * 2 , number++ ) ;
if ( nextDir == dir || nextDir == Down || nextDir == Left)
setTourNumber( x * 2 + 1 , y * 2 , number++ ) ;
if ( nextDir == Down || nextDir == Left)
setTourNumber( x * 2 + 1 , y * 2 + 1 , number++ ) ;
if ( nextDir == Left)
setTourNumber( x * 2 , y * 2 + 1 , number++ ) ;
break ;
case Down:
setTourNumber( x * 2 + 1 , y * 2 , number++ ) ;
if ( nextDir == dir || nextDir == Left || nextDir == Up)
setTourNumber( x * 2 + 1 , y * 2 + 1 , number++ ) ;
if ( nextDir == Left || nextDir == Up)
setTourNumber( x * 2 , y * 2 + 1 , number++ ) ;
if ( nextDir == Up)
setTourNumber( x * 2 , y * 2 , number++ ) ;
break ;
case Left:
setTourNumber( x * 2 + 1 , y * 2 + 1 , number++ ) ;
if ( nextDir == dir || nextDir == Up || nextDir == Right)
setTourNumber( x * 2 , y * 2 + 1 , number++ ) ;
if ( nextDir == Up || nextDir == Right)
setTourNumber( x * 2 , y * 2 , number++ ) ;
if ( nextDir == Right)
setTourNumber( x * 2 + 1 , y * 2 , number++ ) ;
break ;
case Up:
setTourNumber( x * 2 , y * 2 + 1 , number++ ) ;
if ( nextDir == dir || nextDir == Right || nextDir == Down)
setTourNumber( x * 2 , y * 2 , number++ ) ;
if ( nextDir == Right || nextDir == Down)
setTourNumber( x * 2 + 1 , y * 2 , number++ ) ;
if ( nextDir == Down)
setTourNumber( x * 2 + 1 , y * 2 + 1 , number++ ) ;
break ;
}
dir = nextDir;
switch ( nextDir) {
case Right: ++ x; break ;
case Left: -- x; break ;
case Down: ++ y; break ;
case Up: -- y; break ;
}
} while ( number ! = ARENA_SIZE) ; //Loop until we return to the start
}
#ifdef LOG_TO_FILE
void writeTourToFile( ) {
FILE * f = fopen ( "maps.txt" , "w+" ) ;
for ( int y = 0 ; y < ARENA_HEIGHT; ++ y) {
for ( int x = 0 ; x < ARENA_WIDTH; ++ x)
fprintf ( f, "%4d" , getPathNumber( x, y) ) ;
fprintf ( f, "\n " ) ;
}
fclose ( f) ;
}
void writeMazeToFile( ) {
FILE * f = fopen ( "maze.txt" , "w+" ) ;
for ( int y = 0 ; y < ARENA_HEIGHT / 2 ; ++ y) {
fprintf ( f, "#" ) ;
for ( int x = 0 ; x < ARENA_WIDTH / 2 ; ++ x)
if ( canGoRight( x, y) && canGoDown( x, y) )
fprintf ( f, "+" ) ;
else if ( canGoRight( x, y) )
fprintf ( f, "-" ) ;
else if ( canGoDown( x, y) )
fprintf ( f, "|" ) ;
else
fprintf ( f, " " ) ;
fprintf ( f, "#\n " ) ;
}
fclose ( f) ;
}
#endif
} ;
void aiInit( ) {
Maze maze;
maze.generate ( ) ;
}
enum SnakeDirection
{
Right, Left, Up, Down
} ;
SnakeDirection aiGetNewSnakeDirection( int x, int y) {
const int pathNumber = getPathNumber( x, y) ;
const int distanceToFood = path_distance( pathNumber, getPathNumber( food.x , food.y ) ) ;
const int distanceToTail = path_distance( pathNumber, getPathNumber( snake.tail_x , snake.tail_y ) ) ;
int cuttingAmountAvailable = distanceToTail - snake.growth_length - 3 /* Allow a small buffer */ ;
const int numEmptySquaresOnBoard = ARENA_SIZE - snake.drawn_length - snake.growth_length - food.value ;
// If we don't have much space (i.e. snake is 75% of board) then don't take any shortcuts */
if ( numEmptySquaresOnBoard < ARENA_SIZE / 2 )
cuttingAmountAvailable = 0 ;
else if ( distanceToFood < distanceToTail) { /* We will eat the food on the way to the tail, so take that into account */
cuttingAmountAvailable - = food.value ;
/* Once we ate that food, we might end up with another food suddenly appearing in front of us */
if ( ( distanceToTail - distanceToFood) * 4 > numEmptySquaresOnBoard) /* 25% chance of another number appearing */
cuttingAmountAvailable - = 10 ;
}
int cuttingAmountDesired = distanceToFood;
if ( cuttingAmountDesired < cuttingAmountAvailable)
cuttingAmountAvailable = cuttingAmountDesired;
if ( cuttingAmountAvailable < 0 )
cuttingAmountAvailable = 0 ;
// cuttingAmountAvailable is now the maximum amount that we can cut by
bool canGoRight = ! check_for_collision( x + 1 , y) ;
bool canGoLeft = ! check_for_collision( x - 1 , y) ;
bool canGoDown = ! check_for_collision( x, y + 1 ) ;
bool canGoUp = ! check_for_collision( x, y - 1 ) ;
SnakeDirection bestDir;
int bestDist = - 1 ;
if ( canGoRight) {
int dist = path_distance( pathNumber, getPathNumber( x + 1 , y) ) ;
if ( dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Right;
bestDist = dist;
}
}
if ( canGoLeft) {
int dist = path_distance( pathNumber, getPathNumber( x - 1 , y) ) ;
if ( dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Left;
bestDist = dist;
}
}
if ( canGoDown) {
int dist = path_distance( pathNumber, getPathNumber( x, y + 1 ) ) ;
if ( dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Down;
bestDist = dist;
}
}
if ( canGoUp) {
int dist = path_distance( pathNumber, getPathNumber( x, y - 1 ) ) ;
if ( dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Up;
bestDist = dist;
}
}
if ( bestDist >= 0 )
return bestDir;
if ( canGoUp)
return Up;
if ( canGoLeft)
return Left;
if ( canGoDown)
return Down;
if ( canGoRight)
return Right;
return Right;
}
Ly8gU25ha2VBSS5jcHAgOiBUaGlzIGZpbGUgY29udGFpbnMgdGhlICdtYWluJyBmdW5jdGlvbi4gUHJvZ3JhbSBleGVjdXRpb24gYmVnaW5zIGFuZCBlbmRzIHRoZXJlLgovLwoKI2luY2x1ZGUgPGlvc3RyZWFtPgoKaW50IG1haW4oKQp7CiAgICBzdGQ6OmNvdXQgPDwgIkhlbGxvIFdvcmxkIVxuIjsKfQoKLy8gUnVuIHByb2dyYW06IEN0cmwgKyBGNSBvciBEZWJ1ZyA+IFN0YXJ0IFdpdGhvdXQgRGVidWdnaW5nIG1lbnUKLy8gRGVidWcgcHJvZ3JhbTogRjUgb3IgRGVidWcgPiBTdGFydCBEZWJ1Z2dpbmcgbWVudQoKLy8gVGlwcyBmb3IgR2V0dGluZyBTdGFydGVkOiAKLy8gICAxLiBVc2UgdGhlIFNvbHV0aW9uIEV4cGxvcmVyIHdpbmRvdyB0byBhZGQvbWFuYWdlIGZpbGVzCi8vICAgMi4gVXNlIHRoZSBUZWFtIEV4cGxvcmVyIHdpbmRvdyB0byBjb25uZWN0IHRvIHNvdXJjZSBjb250cm9sCi8vICAgMy4gVXNlIHRoZSBPdXRwdXQgd2luZG93IHRvIHNlZSBidWlsZCBvdXRwdXQgYW5kIG90aGVyIG1lc3NhZ2VzCi8vICAgNC4gVXNlIHRoZSBFcnJvciBMaXN0IHdpbmRvdyB0byB2aWV3IGVycm9ycwovLyAgIDUuIEdvIHRvIFByb2plY3QgPiBBZGQgTmV3IEl0ZW0gdG8gY3JlYXRlIG5ldyBjb2RlIGZpbGVzLCBvciBQcm9qZWN0ID4gQWRkIEV4aXN0aW5nIEl0ZW0gdG8gYWRkIGV4aXN0aW5nIGNvZGUgZmlsZXMgdG8gdGhlIHByb2plY3QKLy8gICA2LiBJbiB0aGUgZnV0dXJlLCB0byBvcGVuIHRoaXMgcHJvamVjdCBhZ2FpbiwgZ28gdG8gRmlsZSA+IE9wZW4gPiBQcm9qZWN0IGFuZCBzZWxlY3QgdGhlIC5zbG4gZmlsZQojZGVmaW5lIEFSRU5BX1NJWkUgMTMgKiAxMwojZGVmaW5lIEFSRU5BX0hFSUdIVCAxMwojZGVmaW5lIEFSRU5BX1dJRFRIIDEzCgppbnQgdG91clRvTnVtYmVyW0FSRU5BX1NJWkVdOwoKLyogVGFrZSBhbiB4LHkgY29vcmRpbmF0ZSwgYW5kIHR1cm4gaXQgaW50byBhbiBpbmRleCBpbiB0aGUgdG91ciAqLwppbnQgZ2V0UGF0aE51bWJlcihpbnQgeCwgaW50IHkpIHsKICAgIHJldHVybiB0b3VyVG9OdW1iZXJbeCArIEFSRU5BX1dJRFRIICogeV07Cn0KCmludCBwYXRoX2Rpc3RhbmNlKGludCBhLCBpbnQgYikgewogICAgaWYgKGEgPCBiKQogICAgICAgIHJldHVybiBiIC0gYSAtIDE7CiAgICByZXR1cm4gYiAtIGEgLSAxICsgQVJFTkFfU0laRTsKfQoKc3RydWN0IE1hemUgewogICAgc3RydWN0IE5vZGUgewogICAgICAgIGJvb2wgdmlzaXRlZCA6IDE7CiAgICAgICAgYm9vbCBjYW5Hb1JpZ2h0IDogMTsKICAgICAgICBib29sIGNhbkdvRG93biA6IDE7CiAgICB9OwogICAgTm9kZSBub2Rlc1tBUkVOQV9TSVpFIC8gNF07CiAgICB2b2lkIG1hcmtWaXNpdGVkKGludCB4LCBpbnQgeSkgewogICAgICAgIG5vZGVzW3ggKyB5ICogQVJFTkFfV0lEVEggLyAyXS52aXNpdGVkID0gdHJ1ZTsKICAgIH0KICAgIHZvaWQgbWFya0NhbkdvUmlnaHQoaW50IHgsIGludCB5KSB7CiAgICAgICAgbm9kZXNbeCArIHkgKiBBUkVOQV9XSURUSCAvIDJdLmNhbkdvUmlnaHQgPSB0cnVlOwogICAgfQogICAgdm9pZCBtYXJrQ2FuR29Eb3duKGludCB4LCBpbnQgeSkgewogICAgICAgIG5vZGVzW3ggKyB5ICogQVJFTkFfV0lEVEggLyAyXS5jYW5Hb0Rvd24gPSB0cnVlOwogICAgfQogICAgYm9vbCBjYW5Hb1JpZ2h0KGludCB4LCBpbnQgeSkgewogICAgICAgIHJldHVybiBub2Rlc1t4ICsgeSAqIEFSRU5BX1dJRFRIIC8gMl0uY2FuR29SaWdodDs7CiAgICB9CiAgICBib29sIGNhbkdvRG93bihpbnQgeCwgaW50IHkpIHsKICAgICAgICByZXR1cm4gbm9kZXNbeCArIHkgKiBBUkVOQV9XSURUSCAvIDJdLmNhbkdvRG93bjsKICAgIH0KICAgIGJvb2wgY2FuR29MZWZ0KGludCB4LCBpbnQgeSkgewogICAgICAgIGlmICh4ID09IDApIHJldHVybiBmYWxzZTsKICAgICAgICByZXR1cm4gbm9kZXNbKHggLSAxKSArIHkgKiBBUkVOQV9XSURUSCAvIDJdLmNhbkdvUmlnaHQ7CiAgICB9CgogICAgYm9vbCBjYW5Hb1VwKGludCB4LCBpbnQgeSkgewogICAgICAgIGlmICh5ID09IDApIHJldHVybiBmYWxzZTsKICAgICAgICByZXR1cm4gbm9kZXNbeCArICh5IC0gMSkgKiBBUkVOQV9XSURUSCAvIDJdLmNhbkdvRG93bjsKICAgIH0KCiAgICBib29sIGlzVmlzaXRlZChpbnQgeCwgaW50IHkpIHsKICAgICAgICByZXR1cm4gbm9kZXNbeCArIHkgKiBBUkVOQV9XSURUSCAvIDJdLnZpc2l0ZWQ7CiAgICB9CgogICAgdm9pZCBnZW5lcmF0ZSgpIHsKICAgICAgICBtZW1zZXQobm9kZXMsIDAsIHNpemVvZihub2RlcykpOwogICAgICAgIGdlbmVyYXRlX3IoLTEsIC0xLCAwLCAwKTsKICAgICAgICBnZW5lcmF0ZVRvdXJOdW1iZXIoKTsKICAgICAgICNpZmRlZiBMT0dfVE9fRklMRQogICAgICAgIHdyaXRlTWF6ZVRvRmlsZSgpOwogICAgICAgIHdyaXRlVG91clRvRmlsZSgpOwogICAgICAgI2VuZGlmCiAgICB9CgogICAgdm9pZCBnZW5lcmF0ZV9yKGludCBmcm9teCwgaW50IGZyb215LCBpbnQgeCwgaW50IHkpIHsKICAgICAgICBpZiAoeCA8IDAgfHwgeSA8IDAgfHwgeCA+PSBBUkVOQV9XSURUSCAvIDIgfHwgeSA+PSBBUkVOQV9IRUlHSFQgLyAyKQogICAgICAgICAgICByZXR1cm47CiAgICAgICAgaWYgKGlzVmlzaXRlZCh4LCB5KSkKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIG1hcmtWaXNpdGVkKHgsIHkpOwoKICAgICAgICBpZiAoZnJvbXggIT0gLTEpIHsKICAgICAgICAgICAgaWYgKGZyb214IDwgeCkKICAgICAgICAgICAgICAgIG1hcmtDYW5Hb1JpZ2h0KGZyb214LCBmcm9teSk7CiAgICAgICAgICAgIGVsc2UgaWYgKGZyb214ID4geCkKICAgICAgICAgICAgICAgIG1hcmtDYW5Hb1JpZ2h0KHgsIHkpOwogICAgICAgICAgICBlbHNlIGlmIChmcm9teSA8IHkpCiAgICAgICAgICAgICAgICBtYXJrQ2FuR29Eb3duKGZyb214LCBmcm9teSk7CiAgICAgICAgICAgIGVsc2UgaWYgKGZyb215ID4geSkKICAgICAgICAgICAgICAgIG1hcmtDYW5Hb0Rvd24oeCwgeSk7CgogICAgICAgICAgICAvL1JlbW92ZSB3YWxsIGJldHdlZW4gZnJvbXggYW5kIGZyb215CiAgICAgICAgfQoKICAgICAgICAvKiBXZSB3YW50IHRvIHZpc2l0IHRoZSBmb3VyIGNvbm5lY3RlZCBub2RlcyByYW5kb21seSwKICAgICAgICAgKiBzbyB3ZSBqdXN0IHZpc2l0IHR3byByYW5kb21seSAobWF5YmUgYWxyZWFkeSB2aXNpdGVkKQogICAgICAgICAqIHRoZW4ganVzdCB2aXNpdCB0aGVtIGFsbCBub24tcmFuZG9tbHkuICBJdCdzIG9rYXkgdG8KICAgICAgICAgKiB2aXNpdCB0aGUgc2FtZSBub2RlIHR3aWNlICovCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyOyBpKyspIHsKICAgICAgICAgICAgaW50IHIgPSByYW5kKCkgJSA0OwogICAgICAgICAgICBzd2l0Y2ggKHIpIHsKICAgICAgICAgICAgY2FzZSAwOiBnZW5lcmF0ZV9yKHgsIHksIHggLSAxLCB5KTsgYnJlYWs7CiAgICAgICAgICAgIGNhc2UgMTogZ2VuZXJhdGVfcih4LCB5LCB4ICsgMSwgeSk7IGJyZWFrOwogICAgICAgICAgICBjYXNlIDI6IGdlbmVyYXRlX3IoeCwgeSwgeCwgeSAtIDEpOyBicmVhazsKICAgICAgICAgICAgY2FzZSAzOiBnZW5lcmF0ZV9yKHgsIHksIHgsIHkgKyAxKTsgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgZ2VuZXJhdGVfcih4LCB5LCB4IC0gMSwgeSk7CiAgICAgICAgZ2VuZXJhdGVfcih4LCB5LCB4ICsgMSwgeSk7CiAgICAgICAgZ2VuZXJhdGVfcih4LCB5LCB4LCB5ICsgMSk7CiAgICAgICAgZ2VuZXJhdGVfcih4LCB5LCB4LCB5IC0gMSk7CiAgICB9CgogICAgU25ha2VEaXJlY3Rpb24gZmluZE5leHREaXIoaW50IHgsIGludCB5LCBTbmFrZURpcmVjdGlvbiBkaXIpIHsKICAgICAgICBpZiAoZGlyID09IFJpZ2h0KSB7CiAgICAgICAgICAgIGlmIChjYW5Hb1VwKHgsIHkpKQogICAgICAgICAgICAgICAgcmV0dXJuIFVwOwogICAgICAgICAgICBpZiAoY2FuR29SaWdodCh4LCB5KSkKICAgICAgICAgICAgICAgIHJldHVybiBSaWdodDsKICAgICAgICAgICAgaWYgKGNhbkdvRG93bih4LCB5KSkKICAgICAgICAgICAgICAgIHJldHVybiBEb3duOwogICAgICAgICAgICByZXR1cm4gTGVmdDsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZiAoZGlyID09IERvd24pIHsKICAgICAgICAgICAgaWYgKGNhbkdvUmlnaHQoeCwgeSkpCiAgICAgICAgICAgICAgICByZXR1cm4gUmlnaHQ7CiAgICAgICAgICAgIGlmIChjYW5Hb0Rvd24oeCwgeSkpCiAgICAgICAgICAgICAgICByZXR1cm4gRG93bjsKICAgICAgICAgICAgaWYgKGNhbkdvTGVmdCh4LCB5KSkKICAgICAgICAgICAgICAgIHJldHVybiBMZWZ0OwogICAgICAgICAgICByZXR1cm4gVXA7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYgKGRpciA9PSBMZWZ0KSB7CiAgICAgICAgICAgIGlmIChjYW5Hb0Rvd24oeCwgeSkpCiAgICAgICAgICAgICAgICByZXR1cm4gRG93bjsKICAgICAgICAgICAgaWYgKGNhbkdvTGVmdCh4LCB5KSkKICAgICAgICAgICAgICAgIHJldHVybiBMZWZ0OwogICAgICAgICAgICBpZiAoY2FuR29VcCh4LCB5KSkKICAgICAgICAgICAgICAgIHJldHVybiBVcDsKICAgICAgICAgICAgcmV0dXJuIFJpZ2h0OwogICAgICAgIH0KICAgICAgICBlbHNlIGlmIChkaXIgPT0gVXApIHsKICAgICAgICAgICAgaWYgKGNhbkdvTGVmdCh4LCB5KSkKICAgICAgICAgICAgICAgIHJldHVybiBMZWZ0OwogICAgICAgICAgICBpZiAoY2FuR29VcCh4LCB5KSkKICAgICAgICAgICAgICAgIHJldHVybiBVcDsKICAgICAgICAgICAgaWYgKGNhbkdvUmlnaHQoeCwgeSkpCiAgICAgICAgICAgICAgICByZXR1cm4gUmlnaHQ7CiAgICAgICAgICAgIHJldHVybiBEb3duOwogICAgICAgIH0KICAgICAgICByZXR1cm4gKFNuYWtlRGlyZWN0aW9uKS0xOyAvL1VucmVhY2hhYmxlCiAgICB9CiAgICB2b2lkIHNldFRvdXJOdW1iZXIoaW50IHgsIGludCB5LCBpbnQgbnVtYmVyKSB7CiAgICAgICAgaWYgKGdldFBhdGhOdW1iZXIoeCwgeSkgIT0gMCkKICAgICAgICAgICAgcmV0dXJuOyAvKiBCYWNrIHRvIHRoZSBzdGFydGluZyBub2RlICovCiAgICAgICAgdG91clRvTnVtYmVyW3ggKyBBUkVOQV9XSURUSCAqIHldID0gbnVtYmVyOwogICAgfQoKICAgIHZvaWQgZ2VuZXJhdGVUb3VyTnVtYmVyKCkgewogICAgICAgIGNvbnN0IGludCBzdGFydF94ID0gMDsKICAgICAgICBjb25zdCBpbnQgc3RhcnRfeSA9IDA7CiAgICAgICAgaW50IHggPSBzdGFydF94OwogICAgICAgIGludCB5ID0gc3RhcnRfeTsKICAgICAgICBjb25zdCBTbmFrZURpcmVjdGlvbiBzdGFydF9kaXIgPSBjYW5Hb0Rvd24oeCwgeSkgPyBVcCA6IExlZnQ7CiAgICAgICAgU25ha2VEaXJlY3Rpb24gZGlyID0gc3RhcnRfZGlyOwogICAgICAgIGludCBudW1iZXIgPSAwOwogICAgICAgIGRvIHsKICAgICAgICAgICAgU25ha2VEaXJlY3Rpb24gbmV4dERpciA9IGZpbmROZXh0RGlyKHgsIHksIGRpcik7CiAgICAgICAgICAgIHN3aXRjaCAoZGlyKSB7CiAgICAgICAgICAgIGNhc2UgUmlnaHQ6CiAgICAgICAgICAgICAgICBzZXRUb3VyTnVtYmVyKHggKiAyLCB5ICogMiwgbnVtYmVyKyspOwogICAgICAgICAgICAgICAgaWYgKG5leHREaXIgPT0gZGlyIHx8IG5leHREaXIgPT0gRG93biB8fCBuZXh0RGlyID09IExlZnQpCiAgICAgICAgICAgICAgICAgICAgc2V0VG91ck51bWJlcih4ICogMiArIDEsIHkgKiAyLCBudW1iZXIrKyk7CiAgICAgICAgICAgICAgICBpZiAobmV4dERpciA9PSBEb3duIHx8IG5leHREaXIgPT0gTGVmdCkKICAgICAgICAgICAgICAgICAgICBzZXRUb3VyTnVtYmVyKHggKiAyICsgMSwgeSAqIDIgKyAxLCBudW1iZXIrKyk7CiAgICAgICAgICAgICAgICBpZiAobmV4dERpciA9PSBMZWZ0KQogICAgICAgICAgICAgICAgICAgIHNldFRvdXJOdW1iZXIoeCAqIDIsIHkgKiAyICsgMSwgbnVtYmVyKyspOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIGNhc2UgRG93bjoKICAgICAgICAgICAgICAgIHNldFRvdXJOdW1iZXIoeCAqIDIgKyAxLCB5ICogMiwgbnVtYmVyKyspOwogICAgICAgICAgICAgICAgaWYgKG5leHREaXIgPT0gZGlyIHx8IG5leHREaXIgPT0gTGVmdCB8fCBuZXh0RGlyID09IFVwKQogICAgICAgICAgICAgICAgICAgIHNldFRvdXJOdW1iZXIoeCAqIDIgKyAxLCB5ICogMiArIDEsIG51bWJlcisrKTsKICAgICAgICAgICAgICAgIGlmIChuZXh0RGlyID09IExlZnQgfHwgbmV4dERpciA9PSBVcCkKICAgICAgICAgICAgICAgICAgICBzZXRUb3VyTnVtYmVyKHggKiAyLCB5ICogMiArIDEsIG51bWJlcisrKTsKICAgICAgICAgICAgICAgIGlmIChuZXh0RGlyID09IFVwKQogICAgICAgICAgICAgICAgICAgIHNldFRvdXJOdW1iZXIoeCAqIDIsIHkgKiAyLCBudW1iZXIrKyk7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgY2FzZSBMZWZ0OgogICAgICAgICAgICAgICAgc2V0VG91ck51bWJlcih4ICogMiArIDEsIHkgKiAyICsgMSwgbnVtYmVyKyspOwogICAgICAgICAgICAgICAgaWYgKG5leHREaXIgPT0gZGlyIHx8IG5leHREaXIgPT0gVXAgfHwgbmV4dERpciA9PSBSaWdodCkKICAgICAgICAgICAgICAgICAgICBzZXRUb3VyTnVtYmVyKHggKiAyLCB5ICogMiArIDEsIG51bWJlcisrKTsKICAgICAgICAgICAgICAgIGlmIChuZXh0RGlyID09IFVwIHx8IG5leHREaXIgPT0gUmlnaHQpCiAgICAgICAgICAgICAgICAgICAgc2V0VG91ck51bWJlcih4ICogMiwgeSAqIDIsIG51bWJlcisrKTsKICAgICAgICAgICAgICAgIGlmIChuZXh0RGlyID09IFJpZ2h0KQogICAgICAgICAgICAgICAgICAgIHNldFRvdXJOdW1iZXIoeCAqIDIgKyAxLCB5ICogMiwgbnVtYmVyKyspOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIGNhc2UgVXA6CiAgICAgICAgICAgICAgICBzZXRUb3VyTnVtYmVyKHggKiAyLCB5ICogMiArIDEsIG51bWJlcisrKTsKICAgICAgICAgICAgICAgIGlmIChuZXh0RGlyID09IGRpciB8fCBuZXh0RGlyID09IFJpZ2h0IHx8IG5leHREaXIgPT0gRG93bikKICAgICAgICAgICAgICAgICAgICBzZXRUb3VyTnVtYmVyKHggKiAyLCB5ICogMiwgbnVtYmVyKyspOwogICAgICAgICAgICAgICAgaWYgKG5leHREaXIgPT0gUmlnaHQgfHwgbmV4dERpciA9PSBEb3duKQogICAgICAgICAgICAgICAgICAgIHNldFRvdXJOdW1iZXIoeCAqIDIgKyAxLCB5ICogMiwgbnVtYmVyKyspOwogICAgICAgICAgICAgICAgaWYgKG5leHREaXIgPT0gRG93bikKICAgICAgICAgICAgICAgICAgICBzZXRUb3VyTnVtYmVyKHggKiAyICsgMSwgeSAqIDIgKyAxLCBudW1iZXIrKyk7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBkaXIgPSBuZXh0RGlyOwoKICAgICAgICAgICAgc3dpdGNoIChuZXh0RGlyKSB7CiAgICAgICAgICAgIGNhc2UgUmlnaHQ6ICsreDsgYnJlYWs7CiAgICAgICAgICAgIGNhc2UgTGVmdDogLS14OyBicmVhazsKICAgICAgICAgICAgY2FzZSBEb3duOiArK3k7IGJyZWFrOwogICAgICAgICAgICBjYXNlIFVwOiAtLXk7IGJyZWFrOwogICAgICAgICAgICB9CgogICAgICAgIH0gd2hpbGUgKG51bWJlciAhPSBBUkVOQV9TSVpFKTsgLy9Mb29wIHVudGlsIHdlIHJldHVybiB0byB0aGUgc3RhcnQKICAgIH0KI2lmZGVmIExPR19UT19GSUxFCiAgICB2b2lkIHdyaXRlVG91clRvRmlsZSgpIHsKICAgICAgICBGSUxFKiBmID0gZm9wZW4oIm1hcHMudHh0IiwgIncrIik7CiAgICAgICAgZm9yIChpbnQgeSA9IDA7IHkgPCBBUkVOQV9IRUlHSFQ7ICsreSkgewogICAgICAgICAgICBmb3IgKGludCB4ID0gMDsgeCA8IEFSRU5BX1dJRFRIOyArK3gpCiAgICAgICAgICAgICAgICBmcHJpbnRmKGYsICIlNGQiLCBnZXRQYXRoTnVtYmVyKHgsIHkpKTsKICAgICAgICAgICAgZnByaW50ZihmLCAiXG4iKTsKICAgICAgICB9CiAgICAgICAgZmNsb3NlKGYpOwogICAgfQogICAgdm9pZCB3cml0ZU1hemVUb0ZpbGUoKSB7CiAgICAgICAgRklMRSogZiA9IGZvcGVuKCJtYXplLnR4dCIsICJ3KyIpOwogICAgICAgIGZvciAoaW50IHkgPSAwOyB5IDwgQVJFTkFfSEVJR0hUIC8gMjsgKyt5KSB7CiAgICAgICAgICAgIGZwcmludGYoZiwgIiMiKTsKICAgICAgICAgICAgZm9yIChpbnQgeCA9IDA7IHggPCBBUkVOQV9XSURUSCAvIDI7ICsreCkKICAgICAgICAgICAgICAgIGlmIChjYW5Hb1JpZ2h0KHgsIHkpICYmIGNhbkdvRG93bih4LCB5KSkKICAgICAgICAgICAgICAgICAgICBmcHJpbnRmKGYsICIrIik7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChjYW5Hb1JpZ2h0KHgsIHkpKQogICAgICAgICAgICAgICAgICAgIGZwcmludGYoZiwgIi0iKTsKICAgICAgICAgICAgICAgIGVsc2UgaWYgKGNhbkdvRG93bih4LCB5KSkKICAgICAgICAgICAgICAgICAgICBmcHJpbnRmKGYsICJ8Iik7CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgZnByaW50ZihmLCAiICIpOwogICAgICAgICAgICBmcHJpbnRmKGYsICIjXG4iKTsKICAgICAgICB9CiAgICAgICAgZmNsb3NlKGYpOwogICAgfQojZW5kaWYKfTsKCnZvaWQgYWlJbml0KCkgewogICAgTWF6ZSBtYXplOwogICAgbWF6ZS5nZW5lcmF0ZSgpOwp9CgplbnVtIFNuYWtlRGlyZWN0aW9uCnsKICAgIFJpZ2h0LCBMZWZ0LCBVcCwgRG93bgp9OwoKU25ha2VEaXJlY3Rpb24gYWlHZXROZXdTbmFrZURpcmVjdGlvbihpbnQgeCwgaW50IHkpIHsKICAgIGNvbnN0IGludCBwYXRoTnVtYmVyID0gZ2V0UGF0aE51bWJlcih4LCB5KTsKICAgIGNvbnN0IGludCBkaXN0YW5jZVRvRm9vZCA9IHBhdGhfZGlzdGFuY2UocGF0aE51bWJlciwgZ2V0UGF0aE51bWJlcihmb29kLngsIGZvb2QueSkpOwogICAgY29uc3QgaW50IGRpc3RhbmNlVG9UYWlsID0gcGF0aF9kaXN0YW5jZShwYXRoTnVtYmVyLCBnZXRQYXRoTnVtYmVyKHNuYWtlLnRhaWxfeCwgc25ha2UudGFpbF95KSk7CiAgICBpbnQgY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSA9IGRpc3RhbmNlVG9UYWlsIC0gc25ha2UuZ3Jvd3RoX2xlbmd0aCAtIDMgLyogQWxsb3cgYSBzbWFsbCBidWZmZXIgKi87CiAgICBjb25zdCBpbnQgbnVtRW1wdHlTcXVhcmVzT25Cb2FyZCA9IEFSRU5BX1NJWkUgLSBzbmFrZS5kcmF3bl9sZW5ndGggLSBzbmFrZS5ncm93dGhfbGVuZ3RoIC0gZm9vZC52YWx1ZTsKICAgIC8vIElmIHdlIGRvbid0IGhhdmUgbXVjaCBzcGFjZSAoaS5lLiBzbmFrZSBpcyA3NSUgb2YgYm9hcmQpIHRoZW4gZG9uJ3QgdGFrZSBhbnkgc2hvcnRjdXRzICovCiAgICBpZiAobnVtRW1wdHlTcXVhcmVzT25Cb2FyZCA8IEFSRU5BX1NJWkUgLyAyKQogICAgICAgIGN1dHRpbmdBbW91bnRBdmFpbGFibGUgPSAwOwogICAgZWxzZSBpZiAoZGlzdGFuY2VUb0Zvb2QgPCBkaXN0YW5jZVRvVGFpbCkgeyAvKiBXZSB3aWxsIGVhdCB0aGUgZm9vZCBvbiB0aGUgd2F5IHRvIHRoZSB0YWlsLCBzbyB0YWtlIHRoYXQgaW50byBhY2NvdW50ICovCiAgICAgICAgY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSAtPSBmb29kLnZhbHVlOwogICAgICAgIC8qIE9uY2Ugd2UgYXRlIHRoYXQgZm9vZCwgd2UgbWlnaHQgZW5kIHVwIHdpdGggYW5vdGhlciBmb29kIHN1ZGRlbmx5IGFwcGVhcmluZyBpbiBmcm9udCBvZiB1cyAqLwogICAgICAgIGlmICgoZGlzdGFuY2VUb1RhaWwgLSBkaXN0YW5jZVRvRm9vZCkgKiA0ID4gbnVtRW1wdHlTcXVhcmVzT25Cb2FyZCkgLyogMjUlIGNoYW5jZSBvZiBhbm90aGVyIG51bWJlciBhcHBlYXJpbmcgKi8KICAgICAgICAgICAgY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSAtPSAxMDsKICAgIH0KICAgIGludCBjdXR0aW5nQW1vdW50RGVzaXJlZCA9IGRpc3RhbmNlVG9Gb29kOwogICAgaWYgKGN1dHRpbmdBbW91bnREZXNpcmVkIDwgY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSkKICAgICAgICBjdXR0aW5nQW1vdW50QXZhaWxhYmxlID0gY3V0dGluZ0Ftb3VudERlc2lyZWQ7CiAgICBpZiAoY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSA8IDApCiAgICAgICAgY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSA9IDA7CiAgICAvLyBjdXR0aW5nQW1vdW50QXZhaWxhYmxlIGlzIG5vdyB0aGUgbWF4aW11bSBhbW91bnQgdGhhdCB3ZSBjYW4gY3V0IGJ5CgogICAgYm9vbCBjYW5Hb1JpZ2h0ID0gIWNoZWNrX2Zvcl9jb2xsaXNpb24oeCArIDEsIHkpOwogICAgYm9vbCBjYW5Hb0xlZnQgPSAhY2hlY2tfZm9yX2NvbGxpc2lvbih4IC0gMSwgeSk7CiAgICBib29sIGNhbkdvRG93biA9ICFjaGVja19mb3JfY29sbGlzaW9uKHgsIHkgKyAxKTsKICAgIGJvb2wgY2FuR29VcCA9ICFjaGVja19mb3JfY29sbGlzaW9uKHgsIHkgLSAxKTsKCiAgICBTbmFrZURpcmVjdGlvbiBiZXN0RGlyOwogICAgaW50IGJlc3REaXN0ID0gLTE7CiAgICBpZiAoY2FuR29SaWdodCkgewogICAgICAgIGludCBkaXN0ID0gcGF0aF9kaXN0YW5jZShwYXRoTnVtYmVyLCBnZXRQYXRoTnVtYmVyKHggKyAxLCB5KSk7CiAgICAgICAgaWYgKGRpc3QgPD0gY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSAmJiBkaXN0ID4gYmVzdERpc3QpIHsKICAgICAgICAgICAgYmVzdERpciA9IFJpZ2h0OwogICAgICAgICAgICBiZXN0RGlzdCA9IGRpc3Q7CiAgICAgICAgfQogICAgfQogICAgaWYgKGNhbkdvTGVmdCkgewogICAgICAgIGludCBkaXN0ID0gcGF0aF9kaXN0YW5jZShwYXRoTnVtYmVyLCBnZXRQYXRoTnVtYmVyKHggLSAxLCB5KSk7CiAgICAgICAgaWYgKGRpc3QgPD0gY3V0dGluZ0Ftb3VudEF2YWlsYWJsZSAmJiBkaXN0ID4gYmVzdERpc3QpIHsKICAgICAgICAgICAgYmVzdERpciA9IExlZnQ7CiAgICAgICAgICAgIGJlc3REaXN0ID0gZGlzdDsKICAgICAgICB9CiAgICB9CiAgICBpZiAoY2FuR29Eb3duKSB7CiAgICAgICAgaW50IGRpc3QgPSBwYXRoX2Rpc3RhbmNlKHBhdGhOdW1iZXIsIGdldFBhdGhOdW1iZXIoeCwgeSArIDEpKTsKICAgICAgICBpZiAoZGlzdCA8PSBjdXR0aW5nQW1vdW50QXZhaWxhYmxlICYmIGRpc3QgPiBiZXN0RGlzdCkgewogICAgICAgICAgICBiZXN0RGlyID0gRG93bjsKICAgICAgICAgICAgYmVzdERpc3QgPSBkaXN0OwogICAgICAgIH0KICAgIH0KICAgIGlmIChjYW5Hb1VwKSB7CiAgICAgICAgaW50IGRpc3QgPSBwYXRoX2Rpc3RhbmNlKHBhdGhOdW1iZXIsIGdldFBhdGhOdW1iZXIoeCwgeSAtIDEpKTsKICAgICAgICBpZiAoZGlzdCA8PSBjdXR0aW5nQW1vdW50QXZhaWxhYmxlICYmIGRpc3QgPiBiZXN0RGlzdCkgewogICAgICAgICAgICBiZXN0RGlyID0gVXA7CiAgICAgICAgICAgIGJlc3REaXN0ID0gZGlzdDsKICAgICAgICB9CiAgICB9CiAgICBpZiAoYmVzdERpc3QgPj0gMCkKICAgICAgICByZXR1cm4gYmVzdERpcjsKCiAgICBpZiAoY2FuR29VcCkKICAgICAgICByZXR1cm4gVXA7CiAgICBpZiAoY2FuR29MZWZ0KQogICAgICAgIHJldHVybiBMZWZ0OwogICAgaWYgKGNhbkdvRG93bikKICAgICAgICByZXR1cm4gRG93bjsKICAgIGlmIChjYW5Hb1JpZ2h0KQogICAgICAgIHJldHVybiBSaWdodDsKICAgIHJldHVybiBSaWdodDsKfQ==