DEV Community

rkeeves
rkeeves

Posted on

Heineken: Why classic Java is right and YOU ARE WRONG

#algorithms #java #rust

Hi Dear Reader!

In my earlier posts we dealt with:

  • Time Complexity
  • Space Complexity
  • Cognitive Complexity

In this post we are going after a different kind of complexity:

  • Cyclomatic Complexity

And we'll do OOP!

Are you thinking what I'm thinking?

Yeah :)

It's gonna OOP-pee pants city here real soon!

Beginning

You don't like classic Java, huh?

Well, you are out of luck:

  • Dad bought us tickets for a classical Java Symphony.
  • And we are going to go there.
  • Like it or not.
  • And yes, you are going to miss your dumb little Champions League match on TV, because of it.

Man up!

Dad's tickets

Dad gave us tickets to a classical Java Symphony.

It is a Sliding Puzzle.

There is a 3 x 3 grid, a black square, and some U-shapes:

grid

The goal is to get RED inside BLUE.

goal

By moving the black square and dragging stuff with it:

slider

No. The Symphony is NOT about how to solve the puzzle manually!

The Symphony is about how to implement the puzzle as a game (and also to add a search algorithm on top of it)!

And the Symphony is in classical Java.

Going to the Symphony

While we are driving to the concert, I'm gonna read the Brochure Dad gave me.

Grid is 3 by 3, and you can move the square North, East, South, West:

r1

You can drag other things which are around the square:

r2

You can NOT enter a U-shape from one of its closed sides:

r3

NO! We are not turning home for the match, we are going to the concert! Drive!

So...

The same applies to dragged shapes too. They will collide also:

r4

Etiquette

We were given a problem, and we want to model it.

Officially it is called State Space Representation.

  • Our world can be in a State at a specific point in time,
  • Possible states form a State Space,
  • To filter out nonsense states, we introduce Constraints,
  • We start from Initial State,
  • We are looking for Goal States (i.e. we must define the "is it good?" predicate),
  • We get from state to state with Operators.

I made a checklist:

[ ] Find parking spot: Define State Space + Constraints
[ ] Walk in: Initial State
[ ] Coat check: Predicate for goal state
[ ] Find seats: Operators
Enter fullscreen mode Exit fullscreen mode

Yeah we are really doing it! Yes, you are coming.

Find parking spot: Define State Space + Constraints

While you are parking the car, I'm gonna tell you what our State Space is:

state-space

What is our constraint? Only {0, 1, 2} are allowed out of ints.

We will make sure later in code that holds true, but we'll use ints.

So, our classical Java concert starts with Position:

public record Position(int row, int col) { }
Enter fullscreen mode Exit fullscreen mode

But we need how many Positions?

Four! Corresponding to each shape.

How to model many Positions?

Array-array-array? No, can't query directly a shape:

array3

Record? No, you can't iterate easily:

record

Hashmap? Pfff, buckets for 4 elements? Are you serious? No:

hashmap

Good old array works fine:

array

We can check out the State Space:

[X] Find parking spot: Define State Space + Constraints
[ ] Walk in: Initial State
[ ] Coat check: Predicate for goal state
[ ] Find seats: Operators
Enter fullscreen mode Exit fullscreen mode

Let's walk in!

Walk in: Initial State

Omg hurry, just open the door and get in:

initial

[X] Find parking spot: Define State Space + Constraints
[X] Walk in: Initial State
[ ] Coat check: Predicate for goal state
[ ] Find seats: Operators
Enter fullscreen mode Exit fullscreen mode

Hurry-hurry, coat check!

Coat check: Predicate for goal state

OMG, don't play with your phone! Can you forget about that stupid match for this evening p-l-e-a-s-e?

Now, define the predicate:

goal

[X] Find parking spot: Define State Space + Constraints
[X] Walk in: Initial State
[X] Coat check: Predicate for goal state
[ ] Find seats: Operators
Enter fullscreen mode Exit fullscreen mode

Find seats: Operators

Oh my God. What do you mean you don't know how the seat numbering works?

Argh... I can't believe you sometimes...

Okay. Let me explain.

There are invalid moves, so we want to make a predicate whether "Moving Down/South is valid?"

There are four directions:

public enum Direction {

    UP(-1, 0),
    RIGHT(0, 1),
    DOWN(1, 0),
    LEFT(0, -1);

    private final int rowChange;
    private final int colChange;

    Direction(int rowChange, int colChange) {
        this.rowChange = rowChange;
        this.colChange = colChange;
    }

    ...
Enter fullscreen mode Exit fullscreen mode

So we're gonna branch:

public boolean isLegalMove(Direction direction) {
    return switch (direction) {
        case UP -> canMoveUp();
        case RIGHT -> canMoveRight();
        case DOWN -> canMoveDown();
        case LEFT -> canMoveLeft();
    };
}
Enter fullscreen mode Exit fullscreen mode

Up is legal if:

up

private boolean canMoveUp() {
    return getPosition(BLOCK).row() > 0 && isEmpty(getPosition(BLOCK).moveUp());
}
Enter fullscreen mode Exit fullscreen mode

Left is legal if:

left

private boolean canMoveLeft() {
    return getPosition(BLOCK).col() > 0 && isEmpty(getPosition(BLOCK).moveLeft());
}
Enter fullscreen mode Exit fullscreen mode

Right is legal if:

right

private boolean canMoveRight() {
    if (getPosition(BLOCK).col() == BOARD_SIZE - 1) {
        return false;
    }
    final var right = getPosition(BLOCK).moveRight();
    return isEmpty(right)
            || (getPosition(BLACK_SHOE).equals(right) && !haveSamePosition(BLOCK, BLUE_SHOE));
}
Enter fullscreen mode Exit fullscreen mode

Down is legal if:

down

Hurry, please!!!!!

So, where was I? Oh... down move predicate, yes:

private boolean canMoveDown() {
    if (getPosition(BLOCK).row() == BOARD_SIZE - 1) {
        return false;
    }
    final var down = getPosition(BLOCK).moveDown();
    if (isEmpty(down)) {
        return true;
    }
    if (haveSamePosition(BLACK_SHOE, BLOCK)) {
        return false;
    }
    return getPosition(BLUE_SHOE).equals(down)
            || (getPosition(RED_SHOE).equals(down) && !haveSamePosition(BLUE_SHOE, BLOCK));
}
Enter fullscreen mode Exit fullscreen mode

OMG! NO! We are not done yet! These were just the predicates.

We still have to move things, you dum-dum!

Once again, branch:

public void makeMove(Direction direction) {
    switch (direction) {
        case UP -> moveUp();
        case RIGHT -> moveRight();
        case DOWN -> moveDown();
        case LEFT -> moveLeft();
    }
}
Enter fullscreen mode Exit fullscreen mode

We can move up:

move_up

private void moveUp() {
    if (haveSamePosition(BLACK_SHOE, BLOCK)) {
        if (haveSamePosition(RED_SHOE, BLOCK)) {
            movePiece(RED_SHOE, Direction.UP);
        }
        movePiece(BLACK_SHOE, Direction.UP);
    }
    movePiece(BLOCK, Direction.UP);
}
Enter fullscreen mode Exit fullscreen mode

We can move right:

move_right

private void moveRight() {
    movePieces(Direction.RIGHT, RED_SHOE, BLUE_SHOE, BLACK_SHOE);
}
Enter fullscreen mode Exit fullscreen mode

We can move down:

move_down

private void moveDown() {
    movePieces(Direction.DOWN, RED_SHOE, BLUE_SHOE, BLACK_SHOE);
}
Enter fullscreen mode Exit fullscreen mode

We can move left:

move_left

private void moveLeft() {
    movePieces(Direction.LEFT, RED_SHOE, BLUE_SHOE);
}
Enter fullscreen mode Exit fullscreen mode

And that's it! Yay!

Now take a seat, you are ready for the symphony.

Waiting for the Symphony to begin

So are you excited? Mozart's Graph Quartet is going to begin soon! Real Graph Search!

What?!

Awh my Gawwwwd... you don't know what it is... are you serious?

I can't believe I'm marrying you in two months... omg...

Okay... we wasted so much time with finding seats that we basically have like 1 minute left, so I'll be quick:

graph-01

But be careful of reentries (cycles), this is why it is a Graph search not a Tree search (acyclic):

graph-02

The Breadth First Search... omg...

We really don't have time to explain it, essentially you have a Dequeue or something, plus a Set:

bfs-01

And you do the following:

bfs-02

Sorry, we have no more time... Just listen to the symphony and try enjoying it!

Summary

Now the classic Java Symphony begins!

17

Hmh...

18

Yes.

19

Sorry for the build up.

20

But I had to do it.

21

To make you feel the problem with the methods.

22

From now on, though we're gonna do fun things again.

23

Are you still with us?

The Match

Yeah. Those operators that Java cooked up were a bit too unpleasant.

Forget everything I've said earlier. No more classical Java for today!

Goal 1: User wants arbitrary amount of arbitrary sized and facing U-shapes.

sliding2

Goal 2: Minimize LOC.

Goal 3: It has to be football themed.

We are going to break the entire puzzle down into digestible chunks.

But the overarching picture is:

  • There's Your Half and Enemy Half
  • You score goal by kicking balls from the Half Line into Enemy Half
  • But you have to get to the Half Line from the middle of Your Half

What is a football field?

Your Half vs. Enemy Half. You always kick westward:

simplified-game

No edge cases:

no-open

It will make sense, I'll prove to you.

For now, focus on the goal: Goal.

How to kick the ball into the Enemy Half?

Scoring a goal is easy! Here it is:

how-to-score

What about the other cases?

There are NO other cases

All other cases collide:

nongoal

So, it is simply:

how-to-score-rule

Done.

If things don't make sense yet, they will in the next section.

How to kick the ball upto Half Line?

Now, here's the key: What is a Half?

half

What are U-shapes then?

ushape

And don't forget, who are YOU:

blackrectangle

Now... we have to kick it:

howtokick

Kicking is partitioning (we are trying to partition it into 2 subsets, sort of a graph component / transitive closure / rigid body problem):

partition

So, what is the Go Set?

goset

Now comes the One Billion Dollar Question:

gosetmax

And this is why I said earlier that it WILL have a westward side:

reminder

Now I hope you start feeling where this is headed :)

How to combine them in footbal?

So, how to combine these things into a Game of Football?

We start with some state:

football0

You partition:

football1

Then you score a goal:

football2

Now comes the One Trillion Dollar question:

What happens when you collide / can't score a goal?

Remember all those possibilities? All those code branches?

nongoal

On collision, you simply don't mutate the original state, leave it as it is:

football3

The main thing is The Invariant:

  • Before the algorithm, you have two Halves which are valid.
  • After the algorithm, you have two Halves which are valid.

Now the game is clear, and we can make this into code.

Coding time, yay!

First, let's assume we are storing stuff in arbitrarily ordered arrays.

To look neat, I ordered them, but they are not necessarily in order:

table

You find "Pushed" the greatest pushed:

compute

You min search collision:

collision

Here's an example of the mapping:

collision-example

Okay. How to move things? What things to move?

First find the "Puller", aka the greatest which has walls on both sides:

puller

Then do a stupid for loop:

for-loop

Now we can play the puzzle manually (and breadth first search in the background to suggest next best move):

sliding0

Or even arbitrary puzzle with arbitrary pieces, like the one depicted here:

sliding1

And now, the moment came for the codebase which does the business logic.

Here it is, in its full CS 101, simplified, step by step style:

  • dir is the movement direction the Player picked
  • source_x and source_y is the position of the black square (i.e. the Player)
  • state.pieces is an array storing all U-shapes
  • I purposefully broke it down into multiple loops (you can do it with 2 loops: a combined search, then a mutation pass) 
use egui::Color32;

#[derive(PartialEq, Eq, Clone, Hash, Debug)]
pub enum Dir { N, E, S, W }

#[derive(PartialEq, Eq, Clone, Hash)]
pub struct Piece { pub color: Color32, pub x: i8, pub y: i8, pub rank: i8, pub open: Dir }

#[derive(PartialEq, Eq, Clone, Hash)]
pub struct State { pub size: i8, pub x: i8,  pub y: i8,  pub pieces: Vec<Piece> }

pub fn move_mut(dir: &Dir, state: &mut State) -> bool {
  let source_x = state.x;
  let source_y= state.y;
  let (target_x, target_y, opposite_dir) = match dir {
    Dir::N => (source_x + 0, source_y - 1, Dir::S),
    Dir::E => (source_x + 1, source_y + 0, Dir::W),
    Dir::S => (source_x + 0, source_y + 1, Dir::N),
    Dir::W => (source_x - 1, source_y + 0, Dir::E),
  };
  // 0. Boundary check, you must remain on the Grid
  if target_x < 0 || target_x >= state.size || target_y < 0 || target_y >= state.size { return false; }
  // 1. Find Greatest Pushed
  let mut pushed = 0; // Black square is 0, has all walls, and is in source cell
  for p in & state.pieces {
    if p.x == source_x && p.y == source_y && p.open != *dir {
      pushed = pushed.max(p.rank);
    }
  }
  // 2.1. Find Smallest Hole
  let mut hole = pushed + 1; // Must be vacuously true
  for p in & state.pieces {
    if p.x == target_x && p.y == target_y {
      let rank = if p.open == opposite_dir { p.rank } else { 0 };
      hole = hole.min(rank);
    }
  }
  // 2.2. Collision check (just to make it explicit how dumb it is)
  let fits = pushed < hole;
  // 2.E Return without mutation
  if !fits { return false; }
  // 3.1. Find Greatest Puller
  let mut puller = 0; // Black square is 0, has all walls, and is in source cell
  for p in & state.pieces {
    if p.x == source_x && p.y == source_y && p.open != *dir && p.open != opposite_dir {
      puller = puller.max(p.rank);
    }
  }
  // 3.2. Move all moved U-shapes
  for p in &mut state.pieces {
    if p.x == source_x && p.y == source_y  && (p.open != *dir || p.rank < puller) {
      p.x = target_x; p.y = target_y;
    }
  }
  // 3.3. Move the Black Square too, remember: It is NOT an element of U-shapes!
  state.x = target_x; state.y = target_y;
  return true;
}
Enter fullscreen mode Exit fullscreen mode

And of course, it works on arbitrary cases:

sliding2

And that's it!

Futhermore there's even more order if you take a look at it from bird's eye view:

onion

Which looks neat :) (i.e. further exploitable pattern in the structure)

Real Summary

Just with the Heineken fake event, unknowing football fans were persuaded into the concert by:

By using football, we got the following gains:

  • We made it infinitely scalable (based on Natural Numbers).
  • We replaced 388 LOC, 33 methods and some constructors/private fields/constants I didn't count.

The price we had to pay is that it is no longer directly representing business rules:

  • Remember the first Java part?
  • It was lengthy and complicated,
  • but it directly encoded the literal rules (like you can move up if the target is empty and bla bla...)

All in all, I hope you found it interesting.

In summary:

  • Java is a cool OO GC language.
  • Rust is a cool C-in-spirit language, with some OO, FP paint job.

But to be fair... my eyes don't like Rust.

Doc understates it:

Many new users to Rust experience something we like to call ‘fighting with the borrow checker’, where the Rust compiler refuses to compile a program that the author thinks is valid.
Enter fullscreen mode Exit fullscreen mode

That borrow checker doodad made my eyes hurt.

Yep Rust too has a rap... I mean a Rust whistle.

But objectively though, all languages are cool on its own, and they have their own way of handling problems.

Example: Java has this problem with records, that adding a field messes up the diff due to the ,:

| Original | Added c  |   Diff   |
+----------+----------+----------+
   {          {
     a,         a,
     b          b,      change with ","
   }            c       add "c"
              }
Enter fullscreen mode Exit fullscreen mode

How to tackle this problem?

The Way of Nature

Nature only wants to please itself. Get others to please it too. Likes to lord over them. To have its own way. It finds reasons to be unhappy when all the world is shining around it, and love is smiling through all things.

The Way of Nature is to change the world for the better:

Modify BNF to allow dangling commas.

| Original | Added c  |   Diff   |
+----------+----------+----------+
   {          {
     a,         a,
     b,         b,
   }            c,      add "c,"
              }
Enter fullscreen mode Exit fullscreen mode

The Way of Grace

Grace doesn't try to please itself. Accepts being slighted, forgotten, disliked. Accepts insults and injuries.

The Way of Grace is to accept:

| Original | Added c  |   Diff   |
+----------+----------+----------+
   { a        { a
   , b        , b
   }          , c       add ", c"
              }
Enter fullscreen mode Exit fullscreen mode

According to Terrence Malick, these are the two ways.

The Third Way

Of course Terrence Malick was not trying to make a point about Programming.

In Programming there's always the Third Way: My way of problem solving.

My...khm... solution to the puzzle laid out in this post is just a "solution".

I just arbitrarily decided on a recursively defined Set, with the base case of Black Square to make induction work.

There's an underlying structure though: Nat Set and slap on a 2D vector, plus add the collision relation.

A true solution would truly capture this, work it out in a more elegant form. So my "solution" is just a hack.

If you still not get what I'm poking at, then read this post. It outlines via a carnivale game, that certain problems can be reduced into really cool simple forms.

I hope that you'll come up with the true representation of the underlying structure, unlike my Third Way Solution did!

Top comments (0)