blog-static/code/cs325-langs/sols/hw3.lang

96 lines
2.4 KiB
Plaintext
Raw Permalink Normal View History

2020-01-02 21:20:32 -08:00
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;
}