Puzzle

Table of Contents

• How to run
• Theme
• Thoughts
• Extras
• Abandoned Solutions
• Solution
  • Board
  • State Management
  • UI
• Puzzle Logic References
• Final Thoughts / Future Goal

How to run

• yarn && yarn dev
• yarn; yarn dev

Theme

https://coolors.co

• GRAPHITE: #2E2923
• EGGSHELL: #F1E9DA
• TANGERINE DREAM: #FAA489
• TURQOISE SURF: #00A5CF

Git

• Commit standards: https://www.conventionalcommits.org/en/v1.0.0/
• Branching: <ticketID>-<ticketTitle>

Thoughts

Determining valid tile moves piqued my interest first. I felt this would determine the underlying data structure for the logic and UI. I suppose this aspect of the task was the obvious motivator so that's why I started there. I sketched out some diagrams and abandoned them for various reasons (see Abandonded Solutions). After I arrived at a solution I liked, I made some tickets on this linear board.

Aside from just being the workflow I'm used to, I knew I wouldnt have continous chunks of free time so just filling a board with tickets helped. It allowed me to just pick up tickets whenever I found some free time during the week.

For the solution alone, I'd say I spent 2 or 3 hours specifying and roughly 6 implementing. Altogether, I'd say a full work day but of course there was time in between.

Aside from the solution, I spent some additional time over the weekend creating the explanations page and fixing up the README.

I think the tickets and commit history will illustrate my process but I did under spec some tickets and so the sequence might be off. Perhaps there is a little chaos in there... dT_Tb

Jump to the Solution for a walkthrough of the implementation process

Extras

Things not defined in the Solution:

• I used a directory structure I'm familiar/comfortable with.
• I thought it would be nice to show some sort of interactive element that illustrates the logic underneath, hence the router, with dedicated explanation page.
• I added unit tests to check if the logic was performing ok. (I have to truly thank copilot here and /grill-me to get a more comprehensive idea of how the puzzle logic could break)
• I added Error boundary because puzzle errors were annoying me
• I deployed to muldowney.work with vercel

Abandoned Solutions

I had a some other ideas I sketched out before abandoning them

• 2d Array: Too clunky. Determining valid tile movement required a cacophony of if statements and it felt with an N x N board, it would only get worse. In the end, it didn't seem scalable.

• Node/relation stored as JSON: I really wanted to continue down this path because of flexibility with node and relation properties but thought it was overkill and would probably end up sinking too much time into it.

• Link to diagrams

Solution

Board

• Flat array to represent tiles. Scales relatively well as long as the puzzle remains 2d and is equal width and height

• Get rows by Math.floor(index/size of board) = row

• Get cols by index % size = col

• Fill array with values, to the (size of board x size of board) - 1

• Add null value for empty tile

• eg: 3 x 3 board (size 3) should be [0, 1, 2, 3, 4, 5, 6, 7, 8, null]

• Determine valid moves by saying (very crudely): a valid move is when source tile to target tile distance is 1 (no diagonal movement, and target tile is null). I used the manhattan distance algorightm here. In my opinion this is much easier to explain when referencing a visual 3 x 3 grid but basically:

  distance = | srcRow - trgtRow | + | srcCol - trgtCol |

• At first, to shuffle the board, I,:

  • chose to start from a solved board, ie: [0, 1, 2, 3, 4, 5, 6, 7, 8, null]
  • created shuffledTiles, a copy of boardTiles
  • got index of null tile: boardTiles.getIndexOf(null). In retrospect, boardTiles[boardTiles.length-1] would have sufficed.
  • iterated over shuffledTiles:
    • found possible targets and placed them in an arry
    • selected a random target from possible targets array
    • swapped source with random target
    • updated shuffledTiles
    • updated the index of null tile
    • repeat by board size to the power of 3 times (my worry was how to apply enough shuffling while still being performant. Co-pilot tells me pow3 should suffice)

• Tests seemed to prove that returned a shuffled, yet solvable board but manual testing found that, over time, there wasn't as much shuffling as I expected (thanks co-pilot)

• So thhen to impove, I did some research (see Puzzle Logic References) and implemented a solution using lodash and a solvability algorithm:

  • count the number of inversions
  • if board size is odd, inversion count should be even
  • if board size is even, location of null row (odd/even) determines if inversion count should be (even/odd)

State Management

• Puzzle state management is mainly done via the usePuzzle hook which is responsible for:
  • Boolean determining the solved state of the board (completed)
  • Number determining the width/height of the board (size)
  • Setter for the size state var (setSize)
  • Number dictating the move counter (moves)
  • Array dictating the tiles for the board (tiles)
  • Function to set the board to a solved state (solve())
  • Function to shuffle the board (reset())
  • Callback to update counter and board state (onMove())

UI

I used tailwind and basic css for the puzzle. I thought about using ShadCN but there wasn't anything in the task description (Sider, DatePicker, Dashboard, etc..) that led me to believe a component library would save me time.

I have to admit, mapping image fragments to the tiles melted my brain. I first thought about using canvas but couldn't find an elegant method to suit my existing solution.

I ended up with just leveraging the background css prop to map image fragments to the tiles. I ended up iterating over the tiles and assigning a fragment of the image as background of each tile. I couldn't determine how to size and position the background image correctly for a dynamic board size so copilot got me over the line eventually.

It works like:

1. From a solved grid, find the tile
2. Scale image so its full size of the board as opposed to the size of the tile
3. Offset the image on the tile to match the fragment to the tile

For me, the tricky part was to determine the background position (item 3). After copilot explained it seemed pretty logical:

get x position as percentage, get y position as percentage and drop it into backgroundPostion

ie: row 1, col 2 = 50% 50%

UX

I ran into some UX annoyances when testing the deployed site on my phone:

• number input wasn't playing nicely due to the virtual keyboard and the native min/max props on the html element so I made a parseSize fn to clamp the value and controlled the input that way
• I added a little jiggle animation with css keyframes to give feedback when a user clicks an immovable tile
• I added a basic animation that transitions the gaps between tiles to 0 when board is in completed state and vice versa when shuffled

Puzzle Logic References

Usually, some conjuring of lodash magic gets me out of most algorightmic predicaments but it didn't entirely plug the hole this time.

• I wasn't familiar with Manhattan distance (or Fisher-Yates for that matter). Regardless, I re-aquainted with my long lost love Stack Overflow to watch people politely demolish each other.

• Valid tile movement: https://cp-algorithms.com/geometry/manhattan-distance.html

• Solvability:

  • https://math.stackexchange.com/questions/293527/how-to-check-if-a-8-puzzle-is-solvable
  • https://stackoverflow.com/questions/34570344/check-if-15-puzzle-is-solvable

Final Thoughts / Future Goal

• I didn't go into flashy UI with GSAP, parallax, three.js, etc... in the solution itself because I was focused on the task at hand, so I felt I didn't really showcase pixels moving around on a screen skills too well.
• Self solving puzzle? https://stackoverflow.com/questions/23189211/a-algorithm-with-manhattan-distance-heuristic
• Node/Relation foundation for 3D puzzle
• Shared session for turn based multiplayer solving