/mazesolver

Primary LanguageScalaGNU General Public License v3.0GPL-3.0

mazesolver

This is a demo project showcasing the usage of:

Working together to build a 2D map exploration algorithm laboratory on which:

image

  • A server side is responsible for:

    • Generating sample imputs.
    • Receiving resolution requests.
    • Fullfilling the resolution request, providing asynchronous events on the progress that can be represented at UI side as well as a final event with the completed solution.

  • A client side is responsible for:

    • Allowing loading files with problems to resolve.
    • Configuring the resolution algorithm.
    • Receiving resolution update and finalization events and representing them.

Problem

Given a 2D map where we have walls or open cells, and to which you can only enter through the open cells at the matrix borders (doors). Provide the set of sets of doors that are connected to each other. In other words, that answers to the question: Which doors can I reach from each other door?

From:

seas

To:

seas_resolved

Code structure

This is a multi-module project with the server side being compiled for the JVM, the client side as JS and a common set of entities compiled for both JVM and JS:

  • jvm: Server side application:
    • Solver.scala Resolution algorithm implementation as two functions initialConditions, providing the first resolution step given the input, and explorationStep, generating the next resolution step out of a previous one. This represents a recursive search algorithm decomposed so it can be used to generate a stream of solutions.
    • Generator.scala An input generator.
    • Server.scala Solutions stream and its utilization to provide a WS interface.
    • DisjointSetsWrapper.scala An interface abstracting different implementations of DisjointSets. It provides factories for the cats-collections implementation and for a non-too-functional-nor-efficient approach.
  • shared Entities comprising the communication protocol between the UI and the server.
  • js UI Implementation using Scala.JS. This code is not as curated as the server side, it doesn't follow the functional programming paradigm. Take it as a support tool for the real demo, the server side.