Software Engineering
object-oriented
Updated Sat, 17 Sep 2022 15:22:12 GMT

Best way to manage shared state in parent-child objects where children need to check other children


Is there a best practice for managing shared state between a parent and child objects that is most likely to avoid bugs, maintain consistency, and be easy to implement/understand and maintain?

As a concrete example, consider a crossword puzzle solver. I'm envisioning the following objects:

CrosswordPuzzle
   A grid with horizontal and vertical fillable word-blanks, that intersect at
   particular points.
WordBlank[]
   Children of CrosswordPuzzle. Encapsulates the list of all the x,y coordinates of
   each blank/fillable word, whether vertical or horizontal). After construction, a
   CrosswordPuzzle does not increase or decrease in WordBlanks--both are immutable.
CandidateSolution
   Holds a reference to a CrosswordPuzzle and manages state for a single possible
   set of WordPlacements (0 or 1 WordPlacement per WordBlank). Can be mutable,
   though the preferred implementation is for the `placeWord()` method to return a
   new, cloned CandidateSolution with WordPlacements identical to those existing,
   plus a new WordPlacement with the new word.
WordPlacement[]
    Children of CandidateSolution. When every WordBlank in a CandidateSolution's
    CrosswordPuzzle has exactly one valid WordPlacement associated with it, then
    the CandidateSolution is complete and the puzzle is solved.

The purpose of these objects (and doing this in an OOP way at all) is:

  1. To manage, across WordPlacements, whether a word may be placed into a WordBlank or not. A word may not be placed into a WordBlank within a particular CandidateSolution if at least one of its letters conflicts with an existing WordPlacement in that solution.
  2. Via good sensible method/property names, to make the client code that solves for crosswords be self-documenting, expressive, easy to write, easy to read.
  3. To set out a reusable pattern that could apply to other scenarios that have similar semantics. What if it was changed to a three-dimensional crossword puzzle--could the client code remain nearly unchanged? Could the changes required to support 3D puzzles be restricted to a few key portions of the code?

The concrete question is:

Between these objects (or, propose better ones?), should the parents or the children manage the work of detecting/preventing word placements that are or are not allowed? Let's say we want to try placing the word "TULIP" into a horizontal WordBlank. This needs to be rejected if that WordBlank is not exactly 5 letters long, or if (say) there's already a letter "Q" in the first character. But, it can be allowed if there's already a letter "L" in the third character. Should the logic for this be in the WordPlacement, or in the CandidateSolution? Should the logic that checks the length of the word be in the CrosswordPuzzle (because it does know the length of each WordBlank), while the logic to check for letter conflicts is in the CandidateSolution?

There are many ways to implement this that would work, but I have a feeling that there's some pattern that would tie this all together nicely. Code that has to "remember" to do stuff is bug-prone code. Code that is relied on to "be a good citizen" is more fragile code--it's better if the code is prevented from being a bad citizen at all, due to the way it's structured. There are obvious bugs possible like allowing invalid word placements simply due to not checking all the right conditions, but more subtle bugs are possible such as not sharing references correctly so that even though the proper check is done, that check doesn't access the right data.

I've written code that deals with grid-like data in the past and have had the same problem--it doesn't seem like I've hit on a pattern that really works and is easy to use and hard to get wrong.

  • Should most of the state be in each Placement with the CandidateSolution delegating calls to existing Placements, or should the state be in the CandidateSolution with the Placements mostly being thin shells routing calls back to the parent? Having Placements reach into the parent to get state about siblings seems problematic. But having a CandidateSolution know too much about the Placements also seems problematic.
  • Should I get rid of the child objects entirely, so there is no separate class for WordBlank and WordPlacement, managing those all as arrays and such, giving up OO paradigms in the private fields and methods of the CrosswordPuzzle and CandidateSolution objects?

(Incidentally, there are a few more objects necessary to represent the grid, its points, and each particular letter tied to a particular point, but these are omitted in the example to keep things simple.)

Update

What I figured out was that there didn't need to be any WordPlacement objects. Instead, I realized that the core structure of a crossword puzzle is a grid, so I created a SparseGrid object that could have 0 or 1 values at each (x, y) coordinate. Then, each WordBlank does nothing but remember which grid intersections participate together in each horizontal or vertical word. I also changed the CandidateSolution to maintain a private list of filled WordBlanks. This simplified everything and made it obvious where the data belongs and what methods should be exposed. My solution works and is satisfying.

Here is the final solution code and class/type structure:

const solveCrosswordPuzzle = (
  crosswordLines: string[],
  wordsToPlace: string[]
): string[] => {
  const crosswordPuzzle = new CrosswordPuzzle(crosswordLines)
  let candidateSolutions: CrosswordSolution[] = [
    new CrosswordSolution(
      crosswordPuzzle,
      new SparseGrid<string>(
        crosswordPuzzle.rowCount,
        crosswordPuzzle.columnCount,
        (character: string) => character
      ),
      []
    )
  ]
  wordsToPlace.forEach(word =>
    candidateSolutions = candidateSolutions
      .map(solution => solution.generateNewSolutionsWithWord(word))
      .flat(1)
  )
  if (candidateSolutions.length > 1) {
    throw new Error('Found more than one solution!')
  }
  if (candidateSolutions.length === 0) {
    throw new Error('Found no solutions!')
  }
  if (!candidateSolutions[0].isSolved) {
    throw new Error('Sole remaining solution does not appear to be solved!')
  }
  return candidateSolutions[0].asArrayOfLines
}
interface Point2D {
  readonly y: number
  readonly x: number
  isWithin(startY: number, endY: number, startX: number, endX: number): boolean
  toString(): string
}
interface ICrosswordPuzzle {
  readonly wordBlanks: WordBlank[]
  getWordBlanksAtPoint(point: Point2D): WordBlank[]
}
class SparseGrid<T> {
  get rowCount(): number
  get columnCount(): number
  get points(): Point2D[] {}
  get entries(): [Point2D, T][] {}
  checkValueExistsAtPoint(point: Point2D): boolean {}
  getValueAtPoint(point: Point2D): T {}
  addValueAtPoint(point: Point2D, value: T): void {}
  tryGetValue(point: Point2D): Optional<T> {}
  cloneEntries(): [Point2D, T][] {}
  clone(): SparseGrid<T> {}
}
class CrosswordSolution {
  tryPlace(wordBlank: WordBlank, word: string): Optional<CrosswordSolution> {}
  generateNewSolutionsWithWord(word: string): CrosswordSolution[] {}
  get isSolved(): boolean {}
  get unfilledBlanks(): WordBlank[] {}
  get asArrayOfLines(): string[] {}
}
class WordBlank {
  get points(): Point2D[] {}
  get length(): number {}
  toString(): string {}
}
abstract class Optional<T> {
  abstract readonly hasValue: boolean
  abstract readonly value: T
  static of<TValue>(value: TValue): Optional<TValue> {}
  static empty<TValue>(): Optional<TValue> {}
  resolve<TDefault>(valueIfEmpty: TDefault): T | TDefault {}
}



Solution

Interesting exercise. Here are the two easy rules to follow to achieve your goals / answer your questions:

  1. Do not return instance variables. Ever. This has many names, Law of Demeter, Tell don't Ask, etc. This is the most important rule ever for doing OO.

  2. All public names (class and method names) should be business-related. This prevents things to rely on technical or implementation details of other things.

If you try to do this, I suspect you'll gain a new perspective on things and may help to solve your problems. Answer questions like where some logic should be (it can only be where data for it is).

Clarification: These rules are easy in the sense that they are quite well defined and can be decided quite objectively (although some grey area remains). They are not easy to follow though. You'll need to think about the design much more to actually do it.





Comments (2)

  • +0 – What I figured out was that there didn't need to be any WordPlacement objects. Instead, I realized that the core object of a Crossword is a grid, so I created a SparseGrid object that could have 0 or 1 values at each (x, y) coordinate. Then, each WordBlank did nothing but remember which grid intersections participate together in each horizontal or vertical word. I also changed the CandidateSolution to maintain a list of filled WordBlanks. This simplified everything and made it obvious where the data belongs and what methods should be exposed. My solution works and is satisfying. — Jul 28, 2022 at 02:15  
  • +0 – P.S. See the update in my question for details on the solution I chose. — Jul 28, 2022 at 02:47