Least cost matching algorithm using hungarian method. Probably poorly implemented but it works

hungarian.dwl

%dw 2.0
input payload csv
import * from dw::util::Values
import * from dw::Runtime

//#region Constants
var INF = pow(2, 28)

var countryMap = {
    "USA": "USA",
    "UK": "UK",
    "Australia ": "AUS",
    "Canada": "CAD",
    "United Kingdom": "UK",
    "Israel": "ISR",
    "Hong Kong": "HK",
    "Australia": "AUS",
    "United Kingdon": "UK", 
    "Belgium": "BD",
    "India": "IO",
    "Sweden": "SE"
}
//#endregion

//#region Common functions
var ARR = (size, value) -> ((0 to size-1) as Array) map value //make it a bit easier to initialize an array

//function for while looping
var while = (conditionFn: (s: Any) -> Boolean, whileFn: (s: Any) -> Any, state = {}) ->
  if (conditionFn(state)) while(conditionFn, whileFn, whileFn(state))
  else state

fun splice(arr: Array, index: Number) =
    if (index == 0) arr[1 to -1]
    else (arr[0 to index-1] default []) ++ (arr[index+1 to -1] default [])

fun shuffle(arr: Array) =
    (((0 to sizeOf(arr)-1) as Array) reduce (i, s = {res:[], items: arr}) -> do {
        var ri = floor(random() * sizeOf(s.items))
        ---
        {
            res: s.res << s.items[ri],
            items: s.items splice ri
        }
    }).res
//#endregion

//#region Payload mapping functions
var cleanPayload = (payload) ->
    payload map {
        username: $."What is your reddit username" replace "u/" with "" replace "U/" with "",
        realname: $."What is your real name",
        address: $."what is your full shipping address",
        country: countryMap[$."What is your home country?"],
        shipInternational: $."Are you willing to ship internationally, or prefer the same country?" != "Prefer the same country",
        additionalInfo: {
            penExperience: $."What is your fountain pen experience level?",
            inksPapers: $."What are your favorite ink colors, favorite papers?",
            additional: $."Is there anything else you want us to share with your Secret Santa when considering choosing a gift for you?"
        }
    }
    distinctBy $.username
//#endregion

//#region Algorithm functions
var buildCostMatrix = (givers: Array<Object>, receivers: Array<Object>, costFn: (l: Object, r: Object) -> Number) ->
    givers reduce ((giver, costMatrix=[]) ->
        costMatrix << (receivers reduce ((receiver, giverCostMatrix=[]) -> 
            giverCostMatrix << costFn(giver, receiver)
        ))
    )

var costCalcFn = (l: Object, r: Object) ->
    [
        (INF) if (l.username == r.username),
        (1) if (l.country == r.country),
        (1) if (l.country != r.country),
        (1) if (l.country != r.country and l.shipInternational),
        (INF) if (l.country != r.country and !l.shipInternational)
    ] reduce $$+$

var clearCovers = (in: Object) ->
{
  costMatrix: in.costMatrix,
  state: {
    (in.state - "rowCovered" - "colCovered"),
    rowCovered: ARR(in.state.n, false),
    colCovered: ARR(in.state.n, false)
  }
}

var findAZero = (in: Object) -> do {
  var return = while(
    (s) -> s.return == null and s.i < in.state.n,
    (s) -> 
      while(
        (s2) -> s2.return == null and s2.j < in.state.n,
        (s2) -> 
          if (in.costMatrix[s.i][s2.j] == 0 and !in.state.rowCovered[s.i] and !in.state.colCovered[s2.j]) { return: [s.i, s2.j] }
          else { j: s2.j + 1, return: null },
        { return: null, j: 0 }
      ) ++ {i: s.i + 1}
    ,
    { i: 0, j: 0, return: null}
  )
  ---
  if (return.return == null) [-1, -1] else return.return
}

var findStarInRow = (in: Object, row: Number) -> do {
  var return = while (
    (s) -> s.return == null and s.j < in.state.n,
    (s) -> if (in.state.marked[row][s.j] == 1) { return: s.j } else { j: s.j + 1, return: null },
    { j: 0, return: null }
  )
  ---
  if (return.return == null) -1 else return.return
}

var findStarInCol = (in: Object, col: Number) -> do {
  var return = while(
    (s) -> s.return == null and s.i < in.state.n,
    (s) -> if (in.state.marked[s.i][col] == 1) { return: s.i } else { i: s.i + 1, return: null },
    { i: 0, return: null }
  )
  ---
  if (return.return == null) -1 else return.return
}

var findPrimeInRow = (in: Object, row: Number) -> do {
  var return = while(
    (s) -> s.return == null and s.j < in.state.n,
    (s) -> if (in.state.marked[row][s.j] == 2) { return: s.j } else { j: s.j + 1, return: null },
    { j: 0, return: null }
  )
  ---
  if (return.return == null) -1 else return.return
}

var convertPaths = (in: Object) -> do {
  var updatedMarked = (0 to in.count) reduce ((i, accum=in.state.marked) ->
    accum update [index(in.state.path[i][0]), index(in.state.path[i][1])] with (
      if (accum[in.state.path[i][0]][in.state.path[i][1]] == 1) 0
      else 1
    )
  )
  ---
  {
    (in - "state"),
    state: {
      (in.state - "marked"),
      marked: updatedMarked
    }
  }
}

var erasePrimes = (in: Object) -> do {
  var updatedMarked = (0 to in.state.n-1) reduce ((i, accum=in.state.marked) ->
    (0 to in.state.n-1) reduce ((j, innerAccum=accum) ->
      if (innerAccum[i][j] == 2) innerAccum update [index(i), index(j)] with 0
      else innerAccum
    )
  )
  ---
  {
    (in - "state"),
    state: {
      (in.state - "marked"),
      marked: updatedMarked
    }
  }
}

var findSmallest = (in: Object) -> do {
  (0 to in.state.n-1) reduce ((i, minVal=INF) ->
    (0 to in.state.n-1) reduce ((j, innerMinVal=minVal) ->
      if (!in.state.rowCovered[i] and !in.state.colCovered[j])
        if (innerMinVal > in.costMatrix[i][j])
          in.costMatrix[i][j]
        else innerMinVal
      else innerMinVal
    )
  )
}

var step1 = (in: Object) ->
  step2({
    (in - "costMatrix"),
    costMatrix: in.costMatrix reduce ((row, newMatrix=[]) ->
      newMatrix << (do {
        var min = row minBy $
        ---
        row map ($-min)
      })
    )
  })

var step2 = (in: Object) ->
  step3(clearCovers({
    costMatrix: in.costMatrix,
    (in.costMatrix reduce ((row, accum={ state: in.state, i: 0}) ->
      {
        (
          (row reduce ((cost, innerAccum={ state: accum.state, j: 0, break: false}) ->
              if (!innerAccum.break and cost == 0 and !innerAccum.state.colCovered[innerAccum.j] and !innerAccum.state.rowCovered[accum.i]) {
                state: ((innerAccum.state update ["marked", index(accum.i), index(innerAccum.j)] with 1) update ["colCovered", index(innerAccum.j)] with true) update ["rowCovered", index(accum.i)] with true,
                j: innerAccum.j + 1,
                break: true
              }
              else {
                state: innerAccum.state,
                j: innerAccum.j + 1,
                break: innerAccum.break
              }
            
          )) - "i" - "break" - "j"
        ),
        i: accum.i + 1
      }
    ))
  } - "i"))

var step3 = (in: Object) -> do {
  var out = 
  {
    (in - "state"),
    state: {
      (in.state - "colCovered" - "count"),
      (
        ((0 to in.state.n-1) reduce ((i, accum={count: 0, colCovered: in.state.colCovered}) ->
          (0 to in.state.n-1) reduce ((j, innerAccum=accum) -> 
            if (in.state.marked[i][j] == 1 and !innerAccum.colCovered[j]) 
              {
                count: innerAccum.count + 1,
                colCovered: innerAccum.colCovered update index(j) with true
              } 
            else innerAccum
          )
        ))
      )
    }
  }
  ---
  //done(out - "count")
  if (out.state.count >= in.state.n) done(out)
  else step4({
    (out - "state"),
    state: {
      (out.state - "count")
    }
  })
}

var step4 = (in: Object) -> 
  while(
    (s) -> (not (s is Array)) and !s.done,
    (s) -> do {
      var z = findAZero(s)
      ---
      if (z[0] < 0) step6(s - "done")
      else do {
        var starCol = findStarInRow(s, z[0])
        ---
        if (starCol >= 0) {
          (s - "state"),
          state: {
            (s.state - "marked" - "rowCovered" - "colCovered"),
            marked: s.state.marked update [index(z[0]), index(z[1])] with 2,
            rowCovered: s.state.rowCovered update [index(z[0])] with true,
            colCovered: s.state.colCovered update [index(starCol)] with false
          },
          done: false
        } else step5({
          (s - "state"),
          state: {
            (s.state - "Z0_r" - "Z0_c" - "marked"),
            marked: s.state.marked update [index(z[0]), index(z[1])] with 2,
            Z0_r: z[0],
            Z0_c: z[1]
          }
        } - "done")
      }
    },
    { (in), done: false }
  ) - "done"

var step5 = (in: Object) -> do {
  var newIn = (in update ["state", "path", index(0), index(0)] with in.state.Z0_r) update ["state", "path", index(0), index(1)] with in.state.Z0_c
  ---
  step3(erasePrimes(clearCovers(convertPaths(while(
    (s) -> !s.done,
    (s) -> 
    do 
    {
      var row = findStarInCol(s, s.state.path[s.count][1])
      var res = 
        if (row >= 0) 
          {
            (s - "state" - "count" - "done"),
            count: s.count + 1,
            state: {
              (s.state - "path"),
              path: (s.state.path update [index(s.count+1), 0] with row) update [index(s.count+1), 1] with s.state.path[s.count][1]
            },
            done: false
          } 
        else 
          {
            (s - "done"),
            done: true
          }

      var finalState = 
        if (res.done) 
          res 
        else 
          do {
            var col = findPrimeInRow(res, res.state.path[res.count][0])
            ---
            {
              (res - "state" - "count"),
              count: res.count + 1,
              state: {
                (res.state - "path"),
                path: (res.state.path update [index(res.count+1), index(0)] with res.state.path[res.count][0]) update [index(res.count+1), index(1)] with col
              }
            }
          }
      ---
      finalState
    },
    { (newIn), done: false, count: 0 }
  ) - "done") - "count")))
}

var step6 = (in: Object) -> do {
  var minVal = findSmallest(in)
  ---
  step4({
    (in - "costMatrix"),
    costMatrix: in.costMatrix map ((row, i) -> 
      row map ((col, j) ->
        [
          col,
          (minVal) if (in.state.rowCovered[i]),
          (-1 * minVal) if (!in.state.colCovered[j])
        ] reduce $$+$
      )
    )
  })
}

var done = (in: Object) -> 
  (0 to in.state.n-1) reduce ((i, accum=[]) ->
    (0 to in.state.n-1) reduce ((j, iAccum=accum) ->
      iAccum ++ [([i, j]) if (in.state.marked[i][j] == 1)]
    )
  )

//#endregion


var cleanedPayload = cleanPayload(payload)
var givers = shuffle(cleanedPayload)
var receivers = shuffle(cleanedPayload)
var costMatrix = buildCostMatrix(givers, receivers, costCalcFn)

output application/json
---
step1(
  { 
    costMatrix: costMatrix, 
    state: {
      n: sizeOf(cleanedPayload),
      rowCovered: ARR(sizeOf(cleanedPayload), false),
      colCovered: ARR(sizeOf(cleanedPayload), false),
      marked: ARR(sizeOf(cleanedPayload), ARR(sizeOf(cleanedPayload), 0)),
      path: ARR(sizeOf(cleanedPayload) * 2, ARR(sizeOf(cleanedPayload) * 2, 0)),
      Z0_r: 0,
      Z0_c: 0
    }
  }
) map {
  giver: givers[$[0]],
  receiver: receivers[$[1]]
}