Skip to content

Instantly share code, notes, and snippets.

@lucasew
Last active May 24, 2021 19:56

Revisions

  1. lucasew revised this gist May 12, 2021. No changes.
  2. lucasew created this gist May 12, 2021.
    42 changes: 42 additions & 0 deletions main.nix
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,42 @@
    # https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/
    with builtins;
    rec {
    theFn = l:
    theFnRecur l 0;

    theFnRecur = l: i:
    let
    len = length l;
    in if len >= i then
    let
    this = diff l i;
    next = theFnRecur l (i + 1);
    in
    if this < next
    then this
    else next
    else 999999;

    diff = l: i:
    let
    size = length l;
    left = sumUntil l (i - 1);
    right = sumUntil (reverse l) (size - i - 1);
    value = left - right;
    in abs value;
    # assert i < size

    sumUntil = l: i:
    if i <= 0
    then (head l)
    else
    (head l) + (sumUntil (tail l) (i - 1));

    reverse = l:
    if (length l) == 0
    then []
    else (reverse (tail l)) ++ [(head l)];

    # assert (theFn [3 1 2 4 3] == 1)
    abs = n: if n < 0 then n * -1 else n;
    }