RandomWalk/임인택

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

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

#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 : 1에 STL을 사용하고 약간의 Refactoring

#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 : Recursion 을 이용해봄

#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 : OO 적으로

• 별로 OO 적이지 못한것 같다...(Roach 와 Board 객체가 양방향참조를 한다). DesignPatterns 를 참고하면서 보았어야 하는데.. 나중에 Refactoring 해야 함..

Roach.java

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;
    }
}
 

Board.java

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();
        }
    }
}
 

RandomWalk.java

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 : 재미있을것 같은 CSP

TokenRing 에서 아이디어를 얻어 나름대로 만들어봤는데 (아직 제대로 동작하는지 미확인. 이 글을 작성하는 도중에도 버그가 하나둘 보이고 BadSmell 이 많이 난다. PC가 많은 곳에서 추가작업필요... :( ) 이게 CSP 의 이념에 부합하는지 모르겠다. m by n 배열에 있는 셀들을 TokenRingNetwork 형태를 띠게 하면서 사실은 배열인것처럼 동작하게 했다. 이 방법 말고 마땅한 방법이 떠오르지 않았다. TestDrivenDevelopment 으로 작성해보려고 했지만 실천에 옮기지 못했다. 몸에 밴 습관이란건 극복하기가 쉽지 않은 것 같다.

• Cell.java

/**
 * 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 walkingMaintenance script (talk)
            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

/**
 * 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

/**
 * 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);
    }
}
 

Thread

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

---

RandomWalk