# 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 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 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 ) {
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]);

for(int i=6; i<args.length; i++) {
adjInfo += args[i] + " ";
}