Skip to content

Instantly share code, notes, and snippets.

@juster
Created September 30, 2018 06:23
Show Gist options
  • Save juster/d639d3e4a4975878e424092aff4435e3 to your computer and use it in GitHub Desktop.
Save juster/d639d3e4a4975878e424092aff4435e3 to your computer and use it in GitHub Desktop.
const std = @import("std");
const FileOutStream = std.io.FileOutStream;
const sampleSize = 16;
const heap = std.heap.c_allocator;
const math = std.math;
var stdout : FileOutStream = undefined;
fn randomSample() ![sampleSize]i8 {
var buf: [8]u8 = undefined;
var samples: [sampleSize]i8 = undefined;
try std.os.getRandomBytes(buf[0..]);
const seed = std.mem.readIntLE(u64, buf[0..8]);
var r = std.rand.DefaultPrng.init(seed);
var i: usize = 0;
while (i < sampleSize) {
samples[i] = r.random.intRangeLessThan(i8, -128, 127);
i = i+1;
}
return samples;
}
fn maxSubBrute(A: []const i8) [2]u32 {
var i:u32 = 0;
var j:u32 = undefined;
var k:u32 = undefined;
var range = []u32{0, 1};
var max: i32 = @intCast(i32, A[1]) - @intCast(i32, A[0]);
while(i < A.len-1){
var diff: i32 = A[i];
j = i+1;
while(j < A.len){
//try stdout.stream.print("A[{}] = {}\tA[{}] = {}\tmax = {}\n", i, A[i], j, A[j], max);
diff = @intCast(i32, A[j]) - @intCast(i32, A[i]);
if(diff > max){
max = diff;
range[0] = i;
range[1] = j;
}
j = j+1;
}
i = i+1;
}
return range;
}
fn maxCrossingSub(A: []const i8) [3]i32 {
var mid = A.len/2;
var sub = []i32{@intCast(i32, mid), @intCast(i32, mid), @intCast(i32, A[mid])};
var leftSum = @intCast(i32, A[mid]);
var sum = leftSum;
var i = mid-1;
while(i > 0){
sum += @intCast(i32, A[i]);
if(sum > leftSum){
leftSum = sum;
sub[0] = @intCast(i32, i);
}
i = i-1;
}
var rightSum = @intCast(i32, A[mid]);
sum = rightSum;
i = mid+1;
while(i < A.len){
sum += @intCast(i32, A[i]);
if(sum > rightSum){
rightSum = sum;
sub[1] = @intCast(i32, i);
}
i = i+1;
}
return sub;
}
fn maxSubArray(A:[]const i8) ![3]i32 {
if(A.len == 1) return []i32{0, @intCast(i32, A.len-1), @intCast(i32, A[0])};
var todo = try heap.alloc([2]usize, 1 + 2 * @intCast(usize, math.log2(A.len)));
defer heap.free(todo);
var i:usize = 0;
var j:usize = 1;
todo[0][0] = 0;
todo[0][1] = A.len-1;
while(i < j){
const lo = todo[i][0];
const hi = todo[i][1];
if(lo < hi){
const mid = @divFloor(lo + hi, 2);
todo[j+0][0] = lo;
todo[j+0][1] = mid;
todo[j+1][0] = mid+1;
todo[j+1][1] = hi;
j = j + 2;
}
i = i + 1;
try stdout.stream.print("i={} j={}\n", i, j);
}
// The last two should be a range of lo = hi.
const range = todo[j-1];
if(range[0] != range[1]) unreachable;
var max = maxCrossingSub(A[range[0]..range[1]]);
j = j - 2;
while(true){
const range2 = todo[j];
const x = maxCrossingSub(A[range2[0]..range2[1]]);
if(x[2] > max[2]) max = x;
j = j - 1;
if(j == 0) break;
}
return max;
}
pub fn printSamples(A: []const i8) !void {
for (A) |s| {
try stdout.stream.print("{}\t", s);
}
try stdout.stream.write("\n");
}
pub fn main() !void {
stdout = FileOutStream.init(try std.io.getStdOut());
const samples = try randomSample();
try printSamples(samples[0..]);
var range = maxSubBrute(samples[0..]);
try stdout.stream.print("brute: {} to {}\n", range[0], range[1]);
try stdout.stream.print("DONG!\n");
// comment out these (2) lines and it compiles
const sub = try maxSubArray(samples[0..]);
try stdout.stream.print("max sub: {} to {} ({})\n", sub[0], sub[1], sub[2]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment