U E D R , A S I H C RSS

Random Walk/임인택

ToyProblems 에서 느낀바가 있어 RandomWalk 를 여러가지 방법으로 풀어보려 합니다.


1. 소스 1 : 2학년때 자료구조 숙제로 작성 (약간 Iterative한것 같다)


~cpp 
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

// move direction and board.
int	 direction_x[]={-1,0,1,1,1,0,-1,-1};
int	 direction_y[]={1,1,1,0,-1,-1,-1,0};
int	 board[40][20];	// maximum size of the board is : 40x20
// required variables.
int	 sizeX, sizeY, xPos, yPos, NumOfBlock, loop=0;
const int DIRECTION = 8;

void input();
void output();
void move();
void init_board();

int main()
{
         init_board();
	input();
	move();
	output();
	
	return 0;
}

void init_board()
{
	for(int i=0; i<sizeX; i++)
		for(int j=0; j<sizeY; j++)
			board[i][j]=0;
}

void move()
{
	int k;
	srand((unsigned)time(NULL));

	// initial point
	board[xPos][yPos]++;
         NumOfBlock--;

	// move roach while loop is smaller than 50,000
	while(loop<50000)
	{
		k = rand()%DIRECTION;

		// prevent the roach moves outside of the board
		if(xPos+direction_x[k]<0 || xPos+direction_x[k]>sizeX-1
			|| yPos+direction_y[k]<0 || yPos+direction_y[k]>sizeY-1)
			continue;

		xPos += direction_x[k];
		yPos += direction_y[k];

		if(board[xPos][yPos]==0)
			NumOfBlock--;
		board[xPos][yPos]++;
		
		if(NumOfBlock==0)
			break;
		loop++;
	}

}

void input()
{
	cout << "input size of the board" << endl;

	while(cin >> sizeX >> sizeY)
	{
		if(sizeX>40 || sizeY>20)
		{
			cout << "size is out of range.\ntry again.";
			continue;
		}
		break;
	}

	NumOfBlock=sizeX*sizeY;

	cout << "input start point;" << endl;
	while(cin >> xPos >> yPos)
	{
		if(xPos>40 || yPos>20)
		{
			cout << "point is out of range.\ntry again.";
			continue;
		}
		break;
	}
}

void output()
{
	int i,j;

	// print outputs.
	for(i=0; i<sizeX; i++)
	{
		for(j=0; j<sizeY; j++)
		{
			cout.width(4);
			cout << board[i][j];
			if(j==sizeY-1)
				cout << endl;
		}
	}
	cout << "loop : " << loop << " times" << endl;
}
 

2. 소스 2 : 1에 STL을 사용하고 약간의 Refactoring


~cpp 
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;

#define DIRECTION 8

// move direction and board.
int	 direction_x[]={-1,0,1,1,1,0,-1,-1};
int	 direction_y[]={1,1,1,0,-1,-1,-1,0};
int sizeX, sizeY;
int NumberOfUnvisitedBlocks = 0, LoopCount= 0 ;

vector<vector<int> > board;

void printOutResult();
void moveRoach(int x, int y);

int main()
{
	cout << "Size of the board : ";
	cin >> sizeX >> sizeY;
	NumberOfUnvisitedBlocks = sizeX * sizeY;

	// initizlize the vector
	board.resize(sizeX);
	vector<vector<int> >::iterator iter;
	for(iter=board.begin(); iter!=board.end(); ++iter)
		(*iter).resize(sizeY);


	cout << "Starting Point : ";
	int xPos, yPos;
    cin >> xPos >> yPos;

    
	moveRoach(xPos, yPos);
	
	printOutResult();

	return 0;
}

void moveRoach(int xPos, int yPos)
{
	int k;
	srand((unsigned)time(NULL));

	// initial point
	board[xPos][yPos]++;
	NumberOfUnvisitedBlocks--;

	// move roach while 'loop' is smaller than 50,000
	while(LoopCount<50000)
	{
		k = rand()%DIRECTION;

		// prevent the roach moves outside of the board
		if(xPos+direction_x[k]<0 || xPos+direction_x[k]>sizeX-1
			|| yPos+direction_y[k]<0 || yPos+direction_y[k]>sizeY-1)
			continue;

		xPos += direction_x[k];
		yPos += direction_y[k];

		if(board[xPos][yPos]==0)
			NumberOfUnvisitedBlocks--;

		board[xPos][yPos]++;

		if(NumberOfUnvisitedBlocks==0)
			break;
		
		LoopCount++;
	}
}

void printOutResult()
{
	int i,j;

	// print outputs.
	for(i=0; i<sizeX; i++)
	{
		for(j=0; j<sizeY; j++)
		{
			cout.width(4);
			cout << board[i][j];
		}
		cout << endl;
	}
	cout << "Total : " << LoopCount << " times repeated " << endl;
}
 

3. 소스 3 : Recursion 을 이용해봄


~cpp 
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

#define NUMOFDIRECTIONS 8

typedef vector<vector<int> > Board;
Board roachJourney;

int	 dir_x[]={-1,0,1,1,1,0,-1,-1};
int	 dir_y[]={1,1,1,0,-1,-1,-1,0};
int sizeX, sizeY;

void moveRoachRecursively(int dirIdx);
void printOutResult();

int main()
{
	cout << "Size of the board : ";
	cin >> sizeX >> sizeY;

	roachJourney.resize(sizeX);
	Board::iterator iter;
	for(iter=roachJourney.begin(); iter!=roachJourney.end(); ++iter)
		(*iter).resize(sizeY);

	moveRoachRecursively(rand()%NUMOFDIRECTIONS);
	printOutResult();

	return 0;
}

void moveRoachRecursively(int dirIdx)
{
	// starting point is 0,0
	// i'm not sure that this is an excessive use of 'static' keyword
	static int posX = 0, posY = 0;
    static int numOfUnVstdPlces = sizeX*sizeY;
	
	// if the roach moved outside of the board ignore that case.
	if(! (posX+dir_x[dirIdx]<0 || posX+dir_x[dirIdx]>sizeX-1
		|| posY+dir_y[dirIdx]<0 || posY+dir_y[dirIdx]>sizeY-1) )
	{
		posX += dir_x[dirIdx];
		posY += dir_y[dirIdx];

		if( roachJourney[posX][posY] == 0 )
			numOfUnVstdPlces--;

		roachJourney[posX][posY]++;
	}
    
	if( numOfUnVstdPlces != 0) // choose next direction
        moveRoachRecursively((unsigned)(rand())%NUMOFDIRECTIONS);
	else
		return;
}

void printOutResult()
{
	Board::iterator iterX;
	for(iterX=roachJourney.begin(); iterX!=roachJourney.end(); ++iterX)
	{
		vector<int>::iterator iterY;
		for(iterY=(*iterX).begin(); iterY!=(*iterX).end(); ++iterY)
		{
			cout.width(4);
			cout << (*iterY);
		}
		cout << endl;
	}
}
 

4. 소스 4 : OO 적으로

- 별로 OO 적이지 못한것 같다...(Roach 와 Board 객체가 방향참조를 한다). DesignPatterns 를 참고하면서 보았어야 하는데.. 나중에 Refactoring 해야 함..
  • ~cpp Roach.java
    ~cpp 
    
    import java.util.Random;
    
    public class Roach{
        int dir_x[]={-1,0,1,1,1,0,-1,-1};
        int dir_y[]={1,1,1,0,-1,-1,-1,0};
        Board _board;
        boolean bOnTrip;
        Random rand;
    
        public Roach() {
            bOnTrip = true;
            rand = new Random();
        }
    
        public void move() {
            int randNum;
    
            while( bOnTrip ) {
                randNum = rand.nextInt()%dir_x.length;
                try {
                    _board.walkOn(dir_x[randNum], dir_y[randNum]);
                }  catch (ArrayIndexOutOfBoundsException e) {
                    //System.err.println(e);
                    drink();
                }
            }
        }
    
        public void finishJourney() {
            bOnTrip = false;
        }
    
        public void drink() {
            System.out.println("toast~!");
        }
    
        public void putOnTheBoard(Board board) {
            _board = board;
        }
    }
     
  • ~cpp Board.java
    ~cpp 
    
    public class Board {
        int _board[][];
        int sizeX, sizeY;
        int roaX, roaY; // watch position of the roach
                                  // because the roach doesn't know his position
        int visitedPlace = 1;
        Roach _roach;
    
        public Board(int x, int y) {
            sizeX = x;
            sizeY = y;
            roaX = roaY = 0;
            _board = new int[sizeX][sizeY];
        }
    
        public void walkOn(int x, int y) {
            System.out.println("바퀴위치 : " + (roaX+x) + ", " + (roaY+y));
    
            if ( _board[roaX+x][roaY+y] == 0 )
                visitedPlace++;
    
            roaX += x;
            roaY += y;
    
            System.out.println("바퀴위치 : " + roaX + ", " + roaY);
    
            _board[roaX][roaY]++;
    
            if( visitedPlace == sizeX*sizeY ) {
                _roach.finishJourney();
                printOutBoard();
            }
    
        }
    
        public void putRoachOn(Roach roach) {
            _roach = roach;
        }
    
        public void printOutBoard() {
            for(int i=0; i<sizeX; i++) {
                for(int j=0; j<sizeY; j++) {
                    System.out.print(_board[i][j] + "\t");
                }
                System.out.println();
            }
        }
    }
     
  • ~cpp RandomWalk.java
    ~cpp 
    
    public class RandomWalk {
    
        public static void main(String[] args){
            Roach myRoach = new Roach();
            Board myBoard = new Board(8,8);
    
            myRoach.putOnTheBoard(myBoard);
            myBoard.putRoachOn(myRoach);
    
            myRoach.move();
        }
    }
    
     

5. 소스 5 : 재미있을것 같은 CSP

TokenRing 에서 아이디어를 얻어 나름대로 만들어봤는데 (아직 제대로 동작하는지 미확인. 이 글을 작성하는 도중에도 버그가 하나둘 보이고 BadSmell 이 많이 난다. PC가 많은 곳에서 추가작업필요... :( ) 이게 CSP 의 이념에 부합하는지 모르겠다. m by n 배열에 있는 셀들을 TokenRingNetwork 형태를 띠게 하면서 사실은 배열인것처럼 동작하게 했다. 이 방법 말고 마땅한 방법이 떠오르지 않았다. TestDrivenDevelopment 으로 작성해보려고 했지만 실천에 옮기지 못했다. 몸에 밴 습관이란건 극복하기가 쉽지 않은 것 같다.
  • Cell.java
    ~cpp 
    
    /**
     * Created by IntelliJ IDEA.
     * Author: Intaek Lim
     * Date: 2003. 6. 7.
     * Time: 오후 10:29:36
     */
    
    import java.net.*;
    import java.io.*;
    import java.util.Random;
    
    // operates just like 'token ring'
    public class Cell  implements Runnable {
        private String _nextHostName, _localHostName;
        private int _hostIndex, _nextHostIndex;
        private int _numOfVisited;
        private int _xSize, _ySize;
        private int _adjacentCellIdx[];
        private ServerSocket _serverSock;
        private Socket _nextSock;
        private final int _defaultPort = 38317;
        private boolean _bEndCondition;
    
        public Cell(int localHostNum, int hostIndex, String nextHostName, int nextHostNum) {
            _hostIndex = localHostNum;
            _hostIndex = hostIndex;
            _bEndCondition = false;
    
            try {
                _serverSock = new ServerSocket(_defaultPort);
            } catch(IOException e) {
                System.err.println(e);
            }
        }
    
        public void setXY(int x, int y) {
            _xSize = x;
            _ySize = y;
        }
    
        public void setAdjacentCells(String adjIdx) {
            // parse adjacent cell info
            String adjHostIdxes[] = adjIdx.split(" ");
            _adjacentCellIdx = new int[adjHostIdxes.length];
    
            for(int i=0; i<_adjacentCellIdx.length; i++)
                _adjacentCellIdx[i] = Integer.parseInt(adjHostIdxes[i]);
        }
    
        public void connect() {
            try {
                _nextSock = new Socket(getNextHostName(), _defaultPort);
            } catch(IOException e) {
                System.err.println(e);
            }
        }
    
        // accept after connection was estabilished to previous host.
        public void acceptConnection() {
            try {
                _nextSock = _serverSock.accept();
            } catch(IOException e) {
                System.err.println(e);
            }
        }
    
        public String getNextHostName() {
            return _nextHostName;
        }
    
        public String getHostName() {
            return _localHostName;
        }
    
        public int getHostIndex() {
            return _hostIndex;
        }
    
        public void run() {
            try {
                ObjectInputStream in
                        = new ObjectInputStream(_nextSock.getInputStream());
                while( !_bEndCondition ) {
                    Object obj = in.readObject();
                    parseMessage((Message)obj);
                }
            }  catch(IOException e) {
                System.err.println(e);
            } catch(ClassNotFoundException e) {
                System.err.println(e);
            }
        }
    
        public void parseMessage(Message msg) {
            // if the roach visited all cells..
            if( msg.checkEndCondition(getHostIndex()) ) {
                processFinishing(msg);
            }
            else if( msg.killMessage) { // if the cell received kill message
                killClients(msg);
            } else {  // when the roach is on walking~~~
                if( msg.targetHostNum == getHostIndex() ) {
                    transmitRoach(msg);
                }
                relay(msg);
            }
        }
    
        public void relay(Message msg) {
            try {
                ObjectOutputStream out
                        = new ObjectOutputStream(_nextSock.getOutputStream());
                out.writeObject(msg);
            } catch(IOException e) {
                System.err.println(e);
            }
        }
    
        public void showEndStatus() {
            System.out.println("Random walk finished.");
            System.out.println("There are" + _numOfVisited + " arrivals");
        }
    
        public void processFinishing(Message msg) {
            // if here is the starting point, then send kill signal to others.
            if( getHostIndex()==0 ) {
                msg.killMessage = true;
                relay(msg);
            }  else { // else, relay to the first point.
                relay(msg);
            }
        }
    
        public void killClients(Message msg) {
            // if this is not the last point relay to the last point
            if( _nextHostIndex<getHostIndex() ) {
                relay(msg);
            } else {
                showEndStatus();
            }
        }
    
        public void transmitRoach(Message msg) {
            if( _numOfVisited==0 ) {
                msg.numOfRemainCell--;
            }
    
            int nextIdx = new Random().nextInt() % _adjacentCellIdx.length;
    
            msg.sourceHostNum = getHostIndex();
            msg.targetHostNum = nextIdx;
    
            relay(msg);
        }
    }
     
  • Message.java
    ~cpp 
    
    /**
     * Created by IntelliJ IDEA.
     * Author: Intaek Lim
     * Date: 2003. 6. 7.
     * Time: 오후 10:58:58
     */
    public class Message {
        public int targetHostNum;
        public int sourceHostNum;
        public int numOfRemainCell;
        public boolean killMessage;
    
        public boolean checkEndCondition(int cellIdx) {
            return (numOfRemainCell==0);
        }
    }
    
     
  • RandomWalk.java
    ~cpp 
    
    /**
     * Created by IntelliJ IDEA.
     * Author: Intaek Lim
     * Date: 2003. 6. 8.
     * Time: 오후 4:7:20
     */
    public class RandomWalk {
        public static void main(String args[]) {
            // localhostname, localHostNum, nextHostName, nextHostNum
            // sizeX, sizeY, cellInfo
            String localHostName =args[0];
            int localNum = Integer.parseInt(args[1]);
            String nextHostName = args[2];
            int nextHostNum = Integer.parseInt(args[3]);
            int xSize = Integer.parseInt(args[4]);
            int ySize = Integer.parseInt(args[5]);
    
            String adjInfo = "";
            for(int i=6; i<args.length; i++) {
                adjInfo += args[i] + " ";
            }
    
            System.out.println(adjInfo);
        }
    }
     

6. Thread

  • 다른 방법들은 아직 개념 파악이 되지 않은것이 태반이다. 나중에 좀더 공부를 해서 나머지 방법으로도 해봐야지... :)

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.6034 sec