all stats

luatic's stats

guessed the most

namecorrect guessesgames togetherratio
seshoumara551.000
yui340.750
kimapr12170.706
Palaiologos480.500
Olivia6120.500
kotnen490.444
olus20007170.412
LyricLy9220.409
vspf250.400
moshikoi280.250
olive140.250
taswelll3130.231
essaie150.200
Dolphy2100.200
soup girl160.167
razetime1100.100
JJRubes060.000
IFcoltransG040.000
theqwertiest040.000

were guessed the most by

namecorrect guessesgames togetherratio
kimapr9170.529
yui240.500
olive240.500
moshikoi370.429
LyricLy9220.409
essaie250.400
Dolphy4100.400
taswelll5130.385
kotnen380.375
JJRubes260.333
Palaiologos260.333
olus20004170.235
razetime290.222
vspf150.200
Olivia2120.167
soup girl040.000
seshoumara050.000
theqwertiest040.000

entries

round #66

submitted at
0 likes

guesses
comments 0

post a comment


gijswijt.lua ASCII text
 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
local function suffix_reps(seq, suffix_len)
	assert(suffix_len <= #seq)
	local tail = #seq - suffix_len
	local reps = 1
	while true do
		for offset = 0, suffix_len - 1 do
			if seq[tail - offset] ~= seq[#seq - offset] then
				return reps
			end
		end
		tail = tail - suffix_len
		reps = reps + 1
	end
end

local function gen_seq(n)
	local seq = {}
	for i = 1, n do
		local max = 1
		for j = 1, i / 2 do
			max = math.max(max, suffix_reps(seq, j))
		end
		seq[i] = max
	end
	return seq
end

print(table.concat(gen_seq(tonumber((...))), ", "))

round #62

submitted at
2 likes

guesses
comments 0

post a comment


dir sped
dir src
dir e
josh.zig ASCII text, with very long lines (65536), with no line terminators
oom.zig ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// https://www.gamers.org/~fpv/doomlogo.html
pub const oom =
    \\                      ===============     ===============   ========  ========
    \\                     //. . . . . . .\\   //. . . . . . .\\  \\. . .\\// . . //
    \\                    ||. . ._____. . .|| ||. . ._____. . .|| || . . .\/ . . .||
    \\                    || . .||   ||. . || || . .||   ||. . || ||. . . . . . . ||
    \\                    ||. . ||   || . .|| ||. . ||   || . .|| || . | . . . . .||
    \\                    ||-_ .||   ||. . || || . .||   ||. _-|| ||-_.|\ . . . . ||
    \\                    ||  `-||   || . .|| ||. . ||   ||-'  || ||  `|\_ . .|. .||
    \\                    ||    ||   ||_ . || || . _||   ||    || ||   |\ `-_/| . ||
    \\                    ||    \|.  || `-_|| ||_-' ||  .|/    || ||   | \  / |-_.||
    \\                    ||      `-_||    || ||    ||_-'      || ||   | \  / |  `||
    \\                    ||         `'    || ||    `'         || ||   | \  / |   ||
    \\                    `===.         .==='.`===.         .===' /==. |  \/  |   ||
    \\                    |-_ `===. .==='   _|_   `===. .===' _-|/   `==  \/  |   ||
    \\                       `-_  `='    _-'   `-_    `='  _-'   `-_  /|  \/  |   ||
    \\                          `-__\._-'         `-_./__-'         `' |. /|  |   ||
    \\                                                                  `' |  /==.||
    \\                                                                      \/   `==
    \\                                                                       `-_   /
    \\                                                                          ``'
    \\
;
dir reg
dfa.zig ASCII text
 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
const std = @import("std");
const Allocator = std.mem.Allocator;
const ArrayList = std.ArrayListUnmanaged;
const DynamicBitSet = std.bit_set.DynamicBitSet;

const AutoHashMap = std.AutoArrayHashMapUnmanaged;
fn CharMap(V: type) type {
    return AutoHashMap(u8, V);
}

pub fn DFA(V: type) type {
    const State = struct {
        const Self = @This();
        out: CharMap(usize),
        accepting: bool,
        value: V,
        pub fn init(allocator: Allocator, accepting: bool, value: V) !Self {
            return .{
                .out = try AutoHashMap(u8, usize).init(allocator, &.{}, &.{}),
                .accepting = accepting,
                .value = value,
            };
        }
        pub fn deinit(self: *Self, allocator: Allocator) void {
            self.out.deinit(allocator);
        }
    };
    return struct {
        const Self = @This();
        states: ArrayList(State),
        allocator: Allocator,
        pub fn init(allocator: Allocator) Self {
            return .{
                .states = ArrayList(State).initBuffer(&.{}),
                .allocator = allocator,
            };
        }
        pub fn deinit(self: *Self) void {
            for (self.states.items) |*state|
                state.deinit(self.allocator);
            self.states.deinit(self.allocator);
        }
        pub fn addState(self: *Self, accepting: bool, value: V) !usize {
            try self.states.append(self.allocator, try State.init(self.allocator, accepting, value));
            return self.states.items.len - 1;
        }
        pub fn addTransition(self: *Self, from: usize, via: u8, to: usize) !void {
            try self.states.items[from].out.put(self.allocator, via, to);
        }
        pub fn getTransition(self: Self, from: usize, via: u8) ?usize {
            return self.states.items[from].out.get(via);
        }
        pub fn accepts(self: Self, input: []const u8) bool {
            var state: usize = 0;
            for (input) |c| {
                if (self.getTransition(state, c)) |next_state|
                    state = next_state
                else
                    return false;
            }
            return self.states.items[state].accepting;
        }
    };
}
ex.zig ASCII text
  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
const std = @import("std");
const Allocator = std.mem.Allocator;
const NFAC = @import("nfa.zig").NFA;
const DFAC = @import("dfa.zig").DFA;
const CharSet = std.bit_set.IntegerBitSet(256);

pub fn RegexReader(V: type) type {
    return struct {
        const NFA = NFAC(V);
        const DFA = DFAC(V);
        const Self = @This();
        pub const SyntaxError = error{
            UnexpectedEOF,
            UnclosedParenthesis,
            ExpectedOperand,
            UnexpectedChar,
            InvalidEscape,
        };
        pub const ReadError = SyntaxError || Allocator.Error;
        nfa: *NFA,
        i: usize,
        buf: []const u8,
        pub fn init(nfa: *NFA, expr: []const u8) Self {
            return .{
                .nfa = nfa,
                .i = 0,
                .buf = expr,
            };
        }
        fn getch(self: *Self) ?u8 {
            if (self.eof()) return null;
            const c = self.buf[self.i];
            self.i += 1;
            return c;
        }
        fn getch2(self: *Self) ReadError!u8 {
            return self.getch() orelse return SyntaxError.UnexpectedEOF;
        }
        fn ungetch(self: *Self) void {
            self.i -= 1;
        }
        fn eof(self: Self) bool {
            return self.i >= self.buf.len;
        }
        fn readEscape(self: *Self) ReadError!u8 {
            return switch (try self.getch2()) {
                'x' => l: {
                    const hi = try self.getch2();
                    const lo = try self.getch2();
                    break :l std.fmt.parseUnsigned(u8, &.{ hi, lo }, 16) catch |e| switch (e) {
                        error.Overflow => unreachable,
                        error.InvalidCharacter => return SyntaxError.InvalidEscape,
                    };
                },
                else => |c| c,
            };
        }
        fn readAtom(self: *Self) ReadError!?NFA.Sub {
            if (self.eof()) return null;
            switch (self.getch().?) {
                '(' => {
                    const res = try self.readChoice();
                    return if (try self.getch2() != ')') SyntaxError.UnclosedParenthesis else res;
                },
                '%' => return try self.nfa.str(&.{try self.readEscape()}),
                '[' => {
                    var charset = CharSet.initEmpty();
                    const complement = try self.getch2() == '^';
                    if (!complement) self.ungetch();
                    while (true) {
                        var c = try self.getch2();
                        if (c == ']') break;
                        if (c == '%')
                            c = try self.readEscape();
                        const c2 = try self.getch2();
                        if (c2 == '-') {
                            const c3 = try self.getch2();
                            if (c > c3) continue; // empty range
                            charset.setRangeValue(.{ .start = c, .end = c3 }, true);
                        } else {
                            charset.set(c);
                            self.ungetch();
                        }
                    }
                    if (complement) charset = charset.complement();
                    return try self.nfa.charset(charset);
                },
                ')', '?', '+', '*', '|' => {
                    self.ungetch();
                    return null;
                },
                else => |c| return try self.nfa.str(&.{c}),
            }
        }
        fn readQuantified(self: *Self) ReadError!?NFA.Sub {
            const base = try self.readAtom() orelse return null;
            return try switch (self.getch() orelse return base) {
                '?' => self.nfa.opt(base),
                '+' => self.nfa.rep(base),
                '*' => self.nfa.kleene(base),
                else => {
                    self.ungetch();
                    return base;
                },
            };
        }
        fn readConcat(self: *Self) ReadError!NFA.Sub {
            var base = try self.readQuantified() orelse return SyntaxError.ExpectedOperand;
            while (try self.readQuantified()) |q| base = try self.nfa.concat(&.{ base, q });
            return base;
        }
        fn readChoice(self: *Self) ReadError!NFA.Sub {
            var base = try self.readConcat();
            while (true) {
                if (self.getch()) |c| {
                    if (c == '|') base = try self.nfa.choice(&.{ base, try self.readConcat() }) else {
                        self.ungetch();
                        return base;
                    }
                } else return base;
            }
        }
        pub fn read(self: *Self) !NFA.Sub {
            const res = try self.readChoice();
            if (!self.eof())
                return error.UnexpectedChar;
            return res;
        }
    };
}

fn nothing(_: void, _: void) void {
    return {};
}

pub fn regexToDFA(allocator: Allocator, regex: []const u8) !DFAC(void) {
    var nfa = NFAC(void).init(allocator, {});
    defer nfa.deinit();
    var rr = RegexReader(void).init(&nfa, regex);
    const sub = try rr.read();
    return nfa.toDFA(sub, nothing);
}
nfa.zig ASCII text
  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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
const std = @import("std");
const Allocator = std.mem.Allocator;
const CharSet = std.bit_set.IntegerBitSet(256);
fn HashMap(K: type, V: type) type {
    return std.ArrayHashMapUnmanaged(K, V, struct {
        pub fn hash(_: @This(), k: K) u32 {
            var hasher = std.hash.Wyhash.init(1233543646);
            std.hash.autoHashStrat(&hasher, k, .DeepRecursive);
            return @truncate(hasher.final());
        }
        pub fn eql(_: anytype, k1: K, k2: K, _: anytype) bool {
            return std.mem.eql(@typeInfo(K).Pointer.child, k1, k2);
        }
    }, true);
}
const AutoHashMap = std.AutoArrayHashMapUnmanaged;
const ArrayList = std.ArrayListUnmanaged;

const DFA = @import("dfa.zig").DFA;

const Subset = []const usize;

fn orderUsize(_: void, a: usize, b: usize) std.math.Order {
    return std.math.order(a, b);
}

fn contains(set: Subset, end_state: usize) bool {
    return std.sort.binarySearch(usize, end_state, set, {}, orderUsize) != null;
}

pub fn NFA(V: type) type {
    const Transition = struct { char: ?u8, to: usize };

    const State = struct {
        const Self = @This();

        out: ArrayList(Transition),
        value: V,
        pub fn init(value: V) Self {
            return .{
                .out = ArrayList(Transition).initBuffer(&.{}),
                .value = value,
            };
        }
        pub fn deinit(self: *Self, allocator: Allocator) void {
            self.out.deinit(allocator);
        }
    };

    return struct {
        const Self = @This();

        pub const Sub = struct {
            start: usize,
            end: usize,
        };

        allocator: Allocator,
        states: ArrayList(State),
        value: V, // HACK this is lazy

        pub fn init(allocator: Allocator, value: V) Self {
            return .{
                .allocator = allocator,
                .states = ArrayList(State).initBuffer(&.{}),
                .value = value,
            };
        }
        pub fn deinit(self: *Self) void {
            for (self.states.items) |*state|
                state.deinit(self.allocator);
            self.states.deinit(self.allocator);
        }
        pub fn addState(self: *Self) Allocator.Error!usize {
            try self.states.append(self.allocator, State.init(self.value));
            return self.states.items.len - 1;
        }
        pub fn addTransition(self: *Self, from: usize, char: ?u8, to: usize) Allocator.Error!void {
            try self.states.items[from].out.append(self.allocator, .{ .char = char, .to = to });
        }
        pub fn rep(self: *Self, sub: Sub) Allocator.Error!Sub {
            try self.addTransition(sub.end, null, sub.start);
            return sub;
        }
        pub fn opt(self: *Self, sub: Sub) Allocator.Error!Sub {
            try self.addTransition(sub.start, null, sub.end);
            return sub;
        }
        pub fn kleene(self: *Self, sub: Sub) Allocator.Error!Sub {
            return self.rep(try self.opt(sub));
        }
        pub fn choice(self: *Self, subs: []const Sub) Allocator.Error!Sub {
            const new = Sub{ .start = try self.addState(), .end = try self.addState() };
            for (subs) |sub| {
                try self.addTransition(new.start, null, sub.start);
                try self.addTransition(sub.end, null, new.end);
            }
            return new;
        }
        pub fn concat(self: *Self, subs: []const Sub) Allocator.Error!Sub {
            var last_end = subs[0].end;
            for (subs[1..]) |sub| {
                try self.addTransition(last_end, null, sub.start);
                last_end = sub.end;
            }
            return .{ .start = subs[0].start, .end = last_end };
        }
        pub fn str(self: *Self, s: []const u8) Allocator.Error!Sub {
            const start = try self.addState();
            var end = start;
            for (s) |c| {
                const new_end = try self.addState();
                try self.addTransition(end, c, new_end);
                end = new_end;
            }
            return .{ .start = start, .end = end };
        }
        pub fn charset(self: *Self, set: CharSet) Allocator.Error!Sub {
            const start = try self.addState();
            const end = try self.addState();
            var chars = set.iterator(.{});
            while (chars.next()) |c|
                try self.addTransition(start, @intCast(c), end);
            return .{ .start = start, .end = end };
        }

        fn hull(self: Self, states: Subset, hull_allocator: Allocator) Allocator.Error![]usize {
            const allocator = self.allocator; // should maybe be separate (e.g. arena allocation while algo runs) but meh
            var level = try ArrayList(usize).initCapacity(allocator, 1);
            defer level.deinit(allocator);
            try level.appendSlice(allocator, states);
            var next_level = ArrayList(usize).initBuffer(&.{});
            defer next_level.deinit(allocator);
            var seen = try AutoHashMap(usize, void).init(allocator, states, allocator.alloc(void, states.len) catch unreachable);
            defer seen.deinit(allocator);
            while (level.items.len > 0) {
                for (level.items) |state| {
                    for (self.states.items[state].out.items) |transition| {
                        if (transition.char == null and seen.get(transition.to) == null) {
                            try seen.put(allocator, transition.to, {});
                            try next_level.append(allocator, transition.to);
                        }
                    }
                }
                level.clearRetainingCapacity();
                const old_level = level;
                level = next_level;
                next_level = old_level;
            }
            const res = try hull_allocator.alloc(usize, seen.count());
            var iter = seen.iterator();
            var i: usize = 0;
            while (iter.next()) |e| {
                res[i] = e.key_ptr.*;
                i += 1;
            }
            return res;
        }
        pub fn toDFA(self: Self, sub: Sub, merge_values: fn (v1: V, v2: V) V) Allocator.Error!DFA(V) {
            const allocator = self.allocator; // same here
            var dfa = DFA(V).init(allocator);
            var subsets = std.heap.ArenaAllocator.init(allocator);
            defer subsets.deinit();
            const start_subset = try self.hull(&.{sub.start}, subsets.allocator());
            var nfa_to_dfa = try HashMap(Subset, usize).init(allocator, &.{start_subset}, &.{
                try dfa.addState(contains(start_subset, sub.end), self.states.items[sub.start].value),
            });
            defer nfa_to_dfa.deinit(allocator);
            var next_level = ArrayList(Subset).initBuffer(&.{});
            defer next_level.deinit(allocator);
            var level = try ArrayList(Subset).initCapacity(allocator, 1);
            defer level.deinit(allocator);
            try level.append(allocator, start_subset);
            while (level.items.len > 0) {
                for (level.items) |subset| {
                    var transitions = try AutoHashMap(u8, AutoHashMap(usize, void)).init(allocator, &.{}, &.{});
                    defer {
                        for (transitions.values()) |*set|
                            set.deinit(allocator);
                        transitions.deinit(allocator);
                    }
                    for (subset) |state| {
                        for (self.states.items[state].out.items) |transition| {
                            if (transition.char) |char| {
                                if (transitions.getPtr(char)) |set| {
                                    try set.put(allocator, transition.to, {});
                                } else {
                                    try transitions.put(allocator, char, try AutoHashMap(usize, void).init(allocator, &.{transition.to}, &.{{}}));
                                }
                            }
                        }
                    }
                    var iter = transitions.iterator();
                    while (iter.next()) |e| {
                        var buf: [256]usize = undefined;
                        var i: usize = 0;
                        for (e.value_ptr.keys()) |state| {
                            buf[i] = state;
                            i += 1;
                        }
                        const reached_states = try self.hull(buf[0..i], subsets.allocator());
                        std.sort.pdq(usize, reached_states, {}, std.sort.asc(usize));
                        const gop = try nfa_to_dfa.getOrPut(allocator, reached_states);
                        if (!gop.found_existing) {
                            var v = self.states.items[reached_states[0]].value;
                            for (reached_states[1..]) |s|
                                v = merge_values(v, self.states.items[s].value);
                            const dfa_state = try dfa.addState(contains(reached_states, sub.end), v);
                            gop.value_ptr.* = dfa_state;
                            try next_level.append(allocator, reached_states);
                        }
                        try dfa.addTransition(nfa_to_dfa.get(subset).?, e.key_ptr.*, gop.value_ptr.*);
                    }
                }
                level.clearRetainingCapacity();
                const old_level = level;
                level = next_level;
                next_level = old_level;
            }
            return dfa;
        }
    };
}
test.zig ASCII text
  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
const std = @import("std");

const NFA = @import("nfa.zig").NFA(void);
const DFA = @import("dfa.zig").DFA(void);

const allocator = std.testing.allocator;

fn initNFA() NFA {
    return NFA.init(allocator, {});
}

fn nothing(_: void, _: void) void {
    return {};
}

const expect = std.testing.expect;

test "optional" {
    var nfa = initNFA();
    defer nfa.deinit();
    const sub = try nfa.opt(try nfa.str("test"));
    var dfa = try nfa.toDFA(sub, nothing);
    defer dfa.deinit();
    try expect(dfa.accepts("test"));
    try expect(dfa.accepts(""));
    try expect(!dfa.accepts("t"));
}

test "repetition" {
    var nfa = initNFA();
    defer nfa.deinit();
    const sub = try nfa.rep(try nfa.str("test"));
    var dfa = try nfa.toDFA(sub, nothing);
    defer dfa.deinit();
    try expect(dfa.accepts("test"));
    try expect(dfa.accepts("testtest"));
    try expect(!dfa.accepts(""));
    try expect(!dfa.accepts("t"));
    try expect(!dfa.accepts("testt"));
}

test "kleene" {
    var nfa = initNFA();
    defer nfa.deinit();
    const sub = try nfa.kleene(try nfa.str("test"));
    var dfa = try nfa.toDFA(sub, nothing);
    defer dfa.deinit();
    try expect(dfa.accepts("testtesttest"));
    try expect(dfa.accepts("test"));
    try expect(dfa.accepts(""));
    try expect(!dfa.accepts("t"));
    try expect(!dfa.accepts("testyay"));
}

test "concat" {
    var nfa = initNFA();
    defer nfa.deinit();
    const sub = try nfa.concat(&.{ try nfa.str("hello"), try nfa.str("world") });
    var dfa = try nfa.toDFA(sub, nothing);
    defer dfa.deinit();
    try expect(dfa.accepts("helloworld"));
    try expect(!dfa.accepts(""));
    try expect(!dfa.accepts("hello"));
    try expect(!dfa.accepts("world"));
}

test "choice" {
    var nfa = initNFA();
    defer nfa.deinit();
    const sub = try nfa.choice(&.{ try nfa.str("hi"), try nfa.str("hello") });
    var dfa = try nfa.toDFA(sub, nothing);
    defer dfa.deinit();
    try expect(dfa.accepts("hi"));
    try expect(dfa.accepts("hello"));
    try expect(!dfa.accepts(""));
    try expect(!dfa.accepts("h"));
    try expect(!dfa.accepts("helloworld"));
}

test "putting it all together" {
    var nfa = initNFA();
    defer nfa.deinit();
    const sub = try nfa.choice(&.{
        try nfa.concat(&.{
            try nfa.rep(try nfa.str("ab")),
            try nfa.str("cd"),
        }),
        try nfa.kleene(try nfa.str("ef")),
    });
    var dfa = try nfa.toDFA(sub, nothing);
    defer dfa.deinit();
    try expect(dfa.accepts("abcd"));
    try expect(dfa.accepts("abababcd"));
    try expect(dfa.accepts("efef"));
    try expect(dfa.accepts(""));
    try expect(!dfa.accepts("abcdef"));
    try expect(!dfa.accepts("g"));
    try expect(!dfa.accepts("a"));
}

const origRegexToDFA = @import("ex.zig").regexToDFA;
fn regexToDFA(regex: []const u8) !DFA {
    return origRegexToDFA(allocator, regex);
}

test "simple regex" {
    var dfa = try regexToDFA("(ab)+cd|(ef)*");
    defer dfa.deinit();
    try expect(dfa.accepts("abcd"));
    try expect(dfa.accepts("abababcd"));
    try expect(dfa.accepts("efef"));
    try expect(dfa.accepts(""));
    try expect(!dfa.accepts("abcdef"));
    try expect(!dfa.accepts("g"));
    try expect(!dfa.accepts("a"));
}

test "charset" {
    var dfa = try regexToDFA("[a%]|b]");
    defer dfa.deinit();
    try expect(dfa.accepts("a"));
    try expect(dfa.accepts("b"));
    try expect(dfa.accepts("]"));
    try expect(dfa.accepts("|"));
    try expect(!dfa.accepts("c"));
}

test "charset range" {
    var dfa = try regexToDFA("[a-c]");
    defer dfa.deinit();
    try expect(dfa.accepts("a"));
    try expect(dfa.accepts("b"));
    try expect(!dfa.accepts("d"));
}

test "charset complement" {
    var dfa = try regexToDFA("[^ab]");
    defer dfa.deinit();
    try expect(!dfa.accepts("a"));
    try expect(!dfa.accepts("b"));
    try expect(dfa.accepts("c"));
}
ansi.zig ASCII text
  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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// The necessary parts of ANSI escape sequence support required for this editor to work

const std = @import("std");
const fmt = std.fmt;
const Color = @import("color.zig").Color;
const Pos = @import("pos.zig");

pub fn parseCsiParams(res: []usize, comptime default: usize, params: []const u8, min_params: usize) ![]usize {
    var i: usize = 0;
    var si = std.mem.splitScalar(u8, params, ';');
    while (i < res.len) : (i += 1) {
        const param = si.next();
        if (param) |num| {
            res[i] = if (num.len == 0) default else try std.fmt.parseInt(usize, num, 10);
        } else {
            res[i] = default;
            break;
        }
    }
    if (i == res.len and si.next() != null)
        return error.TooManyParameters;
    while (i < min_params) : (i += 1)
        res[i] = default;
    return res[0..i];
}

pub const AnsiCommand = union(enum) {
    ignore, // something we don't recognize
    tab,
    backspace,
    delete,
    newline,
    carriage_return,
    insert,
    // Control characters (excluding those corresponding to the above)
    ctrl: u8, // a - z
    // Regular printable ASCII key presses
    print: u8,
    cursor_movement: CursorMovement,
    const CursorMovement = struct {
        const Action = enum { left, right, up, down, pos1, end };
        modifier: enum { none, shift, ctrl },
        action: Action,
        times: usize,
    };
};

pub const AnsiCommandIterator = struct {
    buf: []const u8,
    i: usize,
    fn getch(self: *AnsiCommandIterator) ?u8 {
        if (self.eof()) return null;
        const c = self.buf[self.i];
        self.i += 1;
        return c;
    }
    fn ungetch(self: *AnsiCommandIterator) void {
        self.i -= 1;
    }
    fn eof(self: *AnsiCommandIterator) bool {
        return self.i >= self.buf.len;
    }
    fn parseCursorMovement(
        kind: u8,
        params: []const u8,
    ) AnsiCommand {
        var movbuf: [2]usize = undefined;
        const movement = parseCsiParams(&movbuf, 1, params, 1) catch return .{ .ignore = {} };
        const action: AnsiCommand.CursorMovement.Action = switch (kind) {
            'A' => .up,
            'B' => .down,
            'C' => .right,
            'D' => .left,
            'H' => .pos1,
            'F' => .end,
            else => return .{ .ignore = {} },
        };
        const times = movement[0];
        return if (movement.len == 1)
            .{ .cursor_movement = .{ .modifier = .none, .action = action, .times = times } }
        else if (movement.len == 2)
            switch (movement[1]) {
                2 => .{ .cursor_movement = .{ .modifier = .shift, .action = action, .times = times } },
                5 => .{ .cursor_movement = .{ .modifier = .ctrl, .action = action, .times = times } },
                else => .{ .ignore = {} },
            }
        else
            .{ .ignore = {} };
    }
    pub fn next(self: *AnsiCommandIterator) ?AnsiCommand {
        const c = self.getch() orelse return null;
        return switch (c) {
            else => .{ .ignore = {} },
            0x08 => .{ .backspace = {} },
            0x7F => .{ .delete = {} },
            '\n' => .{ .newline = {} },
            '\r' => .{ .carriage_return = {} },
            '\t' => .{ .tab = {} },
            0x01...0x07, 0x0C, 0x0E...0x1A => .{ .ctrl = c - 1 + 'a' },
            // Printable ASCII
            ' '...'~' => .{ .print = c },
            // ANSI escape sequences
            0x1B => switch (self.getch() orelse return .{ .ignore = {} }) { // TODO possible ESC
                else => .{ .ignore = {} },
                // Fe sequence
                0x40...0x5A, 0x5C...0x5F => .{ .ignore = {} },
                '[' => {
                    // CSI sequence
                    if (self.eof()) return .{ .ignore = {} }; // TODO cut off?
                    const start = self.i;
                    var c2 = self.getch() orelse return .{ .ignore = {} };
                    while (c2 >= 0x30 and c2 <= 0x3F)
                        c2 = self.getch() orelse return .{ .ignore = {} };
                    while (c2 >= 0x20 and c2 <= 0x2F)
                        c2 = self.getch() orelse return .{ .ignore = {} };
                    if (c2 < 0x40 or c2 > 0x7E) {
                        self.ungetch();
                        return .{ .ignore = {} }; // TODO syntax error
                    }
                    const params = self.buf[start .. self.i - 1];
                    if (c2 == '~') return switch (fmt.parseInt(usize, params, 10) catch return .{ .ignore = {} }) {
                        2 => .{ .insert = {} },
                        else => .{ .ignore = {} },
                    };
                    return parseCursorMovement(c2, params);
                },
            },
        };
    }
};

pub fn parse(buf: []const u8) AnsiCommandIterator {
    return .{ .buf = buf, .i = 0 };
}

pub fn writeCsi(writer: anytype, seq: []const u8) !void {
    try writer.writeAll("\x1B[");
    try writer.writeAll(seq);
}

pub fn fmtCsi(writer: anytype, csi_type: u8, params: anytype) !void {
    try writer.writeAll("\x1B[");
    if (params.len > 0)
        try fmt.format(writer, "{d}", .{params[0]});
    var i: usize = 1;
    while (i < params.len) : (i += 1)
        try fmt.format(writer, ";{d}", .{params[i]});
    try writer.writeByte(csi_type);
}

pub fn setCursor(writer: anytype, pos: Pos) !void {
    return fmtCsi(writer, 'H', [_]usize{ pos.row + 1, pos.col + 1 });
}

pub fn setFg(writer: anytype, color: Color) !void {
    return fmtCsi(writer, 'm', [_]usize{ 38, 2, color.r, color.g, color.b });
}

pub fn setBg(writer: anytype, color: Color) !void {
    return fmtCsi(writer, 'm', [_]usize{ 48, 2, color.r, color.g, color.b });
}

pub fn clearScreen(writer: anytype) !void {
    return writeCsi(writer, "2J");
}
c.zig ASCII text
 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
const hex_digit = "[0-9A-Fa-f]";
const integer = "(([1-9][0-9]*|0[0-7]*|0[xX]" ++ hex_digit ++ "+)([uU](l|L|ll|LL)|(l|L|ll|LL)[uU]))";
const dexp = "([eE][+-]?[0-9]+)";
const hexp = "([pP][+-]?[0-9]+)";
const decfloat = "([0-9]+%.[0-9]*|%.[0-9]+)" ++ dexp ++ "?|[0-9]+" ++ dexp;
const hexfloat = "0[xX](" ++ hex_digit ++ "+%." ++ hex_digit ++ "*" ++ hexp ++ "?|" ++ hex_digit ++ "+" ++ hexp ++ ")";
const float = "(" ++ decfloat ++ "|" ++ hexfloat ++ ")[fF]";
// TODO fallback tainted invalid escape sequence
const hex_quad = hex_digit ++ hex_digit ++ hex_digit ++ hex_digit;
const escape = "(\\(['\"?\\abfnrtv]|[0-7][0-7]?[0-7]?|x" ++ hex_digit ++ "+|u" ++ hex_quad ++ "|U" ++ hex_quad ++ hex_quad ++ "))";

const tok = @import("tok.zig");
const RegexTokenizer = tok.RegexTokenizer;
const Token = tok.Token;

var cache: ?RegexTokenizer = null;
pub fn tokenizer() !RegexTokenizer {
    cache = cache orelse try RegexTokenizer.init(&.{
        // zig fmt: off
        .{.keyword, "auto|break|case|char|const|continue|default|do|double"
            ++ "|else|enum|extern|float|for|goto|if|inline|int|long"
            ++ "|register|restrict|return|short|signed|sizeof|static|struct|switch"
            ++ "|typedef|union|unsigned|void|volatile|while"
            ++ "|_Alignas|_Alignof|_Atomic|_Bool|_Complex|_Generic|_Imaginary|_Noreturn|_Static_assert|_Thread_local"},
        .{.identifier, "[a-zA-Z_]+[a-zA-Z0-9_]*"},
        .{.quoted, "(u8|[uUL])?\"([^\"\n\\]|" ++ escape ++ ")*\"|[uUL]?'([^'\n\\]|" ++ escape ++ ")*'"},
        .{.number, integer ++ "|" ++ float},
        .{.sym, "[(){}[%]<>.!&|+%-*/%]|%->|%+%+|%-%-|<<|>>|[!=<>]=|%^|&&|%|%||%?|:|;|%.%.%.|([*/&+%-^|]|<<|>>)?=|,|#|##"
            ++ "|<:|:>|<%%|%%>|%%:|%%:%%:"}, // darn digraphs
        .{.pp, "#include[ \t]*\"[^\n\"]*\"|<[^\n>]*>|#(pragma|define|undef|if(n?def)|else|elif|endif|line|error|warning)"},
        .{.comment, "//[^\n]*|/%*(/[^*]|[^/])*%*/"},
        .{.ignore, "[ \n\r\t]+"},
    });
    return cache.?;
}

const expectEq = @import("std").testing.expectEqual;
const Tester = struct {
    t: RegexTokenizer,
    buf: []const u8,
    i: usize = 0,
    pub fn expect(self: *@This(), kind: tok.TokenType, s: []const u8) !void {
        try expectEq(Token{.kind = kind, .len = s.len}, self.t.nextToken(self.buf[self.i..]));
        self.i += s.len;
    }
};
test "things" {
    const buf = "if (1) printf(\"blah\");";
    var t = Tester{.t = try tokenizer(), .buf = buf};
    try t.expect(.keyword, "if");
    try t.expect(.ignore, " ");
    try t.expect(.sym, "(");
    try t.expect(.number, "2");
    try t.expect(.sym, ")");
    try t.expect(.ignore, " ");
    try t.expect(.identifier, "printf");
    try t.expect(.sym, "(");
    try t.expect(.quoted, "\"blah\"");
    try t.expect(.sym, ")");
    try t.expect(.sym, ";");
}
color.zig ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub const Color = struct { r: u8, g: u8, b: u8 };

fn h(u: usize) Color {
    return .{ .r = (u >> 16) & 0xFF, .g = (u >> 8) & 0xFF, .b = u & 0xFF };
}

// not doing proper enum array rn
pub const FG = [_]Color{
    h(0x66ff66), // keyword
    h(0x116611), // identifier
    h(0xff7611), // quoted
    h(0x6666ff), // number
    h(0x113311), // sym
    h(0x1d0878), // pp
    h(0x888888), // comment
    h(0x111111), // ignore
};

pub const BG = Color{ .r = 255, .g = 255, .b = 255 };
editor.zig ASCII text
  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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
const std = @import("std");
const os = std.os;
const posix = std.posix;
const File = std.fs.File;
const ArrayList = std.ArrayList;

const ansi = @import("ansi.zig");
const AnsiCommand = ansi.AnsiCommand;
const txtbuf = @import("txtbuf.zig");
const color = @import("color.zig");
const util = @import("util.zig");

const Pos = @import("pos.zig");
const TextBuffer = txtbuf.TextBuffer;

const tok = @import("tok.zig");

fn asgn(u: usize) isize {
    return @intCast(u);
}

fn asun(i: isize) usize {
    return @intCast(i);
}

const Allocator = std.mem.Allocator;

const Edit = struct {
    const Self = @This();
    at: usize,
    old: []const u8,
    new: []const u8,
    fn init(at: usize, old: []const u8, new: []const u8, a: Allocator) !Self {
        const self_new = try a.alloc(u8, new.len);
        @memcpy(self_new, new);
        const self_old = try a.alloc(u8, old.len);
        @memcpy(self_old, old);
        return .{ .at = at, .new = self_new, .old = self_old };
    }
    // Note: To play nice with arena allocators, this must be in reverse order vs. init!
    fn deinit(self: Self, a: Allocator) void {
        a.free(self.old);
        a.free(self.new);
    }
    fn redo(self: Self, buf: *TextBuffer) !usize {
        try buf.replaceRange(self.at, self.old.len, self.new);
        return self.at + self.new.len;
    }
    fn undo(self: Self, buf: *TextBuffer) !usize {
        try buf.replaceRange(self.at, self.new.len, self.old);
        return self.at + self.old.len;
    }
};

const allocator = std.heap.c_allocator;

// TODO cap history size

const History = struct {
    const Self = @This();
    const ArenaAllocator = std.heap.ArenaAllocator;
    arena: ArenaAllocator,
    edits: ArrayList(Edit),
    cursor: usize,
    pub fn init() Self {
        const arena = ArenaAllocator.init(std.heap.page_allocator);
        return .{
            .arena = arena,
            .edits = ArrayList(Edit).init(allocator),
            .cursor = 0,
        };
    }
    pub fn deinit(self: Self) void {
        self.arena.deinit();
        self.edits.deinit();
    }

    fn undo(self: *Self, text: *TextBuffer) !?usize {
        if (self.cursor == 0)
            return null;
        self.cursor -= 1;
        return try self.edits.items[self.cursor].undo(text);
    }

    fn redo(self: *Self, text: *TextBuffer) !?usize {
        if (self.cursor == self.edits.items.len)
            return null;
        const res = try self.edits.items[self.cursor].redo(text);
        self.cursor += 1;
        return res;
    }

    fn record(self: *Self, at: usize, old: []const u8, new: []const u8) !void {
        // TODO do better than throwing edits away
        // Deinitialize *in reverse order* so the arena can actually free the memory
        if (self.cursor < self.edits.items.len) {
            var i: usize = self.edits.items.len - 1;
            while (true) {
                self.edits.items[i].deinit(self.arena.allocator());
                if (i == self.cursor) break;
                i -= 1;
            }
            self.edits.shrinkRetainingCapacity(self.cursor);
        }
        try self.edits.append(try Edit.init(at, old, new, self.arena.allocator()));
        self.cursor += 1;
    }
};

const Clipboard = struct {
    const Self = @This();
    content: []u8,
    pub fn init() !Self {
        return .{ .content = try allocator.alloc(u8, 0) };
    }
    pub fn deinit(self: Self) void {
        allocator.free(self.content);
    }
    pub fn get(self: Self) []const u8 {
        return self.content;
    }
    pub fn set(self: *Self, content: []const u8) !void {
        self.content = try allocator.realloc(self.content, content.len);
        @memcpy(self.content, content);
    }
};

const TextPane = struct {
    const Self = @This();
    anchor: Pos,
    cursor: Pos,
    mark: ?Pos,
    text: TextBuffer,
    history: History,
    clipboard: *Clipboard,
    multiline: bool,
    pub fn init(clipboard: *Clipboard, multiline: bool) !Self {
        return .{
            .anchor = .{ .row = 0, .col = 0 },
            .cursor = .{ .row = 0, .col = 0 },
            .mark = null,
            .text = try TextBuffer.empty(),
            .history = History.init(),
            .clipboard = clipboard,
            .multiline = multiline,
        };
    }
    pub fn deinit(self: *Self) void {
        self.text.deinit();
        self.history.deinit();
    }

    fn setCursor(self: *Self, cursor: Pos) void {
        self.cursor = cursor;
        self.mark = null;
    }

    pub fn setText(self: *Self, text: TextBuffer) void {
        self.text = text;
        self.setCursor(.{ .row = 0, .col = 0 });
        self.anchor = .{ .row = 0, .col = 0 };
        self.history.deinit();
        self.history = History.init();
    }

    fn moveRows(self: *Self, d: isize) Pos {
        const row = @max(0, @min(asgn(self.text.nRows()) - 1, asgn(self.cursor.row) + d));
        const col = @max(0, @min(self.text.nCols(row), self.cursor.col));
        return .{ .row = row, .col = col };
    }

    fn moveCols(self: *Self, d_cols: isize) Pos {
        var cursor = self.cursor;
        var d = d_cols;
        while (d < 0) {
            const col = asgn(cursor.col) + d;
            if (col >= 0) {
                cursor.col = asun(col);
                break;
            }
            if (cursor.row == 0) {
                cursor.col = 0;
                break;
            }
            cursor.row -= 1;
            cursor.col = self.text.nCols(cursor.row);
            d = col + 1;
        }
        while (d > 0) {
            const col = asgn(cursor.col) + d;
            const nCols = self.text.nCols(cursor.row);
            if (col <= nCols) {
                cursor.col = asun(col);
                break;
            }
            if (cursor.row == self.text.nRows() - 1) {
                cursor.col = nCols;
                break;
            }
            cursor.row += 1;
            cursor.col = 0;
            d = col - asgn(nCols) - 1;
        }
        return cursor;
    }

    fn getCursorIdx(self: Self) usize {
        return self.text.getIdx(self.cursor);
    }

    const Span = struct { min: usize, max: usize };
    fn getSelection(self: Self) ?Span {
        if (self.mark) |mark| {
            const idx = self.getCursorIdx();
            const mark_idx = self.text.getIdx(mark);
            return .{ .min = @min(idx, mark_idx), .max = @max(idx, mark_idx) };
        }
        return null;
    }

    fn getCopySpan(self: Self) Span {
        const idx = self.text.getIdx(.{ .row = self.cursor.row, .col = 0 });
        return self.getSelection() orelse Span{ .min = idx, .max = idx + self.text.nCols(self.cursor.row) + 1 };
    }

    fn copy(self: *Self) !void {
        const sel = self.getCopySpan();
        try self.clipboard.set(self.text.getRange(sel.min, sel.max));
    }

    fn deleteSpan(self: *Self, sel: Span) !void {
        const old = self.text.getRange(sel.min, sel.max);
        try self.history.record(sel.min, old, &.{});
        try self.text.replaceRange(sel.min, old.len, &.{});
        self.setCursor(self.text.getPos(sel.min));
    }

    fn delete(self: *Self) !void {
        const idx = self.getCursorIdx();
        const sel = self.getSelection() orelse Span{ .min = if (idx == 0) return else idx - 1, .max = idx };
        return self.deleteSpan(sel);
    }

    fn cut(self: *Self) !void {
        try self.copy();
        try self.deleteSpan(self.getCopySpan());
    }

    fn insert(self: *Self, new: []const u8) !void {
        if (!self.multiline and std.mem.indexOfScalar(u8, new, '\n') != null)
            return;
        const cur_idx = self.getCursorIdx();
        const sel = self.getSelection() orelse Span{ .min = cur_idx, .max = cur_idx };
        const old = self.text.getRange(sel.min, sel.max);
        try self.history.record(sel.min, old, new);
        try self.text.replaceRange(sel.min, old.len, new);
        self.setCursor(self.text.getPos(sel.min + new.len));
    }

    fn insertNewline(self: *Self) !void {
        const start_row = if (self.mark) |pos| @min(pos.row, self.cursor.row) else self.cursor.row;
        const start_col = if (start_row < self.cursor.row) self.mark.?.col else @min((self.mark orelse self.cursor).col, self.cursor.col);
        const start_idx = self.text.getIdx(.{ .row = start_row, .col = 0 });
        const line = self.text.getRange(start_idx, start_idx + self.text.nCols(start_row));
        var i: usize = 0;
        while (i < start_col and (line[i] == ' ' or line[i] == '\t')) i += 1;
        const indent = line[0..i];
        const indented_line = try std.mem.concat(allocator, u8, &.{ "\n", indent });
        defer allocator.free(indented_line);
        try self.insert(indented_line);
    }

    fn paste(self: *Self) !void {
        try self.insert(self.clipboard.get());
    }

    fn undo(self: *Self) !void {
        if (try self.history.undo(&self.text)) |idx|
            self.setCursor(self.text.getPos(idx));
    }

    fn redo(self: *Self) !void {
        if (try self.history.redo(&self.text)) |idx|
            self.setCursor(self.text.getPos(idx));
    }

    fn selectAll(self: *Self) void {
        self.cursor = .{ .row = 0, .col = 0 };
        self.mark = .{ .row = self.text.nRows() - 1, .col = self.text.nCols(self.text.nRows() - 1) };
    }

    fn selectToken(self: *Self) void {
        var hint = tok.Tokenization.Hint{};
        const token = self.text.tokens.getToken(self.getCursorIdx(), &hint);
        // HACK don't let the trailing newline disappear
        self.cursor = self.text.getPos(@min(hint.sum, self.text.chars.items.len - 1));
        self.mark = self.text.getPos(hint.sum - token.len);
    }

    fn gotoPrevToken(self: *Self) void {
        self.setCursor(self.text.getPos(self.text.tokens.getPreviousTokenStart(self.getCursorIdx())));
    }

    fn gotoNextToken(self: *Self) void {
        self.setCursor(self.text.getPos(self.text.tokens.getNextTokenEnd(self.getCursorIdx())));
    }

    pub fn processCommand(self: *Self, cmd: AnsiCommand) !void {
        switch (cmd) {
            else => {},
            .backspace, .delete => try self.delete(),
            .newline, .carriage_return => try self.insertNewline(),
            .print => |c| try self.insert(&[_]u8{c}),
            .tab => try self.insert("    "), // HACK awful
            .ctrl => |c| switch (c) {
                'z' => try self.undo(),
                'y' => try self.redo(),
                'c' => try self.copy(),
                'x' => try self.cut(),
                'v' => try self.paste(),
                'a' => self.selectAll(),
                't' => self.selectToken(),
                else => {},
            },
            .cursor_movement => |cm| switch (cm.modifier) {
                .none => switch (cm.action) {
                    .up => self.setCursor(self.moveRows(-asgn(cm.times))),
                    .down => self.setCursor(self.moveRows(asgn(cm.times))),
                    .right => self.setCursor(self.moveCols(asgn(cm.times))),
                    .left => self.setCursor(self.moveCols(-asgn(cm.times))),
                    .pos1 => self.setCursor(.{ .col = 0, .row = self.cursor.row }),
                    .end => self.setCursor(.{ .col = self.text.nCols(self.cursor.row), .row = self.cursor.row }),
                },
                .ctrl => switch (cm.action) {
                    .up, .down => {}, // TODO
                    .left => self.gotoPrevToken(),
                    .right => self.gotoNextToken(),
                    .pos1 => self.setCursor(.{ .row = 0, .col = 0 }),
                    .end => self.setCursor(.{ .row = self.text.nRows() - 1, .col = self.text.nCols(self.text.nRows() - 1) }),
                },
                .shift => {
                    if (self.mark == null)
                        self.mark = self.cursor;
                    switch (cm.action) {
                        .up => self.cursor = self.moveRows(-asgn(cm.times)),
                        .down => self.cursor = self.moveRows(asgn(cm.times)),
                        .right => self.cursor = self.moveCols(asgn(cm.times)),
                        .left => self.cursor = self.moveCols(-asgn(cm.times)),
                        .pos1 => self.cursor.col = 0,
                        .end => self.cursor.col = self.text.nCols(self.cursor.row),
                    }
                },
            },
        }
    }

    fn scroll(self: *Self, dim: Pos) void {
        self.anchor = self.anchor.min(self.cursor);
        const bottom_right = self.anchor.add(dim);
        if (self.cursor.row >= bottom_right.row)
            self.anchor.row += self.cursor.row - bottom_right.row + 1;
        if (self.cursor.col >= bottom_right.col)
            self.anchor.col += self.cursor.col - bottom_right.col + 1;
    }

    const ColorManager = struct {
        const CM = @This();
        fg: color.Color,
        bg: color.Color,
        pub fn init(writer: anytype) !CM {
            const fg = color.FG[@intFromEnum(tok.TokenType.ignore)];
            try ansi.setFg(writer, fg);
            const bg = color.BG;
            try ansi.setBg(writer, bg);
            return .{
                .fg = fg,
                .bg = bg,
            };
        }
        pub fn set(self: *CM, writer: anytype, t: tok.TokenType, sel: bool) !void {
            var fg = color.FG[@intFromEnum(t)];
            var bg = color.BG;
            if (sel)
                std.mem.swap(color.Color, &fg, &bg);
            if (!std.meta.eql(fg, self.fg)) {
                try ansi.setFg(writer, fg);
                self.fg = fg;
            }
            if (!std.meta.eql(bg, self.bg)) {
                try ansi.setBg(writer, bg);
                self.bg = bg;
            }
        }
    };

    fn render(self: *Self, dim: Pos, writer: anytype, focus: bool) !void {
        self.scroll(dim);

        const idx = self.getCursorIdx();
        const sel = self.getSelection() orelse Span{ .min = idx, .max = idx + 1 };

        var row: usize = 0;
        var cm = try ColorManager.init(writer);
        var tok_hint: tok.Tokenization.Hint = .{};
        while (row < dim.row) : (row += 1) {
            var col: usize = 0;
            while (col < dim.col) : (col += 1) {
                const pos = .{ .row = row, .col = col };
                const abs = self.anchor.add(pos);
                const c = self.text.get(abs);
                var highlight = false;
                var tt = tok.TokenType.ignore;
                if (abs.row < self.text.nRows() and abs.col <= self.text.nCols(abs.row)) {
                    const c_idx = self.text.getIdx(abs);
                    if (focus) highlight = c_idx >= sel.min and c_idx < sel.max;
                    tt = self.text.tokens.getToken(c_idx, &tok_hint).kind;
                }
                try cm.set(writer, tt, highlight);
                switch (c orelse ' ') {
                    0x20...0x7e => |ch| try writer.writeByte(ch),
                    else => try writer.writeAll(" "),
                }
            }
            if (row + 1 < dim.row)
                try writer.writeAll("\r\n");
        }
        try cm.set(writer, .ignore, false);
    }
};

pub const Editor = struct {
    const Self = @This();
    const BW = @TypeOf(std.io.bufferedWriter(std.io.getStdOut().writer()));
    tty: File,
    tui: *BW,
    path: []u8,
    clipboard: *Clipboard,
    textpane: TextPane,
    state: union(enum) {
        normal: void,
        confirm_quit: void,
        save_path: TextPane,
    },
    pub fn init(tty: File, tui: *BW) !Self {
        const clipboard = try allocator.create(Clipboard);
        clipboard.* = try Clipboard.init();
        return .{
            .tty = tty,
            .tui = tui,
            .path = try allocator.alloc(u8, 0),
            .clipboard = clipboard,
            .textpane = try TextPane.init(clipboard, true),
            .state = .normal,
        };
    }
    pub fn deinit(self: *Self) void {
        self.textpane.deinit();
        self.clipboard.deinit();
        allocator.free(self.path);
        allocator.destroy(self.clipboard);
    }

    fn setPath(self: *Self, path: []const u8) !void {
        self.path = try allocator.realloc(self.path, path.len);
        @memcpy(self.path, path);
    }

    pub fn open(self: *Self, path: []const u8) !void {
        if (TextBuffer.open(path)) |text| {
            self.textpane.setText(text);
            try self.setPath(path);
        } else |err| switch (err) {
            error.FileNotFound => {
                self.textpane.setText(try TextBuffer.empty());
                try self.setPath(path);
            },
            else => try self.setPath(""),
        }
    }

    fn isSaved(self: *Self) bool {
        if (self.path.len == 0)
            return self.textpane.text.chars.items.len == 0;
        const file = std.fs.cwd().openFile(self.path, .{ .mode = .read_only }) catch return false;
        var chars = ArrayList(u8).init(allocator);
        defer chars.deinit();
        file.reader().readAllArrayList(&chars, 16384) catch return false;
        return std.mem.eql(u8, self.textpane.text.chars.items, chars.items);
    }

    fn save(self: *Self) !void {
        if (self.path.len > 0) {
            try self.textpane.text.save(self.path); // TODO error handling
        } else {
            self.state = .{ .save_path = try TextPane.init(self.clipboard, false) };
        }
    }

    fn processCommand(self: *Self, cmd: AnsiCommand) !bool {
        switch (self.state) {
            .normal => switch (cmd) {
                .ctrl => |c| switch (c) {
                    'q' => {
                        if (self.isSaved())
                            return true;
                        self.state = .{ .confirm_quit = {} };
                    },
                    's' => try self.save(),
                    else => try self.textpane.processCommand(cmd),
                },
                else => try self.textpane.processCommand(cmd),
            },
            .confirm_quit => switch (cmd) {
                .ctrl => |c| switch (c) {
                    'q' => return true,
                    else => self.state = .{ .normal = {} },
                },
                else => self.state = .{ .normal = {} },
            },
            .save_path => |prompt| switch (cmd) {
                .ctrl => |c| switch (c) {
                    'q' => {
                        self.state.save_path.deinit();
                        self.state = .{ .normal = {} };
                    },
                    else => try self.state.save_path.processCommand(cmd),
                },
                .newline, .carriage_return => {
                    const path = prompt.text.chars.items;
                    try self.setPath(path[0 .. path.len - 1]); // trim trailing newline (TODO refucktor)
                    try self.textpane.text.save(self.path); // TODO error handling
                    self.state.save_path.deinit();
                    self.state = .{ .normal = {} };
                },
                else => try self.state.save_path.processCommand(cmd),
            },
        }
        return false;
    }

    fn processInput(self: *Self, buf: []const u8) !bool {
        var iter = ansi.parse(buf);
        while (iter.next()) |cmd| {
            switch (cmd) {
                .ignore => {},
                .insert => @import("e/josh.zig").josh(self.tty, self.tui) catch {},
                else => if (try self.processCommand(cmd)) return true,
            }
        }
        return false;
    }

    fn render(self: *Self) !void {
        const us = std.time.microTimestamp();
        const writer = self.tui.writer();
        const dim = try util.getTtySize(self.tty);
        try ansi.setCursor(writer, .{ .row = 0, .col = 0 });
        try self.textpane.render(.{ .row = dim.row - 1, .col = dim.col }, writer, self.state == .normal);
        try writer.writeAll("\r\n");

        switch (self.state) {
            .normal => {
                var buf: [1000]u8 = undefined;
                var fixbuf = std.io.fixedBufferStream(&buf);
                @memset(buf[0..dim.col], ' ');
                std.fmt.format(fixbuf.writer(), "{s}:{d}:{d}  {d} us  {d} lines", .{
                    if (self.path.len == 0) "?" else self.path,
                    self.textpane.cursor.row + 1,
                    self.textpane.cursor.col + 1,
                    std.time.microTimestamp() - us,
                    self.textpane.text.nRows(),
                }) catch {};
                try writer.writeAll(buf[0..dim.col]);
            },
            .confirm_quit => {
                const msg = "You have unsaved changes. Press C-q to quit, any other key to cancel.";
                try writer.writeAll(if (dim.col < msg.len) msg[0..dim.col] else msg);
                var i = msg.len;
                while (i < dim.col) : (i += 1) try writer.writeByte(' ');
            },
            .save_path => {
                const prefix = "save as: ";
                try writer.writeAll(prefix);
                try self.state.save_path.render(.{ .row = 1, .col = dim.col - prefix.len }, writer, true);
            },
        }

        try self.tui.flush();
    }

    pub fn run(self: *Self) !void {
        try self.render();
        var buf: [1000]u8 = undefined;
        while (true) {
            // TODO deal with full buffer (unlikely in normal usage)
            const len = try self.tty.read(&buf);
            if (try self.processInput(buf[0..len]))
                return;
            try self.render();
        }
    }
};
main.zig ASCII text
 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
const std = @import("std");
const fs = std.fs;
const os = std.os;
const posix = std.posix;

const ansi = @import("ansi.zig");
const Editor = @import("editor.zig").Editor;

fn uncook(handle: anytype, tcattr: anytype) !void {
    var raw_attr = tcattr;
    raw_attr.lflag.ECHO = false;
    raw_attr.lflag.ICANON = false;
    raw_attr.lflag.ISIG = false;
    raw_attr.lflag.IEXTEN = false;
    raw_attr.iflag.IXON = false;
    raw_attr.iflag.ICRNL = false;
    raw_attr.iflag.BRKINT = false;
    raw_attr.iflag.INPCK = false;
    raw_attr.iflag.ISTRIP = false;
    raw_attr.oflag.OPOST = false;
    raw_attr.cflag.CSIZE = .CS8;
    // TODO think about these
    raw_attr.cc[@intFromEnum(std.posix.V.TIME)] = 0;
    raw_attr.cc[@intFromEnum(std.posix.V.MIN)] = 1;
    try std.posix.tcsetattr(handle, .FLUSH, raw_attr);
}

fn run() !void {
    var tty = try fs.cwd().openFile("/dev/tty", .{ .mode = .read_write });
    defer tty.close();

    const cooked_attr = try std.posix.tcgetattr(tty.handle);
    defer std.posix.tcsetattr(tty.handle, .FLUSH, cooked_attr) catch {};
    try uncook(tty.handle, cooked_attr);

    const stdout_file = std.io.getStdOut().writer();
    var bw = std.io.bufferedWriter(stdout_file);
    defer bw.flush() catch {};
    const stdout = bw.writer();
    const writeCsi = ansi.writeCsi;

    // Hide / unhide cursor
    try writeCsi(stdout, "?25l");
    defer writeCsi(stdout, "?25h") catch {};
    // Mouse on / off
    // try writeCsi(stdout, "?1000h");
    // defer writeCsi(stdout, "?1000l") catch {};
    // Save / restore cursor pos
    try writeCsi(stdout, "s");
    defer writeCsi(stdout, "u") catch {};
    // Save / restore screen
    try writeCsi(stdout, "?47h");
    defer writeCsi(stdout, "?47l") catch {};
    // Enable alternative buffer / switch back to original buffer
    try writeCsi(stdout, "?1049h");
    defer writeCsi(stdout, "?1049l") catch {};
    try bw.flush();

    var editor = try Editor.init(tty, &bw);
    defer editor.deinit();
    var args = std.process.args();
    if (args.next()) |_| {
        if (args.next()) |path| {
            if (args.next() == null)
                try editor.open(path);
        }
    }
    try editor.run();
}

pub fn main() !void {
    return run() catch |e| switch (e) {
        error.OutOfMemory => std.io.getStdOut().writer().writeAll(@import("e/oom.zig").oom),
        else => e,
    };
}
plain.zig ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
const tok = @import("tok.zig");
const RegexTokenizer = tok.RegexTokenizer;
const Token = tok.Token;

var cache: ?RegexTokenizer = null;
pub fn tokenizer() !RegexTokenizer {
    cache = cache orelse try RegexTokenizer.init(&.{
        // zig fmt: off
        .{.identifier, "[^ \n\r\t]+"},
        .{.ignore, "[ \n\r\t]+"},
    });
    return cache.?;
}
pos.zig ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
const Pos = @This();
row: usize,
col: usize,
pub fn add(p: Pos, q: Pos) Pos {
    return Pos{ .row = p.row + q.row, .col = p.col + q.col };
}
pub fn sub(p: Pos, q: Pos) Pos {
    return Pos{ .row = p.row - q.row, .col = p.col - q.col };
}
pub fn min(p: Pos, q: Pos) Pos {
    return Pos{ .row = @min(p.row, q.row), .col = @min(p.col, q.col) };
}
tok.zig ASCII text
  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
const std = @import("std");

const NFA = @import("reg/nfa.zig").NFA(StateInfo);
const DFA = @import("reg/dfa.zig").DFA(StateInfo);
const RegexReader = @import("reg/ex.zig").RegexReader(StateInfo);
const allocator = std.heap.c_allocator;

pub const TokenType = enum(u8) {
    keyword,
    identifier,
    quoted,
    number,
    sym,
    pp,
    comment,
    ignore,
};

pub const Token = struct {
    kind: TokenType,
    len: usize,
};

const StateInfo = struct {
    tt: TokenType,
    acc: bool,
};

fn mergeTokens(a: StateInfo, b: StateInfo) StateInfo {
    if (a.acc != b.acc) {
        return if (a.acc) a else b;
    }
    return .{
        .tt = @enumFromInt(@min(@intFromEnum(a.tt), @intFromEnum(b.tt))),
        .acc = a.acc,
    };
}

pub const RegexTokenizer = struct {
    const Self = @This();
    dfa: DFA,
    pub fn init(comptime rules: []const struct { TokenType, []const u8 }) !Self {
        var nfa = NFA.init(allocator, .{ .tt = .ignore, .acc = false });
        defer nfa.deinit();
        var subs: [rules.len]NFA.Sub = undefined;
        var i: usize = 0;
        while (i < rules.len) : (i += 1) {
            nfa.value = .{ .tt = rules[i][0], .acc = false };
            var rr = RegexReader.init(&nfa, rules[i][1]);
            subs[i] = try rr.read();
            nfa.states.items[subs[i].end].value.acc = true; // HACK
        }
        const sub = try nfa.choice(&subs);
        return .{
            .dfa = try nfa.toDFA(sub, mergeTokens),
        };
    }
    // no need to deinit
    pub fn nextToken(self: Self, buf: []const u8) Token {
        var state: usize = 0;
        var len: usize = 0;
        while (len < buf.len) : (len += 1) {
            const c = buf[len];
            if (self.dfa.getTransition(state, c)) |next_state| {
                state = next_state;
            } else {
                return .{
                    .kind = self.dfa.states.items[state].value.tt,
                    .len = @max(len, 1), // HACK
                };
            }
        }
        return .{
            .kind = self.dfa.states.items[state].value.tt,
            .len = @max(len, 1),
        };
    }
};

// Two interesting optimizations are possible here:
// - We could retokenize only the affected range.
// - We could use a clever data structure (e.g. B-trees augmented with sums of token lengths)
// All in all this would in theory allow updates in O(edit size) time.
// But we don't have working B-trees so we don't and this is O(text size) on every edit. Urgh.
pub const Tokenization = struct {
    const Self = @This();
    tokens: std.ArrayList(Token),
    pub fn init(text: []const u8, tokenizer: RegexTokenizer) !Self {
        var i: usize = 0;
        var tokens = std.ArrayList(Token).init(allocator);
        while (i < text.len) {
            const t = tokenizer.nextToken(text[i..]);
            try tokens.append(t);
            i += t.len;
        }
        return .{ .tokens = tokens };
    }
    pub fn deinit(self: *Self) void {
        self.tokens.deinit();
    }
    pub const Hint = struct {
        ti: usize = 0,
        sum: usize = 0,
    };
    pub fn getPreviousTokenStart(self: Self, i: usize) usize {
        var sum: usize = 0;
        var res: usize = 0;
        var j: usize = 0;
        while (sum < i and j < self.tokens.items.len) : (j += 1) {
            const token = self.tokens.items[j];
            if (token.kind != .ignore)
                res = sum;
            sum += token.len;
        }
        return res;
    }
    pub fn getNextTokenEnd(self: Self, i: usize) usize {
        var sum: usize = 0;
        var j: usize = 0;
        while (sum < i and j < self.tokens.items.len) {
            sum += self.tokens.items[j].len;
            j += 1;
        }
        while (j < self.tokens.items.len) : (j += 1) {
            sum += self.tokens.items[j].len;
            if (self.tokens.items[j].kind != .ignore) break;
        }
        return sum;
    }
    pub fn getToken(self: Self, i: usize, hint: *Hint) Token {
        while (hint.sum <= i and hint.ti < self.tokens.items.len) {
            hint.sum += self.tokens.items[hint.ti].len;
            hint.ti += 1;
        }
        return self.tokens.items[hint.ti - 1];
    }
};
txtbuf.zig ASCII text
  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
145
const std = @import("std");
const fs = std.fs;
const Path = []const u8;

const stdio = @cImport({
    @cInclude("stdio.h");
});

const Pos = @import("pos.zig");

const char = u8;

const allocator = std.heap.c_allocator;
const Allocator = std.mem.Allocator;

const ArrayList = std.ArrayList;

const Tokenization = @import("tok.zig").Tokenization;

pub const FileType = enum {
    plain,
    c,
    fn init(path: Path) FileType {
        return if (std.mem.endsWith(u8, path, ".c")) .c else .plain;
    }
};

fn tokenize(t: FileType, text: []const u8) !Tokenization {
    return Tokenization.init(text, switch (t) {
        .plain => try @import("plain.zig").tokenizer(),
        .c => try @import("c.zig").tokenizer(),
    });
}

pub const TextBuffer = struct {
    const Self = @This();
    chars: ArrayList(char),
    lineOffsets: ArrayList(usize), // where does the respective line end?
    fileType: FileType,
    tokens: Tokenization,
    pub fn empty() !Self {
        var chars = try ArrayList(char).initCapacity(allocator, 1);
        try chars.append('\n');
        return Self{
            .chars = chars,
            .lineOffsets = try calculateLineOffsets(chars.items),
            .tokens = try tokenize(.plain, chars.items),
            .fileType = .plain,
        };
    }
    pub fn open(path: Path) !Self {
        const file = try fs.cwd().openFile(path, .{ .mode = .read_only });
        const reader = file.reader();
        var chars = ArrayList(char).init(allocator);
        {
            defer file.close();
            try reader.readAllArrayList(&chars, 16384);
        }
        const ft = FileType.init(path);
        return .{
            .chars = chars,
            .lineOffsets = try Self.calculateLineOffsets(chars.items),
            .tokens = try tokenize(ft, chars.items),
            .fileType = ft,
        };
    }
    pub fn save(self: *TextBuffer, path: Path) !void {
        const old_ft = self.fileType;
        self.fileType = FileType.init(path);
        if (old_ft != self.fileType) {
            self.tokens.deinit();
            self.tokens = try tokenize(self.fileType, self.chars.items);
        }

        const dirname = fs.path.dirname(path);
        const basename = fs.path.basename(path);
        const tmpname = try std.mem.concat(allocator, u8, &.{ ".~sped-tmp-", basename });
        defer allocator.free(tmpname);
        const tmpath = try fs.path.join(allocator, if (dirname) |name| &.{ name, basename } else &.{basename});
        defer allocator.free(tmpath);
        const file = try fs.cwd().createFile(tmpath, .{});
        {
            defer file.close();
            try file.writeAll(self.chars.items);
        }
        try fs.cwd().rename(tmpath, path);
    }
    pub fn deinit(self: *Self) void {
        self.chars.deinit();
        self.lineOffsets.deinit();
        self.tokens.deinit();
    }
    /// Number of rows, always >= 1.
    pub fn nRows(self: Self) usize {
        return self.lineOffsets.items.len;
    }
    pub fn nCols(self: Self, row: usize) usize {
        return if (row == 0)
            self.lineOffsets.items[0]
        else
            self.lineOffsets.items[row] - self.lineOffsets.items[row - 1] - 1;
    }
    // TODO LFs (<=)
    pub fn inBounds(self: Self, pos: Pos) bool {
        return pos.row < self.nRows() and pos.col < self.nCols(pos.row);
    }
    fn rowStart(self: Self, row: usize) usize {
        return if (row == 0) 0 else self.lineOffsets.items[row - 1] + 1;
    }
    pub fn getIdx(self: Self, pos: Pos) usize {
        return self.rowStart(pos.row) + pos.col;
    }
    fn loLt(_: void, lhs: usize, rhs: usize) bool {
        return lhs < rhs;
    }
    /// O(log n)
    pub fn getPos(self: Self, idx: usize) Pos {
        const row = std.sort.lowerBound(usize, idx, self.lineOffsets.items, void{}, loLt);
        return .{ .row = row, .col = idx - self.rowStart(row) };
    }
    pub fn get(self: Self, pos: Pos) ?char {
        return if (self.inBounds(pos)) self.chars.items[self.getIdx(pos)] else null;
    }
    pub fn getRange(self: Self, from: usize, to: usize) []const u8 {
        return self.chars.items[from..to];
    }
    fn calculateLineOffsets(chars: []const u8) !ArrayList(usize) {
        var lineOffsets = ArrayList(usize).init(allocator);
        var i: usize = 0;
        while (std.mem.indexOfScalar(char, chars[i..], '\n')) |offset| {
            try lineOffsets.append(i + offset);
            i += offset + 1;
        }
        if (chars.len == 0 or i < chars.len) // no trailing newline
            try lineOffsets.append(chars.len); // note: no newline!
        return lineOffsets;
    }
    pub fn replaceRange(self: *Self, from: usize, len: usize, replacement: []const u8) !void {
        try self.chars.replaceRange(from, len, replacement);
        self.lineOffsets.deinit();
        self.lineOffsets = try calculateLineOffsets(self.chars.items);
        self.tokens.deinit();
        self.tokens = try tokenize(self.fileType, self.chars.items);
    }
};
util.zig ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
const std = @import("std");
const Pos = @import("pos.zig");

pub fn getTtySize(tty: std.fs.File) !Pos {
    var size: std.c.winsize = undefined;
    size.ws_row = 60;
    size.ws_col = 80;
    const err = std.c.ioctl(tty.handle, std.c.T.IOCGWINSZ, &size);
    if (err != 0)
        return error.TerminalSizeUnknown;
    return .{ .row = size.ws_row, .col = size.ws_col };
}
build.zig ASCII text
 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
const std = @import("std");

pub fn build(b: *std.Build) void {
    const target = b.standardTargetOptions(.{});
    const optimize = b.standardOptimizeOption(.{});

    const exe = b.addExecutable(.{
        .name = "sped",
        .root_source_file = b.path("src/main.zig"),
        .target = target,
        .optimize = optimize,
        .link_libc = true,
    });

    b.installArtifact(exe);

    const run_cmd = b.addRunArtifact(exe);

    run_cmd.step.dependOn(b.getInstallStep());

    if (b.args) |args| {
        run_cmd.addArgs(args);
    }

    const run_step = b.step("run", "Run editor");
    run_step.dependOn(&run_cmd.step);

    const exe_unit_tests = b.addTest(.{
        .root_source_file = b.path("src/c.zig"),
        .target = target,
        .optimize = optimize,
        .link_libc = true,
    });

    const run_exe_unit_tests = b.addRunArtifact(exe_unit_tests);

    const test_step = b.step("test", "Run unit tests");
    test_step.dependOn(&run_exe_unit_tests.step);
}
build.zig.zon ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
.{
    .name = "sped",
    .version = "0.0.0",
    .minimum_zig_version = "0.13.0",
    .dependencies = .{},
    .paths = .{
        "build.zig",
        "build.zig.zon",
        "src",
        // TODO license
    },
}
tut.txt ASCII text
 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
sped is a lightweight, primitive text editor

if first command line argument is a file that is opened

stuff marked with [ ] is not yet implemented

features:

- syntax highlighting (C only)
- [ ] good performance even for massive files

keybindings:

notation:

- Control: C
- Shift: S
- Arrow Keys: L, R, U, D

cursor movement:

- L / R / U / D: move cursor
- begin / end: move to begin / end of line
- C-begin / C-end: move to begin / end of file
- [ ] page up / page down: move cursor up / down one page
- C-L / C-R: move to previous / next token
- [ ] C-U / C-D:
    * if parentheses (tokens) are unmatched at cursor position:
      move to previous opening / subsequent closing parenthesis
    * otherwise:
      move to previous / subsequent smaller indentation level

selection:

- S-L / S-R / S-U / S-D: start or continue selection 
- C-c / C-x / C-v: copy / cut / paste
	* operate on the given line if nothing is selected
- C-a / C-t: select all / token

editing:

- character keys: insert character
- backspace: delete
- [ ] tab:
	* if preceding characters are whitespace (incl. newline): indent
	* otherwise: autocomplete token
- [ ] S-tab: dedent
- enter: insert newline (with indentation)
- C-z / C-y: undo / redo

meta:

- C-q: quit
- C-s: save file
- [ ] C-f: find
- [ ] C-r: replace
- [ ] C-g: goto
- [ ] C-i: help

round #61

submitted at
1 like

guesses
comments 0

post a comment


rps-royale.lua ASCII text
 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
-- y'all will guess me anyway but who cares,
-- scissors is winning rock paper scissors royale!
-- (i hope)
getmetatable"".__index = function(str, key)
  if type(key) == "number" then
    return (key >= 1 and key <= #str) and str:sub(key, key) or nil
  end
  return string[key]
end
local readline = io.lines()
while 1 do
  local grid = {}
  repeat
    local line = readline()
    if not line then break end -- being nice or something
    grid[#grid+1] = line
  until line == ""
  local x = assert(tonumber(readline()))
  local y = assert(tonumber(readline()))
  local dirs = {
    L = {-1, 0},
    R = {1, 0},
    U = {0, -1},
    D = {0, 1},
  }
  local function get_tile(tx, ty)
    return (grid[ty] or {})[tx] or "#"
  end
  local function murder(K, V)
    local function dist(mx, my)
      local res = 0
      local level = {{mx, my}}
      local visited = {[my] = {[mx] = true}}
      repeat
        local next_level = {}
        for _, pos in ipairs(level) do
          local px, py = table.unpack(pos)
          for dn, dp in pairs(dirs) do
            local dx, dy = table.unpack(dp)
            local nx, ny = px + dx, py + dy
            if ({[K..V]=1,[V..K]=1})[get_tile(px,py)..get_tile(nx,ny)] then
              return res
            end
            if get_tile(nx, ny) ~= "#" and not (visited[ny] or {})[nx] then
              visited[ny] = visited[ny] or {}
              visited[ny][nx] = true
              next_level[#next_level+1] = {nx, ny}
            end
          end
        end
        level = next_level
        res = res + 1
      until not level[1]
      return math.huge
    end
    local best_move, min_dist = nil, math.huge
    for dn, dp in pairs(dirs) do
      local dx, dy = table.unpack(dp)
      if ({[K..V]=1,[V..K]=1})[get_tile(x,y)..get_tile(x+dx,y+dy)] then
        print"I"
        print(dn)
        return
      end
      local can_dist = dist(x + dx, y + dy)
      if can_dist < min_dist then
        best_move, min_dist = dn, can_dist
      end
    end
    if best_move then
      print"M"
      print(best_move)
      return
    end
    print"P" -- there is nothing we can do
  end
  if table.concat(grid):find"R" then
    murder("P", "R")
  else
    murder("S", "P")
  end
end

round #56

submitted at
0 likes

guesses
comments 0

post a comment


sus.zig ASCII text
 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
                                 const std=@import("std");const ArrayList                 
                                 =std.ArrayList;const Doer=struct{                        
                                 const State=enum{Normal,JustTainted                      
                        ,Tainted,TaintedGroup,Ignore,};const SyntaxError=error            
                        .InvalidSyntax;buf:ArrayList(u8),stk:ArrayList(usize              
                        ),stateStk:ArrayList(State),state:State,concatBegin               
                        :usize,pub                     fn init(alloc:anytype)Doer         
                        {return Doer                  {.buf=ArrayList(u8).init            
                        (alloc),.                     stk=ArrayList(usize).init           
                     (alloc),.         stateStk=ArrayList(State).init(alloc),.state       
                     =.Normal,         .concatBegin=0,};}pub fn startConcat(self:         
                     *Doer)void        {self.eraseConcat();self.state=.Normal;}pub        
                     fn eraseConcat (self:*Doer)void                    {self.buf.shrinkRetainingCapacity
                     (self.concatBegin);}pub fn pushState               (self:*Doer)!void 
                     {try self      .stk.append(self                    .concatBegin);try 
      self.stateStk.append(         self.state);self                             .concatBegin
      =self.buf.items.len;}         pub fn popState                              (self:   
      *Doer)!void{self.concatBegin  =self.stk.popOrNull                          () orelse 
   return SyntaxError;self.         state=self.stateStk.popOrNull() orelse unreachable;}   
   pub fn taint(self:*Doer)         void{self.eraseConcat();self.state=.Tainted;}pub fn   
   bufChar(self:*Doer,c:u8)         !void{try self.buf.append(c);}pub fn do(self:*Doer,   
   in:anytype     )![]const             u8{while(in.readByte())|c|{switch(self.state){.   
   Normal=>switch (c){'\\'=>           try self.bufChar(try in.readByte()),'|'=>self.state
   =.Ignore,      '*'=>{},'['          =>{if(try in.readByte()!=']')return SyntaxError;   
   self.state     =.JustTainted           ;},']'=>return SyntaxError,'('=>try self.pushState
   (),')'=>try     self.popState          (),else=>try self.bufChar(c),},.JustTainted     
   =>switch(      c){'\\'=>               {try in.skipBytes(1,.{});self.taint();},'*'     
   =>self.state   =.Normal,                                                '|'=>self      
   .startConcat   (),'('=>{                                                self.taint     
   ();try self    .pushState                                               ();},')'=>     
   {self.         eraseConcat                                              ();self.state  
   =.TaintedGroup ;},else=>                                                self.taint     
   (),},.         Tainted=>                                                switch(c)      
   {'\\'=>        try in.skipBytes                                         (1,.{}),'|'    
   =>self         .startConcat                                             (),'('=>try    
   self.pushState (),')'=>{                                                self.eraseConcat
   ();self.state  =.TaintedGroup                                           ;},else=>      
   {},},.TaintedGroup=>switch                                              (c){'*'=>      
   try self.      popState(                                                ),'|'=>{try    
   self.popState  ();self.startConcat                                      ();},'('=>     
   {try self.popState();self                                               .taint();      
   try self.pushState();},')'                                              =>{try self    
      .popState();self.state              =.TaintedGroup;},'\\'=>{try    in.skipBytes     
      (1,.{});try self.popState           ();self.taint();},else=>{try   self.popState    
      ();self.taint();}},.Ignore          =>switch(c){'\\','['=>try in  .skipBytes        
                     (1,.{}               ),']'=>return SyntaxError     ,'('=>try         
                     self.pushState       (),')'=>try  self.popState    (),else=>         
                     {},},}               }else|err   |{if(err!=error   .EndOfStream      
                     )return               err;}switch(self.state       ){.Normal         
                     ,.Ignore             =>return self.buf.toOwnedSlice(),else=>         
                     return                SyntaxError,}}};pub fn        main()!void      
                     {const stdout=std.io.getStdOut   ().writer();var bufout=std          
                     .io.bufferedWriter(stdout);const  stdin=std.io.getStdIn()            
                     ;var bufin=std.io.bufferedReader (stdin.reader());var arena          
                     =std.heap.ArenaAllocator.init                                        
                     (std.heap.page_allocator);defer                                      
                     arena.deinit();var doer=Doer                                         
.init(arena.allocator());try bufout.writer().writeAll(try doer.do(bufin.reader()));try bufout.flush();}

round #55

submitted at
0 likes

guesses
comments 0

post a comment


lyric.py ASCII text
 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
from sys import stdin

M = {
    '+' : ((1, 0),
           (0, 1)),
    '/' : ((0,-1),
           (-1,0)),
    '\\': ((0, 1),
           (1, 0)),
}

L = tuple(map(str.rstrip, stdin.readlines()))

W, H = S = max(map(len, L)), len(L)

def I(p):
    x, y = p
    return y in range(H) and x in range(len(L[y])) and L[y][x] in M

def D(v, w):
    return sum(x * y for x, y in zip(v, w))

def F(p, v):
    x, y = p
    m = M[L[y][x]]
    w = tuple(map(lambda r: D(r, v), m))
    return (x + w[0], y + w[1]), w

def P(p, v):
    o = p
    while I(p):
        p, v = F(p, v)
    if abs(D(o, v) - D(p, v)) >= abs(D(S, v)) >= 8:
        exit(1)

for x in range(W):
    P((x, 0), (0, 1))
    P((x, H-1), (0, -1))

for y in range(H):
    P((0, y), (1, 0))
    P((W-1, y), (-1, 0))

def C(p):
    for v in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        q = set()
        while I(p):
            q.add(p)
            p, v = F(p, v)
            if p in q:
                exit(1)

for y, l in enumerate(L):
    for x in range(len(l)):
        C((x, y))

round #54

submitted at
0 likes

guesses
comments 0

post a comment


bnuuy.tar.paq8px208fix1 data

round #53

submitted at
2 likes

guesses
comments 0

post a comment


.php Unicode text, UTF-8 text
  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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#!/c/Program\ Files/PHP/php.exe
<?php
ini_set('evil_bit', 1);
$a=[];
while ($b=rtrim(fgets(STDIN), "\n\r"))
	{ $cs=array();
	  preg_match_all('/./u',$b,$cs);
	  $a[]=$cs[0];
	}
function d() {
global $a;
foreach ($a as $r)
{
	foreach ($r as $c)
		echo $c;
	echo "\n";
}
}
function ass($c) {
	if ($c) {
		return;
	}
	echo "invalid!!!";
	exit(69);
}
class RectAngle
{
	public readonly int $x1, $x2, $y1, $y2;
	public function __construct($x1, $x2, $y1, $y2) {
		$this->x1 = $x1;
		$this->x2 = $x2;
		$this->y1 = $y1;
		$this->y2 = $y2;
    }
    public function loop($f) {
		for ($x = $this->x1; $x <= $this->x2; $x++)
			for ($y = $this->y1; $y <= $this->y2; $y++)
				$f($x,$y);
    }
    public function cr() {
    	global $a;
    	$a[$this->y1][$this->x1]=$a[$this->y1][$this->x2]=$a[$this->y2][$this->x1]=$a[$this->y2][$this->x2]=' ';
    }
    public function inp($x,$y) {
    	return $x >= $this->x1 && $x <= $this->x2 && $y >= $this->y1 && $y <= $this->y2;
    }
}
if (!($h=count($a))) {
	exit;
}
$w=count($a[0]);
$rn=0;
$ls=[
	'│' => "UD",
	'─' => "LR",
	'┴' => "LRU",
	'┬' => "LRD",
	'┤' => "LUD",
	'├' => "RUD",
	'┌' => "DR",
	'┐' => "LD",
	'└' => "UR",
	'┘' => "LU",
];
$ds=[
	"L" => [-1,0],
	"R" => [1,0],
	"U" => [0,-1],
	"D" => [0,1],
];
$br=[];
foreach ($a as $y=>$r) {
	foreach ($r as $x=>$c) {
		switch ($c) {
			case '┌':
				$xn = $x;
				while (++$xn < $w && $r[$xn] != '┐');
				if ($xn==$w) continue 2;
				$yn = $y;
				while (++$yn < $h && $a[$yn][$x] != '└');
				if ($yn==$h) continue 2;
				if ($a[$yn][$xn] != '┘') continue 2;
				$re=new RectAngle($x,$xn,$y,$yn);
				$re->cr();
				$con=[++$rn=>true];
				$fl = function($x,$y) use ($re,&$br,$rn,$ds,$ls,$w,$h,&$con) {
					global $a;
					$br[$y][$x] = $rn;
					$in=0;
					$dv=null;
					ass(array_key_exists($a[$y][$x],$ls));
					foreach (str_split($ls[$a[$y][$x]]) as $dc) {
						$dw=$ds[$dc];$xm=$x+$dw[0];$ym=$y+$dw[1];
						if ($re->inp($xm,$ym)) $in++;
						else $dv = $dw;
					}
					ass($in==2);
					$a[$y][$x]=' ';
					if ($dv==null) return;
					$kill=[];
					while (1) {
						$x+=$dv[0];$y+=$dv[1];
						$kill[]=[$x,$y];
						ass((new RectAngle(0,$w-1,0,$h-1))->inp($x,$y));
						$re2 = null;
						if (array_key_exists($y,$br) && array_key_exists($x,$br[$y]))
							$re2 = $br[$y][$x];
						if ($re2!=null) {
							ass(!array_key_exists($re2,$con));
							$con[$re2]=true;
							foreach ($kill as $k)
								$a[$k[1]][$k[0]]=' ';
							break;
						}
						ass(array_key_exists($a[$y][$x],$ls));
						$sl = strlen($ls[$a[$y][$x]]);
						if ($sl==3) break;
						ass($sl==2);
						$dv2=null;
						foreach (str_split($ls[$a[$y][$x]]) as $dc) {
							$dvc=$ds[$dc];
							if ($dvc[0]!=-$dv[0] || $dvc[1]!=-$dv[1])
								$dv2=$dvc; #there is no going back
						}
						$dv=$dv2;
					}
				};
				(new RectAngle($x+1, $xn-1, $y+1, $yn-1))->loop(function($x,$y) {
					 global $a;
					ass($a[$y][$x] == ' ');
				});
				foreach ([
					new RectAngle($x+1, $xn-1, $y, $y),
					new RectAngle($x+1, $xn-1, $yn, $yn),
					new RectAngle($x, $x, $y+1, $yn-1),
					new RectAngle($xn, $xn, $y+1, $yn-1)
				] as $rl) $rl->loop($fl);
				break;
			case '│':
			case '─':
			case '┴':
			case '┬':
			case '┤':
			case '├':
			case '┐':
			case '└':
			case '┘':
			case ' ':
				break; # a ok
			default:
				ass(0);
		}
	}
}
foreach ($a as $r)
	foreach ($r as $c)
		ass($c==' ');
?>

round #52

submitted at
0 likes

guesses
comments 0

post a comment


thuemorseq.hs Unicode text, UTF-8 text
1
2
3
4
5
6
import Data.Bits (popCount, (.&.))
import Data.Function (on)
naive = [0] ++ go [0] where go seq = let inv = map (1-) seq in inv ++ go (seq ++ inv)
parity = go (0 :: Integer) where go i = popCount i .&. 1 : go (succ i)
main = if ((==) `on` take 1000) naive parity then putStrLn "Test passed" else error "Test failed"
-- 🥱

round #51

submitted at
1 like

guesses
comments 0

post a comment


tm.c ASCII text
 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
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#define mapass(v,f,...) v=f(v,##__VA_ARGS__)
enum C {Z,O,E};
const char L=-1,R=1;
typedef struct {char m;enum C w;int n;} T;
const T sts[7][3]={{
	{L,E,1},
	{L,E,1},
	{L,E,5},
},{
	{L,O,4},
	{L,Z,1},
	{R,E,2},
},{
	{R,O,3},
	{R,O,2},
	{R,O,0},
},{
	{R,Z,3},
	{R,Z,2},
	{R,Z,0},
},{
	{L,Z,4},
	{L,O,4},
	{R,E,6},
},{
	{L,Z,5},
	{L,O,5},
	{R,E,-1},
},{
	{R,E,2},
	{R,E,2},
	{R,E,2},
}};
char *dostuff(char *t)
{
	int s=0;
	++t;
	do {
		T tr=sts[s][*t];
		*t=tr.w; t+=tr.m; s=tr.n;
	} while (s!=-1);
	return t;
}
main()
{
	char c,*t=malloc(1);
	t[0]=E;
	int nt=1,ct=1;
	while (EOF!=(c=getchar())) {
		if (nt==ct) assert(mapass(t,realloc,ct<<=1));
		t[nt++]=Z;
	}
	if (nt+2>ct) assert(mapass(t,realloc,ct+2));
	t[nt++]=E;
	t[nt++]=E;
	assert(feof(stdin));
	mapass(t,dostuff);
	for(char *e=t+nt;t!=e&&*t!=E;++t)
		assert(EOF!=putchar('0'+*t));
}

round #50

submitted at
0 likes

guesses
comments 0

post a comment


thing.java ASCII text
 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
import java.util.*;import java.util.regex.Pattern;import java.util.stream.*;import java.io.*;
// da spek sed "Your complete function may produce any amount of output, although the result should depend on text_so_far given some corpus."
// dis meks a infinte strem o'. do smth liek java thing.java "I like fish" <bible.txt | head -c 1000 o jst ctrl^C idk
class Thing{
public static void main(String... args){
final var corpus=new BufferedReader(new InputStreamReader(System.in)).lines().collect(Collectors.joining("\n"));
final var text_so_far=args[0];
final var n=3;
var next=new HashMap<String,ArrayList<String>>();
var p=Pattern.compile("\\w+");
var m=p.matcher(corpus);
var prevs=new ArrayList<String>();
prevs.add("");
while(m.find()){
var tok=m.group();
var ctx=prevs.get(prevs.size()-1);
for(var i=1;i<=Math.min(prevs.size()-1,n);i++){
var nexts=next.getOrDefault(ctx,new ArrayList<>());
nexts.add(tok);
next.put(ctx,nexts);
ctx=" "+prevs.get(prevs.size()-1-i)+" "+ctx;
}
prevs.add(tok);
}
var r=new Random();
m=p.matcher(text_so_far);
var ks=prevs;
prevs=new ArrayList<String>();
for (var i=0;i<n;i++)
prevs.add(ks.get(r.nextInt(ks.size())));
while (m.find())
prevs.add(m.group());
while(true){
var ctx = prevs.get(prevs.size()-1);
var choisez = new ArrayList<String>();
for(var j=1;j<=Math.min(prevs.size()-1,n);j++) {
choisez.addAll(next.getOrDefault(ctx, new ArrayList<>()));
ctx = prevs.get(prevs.size()-1-j)+" "+ctx;
}
if(choisez.isEmpty()){
for(var i=0;i<n;i++)
prevs.add(ks.get(r.nextInt(ks.size())));
}
var w = choisez.get(r.nextInt(choisez.size()));
System.out.print(" "+w);
prevs.add(w);
}
}
}

round #49

submitted at
0 likes

guesses
comments 0

post a comment


crisp.rkt ASCII text
  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
#lang racket
(define (proceed-parse in) (read-char in) (parse in))
(define (assert cond) (when (not cond) (raise "assertion failed")))
(define (expect in c) (assert (eqv? c (read-char in))))
(define (read-atom in)
  (let [(c (peek-char in))]
    (if (or (char-whitespace? c) (char=? #\) c)) '()
        (begin (read-char in) (cons c (read-atom in))))))
(define (skip-line in)
  (if (eqv? #\newline (read-char in)) (void) (skip-line in)))
(define (parse in)
  (let [(c (peek-char in))]
    (cond
      [(or (eof-object? c) (char=? #\) c)) '()]
      [(char=? #\# c) (begin (skip-line in) (parse in))]
      [(char-whitespace? c) (proceed-parse in)]
      [(char=? #\( c) (let [(r (proceed-parse in))]
                        (begin (expect in #\)) (cons r (parse in))))]
      [else (cons (let [(s (list->string (read-atom in)))]
                    (or (string->number s) (list 'name s)))
                  (parse in))])))
(define (fnify f)
  (lambda (args ctx) (f (eval-args args ctx))))
(define (thunk args ctx)
  (fnify (lambda (_) (last (eval-args args ctx)))))
(define (my-lambda args ctx)
  (letrec [(param (begin (assert (eqv? 'name (caar args))) (cadar args)))
           (body (cdr args))
           (f (lambda (xs)
                (if (null? xs) f
                    (let* [(new-ctx (hash-set ctx param (car xs)))
                           (res (last (eval-args body new-ctx)))]
                      (if (null? (cdr xs)) res
                          (res (cdr xs) ctx))))))]
    (fnify f)))
(define (my-quote args _) args)
(define (fnify-n n f)
  (letrec [(l (lambda (args ctx)     
                (if (null? args) l
                    (let [(arg (eval (car args) ctx))]
                      (if (= n 1)
                          (if (null? (cdr args))
                              (f arg)
                              ((f arg) (eval-args (cdr args) ctx)))
                          ((fnify-n (- n 1) (curry f arg)) (cdr args) ctx)))
                    )))] l))
(define my-t (fnify-n 2 (lambda (x y) x)))
(define my-f (fnify-n 2 (lambda (x y) y)))
(define (my-<= n m)
  (cond
    [(eq? n m) my-t]
    [(and (number? n) (number? m)) (if (<= n m) my-t my-f)]
    [(null? n) (if (pair? m) my-t my-f)]
    [(and (pair? n) (pair? m))
     (cond
       [(not (my-<= (car n) (car m))) my-f]
       [(not (my-<= (car m) (car n))) my-t]
       [else (my-<= (cdr n) (cdr m))])]
    [else my-f]))
(define (d args)
  (display args)
  (newline))
(define (my-macro margs mctx)
  (lambda (args ctx)
    (eval (last (eval-args margs (hash-set ctx "..." args))) ctx)))
(define predefs
  (hash
   ;; builtins (mostly inherited from racket)
   "d" (fnify d)
   "ib" (fnify (lambda (_) (char->integer (read-char))))
   "ob" (fnify-n 1 (lambda (c) (write-char (integer->char c))))
   "do" (fnify last)
   "car" (fnify-n 1 car)
   "cdr" (fnify-n 1 cdr)
   "cons" (fnify-n 2 cons)
   "list" (fnify identity)
   "-" (fnify-n 1 -)
   "+" (fnify-n 2 +)
   "*" (fnify-n 2 *)
   "<=" (fnify-n 2 my-<=)
   "t" my-t
   "f" my-f
   ;; special forms
   "\\\\" thunk
   "\\" my-lambda
   "'" my-quote
   "$" my-macro)) 
(define (eval-args args ctx)
  (map (lambda (arg) (eval arg ctx)) args))
(define (eval expr ctx)
  (if (pair? expr)
      (let [(f (car expr)) (args (cdr expr))]
        (if (eqv? f 'name) (hash-ref ctx (car args))
            ((eval f ctx) args ctx)))
      expr))
(define (get-file-name)
  (command-line
   #:program "crisp"
   #:args (filename)
   filename))
(define (maybe-display v)
  (when (not (eq? v (void))) (display v)))
(maybe-display (eval
                (cons (list 'name "do")
                      (call-with-input-file (get-file-name) parse))
                predefs))
stuff.crisp ASCII text
 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
# she bangs
# (all lines starting with # actually) are ignored

# run this using "racket crisp.rkt stuff.crisp"

# d is a debug print for a list of arguments
(d 1 2 3)
# (ib) reads a byte, (ob b) writes a byte
(ob 65)
# (d (ib))
# basic math works; - is unary; +, * are strictly binary, fold them yourself
(d (+ (+ (* 4 5) (* 2 3)) (- 1)))
# lambdas (single parameter only)
(d ((\ x (\ y (+ x y))) 1 2))
# you can quote stuff, albeit unusually
(d (' + 1 2))
# automatic currying
(d (+ 1))
(d 42)
(d ((+ 1) 2))
(d 69)
# "thunks" (paramless lambdas)
(d ((\\ (+ 1 2))))
# we've got cons, car, cdr, list
(d (cons 1 2))
(d (car (cons 1 2)))
(d (cdr (cons 1 2)))
(d (')) # empty list
(d (cons 1 ('))) # list with one elem
(d (list 1 2 3))
# bools are just functions
(d (t 1 0))
(d (f 1 0))
(d (<= 1 2))
(d ((<= 1 2) 1 0))
# <= is special: it compares lexicographically and can be used to test for nil
(d ((<= (') (')) 1 0))
(d ((<= (') (' 1 2)) 1 0))
(d ((<= (' 1 2) (')) 1 0))
(d ((<= (' 1 2) (' 1 2)) 1 0))
# this is enough for a simple recursive fibonacci already
(d ((\ f (f f 10))
	(\ f (\ n (((<= n 1)
		(\\ n)
		(\\ (+ (f f (+ n (- 1))) (f f (+ n (- 2)))))))))))
# multiple things are awkward here:
# - nesting of lambdas
# - no let(rec)
# - thunks
# it's time to introduce "macros". macros are like functions,
# except they operate on the raw sexprs rather than the evaluated sexprs.
# $ is like \, but the parameter is always called ... and is implicit.
# "macro" "expansion" happens at runtime.
(d (($ (car ...)) 1 2 3))
(($ (d (list (car (' d)) ...)) (cons (car (' d)) ...)) 1 2 3)
(($ ...
	(list (list
		(car ...)
		(list (car (' \\)) (car (cdr ...)))
		(list (car (' \\)) (car (cdr (cdr ...)))))))
	t (d 1) (d 0))
# macros to solve the other problems are left as exercises to the reader

round #48

submitted at
0 likes

guesses
comments 0

post a comment


entry.ts ASCII text
1
export function entry(h:string,n:string):[number,number]|null{for(let g=1;n.length*g<=h.length;++g){const m=RegExp(n.split('').map(c=>(/[.*+?^${}()|[\]\\]/.test(c)?'\\':'')+c).join(`.{${g-1}}`)).exec(h);if(m)return[m.index,--g]}return null}// dis  onli wroks on WIDE CHARS because YES

round #47

submitted at
0 likes

guesses
comments 0

post a comment


LIS.groovy Unicode text, UTF-8 text
  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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
/*
    Efficient longest increasing subsequence finding.
    Written for Code Guessing Round 47 (https://cg.esolangs.gay/47/).
    Input: Sequence of integers delimited by spacing, ex.: 4 5 2 6 3 5
    Output: Subsequence in the same format, ex.: 4 5 6

    Code may contain minor inconsistencies;
    the author was initially trying to conceal their style (this was for code guessing, after all)
    but then effectively backpedaled on that too.

    The author recommends using at least a gigabyte of IDE bloat to have a half-decent Groovy experience.
 */

class BigIntTree implements Iterable<Iterable<Integer>> {
    class Node {
        List<Integer> is
        Node left, right
    }
    Node root

    void set(BigInteger k, int i) {
        Node node = root ?= new Node()
        for (int j = k.bitLength() - 1; j > -1; --j)
            node = k.testBit(j) ? (node.right ?= new Node()) : (node.left ?= new Node())
        (node.is ?= []).add(i)
    }
    // Breadth-first traversal of the tree gives lets us traverse the keys in sorted order
    // in linear time in the total number of digits in the input
    @Override
    Iterator<Iterable<Integer>> iterator() {
        List<Node> lvl = root == null ? [] : [root]
        int i = 0
        return new Iterator<Iterable<Integer>>() {
            @Override
            boolean hasNext() {
                return !lvl.isEmpty()
            }

            @Override
            Iterable<Integer> next() {
                List<Integer> vs
                do {
                    vs = lvl.get(i).is
                    if (++i >= lvl.size()) {
                        List<Node> nlvl = []
                        for (nd in lvl) {
                            if (nd.left != null) nlvl.add(nd.left)
                            if (nd.right != null) nlvl.add(nd.right)
                        }
                        lvl = nlvl
                        i = 0
                    }
                } while (vs == null)
                return vs
            }
        }
    }
}

class Subseq {
    class Node {
        int i
        Node prev

        Node(int i, Node prev) {
            this.i = i
            this.prev = prev
        }
    }
    int len
    Node root
    static Subseq EMPTY = new Subseq()

    Subseq() {}

    Subseq(Subseq p, int i) {
        len = (p == null ? 0 : p.len) + 1
        root = new Node(i, p.root)
    }

    BigInteger[] apply(BigInteger[] seq) {
        def res = new BigInteger[len]
        def node = this.root
        for (def i = len - 1; i > -1; i--) {
            res[i] = seq[node.i]
            node = node.prev
        }
        return res
    }
}

class SegmentTree {
    class Node {
        Subseq subseq = Subseq.EMPTY
        Node left, right

        Node(int n) {
            assert (n > 0)
            if (n == 1) return
            def mid = n >> 1
            left = new Node(mid)
            right = new Node(n - mid)
        }
        // Get best subseq s with max(s) <= n
        Subseq get(int w, int n) {
            assert n <= w
            if (w == n)
                return subseq
            def mid = w >> 1
            if (n <= mid)
                return left.get(mid, n)
            def ssl = left.subseq
            def ssr = right.get(w - mid, n - mid)
            return (ssr.len > ssl.len) ? ssr : ssl
        }
        // Set new best subseq s for max(s) <= n
        void set(int w, int n, Subseq ss) {
            assert n <= w
            if (w == n) {
                if (ss.len > subseq.len)
                    subseq = ss
                return
            }
            if (ss.len > subseq.len)
                subseq = ss
            def mid = w >> 1
            if (n <= mid) {
                left.set(mid, n, ss)
                return
            }
            // Note: We can't install this for left, since left has a stricter bound
            right.set(w - mid, n - mid, ss)
        }
    }
    Node root
    int n

    SegmentTree(int n) {
        root = new Node(this.n = n)
    }

    Subseq get(int n) {
        return root.get(this.n, n)
    }

    Subseq set(int n, Subseq ss) {
        return root.set(this.n, n, ss)
    }
}

static BigInteger[] solve(BigInteger[] seq) {
    if (seq.length == 0) return new BigInteger[0]
    def t = new BigIntTree()
    for (int i = 0; i < seq.length; ++i)
        t.set(seq[i], i)
    // Remove gaps in the ordering.
    // This is important for achieving good time complexity.
    int o = 0
    def ordinals = new int[seq.length]
    for (is in t) {
        ++o
        for (i in is)
            ordinals[i] = o
    }
    // Do the "greedy" / "dynamic programming" solving
    // using a segment tree of best subsequences for upper bounds of the last element.
    def st = new SegmentTree(o)
    for (int i = 0; i < ordinals.length; ++i) {
        def n = ordinals[i]
        def ss = n == 1 ? Subseq.EMPTY : st.get(n - 1)
        st.set(n, new Subseq(ss, i))
    }
    return st.get(o).apply(seq)
}

static BigInteger[] read() {
    def sc = new Scanner(System.in)
    List<BigInteger> s = []
    while (sc.hasNext())
        s << new BigInteger(sc.next())
    return s.toArray(new BigInteger[s.size()])
}

static void write(BigInteger[] subseq) {
    print(subseq[0])
    for (int i = 1; i < subseq.length; i++) {
        print(" ")
        print(subseq[i])
    }
    println()
}

static void main(String[] args) {
    write(solve(read()))
}

/*
    Runtime analysis:

    Let the input be a sequence of n numbers encoded in some base
    (say, binary, or decimal, with at least one digit per number), delimited by some delimiter.
    Then the length of the input is O(m), where m is the total count of digits in the input (in any fixed base).
    Constructing the prefix tree to sort the numbers is O(m) then,
    as is traversing the prefix tree in level-order (breadth-first, left to right);
    replacing numbers with their ordinals is O(m) as well
    (incrementing the ordinal o would be amortized constant time even if o were a bigint).

    For each distinct ordinal, there needs to be a distinct number in the input.
    To encode k distinct numbers, you need Θ(log(k)) bits (on average) for each number.
    This implies an input length of Θ(n log(k)) (in bits, bytes, characters, whatever, as long as it's fixed size).
    (This also imposes an upper bound of O(log n) on the length of each ordinal in bits,
    which is why this implementation elects to represent ordinals as "just integers":
    larger sequences couldn't be represented using Java data structures anyways.)

    The next step maintains a "segment tree" which maps maxima to longest subsequences
    using only elements encountered so far (a prefix of the sequence).
    Since the largest value is the largest ordinal, this segment tree has depth log(k).
    For each element in the sequence, one get and set operation are issued.
    Since these operations can both easily be seen (*) to be O(log(k)),
    we obtain O(n log(k)), which is true linear time in the input size (in bits, not in integer registers).

    (*) For a simplified analysis, assume a perfect binary segment tree (that is, k is a power of two).
    We presume big integers (which this implementation does not use for aforementioned reasons,
    but which are nevertheless relevant for runtime analysis).
    Then the comparison `w == n` would not be constant time,
    but for each bit it has to compare, it saves having to dive a layer deeper, so it is fine.
    Since we split perfectly in the middle, `n <= mid` would only have to look at the most significant bit.
    `w - mid` / `n - mid` effectively just removes that most significant bit, thus is also constant time.

    A proof of correctness will be supplied when the author finds the time and motivation.
    For now, you will have to take the author's "trust me bro" for it.

    Exercises left to the reader:

    * Test this thoroughly to convince yourself of the correctness.
    * Constant-factor optimization of the binary tree / prefix tree:
      "Compress" long paths of multiple bits (trie -> patricia tree)
    * Constant-factor optimization of the segment tree:
      Store it in an array, avoids many heap allocations, improves cache locality.
    * Rewrite this in a "better" programming language.
 */

round #46

submitted at
0 likes

guesses
comments 0

post a comment


README.rst ASCII text
 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
==========================
CG 46: Find Candidate Keys
==========================

Input
=====

**Tab-Separated Values** (TSV) on standard input as Olive intended.
The escape sequences ``\t``, ``\n``, ``\r`` and ``\\`` are supported.

Example
-------

Here is the example table in TSV format::

	contest	date held	winner	winner's second name
	dog fight	oct 17 2000	discarding sabot	sabot
	cat-off	jul 01 2001	palm tree oil	tree
	rat duel	oct 05 2001	cart of iron	of
	rat duel	mar 21 2006	cart of iron	of
	shark race	mar 21 2006	linguist	NULL

Output
======

For consistency, the output is also **pseudo-TSV** that is written to standard output.

Edge cases:

* The empty set of columns is represented by an empty line.
* The empty set of candidate keys is represented by no lines being printed.

Example
-------

Here is the output for the example table::

	date held	winner's second name
	date held	winner
	contest	date held
find_candidate_keys.clj Unicode text, UTF-8 text
 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
;; © 2042 Kim Apr
(ns find_candidate_keys
  (:require [clojure.string :as str]
            [clojure.set :as set]))
(def escs {"\\t" "\t" "\\n" "\n" "\\r" "\r" "\\\\" "\\"})
(defn rd-row [line]
  (map
   (fn [s] (str/replace s #"\\." (fn [c] (escs c c))))
   (str/split line #"\t")))
(defn rd-tsv []
  (let [ln (read-line)]
    (if (nil? ln) nil
           (cons (rd-row ln) (rd-tsv)))))
(defn transp [rws]
  (let [rst-rws (rest rws)]
    (if (empty? rst-rws)
         (map list (first rws))
        (map cons (first rws)
             (transp rst-rws)))))
(defn ntrvl [col]
  (filter
   ;; clj-kondo WILL lie to you!!!
   (fn [cl] (not (empty? (rest cl))))
   col))
(defn cl-add [cl i el] (assoc cl el (conj (cl el #{}) i)))
(defn eq-cls [col]
   (vals
    (reduce
     (fn [cl pair]
       (let [[i el] pair] (cl-add cl i el)))
      {}
     (map-indexed vector col))))
(defn mapify-eq-cls [cls]
  (reduce
   (fn [map cl]
     (reduce
      (fn [map i] (assoc map i cl))
      map
      cl))
   {}
   cls))
(defn merge-eq-cls [cls1 cls2]
  (let [m2 (mapify-eq-cls cls2)]
    (reduce
     (fn [cls cl1]
       (reduce
        (fn [cls cl2] (cons (set/intersection cl1 cl2) cls))
        cls
        (set (remove nil? (map m2 cl1)))))
     '()
     cls1)))
(defn map-subseq [f seq]
  (if (empty? seq) '()
      (cons (f seq) (map-subseq f (rest seq)))))
(defn cands [keys cnds]
  (if
   (empty? cnds) keys
   (reduce
    (fn [keys cnd]
      (if (empty? (cnd :eq))
        (cons (rest (reverse (map (comp first first) (cnd :cols)))) keys)
        (cands
         keys
         (remove nil? (map-subseq
          (fn [col]
            (let [mrgd (ntrvl (merge-eq-cls
                               (cnd :eq)
                               (ntrvl (eq-cls (rest (first col))))))]
              (if (= (cnd :eq) mrgd) nil
                  {:cols (cons col (cnd :cols)) :eq mrgd})))
          (rest (first (cnd :cols))))))))
    keys
    cnds)))
(defn cnd-empty [cols]
  (list {:cols (list (cons '() cols))
         :eq (ntrvl (list (set (range (count (rest (first cols)))))))}))
(def unescs (set/map-invert escs))
(defn wr-row [cnd]
  (println
   (str/join
    "\t"
    (map
     ;; It is with great disgust that I have to inform you that `.` in Java
     ;; matches "any character (may or may not match line terminators)"
     (fn [s] (str/replace s #".|\r|\n" (fn [c] (unescs c c)))) cnd))))
(defn wr-tsv [cnds]
  (run! wr-row cnds))
(wr-tsv (cands '() (cnd-empty (transp (rd-tsv)))))

round #45

submitted at
0 likes

guesses
comments 0

post a comment


bot.nim ASCII text
  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
145
146
147
148
149
import std/bitops
import std/strutils
import std/options

type
    X = range[0'u8..6'u8]
    Y = range[0'u8..5'u8]
    Stack = set[Y]
    Mask = array[X, Stack]
    Board = tuple[ours: Mask, theirs: Mask]

type RowBitset = range[0'u8..127'u8]

proc winRowUtil (row: RowBitset): bool =
    (row and 0b0001111) == 0b0001111 or
    (row and 0b0011110) == 0b0011110 or
    (row and 0b0111100) == 0b0111100 or
    (row and 0b1111000) == 0b1111000

var winRows: set[RowBitset]
for i in RowBitset(0)..127'u8:
    if winRowUtil(i):
        winRows.incl i

proc winRow (row: RowBitset): bool =
    row in winRows

proc row (m: Mask, y: Y): RowBitset =
    for x in X(0)..6:
        if y in m[x]:
            result = result or (1'u8 shl x)

proc ascDiag (m: Mask, x: X, y: Y): RowBitset =
    var j = 0'u8
    for i in -int8(x.min(y))..int8((6-x).min(5-y)):
        if Y(int8(y) + i) in m[X(int8(x) + i)]:
            result = result or (1'u8 shl j)
        j += 1

proc descDiag (m: Mask, x: X, y: Y): RowBitset =
    var j = 0'u8
    for i in -int8((6-x).min(y))..int8(x.min(5-y)):
        if Y(int8(y) + i) in m[X(int8(x) - i)]:
            result = result or (1'u8 shl j)
        j += 1

proc winMove (m: Mask, x: X, y: Y): bool =
    winRow(cast[RowBitset](m[x])) or
    winRow(m.row(y)) or
    winRow(m.descDiag(x, y)) or
    winRow(m.ascDiag(x, y))

proc top (board: Board, x: X): Option[Y] =
    let used = cast[uint8](board.ours[x] + board.theirs[x])
    if used == 0:
        return Y(0).some
    let y = 8 - used.countLeadingZeroBits
    if y > 5:
        return Y.none
    return Y(y).some

#[
import std/unittest
suite "bot":
    test "winRow":
        check(winRow 0b1111000)
        check(winRow 0b0111100)
        check(winRow 0b0011110)
        check(winRow 0b0001111)
        check(not winRow 0b0001101)
    let m: Mask = [
        {1, 2, 3},
        {0, 3},
        {1, 2},
        {0, 1},
        {0, 4},
        {3, 4, 5},
        {1, 2, 3},
    ]
    test "row":
        check(m.row(0) == 0b0011010)
        check(m.row(1) == 0b1001101)
    test "ascDiag":
        check(m.ascDiag(1, 1) == 0b110100)
    test "descDiag":
        check(m.descDiag(1, 1) == 0b100)
    test "winMove":
        let m: Mask = [{1, 2, 3, 4}, {}, {}, {}, {}, {}, {}]
        check(m.winMove(0, 4))
    test "top":
        check((ours: m, theirs: m).top(5) == none(Y))
        check((ours: m, theirs: m).top(1) == some(Y(4)))
]#

proc applyMove (board: var Board, x: X, ours: bool) =
    let y = board.top(x).get
    if ours:
        board.ours[x].incl y
    else:
        board.theirs[x].incl y

proc maximize (board: Board, depth: uint8): tuple[score: float, move: X] =
    if depth > 7:
        return
    result.score = -1
    var foundValidMove = false
    for x in X(0)..6:
        let top = board.top(x)
        if top.isNone:
            continue
        let y = top.unsafeGet
        foundValidMove = true
        # Pick a valid move, even if it may seem futile.
        if result.score == -1:
            result.move = x
        var ours = board.ours
        ours[x].incl y
        if ours.winMove(x, y):
            return (score: 1, move: x)
        let min = -(ours: board.theirs, theirs: ours).maximize(depth + 1).score
        # Indirect win forcable?
        if min == 1:
            return (score: 1, move: x)
        if min > result.score:
            result.score = min
            result.move = x
    # Returns an invalid move value (0) but meh
    if not foundValidMove:
        result.score = 0
        

var board: Board

proc makeMove () =
    let move = board.maximize(0).move
    board.applyMove(move, true)
    echo $(move + 1)

let line = stdin.readLine
if line == "f":
    makeMove()
else:
    assert line == "s"

while true:
    let move = stdin.readLine.parseUInt()
    assert move >= 1 and move <= 7
    board.applyMove(X(move - 1), false)
    makeMove()
client.nim ASCII text
 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
import os
import osproc
import std/strutils
import std/streams

type
    Spot = enum Free, Ours, Theirs
    Stack = array[6, Spot]
    Board = array[7, Stack]

var board: Board
var winner: Spot = Free

proc printBoard =
    for row in countdown(5, 0):
        for col in 0..6:
            const spotChar: array[Spot, char] = ['.', 'O', 'X']
            stdout.write spotChar[board[col][row]]
        stdout.write '\n'
    stdout.flushFile()

proc invalidMove (move: uint): bool =
    move < 1 or move > 7 or board[move - 1][^1] != Free

proc inBounds (x, y: int): bool =
    x >= 0 and x < 7 and y >= 0 and y < 6

proc countDir(x, y: uint, dx, dy: int): uint =
    var count: uint = 0
    var x = int(x)
    var y = int(y)
    let expected = board[x][y]
    while true:
        x += dx
        y += dy
        if not inBounds(x, y) or board[x][y] != expected:
            break
        count += 1
    return count

proc checkWinDir (x, y: uint, dx, dy: int): bool =
    return countDir(x, y, -dx, -dy) + 1 + countDir(x, y, dx, dy) >= 4

proc checkWin (x, y: uint): bool =
    checkWinDir(x, y, 0, 1) or checkWinDir(x, y, 1, 0) or checkWinDir(x, y, 1, 1)

var moves = 0
proc makeMove (move: uint, player: Spot) =
    assert player != Free
    for y, spot in board[move]:
        if spot == Free:
            board[move][y] = player
            if checkWin(move, uint(y)):
                winner = player
            moves += 1
            break

var bot = startProcess(paramStr(1), options = {})
var botIn = bot.inputStream
var botOut = bot.outputStream
proc sendCommand (command: string) =
    botIn.writeLine command
    botIn.flush
sendCommand "s" # hoomans go first!

while true:
    printBoard()
    if winner != Free or moves == 6*7:
        break
    block:
        echo "Make a move:"
        let move = stdin.readLine.parseUInt
        if invalidMove(move):
            echo "Invalid move"
            continue
        makeMove(move - 1, Ours)
        sendCommand $move
    if winner == Free:
        var line: string
        assert botOut.readLine line
        let move = line.parseUInt
        if invalidMove(move):
            echo "Invalid move from bot"
            break # can't resume with a broken bot
        makeMove(move - 1, Theirs)
bot.terminate
bot.close

const outcome: array[Spot, string] = ["Draw", "You win!", "They win!"]
echo outcome[winner]
help.txt ASCII text
1
2
Compile bot (or client): nim compile -d:release bot
Use client: ./client bot

round #44

submitted at
0 likes

guesses
comments 0

post a comment


countdown.py ASCII text
 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
#programmer time (MY TIME) is worth MOAR than cpu time!!!!!!
import argparse
from collections import Counter
from itertools import permutations,product
class Param:
	n=1
	def eval(it): return next(it)
class Expr:
	def __init__(self,l,op,r):
		self.l,self.op,self.r,self.n=l,op,r,l.n+r.n
	def eval(self,it):
		l,r=self.l.eval(it),self.r.eval(it)
		match self.op:
			case '+': return l+r
			case '*': return l*r
			case '-': return float('nan') if l<r else l-r
			case '/': return float('nan') if not r or l%r else l/r
class Bag:
	def __init__(self,s):
		self.ops=Counter()
		self.digits=Counter()
		for c in s:
			if c in '+-*/':
				self.ops.update((c,))
			elif (d:=ord(c)-ord('0')) in range(10):
				self.digits.update((d,))
			else:
				raise ValueError('invalid string')
	def _exprs(ops):
		yield Param
		if not any(ops.values()): return
		nz=[o for o in ops if ops[o]]
		if sum(1 for _ in nz)==1 and (op:=nz[0]) in '+*':
			e=Param
			for _ in range(ops[op]):
				yield (e:=Expr(e,op,Param))
			return
		for op in ops:
			ops[op]-=1
			for splt in product(*(range(ops[o]+1) for o in ops)):
				for l,r in product(Bag._exprs({o:n for n,o in zip(splt,ops)}),Bag._exprs({o:ops[o]-n for n,o in zip(splt,ops)})):
					yield Expr(l,op,r)
			ops[op]+=1
	def exprs(self): return Bag._exprs(self.ops)
	def params(self,n): return permutations(self.digits,r=n)
	def solve(self,num): return min((expr.eval(iter(params)) for expr in self.exprs() for params in self.params(expr.n)),key=lambda x:abs(num-x))
if __name__=='__main__':
	parser=argparse.ArgumentParser()
	parser.add_argument('bag')
	parser.add_argument('num')
	args=parser.parse_args()
	print(Bag(args.bag).solve(int(args.num)))
ink.jpg JPEG image data, JFIF standard 1.01, resolution (DPI), density 300x300, segment length 16, progressive, precision 8, 4160x3120, components 3

round #43

submitted at
0 likes

guesses
comments 0

post a comment


dir spirou
main.lua Unicode text, UTF-8 text
 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
-- (c) 2021 🥺🥺🥺
-- this code was manualy cursed to meet the lowest standards ✅✅✅
-- "Inter-token spacing is the root of all evil." - Mahatma Gandhi
local splurped={}
do
	local ts={_G}
	local s={}
	repeat
		local ns={}
		local fr={}
		for _,t in pairs(ts) do
			s[t]=1
			for k,v in pairs(t) do
				if fr[k]==nil then
					fr[k]=v
				else
					fr[k]=fr
				end
				if type(v)=="table" and not s[v] then
					ns[#ns+1]=v
				end
			end
		end
		for k,v in pairs(fr) do
			if splurped[k]==nil and v~=fr then
				splurped[k]=v
			end
		end
		ts=ns
	until#ts==0
end
setfenv(1,setmetatable({},{__index=splurped}))
local function mapva(f,...)
	if select("#",...)==0 then return end
	return f((...)),mapva(f,select(2,...))
end
p,x,pts,stp=400,0,{},{} -- 400² is the HOLY RESOLUTION - DO NOT TOUCH!
function love.load(args)
	R,r,d=mapva(tonumber,unpack(args))
	m=p/(R-r+abs(d))*0.5*0.75
	R,r,d=R*m,r*m,d*m
	mdt = min(abs(1/(R-r)),abs(r/(R-r)/d))/10
	setTitle(((r<0)and"epi"or"hypo").."trochoid")
	setMode(p,p)
end
function love.update(fdt)
	n=ceil(fdt/mdt)
	dt=fdt/n
	for i=1,n do
		x=x-dt
		y=-x*(R-r)/r
		cx,cy=p/2,p/2
		rx,ry=cx+(R-r)*cos(x),cy+(R-r)*sin(x)
		px,py=floor(rx-d*cos(y)),floor(ry-d*sin(y))
		h=py*p+px
		if not stp[h] then
			stp[h]=1
			insert(pts,{px,py})
		end
	end
end
function love.draw()
	setColor(0,1,0,1)
	ellipse("line",cx,cy,R,R)
	ellipse("line",rx,ry,abs(r),abs(r))
	line(rx,ry,px,py)
	setColor(1,0,0,1)
	points(pts)
end
uhh.txt ASCII text
1
2
3
so uh i maded some sussy hax but they shoud work on
LOVE 11.3 (Mysterious Mysteries)
oh uh also run is "love . R r d" in foldr

round #42

submitted at
0 likes

guesses
comments 0

post a comment


dir 42
dir src
main.rs ASCII text
  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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
// Simple 2048 game for the terminal

use crossterm::{
    self, cursor,
    event::{read, Event, KeyCode},
    execute, queue, terminal,
};
use rand::Rng;
use std::{
    fmt,
    io::{self, Stdout, Write},
};

#[derive(Copy, Clone, PartialEq)]
enum Move {
    Left,
    Right,
    Up,
    Down,
}

impl TryFrom<KeyCode> for Move {
    type Error = ();
    fn try_from(value: KeyCode) -> Result<Self, Self::Error> {
        match value {
            KeyCode::Left | KeyCode::Char('a') => Ok(Move::Left),
            KeyCode::Right | KeyCode::Char('d') => Ok(Move::Right),
            KeyCode::Up | KeyCode::Char('w') => Ok(Move::Up),
            KeyCode::Down | KeyCode::Char('s') => Ok(Move::Down),
            _ => Err(()),
        }
    }
}

#[derive(PartialEq, Clone)]
struct Board {
    tiles: [[u8; 4]; 4],
}

impl Board {
    fn random_tile() -> u8 {
        if rand::thread_rng().gen_range(1..=10) == 10 {
            2
        } else {
            1
        }
    }
    fn place_random_tile(&mut self) {
        loop {
            let y = rand::thread_rng().gen_range(0..4);
            let x = rand::thread_rng().gen_range(0..4);
            if self.tiles[y][x] == 0 {
                self.tiles[y][x] = Self::random_tile();
                break;
            }
        }
    }
    fn init() -> Self {
        let mut this = Self { tiles: [[0; 4]; 4] };
        this.place_random_tile();
        this.place_random_tile();
        this
    }
    fn transpose(&mut self) {
        let tiles = &mut self.tiles;
        for y in 0..tiles.len() {
            for x in 0..y {
                (tiles[y][x], tiles[x][y]) = (tiles[x][y], tiles[y][x]);
            }
        }
    }
    fn reverse_rows(&mut self) {
        for row in self.tiles.as_mut() {
            row.reverse()
        }
    }
    fn move_left(&mut self) {
        for row in self.tiles.as_mut() {
            for x in 1..4 {
                let mut nx = x;
                while nx > 0 && row[nx - 1] == 0 {
                    nx -= 1;
                }
                if nx > 0 && row[nx - 1] == row[x] {
                    row[nx - 1] += 1;
                    row[x] = 0;
                } else if nx < x {
                    row[nx] = row[x];
                    row[x] = 0;
                }
            }
        }
    }
    fn make_move(&mut self, mov: Move) {
        match mov {
            Move::Left => self.move_left(),
            Move::Right => {
                self.reverse_rows();
                self.move_left();
                self.reverse_rows();
            }
            Move::Up => {
                self.transpose();
                self.move_left();
                self.transpose();
            }
            Move::Down => {
                self.transpose();
                self.reverse_rows();
                self.move_left();
                self.reverse_rows();
                self.transpose();
            }
        }
    }
    fn valid_moves(&self) -> impl Iterator<Item = &Move> {
        [Move::Left, Move::Right, Move::Up, Move::Down]
            .iter()
            .filter(|&&mov| {
                let mut clone = self.clone();
                clone.make_move(mov);
                clone != *self
            })
    }
    fn won(&self) -> bool {
        const TILE_2048: u8 = 11;
        self.tiles.iter().flatten().any(|&t| t == TILE_2048)
    }
}

// TODO (...) the hardcoded carriage returns for raw terminal mode feel dirty.
impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let sep: String = "+----".repeat(4) + "+\r\n";
        for row in self.tiles {
            f.write_str(&sep)?;
            f.write_str(
                &(String::from("|")
                    + &row
                        .map(|tile| {
                            if tile == 0 {
                                "    ".into()
                            } else {
                                format!("{:^4}", 1 << tile)
                            }
                        })
                        .join("|")
                    + "|\r\n"),
            )?;
        }
        f.write_str(&sep)?;
        Ok(())
    }
}

struct RawTerminal {
    stdout: Stdout,
}
impl RawTerminal {
    fn init() -> Result<Self, io::Error> {
        terminal::enable_raw_mode()?;
        let mut stdout = io::stdout();
        execute!(
            stdout,
            terminal::EnterAlternateScreen,
            crossterm::cursor::Hide
        )?;
        Ok(Self { stdout })
    }
    fn queue_reset(&mut self) -> Result<(), io::Error> {
        queue!(
            self.stdout,
            terminal::Clear(terminal::ClearType::FromCursorUp),
            cursor::MoveTo(0, 0)
        )
    }
    fn flush(&mut self) -> Result<(), io::Error> {
        self.stdout.flush()
    }
}
impl Drop for RawTerminal {
    fn drop(&mut self) {
        execute!(
            self.stdout,
            crossterm::cursor::Show,
            terminal::LeaveAlternateScreen
        )
        .unwrap();
        terminal::disable_raw_mode().unwrap();
    }
}

enum GameOutcome {
    Win,
    Loss,
    Quit,
}

fn play() -> Result<GameOutcome, io::Error> {
    let mut terminal = RawTerminal::init()?;
    let mut board = Board::init();
    'game: loop {
        terminal.queue_reset()?;
        print!("{board}");
        print!("arrow keys or WASD to play, q to quit");
        terminal.flush()?;
        if board.won() {
            return Ok(GameOutcome::Win);
        }
        let valid_moves: Vec<&Move> = board.valid_moves().collect();
        if valid_moves.is_empty() {
            return Ok(GameOutcome::Loss);
        }
        let mov = loop {
            match read()? {
                Event::Key(event) => {
                    if event.code == KeyCode::Char('q') {
                        return Ok(GameOutcome::Quit);
                    }
                    if let Ok(mov) = Move::try_from(event.code) {
                        if valid_moves.contains(&&mov) {
                            break mov;
                        }
                    }
                }
                Event::Resize(_, _) => {
                    continue 'game;
                }
                _ => (),
            }
        };
        board.make_move(mov);
        board.place_random_tile();
    }
}

fn main() {
    let outcome = play().unwrap();
    println!(
        "{}",
        match outcome {
            GameOutcome::Win => "You win!",
            GameOutcome::Loss => "You lose!",
            GameOutcome::Quit => "quit",
        }
    );
}
Cargo.lock ASCII text
  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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
# This file is automatically @generated by Cargo.
# It is not intended for manual editing.
version = 3

[[package]]
name = "_2048"
version = "0.1.0"
dependencies = [
 "crossterm",
 "rand",
]

[[package]]
name = "autocfg"
version = "1.1.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa"

[[package]]
name = "bitflags"
version = "1.3.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"

[[package]]
name = "bitflags"
version = "2.4.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "b4682ae6287fcf752ecaabbfcc7b6f9b72aa33933dc23a554d853aea8eea8635"

[[package]]
name = "cfg-if"
version = "1.0.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"

[[package]]
name = "crossterm"
version = "0.27.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f476fe445d41c9e991fd075