So I am trying to make the most memory efficient algorithm for the following problem: We have an infinite basement.
Now we start with no coins on the grid, so the outcome is always predictable. I used a 2D array for this. I was wondering if there was another way. I was thinking about Hashmaps or Hashsets but i don't know how that would work
Track only the locations visited that have coins.
A HashSet where each entry is an x,y pair will do; initially it is empty.
If x,y is not in the map, it has no coin - add an entry.
If x,y is in the map, it has a coin - remove the entry.
This should have better memory utilization than an array that covers everywhere you 'might' visit, and you don't have to guess at how large an array is large enough.
If you want to introduce a Map in your project, that's doable.
As a key you can generate a String combined from x and y coordinates, and Boolean will be a convenient option as a value, if you don't need to represent other cases apart from coin is present or not.
The HashMap can entirely substitute the basement array in your code. In addition to a map you need to introduce two int fields that will represent the size in x and y directions.
You can prepopulate the map in the same way you've done it with the array. And instead of initializing all coordinates with the same default value, you can generate random starting values.
In the game-loop you can toggle the value mapped to a particular tile like that:
map.put(key, !map.get(key));
or this way by using Java 8 method compute():
hasCoinByTileKey.compute(key, (k, v) -> !v);
And to find out whether the tile contains the coin, use get():
if (map.get(key)) {
// do something
}
In regard to performance, it'll perform reasonably well, but slightly slower than an array-based solution. Because under the hood, HashMap is backed by the array. In short, each array element constitutes a bucket, which correspond to a particular range of hash-values. Map-entries will form a linked list, if several keys are mapped to the same bucket (after a certain threshold, the list will get transformed into a tree). The same will holds true for a HashSet, because the HashSet class is build on top of the HashMap.
If you replace an array with the HashMap your Basement class might look like that:
public class Basement {
public static void main(String[] args) {
new Basement(20, 20).update();
}
private static final int STEPS = 20;
private Map<String, Boolean> hasCoinByTileKey = new HashMap<>();
private List<Tile> path = new ArrayList<>();
private int rows;
private int cols;
private record Tile(int x, int y) {}
public Basement(int rows, int cols) {
this.rows = rows;
this.cols = cols;
Random random = new Random();
for (int row = 0; row < cols; row++) {
for (int col = 0; col < cols; col++) {
hasCoinByTileKey.put(getKey(row, col), random.nextBoolean());
}
}
}
public static String getKey(int row, int col) {
return row + "," + col;
}
public void update() {
path.clear(); // cleaning the previous keys
int x = rows / 2;
int y = cols / 2;
int orientation = 0;
/*
0 - up
1 - right
2 - left
3 - down
*/
for (int steps = 0; steps < STEPS; steps++) {
path.add(new Tile(x, y)); // updating the path will current coordinates
String key = getKey(x, y);
if (!hasCoinByTileKey.get(key)) {
hasCoinByTileKey.compute(key, (k, v) -> !v); // toggling the boolean value of the tile
if (orientation == 0) {
y += 1;
orientation = 1;
} else if (orientation == 1) {
x += 1;
orientation = 3;
} else if (orientation == 2) {
x -= 1;
orientation = 0;
} else {
y -= 1;
orientation = 2;
}
} else {
hasCoinByTileKey.compute(key, (k, v) -> !v); // toggling the boolean value of the tile
if (orientation == 0) {
y -= 1;
orientation = 2;
} else if (orientation == 1) {
x -= 1;
orientation = 0;
} else if (orientation == 2) {
x += 1;
orientation = 3;
} else {
y += 1;
orientation = 1;
}
}
}
System.out.println(path.size());
System.out.println(path);
this.print();
}
public void print() {
boolean[][] grid = new boolean[rows][cols];
for (Tile tile: path) {
grid[tile.x][tile.y] = true;
}
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
System.out.print(grid[row][col] ? 'a' : ' ');
}
System.out.println();
}
}
}
In order to print the path, a separate list is used to track the path durin the execution of update method. Object that hold coordinates is a record.
main() - demo
public static void main(String[] args) {
new Basement(20, 20).update();
}
Output - 20 steps (the pattern differs from your example because roughly a half of the tiles will be prepopulated with coins)
aaaa
aaaa
aaa
aaaaa
aaaa
aa
public final class Basement {
private final Map<Integer, Set<Integer>> board = new HashMap<>();
private final Tile curTile = new Tile();
private final Axis row = new Axis();
private final Axis col = new Axis();
public void nextStep() {
if (hasCoin())
pickUpCoinAndRotate();
else
placeCoinAndRotate();
col.update(curTile.col);
row.update(curTile.row);
}
private boolean hasCoin() {
return hasCoin(curTile.col, curTile.row);
}
private boolean hasCoin(int col, int row) {
return board.getOrDefault(row, Set.of()).contains(col);
}
private void placeCoinAndRotate() {
board.computeIfAbsent(curTile.row, val -> new HashSet<>()).add(curTile.col);
curTile.rotateClockwise();
}
private void pickUpCoinAndRotate() {
board.computeIfAbsent(curTile.row, val -> new HashSet<>()).remove(curTile.col);
curTile.rotateCounterclockwise();
}
private void print() {
for (int row = this.row.min; row <= this.row.max; row++) {
for (int col = this.col.min; col <= this.col.max; col++)
System.out.print(hasCoin(col, row) ? 'a' : '.');
System.out.println();
}
}
private enum Orientation {
UP {
@Override
public Orientation rotateClockwise(Tile curTile) {
curTile.col++;
return RIGHT;
}
@Override
public Orientation rotateCounterclockwise(Tile curTile) {
curTile.col--;
return LEFT;
}
},
RIGHT {
@Override
public Orientation rotateClockwise(Tile curTile) {
curTile.row++;
return DOWN;
}
@Override
public Orientation rotateCounterclockwise(Tile curTile) {
curTile.row--;
return UP;
}
},
DOWN {
@Override
public Orientation rotateClockwise(Tile curTile) {
curTile.col--;
return LEFT;
}
@Override
public Orientation rotateCounterclockwise(Tile curTile) {
curTile.col++;
return RIGHT;
}
},
LEFT {
@Override
public Orientation rotateClockwise(Tile curTile) {
curTile.row--;
return UP;
}
@Override
public Orientation rotateCounterclockwise(Tile curTile) {
curTile.row++;
return DOWN;
}
};
public abstract Orientation rotateClockwise(Tile curTile);
public abstract Orientation rotateCounterclockwise(Tile curTile);
}
private static final class Tile {
private int row;
private int col;
private Orientation orientation = Orientation.UP;
public void rotateClockwise() {
orientation = orientation.rotateClockwise(this);
}
public void rotateCounterclockwise() {
orientation = orientation.rotateCounterclockwise(this);
}
}
private static final class Axis {
private int min;
private int max;
public void update(int cur) {
min = Math.min(min, cur);
max = Math.max(max, cur);
}
}
public static void main(String... args) {
Basement basement = new Basement();
for (int steps = 0; steps < 200; steps++) {
basement.nextStep();
basement.print();
System.out.println();
}
}
}
Demo:
..aaaa...
.a....a..
aaa....a.
aaaaaaaa.
.aa.a..a.
.a...a.aa
..aaa.aaa
aaa....a.
...aaaa..
use sparse matrix
class Node {
int row;
int col;
int value;
Node next;
Node(int r, int c, int val)
{ row = r; col = c; this.value = val; }
}
public class Sparse{
public static void main(String[] args)
{
/*Assume a 4x4 sparse matrix */
int sparseMatrix[][] = {
{0, 0, 1, 2},
{3, 0, 0, 0},
{0, 4, 5, 0},
{0, 6, 0, 0}
};
Node start = null; /*Start with the empty list*/
Node tail = null;
int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
{
if (sparseMatrix[i][j] != 0) /*Pass only non-zero values*/
{
Node temp = new Node(i, j, sparseMatrix[i][j]);
temp.next = null;
if(start == null){
start = temp;
tail=temp;
}
else{
tail.next = temp;
tail = tail.next;
}
}
}
Node itr = start;
while(start != null){
System.out.println(start.row + " " + start.col + " " + start.value);
start = start.next;
}
}
}