kallko/game-demo-2

Part 1 - start app:

Hi. To start app you need computer with installed git (https://git-scm.com/book/en/v2/Getting-Started-Installing-Git) and Docker (https://docs.docker.com/engine/install/)

Create some test folder and move in:

git clone https://github.com/kallko/game-demo-2.git

cd game-demo-2

docker-compose -p master up

wait a little.

In Your browser:

http://localhost:8090

Also Project included 27 unit-tests, which You could run localy with: npm run test

Part 2:

Sources: Long time ago I met this man: https://www.youtube.com/watch?v=NvkM1immvWo

I decided to use his project like draft for front/back.

original repo:

https://github.com/Juriy/game-demo.git

Part 3:

Logic: Object game include:

board: Array of null or 1

filledCells: Array of coordinates with 1 (we could look for them in board, but store need less)

biggestRectangleCoordinate

biggestRectangleSize

Just to calculate everything on back, and front only for display.

We will use filledCells to check size of rectangle with this cell in left-top of rectangle.

We sort filledCells by distance to [0,0] less distance means more potential rectangle size. So if we already found rectangle with size 9, we could skip check any rectangle with left-top coordinate [13,13], As maximum size for such rectangle would be 4

We also could find potential size of rectangle with fixed left-top cell and some diagonal to right or to bottom, to exclude unnecessary calculation, if this rectangles could be bigger then already found one. Also, when potential size of rectangle with fixed left-top cell and some diagonal to right more then to bottom, we could start with direction to avoid possible unnecessary calculation. And vice versa.

First i have implemented simple scenario and tests, and then added all this adjustment to logic.

So steps:

• take from filledCells first cell, which could potentially create the biggest rectangle.
• set as maximum rectangle
  • check if is possible a square with diagonal + 1
  • find direction with the biggest potential
  • find the biggest rectangle in this direction
  • check second direction
• repeat

One more potential adjustment stop checking filled cells from some time, when it's not possible to create the biggest rectangle.

Part 4: Possible solutions. One more possible option imagine field like 15 binary numbers Calculate all possible variants and store them in SQL db. Thanks to correct index maximum check for 1 variant would be not more than 15 * 32K