Fork me on GitHub
Drew Verlee14:05:05

I have done a number of coding challenges now that involve a grid/matrix. For example, tic-tac-toe, tetris, minesweeper. I feel we (developers) like to ask questions involve these grids because the data model is relatively controlled. Things relate to each other via their position. At the same time, we know there is ample room for mis managing state operations. Has anyone noticed this trend? What do you think it implies? Having done these exercises a couple times, its interesting that my tendency is to represent a grid as a single vector and then extract the length from the grid via function that knows its square or knows the length already. Anyone have a different suggestion on how to represent a grid? Are their any libraries that tend to make working with that structure easier? However, both models (multi-vector, vector) make certain semantics less declarative. E.g sometimes have to know when the next row starts even when asking questions with dont care about the bounds. Also, annoyingly, functions that are less susceptible to bounds issues (like get) dont work on lists, which is unfortunate in this case as many transformations return lists. Lastly, i’m curious if modeling change to the information in the grid is best done reactively (callbacks) or explicitly. Here is an example of what i mean, as its possible i’m abusing those terms: Reactively: If my neighbor cell (in the grid) changes, i should change in this way. Explicitly: I have changed, so my neighbor cell should change. Or if there is really no right answer and what i should do is make the model viewable from either perspective. The information about how to change wouldn’t even need to be located inside the cell in either model, that information could be managed in another place.


A lot of puzzles and problems use grids, likely for the reasons you mentioned. As for representation, it wholly depends on the information being tracked and the moving parts of the problem. Sometimes nested vectors is useful, sometimes having a collection of entities that just hold their own position in a grid is useful, etc.


Reactive changes to a grid are difficult because of the relative likelihood of infinite effect loops; you need some sort of reliable bottom to any effect


So modeling effects becomes pretty vital in scenarios that require it. Game of Life is trivial, as each cell's next state can be derived without real interaction between cells. A more complex problem would force you to figure out the order of resolution of effects within a single tick of time.


(It's probably useful to note a lot of those grid-based problems include time-step elements; not all, but many.)

Drew Verlee17:05:43

@fellshard > Reactive changes to a grid are difficult because of the relative likelihood of infinite effect loops; you need some sort of reliable bottom to any effect Most live systems have some reactive element though right? I feel the choice is how we model that change. One choice might be to add transparency to the chain at a central location via something like an event log:

[…, {new event: "add x"}]
Which then subscribers can read and transactionaly add reactive changes:
[…, {new event: "add x"}, {new event: "update grid based on x"]
Which is the same logic you can push into the grid itself somehow via a callback:
      listen for events…
      if new event -> update_self(event)
With the downside that people have to search around for these reactive elements and piece together the event log from above if there are issues. Does that interpretation make sense?

Drew Verlee17:05:03

Hmm. I guess alternatively, you can dispatch to explicitly to the logic and not use a subscription model at all.

   if new-event == 'add x':
       do what ever...

Drew Verlee17:05:06

I feel like i’m brow beating options without any specific context to say which makes more sense.


That's the typical problem, yeah. Gotta tailor the approach to the problem you're modeling


If you have to model in-system time, you have to have a way to organize how events are handled within / between time increments


So purely reactive isn't necessarily sufficient


Unless time steps are just another event 😄