Generalized BFS(Breadth-First-Search) implementation for TypeScript

bfs.ts

import { CircularQueue } from './somewhere'

export enum SearchEvaluation {
  SUCCESS = 'SUCCESS',
  KEEP = 'KEEP',
  TERMINATE = 'TERMINATE',
}

export interface SearchChoice<S> {
  nextState: S
  description?: string
}

interface SearchNode<S> {
  state: S
  from?: {
    prev: SearchNode<S>
    by: SearchChoice<S>
  }
  depth: number
}

function backtrack<S>(node?: SearchNode<S>): SearchChoice<S>[] {
  const result: SearchChoice<S>[] = []
  while (node?.from?.by) {
    result.push(node.from.by)
    node = node.from?.prev
  }
  return result.reverse()
}

interface BFSOption<S> {
  initialState: S
  getActions: (s: S) => SearchChoice<S>[]
  decide: (s: S) => SearchEvaluation
  depthLimit?: number
  iterationLimit?: number
  dupChecker?: (s: S) => string
}

export function bfs<S>({
  initialState,
  getActions,
  decide,
  depthLimit,
  iterationLimit,
  dupChecker,
}: BFSOption<S>): SearchChoice<S>[] | undefined {
  const q = new CircularQueue<SearchNode<S>>()
  const dup: Record<string, boolean> = {}
  let iteration = 0

  q.push({
    state: initialState,
    depth: 0,
  })

  if (dupChecker) {
    dup[dupChecker(initialState)] = true
  }

  while (q.size() > 0 && iteration++ < (iterationLimit ?? iteration + 1)) {
    const currentNode = q.pop()!
    const { state: currentState, depth } = currentNode

    switch (decide(currentState)) {
      case SearchEvaluation.TERMINATE:
        continue
      case SearchEvaluation.SUCCESS:
        return backtrack(currentNode)
    }

    if (depth === depthLimit) continue

    getActions(currentState).forEach((choice) => {
      if (dupChecker) {
        const key = dupChecker(choice.nextState)
        if (dup[key]) return
        dup[key] = true
      }

      q.push({
        state: choice.nextState,
        from: {
          prev: currentNode,
          by: choice,
        },
        depth: depth + 1,
      })
    })
  }
  return undefined
}

example.ts

import { bfs, SearchEvaluation } from './bfs'

const target = 72

const path = bfs<number>({
  initialState: 1,
  getActions(x: number) {
    return [
      {
        nextState: 3 * x + 1,
        description: '3x+1',
      },
      {
        nextState: Math.floor(x / 2),
        description: 'x/2',
      },
    ]
  },
  decide(x: number) {
    return x === target ? SearchEvaluation.SUCCESS : SearchEvaluation.KEEP
  },
  dupChecker(x: number) {
    return `${x}`
  },
})
  
console.log(path)

Generalized BFS implementation. This checks state duplication before entering queue.

For CircularQueue implementation, look and grab from here.

In the example, it'll try to find the shortest path between given number and 1 using two choices- one with 3*x + 1 and the other with x / 2.