A Hugo incarnation of the blog. https://danilafe.com
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 95 lines 2.4 KiB Raw Permalink Blame History

 `function qselect(xs, k, c) {` ` if xs == [] {` ` return 0;` ` }` ``` ``` ` traverser bisector(list: xs, span: (0,len(xs)));` ` traverser pivot(list: xs, random: true);` ``` ``` ` let pivotE = pop!(pivot);` ` let (leftList, rightList) = bisect!(bisector, (x) -> c(x) < c(pivotE));` ` ` ` if k > len(leftList) + 1 {` ` return qselect(rightList, k - len(leftList) - 1, c);` ` } elsif k == len(leftList) + 1 {` ` return pivotE;` ` } else {` ` return qselect(leftList, k, c);` ` }` `}` ``` ``` `function closestUnsorted(xs, k, n) {` ` let min = qselect(list(xs), k, (x) -> abs(x - n));` ` let out = [];` ` let countEqual = k;` ``` ``` ` traverser iter(list: xs, span: (0, len(xs)));` ` while valid!(iter) {` ` if abs(at!(iter)-n) < abs(min-n) {` ` let countEqual = countEqual - 1;` ` }` ` step!(iter);` ` }` ``` ``` ` traverser iter(list: xs, span: (0, len(xs)));` ` while valid!(iter) {` ` if abs(at!(iter)-n) == abs(min-n) and countEqual > 0 {` ` let countEqual = countEqual - 1;` ` let out = out + [at!(iter)];` ` } elsif abs(at!(iter)-n) < abs(min-n) {` ` let out = out + [at!(iter)];` ` }` ` step!(iter);` ` }` ``` ``` ` return out;` `}` ``` ``` `function closestSorted(xs, k, n) {` ` let start = bisect(xs, n);` ` let counter = 0;` ` traverser left(list: xs, span: (0, start), reverse: true);` ` traverser right(list: xs, span: (start, len(xs)));` ``` ``` ` while counter != k and canstep!(left) and valid!(right) {` ` if abs(at!(left, 1) - n) < abs(at!(right) - n) {` ` step!(left);` ` } else {` ` step!(right);` ` }` ` let counter = counter + 1;` ` }` ``` ``` ` while counter != k and (canstep!(left) or valid!(right)) {` ` if canstep!(left) { step!(left); }` ` else { step!(right); }` ` let counter = counter + 1;` ` }` ``` ``` ` return subset!(left, right);` `}` ``` ``` `sorted function xyz(xs, k) {` ` traverser x(list: xs, span: (0,len(xs)));` ` let dest = [];` ``` ``` ` while valid!(x) {` ` traverser z(list: xs, span: (pos!(x)+2,len(xs)));` ` traverser y(list: xs, span: (pos!(x)+1,pos!(z)));` ``` ``` ` while valid!(y) and valid!(z) {` ` if at!(x) + at!(y) == at!(z) {` ` let dest = dest + [(at!(x), at!(y), at!(z))];` ` step!(z);` ` } elsif at!(x) + at!(y) > at!(z) {` ` step!(z);` ` } else {` ` step!(y);` ` }` ` }` ``` ``` ` step!(x);` ` }` ``` ``` ` return dest;` ```} ``` ``` ```