~turminal/flood

flood/main.ha -rw-r--r-- 3.0 KiB
77e15b0aBor Grošelj Simić img 4 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
use bufio;
use crandom = crypto::random;
use endian;
use errors;
use fmt::*;
use fmt;
use fs;
use io;
use math::random;
use os;
use strconv;
use strings;
use sort;

use image;

fn read_uint(h: io::handle) uint = {
	let arr = bufio::scantok(h, ' ': u32: u8, '\n': u32: u8) as []u8;
	let string = strings::fromutf8(arr);
	return strconv::stou(string)!;
};

fn read(hn: io::handle, casenr: uint) bool = {
	bufio::scantok(hn, '\n': u32: u8) as []u8; // empty line
	let tc: uint = read_uint(hn);

	w = read_uint(hn);
	h = read_uint(hn);
	b = read_uint(hn);

	if (tc == casenr) {
		a = image::create(w, h, 0);
		assert(len(a) == h);
		assert(len(a[0]) == w);
	};
	for (let i = 0z; i < h; i += 1) {
		for (let j = 0z; j < w; j += 1) {
			if (tc == casenr) {
				a[i][j] = read_uint(hn);
			} else {
				read_uint(hn);
			};
		};
	};
	return tc == casenr;
};

fn distcmp(a: const *void, b: const *void) int = {
	let a = g[*(a: *size)].dist;
	let b = g[*(b: *size)].dist;
	return (a-b): int;
};

fn draw(hn: io::handle, img: image::image) void = {
	let cl: []image::color = [];
	image::pick_colors(&cl, b);
	image::write(hn, cl, img);
	assert(len(cl) == b);
	free(cl);
};

fn drawgraph(hn: io::handle) void = {
	let img = image::create(w, h, 0);
	defer image::finish(img);
	for (let r = 0z; r < h; r += 1) {
		for (let c = 0z; c < w; c += 1) {
			img[r][c] = g[ids[r][c]].col;
		};
	};
	draw(hn, img);
};

fn dbg(v: uint) void=  {
	for (let r = 0z; r < h; r += 1) {
		for (let c = 0z; c < w; c += 1) {
			if (ids[r][c] == v) {
				g[ids[r][c]].col = 0;
			};
		};
	};
};

export fn main() void = {
	let animate = false;
	let casenr = switch (len(os::args)) {
	case 2 =>
		yield strconv::stou(os::args[1]) as uint;
	case 4 =>
		assert(os::args[2] == "draw", "invalid argument");
		animate = true;
		yield strconv::stou(os::args[1]) as uint;
	case => abort("invalid argument");
	};

	// read
	bufio::scantok(os::stdin, '\n': u32: u8) as []u8; // header "Poplavljanje"
	bufio::scantok(os::stdin, '\n': u32: u8) as []u8; // number of tests
	for (!read(os::stdin, casenr)) void;

	// rng init
	let buf: [8]u8 = [0...];
	crandom::buffer(buf);
	rng = random::init(endian::begetu64(buf));

	// dsinit
	ids = image::create(w,h, -1);
	let n = buildgraph();
	bfs();
	for (let i = 0z; i < n; i += 1) {
		append(dists, i);
	};
	sort::sort(dists, size(size), &distcmp);
	assert(len(dists) != 0);

	if (animate) {
		animation(os::args[3]);
		return;
	};

	let opt: size = -1;
	printf("{}\nPoplavljanje\n\n", TOKEN)!;

	let c = copyg(g);
	let distcp: []size = alloc(dists...);
	let fctx = context { sol = [], curr = [], g = g, d = dists };
	for (true) {
		let ctx = ctx_copy(&fctx);
		defer ctx_finish(ctx);

		solve(ctx);

		if (len(ctx.sol) >= opt) continue;
		let img = fs::create(os::cwd, "img.ppm", 0o777, fs::flags::TRUNC, fs::flags::RDWR)!;
		drawgraph(img);
		io::close(img);
		opt = len(ctx.sol);
		assert(len(ctx.sol) != 0);
		fmt::printf("{}\n{}\n", casenr, len(ctx.sol))!;
		for (let i = 0z; i < len(ctx.sol) - 1; i += 1) {
			fmt::printf("{} ", ctx.sol[i])!;
		};
		fmt::printf("{}\n\n", ctx.sol[len(ctx.sol) - 1])!;
	};
};