More actions
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 해야 함..
~cpp 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;
}
}
~cpp 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();
}
}
}
~cpp 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 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
/**
* 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
- 다른 방법들은 아직 개념 파악이 되지 않은것이 태반이다. 나중에 좀더 공부를 해서 나머지 방법으로도 해봐야지... :)