Random walk on a 2D grid

The program assignment:

A drunkard in a grid of streets randomly picks one of four directions and stumbles to the next intersection, then again randomly picks one of four directions, and so on. You might think that on average the drunkard doesn't move very far because the choices cancel each other out, but that is not the case. Represent locations as integer pairs (x,y). Implement the drunkard's walk over 100 intersections, starting at (0,0) and print the ending location.

I created this Drunkard class:

import java.util.*;

class Drunkard {
int x, y;
Drunkard(int x, int y) {
this.x = x;
this.y = y;
}
void moveNorth() {
this.y -= 1;
}
void moveSouth() {
this.y += 1;
}
void moveEast() {
this.x += 1;
}
void moveWest() {
this.x -= 1;
}
void report() {
System.out.println("Location: " + x + ", " + y);
}
}


And this DrunkardTester class to test the above class

import java.util.Random;

public class DrunkardTester {
public static void main(String[] args) {
Random generator = new Random();
Drunkard drunkard = new Drunkard(0, 0);
int direction;
for (int i = 0; i < 100; i++) {
direction = Math.abs(generator.nextInt()) % 4;
if        (direction == 0) { // N
drunkard.moveNorth();
} else if (direction == 1) { // E
drunkard.moveEast();
} else if (direction == 2) { // S
drunkard.moveSouth();
} else if (direction == 3) { // W
drunkard.moveWest();
} else {
System.out.println("Impossible!");
}
}
drunkard.report();
}

}


It complies and runs fine, and it prints a different coordinate location each time I run it, but I just wanted to get a few other pairs of eyes on it to see if there are any glaring errors.

Also, on my DrunkardTester class is there anyway to eliminate the "Impossible!" else statement? I wasn't really sure if that was necessary or what else could be put there.

migrated from stackoverflow.comNov 8 '13 at 12:50

This question came from our site for professional and enthusiast programmers.

• Simplify your random call to generator.nextInt(MAX_DIRECTION) where MAX_DIRECTION is an int constant and == 4. – Hovercraft Full Of Eels Nov 8 '13 at 1:54
• Your code is correct, easy to follow, and neatly formatted. It's standard practice to indent the statements in each of the if branches, but you might consider replacing the multi-part if with switch. – Adam Liss Nov 8 '13 at 1:58

There is absolutely no need to call Math.abs for generator.nextInt() since nextInt will never produce a negative number. Also, your last else-statement is impossible to happen so you can erase that one.

There is also no need to use the modulo (%) operator to fix your direction variable to the correct range when you instead can supply an integer value to the nextInt method. generator.nextInt(4); will give you a value from 0 to 3 (inclusive).

It is a Java coding convention to indent your code properly, after each { the next line should have one more indentation step, like this:

void moveSouth() {
this.y += 1;
}


The below might be a little bit over your level, but it is a really nice solution and is very useful to learn. When you are dealing with four directions, I would create an enum to help with the different direction possibilities.

public enum Direction4 {
NORTH(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);

private final int dx;
private final int dy;

private Direction4(int dx, int dy) {
this.dx = dx;
this.dy = dy;
}
public int getX() { return dx; }
public int getY() { return dy; }
}


Using this enum, you can simplify several things of your other code. For starters, you can replace your move-methods with one single move method:

void move(Direction4 direction) {
this.x += direction.getX();
this.y += direction.getY();
}


And when generating the direction to move at, you can use the Direction4 enum:

// Get an index number and input the "size" of the enum to nextInt
int directionIndex = generator.nextInt(Direction4.values().length);

// Get the direction from the index generated above
Direction4 dir = Direction4.values()[directionIndex];

// Make the move:
drunkard.move(dir);


It might be subjective whether four different moveNorth, moveSouth etc. methods are preferable instead of using a single move-method that takes the direction as an argument. I myself find that using an enum redures the amount of code and it makes the code flexible and scalable (if you want to add or modify existing directions you can do so, for example adding MEGA_NORTH that moves 10 steps north just for fun).

If you don't perform the enum approach, then at least use a switch

direction = generator.nextInt(4);
switch (direction) {
case 0:
drunkard.moveNorth();
break;
case 1:
drunkard.moveEast();
break;
case 2:
drunkard.moveSouth();
break;
case 3:
drunkard.moveWest();
break;
}


Although I must say: There's not much that beat a nice little enum :)

• I would probably add one more abstraction around choosing a direction. Enum.values() returns an array, so I would want to have an interface with a signature like <T> T choose(T[] choices); one of the implementations of which uses an instance of Random to pick from the array. – VoiceOfUnreason Nov 8 '13 at 16:14
• @VoiceOfUnreason I don't see the reason for making it an interface, but it surely could be a static utility method. – Simon Forsberg Nov 8 '13 at 16:18

Your sequence of if-elses would be better as a switch — it's more efficient and more readable. However, in general, a big switch statement in Java can usually be replaced with something better. In this case, an enum for the four cardinal directions would really help.

enum Direction {
NORTH(0, 1),
EAST(1, 0),
SOUTH(0, -1),
WEST(-1, 0);

public final int x, y;

private Direction(int x, int y) {
this.x = x;
this.y = y;
}

private static Random generator = new Random();

public static Direction random() {
return values()[generator.nextInt(4)];
}
}


Notice the following benefits from using an enum:

• No more switch statement.
• In the Drunkard class, four methods can be replaced with void move(Direction d).
• A lot of code (i.e., machine instructions) has been replaced with data. Data is usually easier to manage than code.
• The assumption of four cardinal directions is centralized, rather than divided between Drunkard and DrunkardTester. If, for example, you wanted to allow diagonal moves, you would only need to modify the Direction enum.

You asked, what to do about the impossible case. To assert that a situation is impossible, use an assert. Alternatively, throw a RuntimeException. Printing a message to System.out just clutters the output and lets your faulty program continue, when the right thing to do is to abort. (By the way, if you must print diagnostics, print to System.err instead, to avoid contaminating the output on System.out.)

Also note that a more proper way to uniformly pick a number from [0, 1, 2, 3] is random.nextInt(4). In general, doing random.nextInt() % n might be slightly biased. (Consider a hypothetical case where n = 1 billion. Since .nextInt() picks uniformly from integers between 0 and 2 147 483 647, the lowest 147 483 647 numbers are 50% more likely to be picked with random.nextInt() % 1000000000. When n = 4, there happens to be no bias, but you might as well call the right code out of habit.)

A few more tips:

• In Drunkard, instead of void report() { System.out.println(...); }, prefer String toString() { ... }. This gives the caller flexibility to display the result, for example, in a graphical UI.
• In Drunkard, also offer a no-argument constructor that places the drunkard at the origin.

Why don't you indent inner statements?

The constants 0, 1, 2, 3 could be declared as constants like

private static final short NORTH = 0;
private static final short EAST = 1;
etc...


Also, the "Impossible!" is an unreachable statement so it would be fine to remove it in your case.

• No sure who down-voted this without a comment, but extracting a magic number to a constant is always a good idea. As stated above, a Enum is a better choice here, but if you go with the current approach extracting the constant make your code easier to handle. – mheinzerling Nov 10 '13 at 6:23

It's functional.

A suggestion: It's good java practice to only import the classes you need. So I suggest not using the * notation to import all of the java.util package, actually you don't even use anything from the java.util package so you might as well remove unused imports.

Remove this:

import java.util.*;