DBMS for algorithmic problems

In your JS/TS project

Guide

Examples

Paths count

extern type Id
  extern type Value

  data input: {values: {[Id]: Value}, edges: {[Id]: [Id]}}

  paths = dp {
    node {
      key: Id
      payload = input.values[key]
      next = || {
        for to in input.edges[key] {
          yield node(to)
        }
      }

      combine = |a, b| a + b
      extend  = |a, b| a * b
      unit    = 1
      zero = 0
    }
  }

Knapsack 01

  extern type Id
  extern type Weight
  extern type Value

  data input: {first_id: Id, last_id: Id, capacity: Weight, items: {[Id]: {weight: Weight, value: Value}}}

  backpack = dp {
      node (name = 'main') {
          key: {weight: Weight, id: Step}
          payload = 0
          next = || {
              if key.weight + input.items[key.id.current].weight <= input.capacity {
                  yield node.take({
                      weight: key.weight + input.items[key.id.current].weight,
                      id: key.id
                  })
              }
              if key.id.current == input.last_id {
                  yield node.result()
              } else {
                  yield node.main({weight: key.weight, id: key.id.incremented()})
              }
          }
          combine = |a, b| max(a, b)
          extend = |a, b| a + b
          unit = 0
          zero = 0
      }

      node (name = 'take') {
          key: {weight: Weight, id: Step}
          payload = input.items[key.id.current].value
          next = || {
              if key.id.current == input.last_id {
                  yield node.result()
              } else {
                  yield node.main({weight: key.weight, id: key.id.incremented()})
              }
          }
          combine = |a, b| max(a, b)
          extend = |a, b| a + b
          unit = 0
          zero = 0
      }

      node (name = 'result') {
          key: {}
          payload = 0
          next = || {}
          combine = |a, b| max(a, b)
          extend = |a, b| a + b
          unit = 0
          zero = 0
      }
  }