previndexinfonext

code guessing, round #59 (completed)

started at ; stage 2 at ; ended at

specification

the challenge is to interpret probablistic PricK. submissions may be written in any language.

PricK is a total stack-based language created by our very own olus2000. Probabilistic PricK is a variant of PricK created by me for this challenge, the details of which I will describe below.

like normal PricK, there is a stack and random access memory available. the only data type is unbounded non-negative integers, which both the stack and the memory store and the memory is indexed by. reading uninitialized memory or popping from the stack when it is empty both yield 0; it is equivalent to say that the memory and stack are initialized with an infinite number of 0s.

like compact PricK, words are tokenized by character instead of being whitespace-delimited, so ++ is the word + followed by +. also, there are no definitions: the only valid words are the built-in ones. the behaviour when there are unrecognized tokens is unspecified; you may ignore them or emit a diagnostic.

the words in the language are as follows:

there is also syntax for loops: a loop [cond|body], where cond and body are arbitrary code, has the following semantics:

  1. a number is popped from the stack and set as the loop's bound, which persists until the loop ends
  2. cond is executed
  3. a number is popped. if this number is 0, or the loop's bound is 0, the loop ends and the following steps are not performed.
  4. body is executed
  5. the loop's bound is decremented and execution repeats at step 2.

the formal grammar for the language is as follows:

program = ε | inst program
inst = '#' | '+' | '@' | '!' | '?' | '[' program '|' program ']'

for PricK programs inlined such that they contain no definitions and converted to compact syntax, the behaviour of PricK and Probabilistic PricK is identical. the difference is the ? operator, which makes the language non-deterministic. your goal in this challenge is to interpret Probabilistic PricK and yield the program's most likely result.

for instance, take the program #+++++?+ #+++++?+ [#+|+], which is equivalent to rolling two 6-sided dice and adding them together. the most likely result is 7, so this is what your program should output.

randomness can be put in many places and have a variety of distributions!

your challenge, given a valid PricK program, is to identify what its most probable output is. if there are multiple answers with the maximum probability, you may pick any one of them. as any language is allowed, there is no fixed API.

some tools are provided to help you on your quest. compiler.py will translate programs written in ordinary PricK to the simplified syntax used in Probabilistic PricK, with no definitions or spaces between tokens. it also includes a prelude with the convenience functions defined on the wiki. the compiler should make it easier to make Probabilistic PricK programs for you to test on. entry.py is a reference implementation of the program you can use to test against or to reference.

while the reference implementation gives exact answers, it is acceptable to give approximate answers to this challenge. for instance, you may decide that probability theory is too hard for you and compute the result via simply running the program multiple times and taking the most common answer.

note that PricK has no notion of outputting, and there are different ways you could interpret a program's "output", which can give you different probability distributions. for this challenge, it is acceptable to do one of the following:

to see the difference between these approaches, try compiling 2 ? -- 1 [ dup 1 != | 5 ? swap ] and running it with and without -o 1 in the reference implementation. the -F flag might make it clearer what's happening.

note

this round was played with a special rule in which moshikoi (aka Indigo) was chosen to be given 4 bonus points in return for not being able to read the specification while writing his entry. instead, he was allowed to read the other player's entries while writing his entry, so he could guess what the challenge was.

results

  1. 👑 LyricLy +5 ~0 -0 = 5
    1. essaie
    2. olus2000
    3. kimapr (was Dolphy)
    4. Dolphy (was kimapr)
    5. moshikoi
    6. kotnen
    7. taswelll
  2. Dolphy +5 ~0 -0 = 5
    1. essaie
    2. olus2000
    3. kimapr
    4. moshikoi
    5. taswelll (was LyricLy)
    6. kotnen
    7. LyricLy (was taswelll)
  3. kimapr +4 ~0 -1 = 3
    1. essaie
    2. olus2000
    3. LyricLy (was Dolphy)
    4. moshikoi
    5. taswelll (was LyricLy)
    6. kotnen
    7. Dolphy (was taswelll)
  4. moshikoi +3 ~4 -6 = 1
    1. essaie
    2. olus2000
    3. kimapr (was Dolphy)
    4. LyricLy (was kimapr)
    5. taswelll (was LyricLy)
    6. kotnen
    7. Dolphy (was taswelll)
  5. taswelll +2 ~0 -2 = 0
    1. Dolphy (was essaie)
    2. olus2000
    3. kimapr (was Dolphy)
    4. LyricLy (was kimapr)
    5. moshikoi
    6. kotnen (was LyricLy)
    7. essaie (was kotnen)
  6. essaie +3 ~0 -5 = -2
    1. olus2000
    2. LyricLy (was Dolphy)
    3. Dolphy (was kimapr)
    4. kimapr (was moshikoi)
    5. moshikoi (was LyricLy)
    6. kotnen
    7. taswelll
  7. olus2000 +3 ~0 -6 = -3
    1. essaie
    2. kimapr (was Dolphy)
    3. LyricLy (was kimapr)
    4. moshikoi
    5. taswelll (was LyricLy)
    6. kotnen
    7. Dolphy (was taswelll)
  8. kotnen +1 ~0 -6 = -5
    1. taswelll (was essaie)
    2. kimapr (was olus2000)
    3. LyricLy (was Dolphy)
    4. essaie (was kimapr)
    5. moshikoi
    6. Dolphy (was LyricLy)
    7. olus2000 (was taswelll)

entries

you can download all the entries

entry #1

written by essaie
submitted at
2 likes

guesses
comments 0

post a comment


d.d 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
# hey, moshikoi. youre finally awake. you can trust me. i know what i'm doing.
# just copy my submissive! or read up on https://esolangs.org/wiki/Stack <3 <3

who = 0;
STACK = [];
p = 0;
KCATS = [];
q = 0;
RAM = {};


def POP() -> int:
   global who, STACK, p, KCATS, q;
   if (who):
      if (not KCATS):
         return 0;
      else:
         q = q - 1;
         return KCATS[q];
   else:
      if (not STACK):
         return 0;
      else:
         p = p - 1;
         return STACK[p];


def PUSH(v: int) -> None:
   global who, STACK, p, KCATS, q;
   if (who):
      if (len(KCATS) > q):
         KCATS[q] = v;
      else:
         KCATS = KCATS + [v];
      q = q + 1;
   else:
      if (len(STACK) > p):
         STACK[p] = v;
      else:
         STACK = STACK + [v];
      p = p + 1;


def READ(i: int) -> int:
   global RAM;
   return RAM.get(i, 0);


def WRITE(i: int, v: int) -> None:
   global RAM;
   RAM[i] = v;


from random import randrange as RAND;
from random import seed as ROUND;
def RECOMB(S: str) -> list[int | tuple[int, str, str]]:
   global who;
   i: int; j: int; c: int; m: int;
   i = 0;
   while (i < len(S)):
      match (S[i]):
         case 's':
            who = 1 - who;
         case 'o':
            who = 0;
         case 'p':
            WRITE(POP(), 0);
         case 'f':
            PUSH(READ(POP()));
         case 'w':
            WRITE(POP(), who);
         case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' as v:
            PUSH(v - '0');
         case '"':
            j = i + 1;
            while ((d := S[j]) != '"'):
               PUSH(d);
               j = j + 1;
            i = j;
         case '?':
            PUSH(RAND(POP() + 1));
         case '¿':
            ROUND(POP());
         case '+':
            PUSH(POP() + 1);
         case '-':
            PUSH(POP() - 1);
         case '/':
            PUSH(1 / POP() * POP());
         case '*':
            PUSH(POP() * POP() / 1);
         case '%':
            PUSH(-POP() + POP());
         case '<' | '=' | '>' | '&' | '|' as c:
            PUSH(eval(str(POP()) + c + str(POP())));
         case '!':
            WRITE(POP(), POP());
         case '\\':
            c = POP();
            PUSH(c);
         case ':':
            PUSH(POP());
            PUSH(i);
         case '@':
            PUSH(READ(POP()));
         case '#':
            PUSH(0);
         case '.':
            POP();
         case ',':
            PUSH(READ(i));
         case 'î':
            if (POP()):
               PUSH(POP());
               PUSH(i);
         case 'ô':
            if (POP()):
               PUSH(p);
            else:
               PUSH(q);
         case '[':
            c = 1;
            j = i;
            while (c):
               j = j + 1;
               match (S[j]):
                  case '[':
                     c = c + 1;
                  case ']':
                     c = c - 1;
                  case '|':
                     if (c == 1):
                        m = j;
            c = POP();
            while (1):
               RECOMB(S[i + 1:m]);
               if (not POP() or not c):
                  break;
               RECOMB(S[m + 1:j]);
               c = c - 1;
            i = j;
         case '~':
            who = POP() % 2;
         case '§':
            i = -1;
         case _:
            None;
      i = i + 1;


if (__name__ == "__main__"):
   import sys;
   
   ROUND(59);
   
   if (len(sys.argv) - 1):
      RECOMB(sys.argv[1]);
   else:
      RECOMB(input());
   
   print(f"{STACK[:p]}\040\162\145\163\165\154\164\163\040\061\060\060\045\
   \157\146\040\164\150\145\040\164\151\155\145\056\040\040\040\040\040\040");
   #\163\141\156\163\040\165\156\144\145\162\164\141\154\145 look at stripes!
   #/   /   /   /   /   /   /   /   /   /   /   /   /   /   ,_______________
  #/   /   /   /   /   /   /   /   /   /   /   /   /   /   /   /   /   /   |\
#--\___\___\___\___\___\___\___\___\___\___\___\___\___\___\___\___\___\___\/

entry #2

written by olus2000
submitted at
3 likes

guesses
comments 2
LyricLy

what language is this


olus2000 *known at the time as [author of #2]

green


post a comment


test2.prog data

entry #3

written by Dolphy
submitted at
0 likes

guesses
comments 0

post a comment


cg59.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
 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
local function gen_array(n, x)
    local l = {}
    for i=1,n do
        l[i] = x
    end
    return l
end

local function clone_table(original)
    local copy = {}
    for key, value in pairs(original) do
        if type(value) == "table" then
            copy[key] = clone_table(value)
        else
            copy[key] = value
        end
    end
    return copy
end

local function push_table(dest, src)
    for i=1,#src do
        dest[#dest + 1] = src[i]
    end
end

local MAX_DEPTH = 10
local finished_interpreters = {}
local new_interpreters = {}

local function make_interpreter()
    local interpreter = {
        stack = {},
        random_access_memory = gen_array(30000, 0),
        depth = 0,
        bounds = {},
        loops = {},
        idx = 1,
        has_finished = false,
        coe = 1.0,
        code = '',
    }

    function interpreter.pop_stack(i)
        if #i.stack == 0 then
            return 0
        end

        local x = i.stack[#i.stack]
        table.remove(i.stack)
        return x
    end

    function interpreter.push_stack(i, x)
        table.insert(i.stack, x)
    end

    function interpreter.clone(i, upto)
        if i.depth >= MAX_DEPTH then
            return {}
        end

        local clones = {}
        for idx=0,upto do
            local new_interpreter = clone_table(i)
            new_interpreter.depth = i.depth + 1
            new_interpreter.coe = i.coe / (upto + 1)
            new_interpreter:push_stack(idx)
            table.insert(clones, new_interpreter)
        end
        return clones
    end

    function interpreter.step(i)
        if i.has_finished then
            return false
        end
        if i.idx > #i.code or i.depth >= MAX_DEPTH then
            table.insert(finished_interpreters, i)
            i.has_finished = true
            return false
        end

        local chr = string.sub(i.code, i.idx, i.idx)
        i.idx = i.idx + 1

        if chr == '#' then
            i:push_stack(0)
        elseif chr == '+' then
            local x = i:pop_stack()
            i:push_stack(x + 1)
        elseif chr == '@' then
            local address = i:pop_stack() + 1
            i:push_stack(i.random_access_memory[address])
        elseif chr == '!' then
            local address = i:pop_stack() + 1
            local value = i:pop_stack()
            i.random_access_memory[address] = value
        elseif chr == '?' then
            local number = i:pop_stack()
            push_table(new_interpreters, i:clone(number))
            return false
        elseif chr == '[' then
            local bound = i:pop_stack()
            table.insert(i.bounds, bound)
            table.insert(i.loops, i.idx)
        elseif chr == '|' then
            local condition = i:pop_stack()
            if condition == 0 or i.bounds[#i.bounds] == 0 then
                table.remove(i.loops, #i.loops)
                table.remove(i.bounds, #i.bounds)
                local lc = 0
                while true do
                    local char = string.sub(i.code, i.idx, i.idx)
                    if char == '[' then
                        lc = lc + 1
                    elseif char == ']' then
                        if lc == 0 then
                            break
                        end
                        lc = lc - 1
                    end
                    i.idx = i.idx + 1
                end
                i.idx = i.idx + 1
            end
        elseif chr == ']' then
            i.bounds[#i.bounds] = i.bounds[#i.bounds] - 1
            i.idx = i.loops[#i.loops]
        end

        return true
    end
    return interpreter
end


function entry(code)
    local interpreter = make_interpreter()
    interpreter.code = code

    local interpreters = {interpreter}
    finished_interpreters = {}
    new_interpreters = {}

    local stepped = true
    while stepped or #new_interpreters ~= 0 do
        new_interpreters = {}
        stepped = false

        local idx = 1
        while idx <= #interpreters do
            local i = interpreters[idx]
            if i:step() == false then
                table.remove(interpreters, idx)
            else
                stepped = true
                idx = idx + 1
            end
        end

        push_table(interpreters, new_interpreters)
    end

    local outputs = {}

    for _,i in ipairs(finished_interpreters) do
        local top = i:pop_stack()
        if outputs[top] == nil then
            outputs[top] = i.coe
        else
            outputs[top] = outputs[top] + i.coe
        end
    end

    local most_probable_outcomes = {}
    local high = 0

    for k,v in pairs(outputs) do
        if v > high then
            most_probable_outcomes = {k}
            high = v
        elseif v == high then
            table.insert(most_probable_outcomes, k)
        end
    end

    return most_probable_outcomes
end
meme_solution.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
 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
local function gen_array(n, x)
    local l = {}
    for i=1,n do
        l[i] = x
    end
    return l
end

local function clone_table(original)
    local copy = {}
    for key, value in pairs(original) do
        if type(value) == "table" then
            copy[key] = clone_table(value)
        else
            copy[key] = value
        end
    end
    return copy
end

local interpreter = {
    stack = {},
    random_access_memory = gen_array(30000, 0),

    pop_stack = function (i)
        if #i.stack == 0 then
            return 0
        end
        
        local x = i.stack[#i.stack]
        table.remove(i.stack)
        return x
    end,
    push_stack = function (i, x)
        table.insert(i.stack, x)
    end,
    execute = function (i, stmts)
        for _, v in ipairs(stmts) do
            v:run(i)
        end
    end,
    clone = function (i, upto)
        local clones = {}
        for idx=0,upto do
            local new_interpreter = clone_table(i)
            new_interpreter:push_stack(idx)
            table.insert(clones, new_interpreter)
        end
        return clones
    end
}

local function instruction_new(exec)
    return {
        run = exec,
    }
end

local function loop_new(c, b)
    return {
        cond = c,
        body = b,
        run = function (self, i)
            local bound = i:pop_stack()

            while bound ~= 0 do
                i:execute(self.cond)
                local num = i:pop_stack()

                if num == 0 or bound == 0 then
                    break
                end

                i:execute(self.body)
                bound = bound - 1
            end
        end,
    }
end

local instructions = {
    h = instruction_new(function (_, i)
        i:push_stack(0)
    end),
    p = instruction_new(function (_, i)
        local x = i:pop_stack()
        i:push_stack(x + 1)
    end),
    a = instruction_new(function (_, i)
        local address = i:pop_stack() + 1
        i:push_stack(i.random_access_memory[address])
    end),
    e = instruction_new(function (_, i)
        local address = i:pop_stack() + 1
        local value = i:pop_stack()
        i.random_access_memory[address] = value
    end),
    q = instruction_new(function (_, i)
        local number = i:pop_stack()
        i:push_stack(math.random(number + 1) - 1)
    end),
}

local function parse(code, idx)
    local stmts = {}

    while idx <= #code do
        local char = string.sub(code, idx, idx)

        if char == '#' then
            table.insert(stmts, instructions.h)
        elseif char == '+' then
            table.insert(stmts, instructions.p)
        elseif char == '@' then
            table.insert(stmts, instructions.a)
        elseif char == '!' then
            table.insert(stmts, instructions.e)
        elseif char == '?' then
            table.insert(stmts, instructions.q)
        elseif char == '|' or char == ']' then
            return stmts, idx
        elseif char == '[' then
            local body
            local condition

            condition, idx = parse(code, idx + 1)
            char = string.sub(code, idx, idx)

            if char ~= '|' then
                print("Expected '|', got '"..char.."'")
                os.exit(1)
            end

            body, idx = parse(code, idx + 1)
            char = string.sub(code, idx, idx)
            if char ~= ']' then
                print("Expected ']', got '"..char.."'")
                os.exit(1)
            end
            table.insert(stmts, loop_new(condition, body))
        end
        idx = idx + 1
    end

    return stmts, idx
end

function entry(code)
    local parsed = parse(code, 1)

    local N = 10000
    local dict = {}
    for _=1,N do
        interpreter:execute(parsed)

        local outcome = interpreter:pop_stack()
        if dict[outcome] == nil then
            dict[outcome] = 1
        else
            dict[outcome] = dict[outcome] + 1
        end
    end

    local max = 0
    local max_k = 0
    for k,v in pairs(dict) do
        if v > max then
            max_k = k
            max = v
        end
    end

    return max_k
end

entry #4

written by kimapr
submitted at
3 likes

guesses
comments 5
kotnen

meow


kimapr *known at the time as [author of #4] replying to kotnen

meow!


kotnen

i know who you are now.


kotnen

meowmeowmeow


kimapr *known at the time as [author of #4] replying to kotnen

nyo you don't nyaa :3


post a comment


entry.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
 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
def encourage(bottom, pleading=[]):
    bottom = [squirm for squirm in bottom]

    def lap(top):
        try:
            top.hard.append (
                top.soft [
                    top.hard.pop()])
        except (IndexError, KeyError):
            reduce(0)

    def reduce(item):
        item.hard.append(0)

    def induce(current):
        try:
            golden = current.hard.pop()
        except IndexError:
            golden = 0
        try:
            retriever = current.hard.pop()
        except IndexError:
            retriever = 0
        current.soft [
            golden ]= retriever

    def seduce(victim):
        try:
            victim.hard.append (
                victim.hard.pop() + 1)
        except IndexError:
            victim.hard.append(1)

    def deduce(crime):
        try:
            crime.hard.append (
                crime.random (
                    crime.hard.pop()))
        except IndexError:
            crime.hard.append(0)
            return

    def genetic(spawn):
        try:
            insistence = spawn.hard.pop()
        except IndexError:
            insistence = 0
        spawn.crows.append(insistence)

    def stochastic(crow):
        relativity = crow.monads [
            crow.monadic]
        crow.monadic = crow.monadic + 1
        try:
            questionable = crow.hard.pop()
        except IndexError:
            questionable = 0
        try:
            dogmatic = crow.crows[-1:][0]
            sabotage = 42
            sabotage /= questionable
            sabotage /= dogmatic
        except ZeroDivisionError:
            crow.monadic = relativity
            crow.crows.pop()

    def deterministic(pickle):
        relativity = pickle.monads [
            pickle.monadic]
        pickle.monadic = relativity
        pickle.crows.append (
            pickle.crows.pop() - 1)

    class constructor:
        genetic = None
        stochastic = None
        deterministic = None

    clone = __import__("copy").deepcopy
    copy = __import__("copy").copy

    class objection:
        soft = {}
        hard = []
        crows = []
        monads = []
        monadic = 0
        constructural = []
        random = None
        def __deepcopy__(self, memo):
            obj = objection()
            obj.monads = self.monads
            obj.monadic = self.monadic
            obj.random = self.random
            obj.hard = clone(self.hard,memo)
            obj.soft = clone(self.soft,memo)
            obj.crows = clone(self.crows,memo)
            return obj

    def std__forward_inserter(iterator,iterant,functor):
        def fungus(objection):
            objection.monads.append(functor)
        iterator[iterant] = fungus

    def std__genetic_inserter(iterator,iterant):
        def fungus(objection):
            const = constructor()
            const.genetic = len(objection.monads)
            objection.constructural.append(const)
            objection.monads.append(genetic)
        iterator[iterant] = fungus

    def std__stochastic_inserter(iterator,iterant):
        def fungus(objection):
            const = objection.constructural[-1:][0]
            const.stochastic = (len(objection.monads)
                if const.stochastic == None
                else 1/0)
            objection.monads.append(stochastic)
            objection.monads.append(None)
        iterator[iterant] = fungus

    def std__deterministic_inserter(iterator,iterant):
        def fungus(objection):
            const = objection.constructural.pop()
            const.deterministic = len(objection.monads)
            objection.monads [
                const.stochastic + 1 ]= const.deterministic + 2
            objection.monads.append(deterministic)
            objection.monads.append(const.genetic + 1)
        iterator[iterant] = fungus

    npcs = {}
    std__forward_inserter(npcs,"@",lap)
    std__forward_inserter(npcs,"#",reduce)
    std__forward_inserter(npcs,"!",induce)
    std__forward_inserter(npcs,"+",seduce)
    std__forward_inserter(npcs,"?",deduce)
    std__genetic_inserter(npcs,"[")
    std__stochastic_inserter(npcs,"|")
    std__deterministic_inserter(npcs,"]")

    world = objection()
    for sans_undertale in bottom:
        try:
            excited = npcs[sans_undertale]
        except:
            continue
        excited(objection)

    outputs = {}

    def excite(objection):
        while objection.monadic < len(objection.monads):
            monad = objection.monads[objection.monadic]
            if monad == deduce and objection.random == None:
                for i in range(0,([0] + objection.hard[-1:]).pop() + 1):
                    __objection__ = clone(objection)
                    def random(n):
                        return i
                    __objection__.random = random
                    excite(__objection__)
                return
            objection.monadic = objection.monadic + 1
            monad(objection)
            objection.random = None
        output = tuple(objection.hard)
        outputs[output] = (outputs.get(output) or 0) + 1

    world.hard = clone(pleading)
    excite(world)

    return list(sorted(outputs.items(), key=lambda key:key[1]).pop()[0])

entry #5

written by moshikoi
submitted at
2 likes

guesses
comments 0

post a comment


indigo.cpp 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
#include <algorithm>
#include <format>
#include <iostream>
#include <map>
#include <numeric>
#include <print>
#include <ranges>
#include <stack>
#include <string>
#include <string_view>
#include <vector>

class Interpreter {
  std::reference_wrapper<std::vector<Interpreter>> _interpreters;

  std::stack<int> _stack;
  std::stack<std::size_t> _reps;
  std::stack<std::size_t> _jmps;
  std::size_t _ic = 0;
  bool _finished = false;
  double _weight = 0.0;
  std::string_view _code;

  std::vector<int> _memory;

public:
  Interpreter(std::vector<Interpreter> &interpreters, std::string_view code)
      : _interpreters{interpreters}, _code{code}, _memory(0xffffff) {}

  int pop() {
    if (_stack.empty()) {
      return 0;
    }
    auto const value = _stack.top();
    _stack.pop();
    return value;
  }

  bool step() {
    if (_ic >= _code.length()) {
      return false;
    }

    char const ch = _code[_ic++];
    switch (ch) {
    case '#':
      _stack.push(0);
      break;
    case '+':
      ++_stack.top();
      break;
    case '@': {
      auto const address = pop();
      _stack.push(_memory[address]);
      break;
    }
    case '!': {
      auto const address = pop();
      auto const value = pop();
      _memory[address] = value;
      break;
    }
    case '?': {
      auto const value = pop();
      _interpreters.get().append_range(make_copies(value));
      break;
    }
    case '[': {
      auto const value = _stack.top();
      _reps.push(value);
      _jmps.push(_ic);
      break;
    }
    case ']':
      --_reps.top();
      _ic = _jmps.top();
      break;
    case '|': {
      auto const value = _stack.top();
      if (value == 0 or _reps.top() == 0) {
        _reps.pop();
        _jmps.pop();
        int braces = 1;

        while (true) {
          if (_code[_ic] == '[') {
            ++braces;
          } else if (_code[_ic] == ']') {
            if (braces == 0) {
              break;
            } else {
              --braces;
            }
          }
          ++_ic;
        }
        ++_ic;
      }
    }
    default:
      throw std::runtime_error(std::format("Invalid character {}", ch));
    }
    return true;
  }

  std::vector<Interpreter> make_copies(int n) {
    return to<std::vector>(std::ranges::views::iota(n) |
                           std::ranges::views::transform([&](auto i) {
                             auto copy = *this;
                             copy._weight = _weight / (n + 1);
                             copy._stack.push(_ic);
                             return copy;
                           }));
  }

  double weight() { return _weight; }
};

int interpret(std::string_view code) {
  std::vector<Interpreter> interpreters;
  std::vector<Interpreter> finished_interpreters;

  interpreters.emplace_back(interpreters, code);

  while (not interpreters.empty()) {
    for (int i = 0; i < interpreters.size();) {
      if (not interpreters[i].step()) {
        finished_interpreters.push_back(interpreters[i]);
        interpreters.erase(interpreters.begin() + i);
      } else {
        ++i;
      }
    }
  }

  std::map<int, double> outputs;
  for (auto &&interpreter : finished_interpreters) {
    outputs[interpreter.pop()] += interpreter.weight();
  }

  return std::ranges::max_element(
             outputs, [](auto &p1, auto &p2) { return p1.second < p2.second; })
      ->first;
}

int main() {
  std::string line;
  std::getline(std::cin, line);
  std::println("{"
               "}",
               interpret(line));
}

entry #6

written by LyricLy
submitted at
1 like

guesses
comments 0

post a comment


entry.jq 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
#!/usr/bin/env -S jq -Rrf

def parse: [
  scan("(?<r>[#+@!?]|\\[((?&r)*)\\|((?&r)*)])") |
  if .[1] != null then {cond: .[1] | parse, body: .[2] | parse}
  else .[0]
  end
];

def new_state: {
    stack: [],
    memory: {},
};

def ensure_height($height):
  .stack |= [range([$height - (. | length), 0] | max) | 0] + .
;

def gcd($a; $b): if $b == 0 then $a else gcd($b; $a % $b) end;
def lcm($a; $b): $a * $b / gcd($a; $b);
def lcm: reduce .[] as $n (1; lcm(.; $n));

def probpipe(x; y):
  [x | [y]] | (map(length) | lcm) as $l |
  .[] as $p | range($l / ($p | length)) | $p[]
;

def for($vals; filter):
  if ($vals | length) == 0 then .
  else {val: $vals[0], state: .} | filter | for(vals[1:]; filter)
  end
;

def eval($code):
  def do_loop($bound; $loop): probpipe(
    eval($loop.cond);
    ensure_height(1) | .stack[-1] as $cond | del(.stack[-1]) |
    if $bound != 0 and $cond != 0 then
      eval($loop.body) | do_loop($bound - 1; $loop)
    end
  );

  for($code; . as {$val, $state} | $state |
    if $val == "#" then
      .stack += [0]
    elif $val == "+" then
      ensure_height(1) | .stack[-1] += 1
    elif $val == "@" then
      ensure_height(1) | .stack[-1] = .memory[.stack[-1] | tostring]
    elif $val == "!" then
      ensure_height(2) |
      .memory[.stack[-1] | tostring] = .stack[-2] |
      del(.stack[-1, -2])
    elif $val == "?" then
      ensure_height(1) |
      range(.stack[-1] + 1) as $n | .stack[-1] = $n
    else
      ensure_height(1) |
      .stack[-1] as $bound | del(.stack[-1]) | do_loop($bound; $val)
    end
  )
;

def run:
  parse as $code | new_state | eval($code) |
  ensure_height(1).stack[-1] | tostring
;

def most_frequent:
  reduce .[] as $k ({}; .[$k] += 1) | to_entries | max_by(.value).key
;

[run] | most_frequent

entry #7

written by kotnen
submitted at
1 like

guesses
comments 0

post a comment


kimapr.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
 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
// the extension time is almost gone, and i don't have anymore time to work on this (im going to a concert!)
// so i can't work on this anymore. so, i'm submitting an unfinished copy of this.
// i really am sorry about it being unfinished, but i don't have much of a choice here: it's either participate or don't,
// and i really do want to participate.

// P.S. compile with       g++ kimapr.c -fpermissive -lgmp
//      IF  :   you dont have obstack
//      THEN:   add obstack.c to the g++ command.


/* DONE:
    all of the trivial shit
*/

/* TODO:
    fix all of the FIXME list
    add randomi[zs]ation for probablistic-ization of PricK
*/

/* FIXME:
    conditionals are fucked
    like really really fucked
*/

/*
The author of this file IS NOT one of the following people:
 lyricly
 razetime
 r. "essaie" sa
 olive
 olus "olly" 2000
 olivia
 IFcoltransG
 sofia
 kotnen
 zptr yui
 mark
 palailogos
 at (DataKinds)

The author of this file IS one of the following people:
 GNU Radio Shows
 seshoumara

Impersonating people who aren't even playing is fun. Maybe next time i'll impersonate someone else.
*/



#if __has_include(<obstack.h>)
# include <obstack.h>
#else
# include "obstack.h"
#endif


static struct flags
{
    int helpinfo, versions;
    char*verb,*post,*p, sn;
} flgs;

#include <unordered_map>

#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
static int c, i, v, n;
void parseopt(int argc, char *const argv[])
{
    static const struct option lopts[] = {
        {"help",     no_argument,       &flgs.helpinfo, 1},
        {"version",  no_argument,       &flgs.versions, 1},
        {"before",   required_argument, 0,              'b'},
        {"after",    required_argument, 0,              'a'},
        {"command",  required_argument, 0,              'c'},
        {0,          0,                 0,              0},
    };
    while((c = getopt_long(argc, argv, "hHvVc:C:b:B:a:A:",
                           lopts, &i)) != -1){
        switch(c) {
        case '?':
            printf("use --help\n");
        case 0:
            break;
        case 'h': case 'H':
            flgs.helpinfo = 1;
            break;
        case 'v': case 'V':
            flgs.versions = 1;
            break;
        case 'c': case 'C':
            flgs.p=optarg;
            flgs.sn=1;
            break;
        case 'b': case 'B':
            flgs.verb=optarg;
            break;
        case 'a': case 'A':
            flgs.post=optarg;
            break;
        }
    }
    if (optind < argc){
        if (flgs.p||++optind<argc) {
            printf("%s: unexpected positional argument -- %s",
                   argv[0], argv[optind]);
            exit(-1);
        }
        flgs.p = argv[--optind];
    }
}



#include <string.h>
#include <stack>
char *E;
int exc(char*e){strcpy((E=realloc(E,(n+=(i=strlen(e)))+1))+n-i,e);}



#if __has_include(<gmp.h>)
# include <gmp.h>
#else
# error what the SIGMA?!you promised me gmplib!
#endif
int rnc();
static struct Ss{
    struct obstack ostcak{};
    std::stack<int> stcak{};
    std::unordered_map<int,int> arm{}; // sparse memory representation
} *stk;
#define MPZ_POP(n)\
if(cr.stcak.empty())mpz_init(n); \
else (mpz_init_set_ui(n,cr.stcak.top()),cr.stcak.pop());
#define MPZ_MEM(n, a)\
if(!cr.arm.count(mpz_get_ui(a)))mpz_init(n); \
else mpz_init_set_ui(n,cr.arm[mpz_get_ui(a)]);
#ifdef useobskcatk
#define OBJECTSTAKDFLK\
obstack_init(&cr.ostcak);obstack_free(&cr.ostcak, NULL);
#else
#define OBJECTSTAKDFLK
#endif
#define FALL \
for(c = 0; c < v; c++){struct Ss& cr = stk[c];OBJECTSTAKDFLK
int cond(){
    struct Ss& cr = stk[c];
    i++;
    int I=i;
    int J=i;
    int bal=1;
    for(;bal;J++){
        bal += E[J] == '[';
        bal -= E[J] == ']';
    };
    mpz_t b; MPZ_POP(b);
    while (1){
        while(E[i]!='|')
            rnc();
        mpz_t N; MPZ_POP(N);
        if (mpz_cmp_ui(N, 0) && mpz_cmp_ui(b, 0)){
            while(E[i]!=']')
                rnc();
        } else break;
        i=I;
    }
    i=J;
}
int rnc(){
    printf("%d %c\n", E[i], E[i]);
switch(E[i]){
case '#':
    FALL;cr.stcak.push(0);};
break;case '+':
    FALL;mpz_t t;MPZ_POP(t);mpz_add_ui(t, t, 1);
   cr.stcak.push(mpz_get_ui(t));mpz_clear(t);};
break;case '@':
    FALL;mpz_t s,m;MPZ_POP(s);MPZ_MEM(m,s);mpz_clear(s);
   cr.stcak.push(mpz_get_ui(m));mpz_clear(m);};break;
case '!':
    FALL;mpz_t a,V;MPZ_POP(a);MPZ_POP(V);
   cr.arm[mpz_get_ui(a)]=mpz_get_ui(V);
   mpz_clear(a);mpz_clear(V);};
break;case '[':cond();
break;case '|':case ']':i++;return;
break;case '?':
break;default:
    printf("bad syntax. %s",
           "see --help output for more information.\n");
exit(-1);
};i++;}
int cleanup() {for (; i < n-1 && E[i];)rnc();
FALL;printf("%d\n", cr.stcak.top());};
}

int main(int argc, char* argv[]) {
    parseopt(argc, argv); v++;
    if (flgs.helpinfo)
        printf("lol no, just read the source code\n"), exit(-1);
    if (flgs.versions)
        printf("%s v6.9\n", argv[0]),                  exit(-1);
    stk = (struct Ss *)calloc(v, sizeof(struct Ss));
    stk[0] = Ss{};
    E = (char *)malloc(n=0);
    if (flgs.verb) exc(flgs.verb);
    if (flgs.sn)   exc(flgs.p);
    else {
        FILE* f = flgs.p ? fopen(flgs.p, "r") : stdin;
        while ((c = getc(f)) != EOF) exc((char *)&c);
    }
    if (flgs.post) exc(flgs.post);
    i=0;cleanup();
}
obstack.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
 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
/* obstack.c - subroutines used implicitly by object stack macros
   Copyright (C) 1988-2024 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   This file is free software: you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation, either version 3 of the
   License, or (at your option) any later version.

   This file is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */


#ifdef _LIBC
# include <obstack.h>
#else
//# include <config.h>
# include "obstack.h"
#endif

/* NOTE BEFORE MODIFYING THIS FILE IN GNU LIBC: _OBSTACK_INTERFACE_VERSION in
   gnu-versions.h must be incremented whenever callers compiled using an old
   obstack.h can no longer properly call the functions in this file.  */

/* If GCC, or if an oddball (testing?) host that #defines __alignof__,
   use the already-supplied __alignof__.  Otherwise, this must be Gnulib
   (as glibc assumes GCC); defer to Gnulib's alignof_type.  */
#if !defined __GNUC__ && !defined __alignof__
# include <alignof.h>
# define __alignof__(type) alignof_type (type)
#endif
#include <stdlib.h>
#include <stdint.h>

#ifndef MAX
# define MAX(a,b) ((a) > (b) ? (a) : (b))
#endif

/* Determine default alignment.  */

/* If malloc were really smart, it would round addresses to DEFAULT_ALIGNMENT.
   But in fact it might be less smart and round addresses to as much as
   DEFAULT_ROUNDING.  So we prepare for it to do that.

   DEFAULT_ALIGNMENT cannot be an enum constant; see gnulib's alignof.h.  */
#define DEFAULT_ALIGNMENT MAX (__alignof__ (long double),		      \
                               MAX (__alignof__ (uintmax_t),		      \
                                    __alignof__ (void *)))
#define DEFAULT_ROUNDING MAX (sizeof (long double),			      \
                               MAX (sizeof (uintmax_t),			      \
                                    sizeof (void *)))

/* Call functions with either the traditional malloc/free calling
   interface, or the mmalloc/mfree interface (that adds an extra first
   argument), based on the value of use_extra_arg.  */

static void *
call_chunkfun (struct obstack *h, size_t size)
{
  if (h->use_extra_arg)
    return h->chunkfun.extra (h->extra_arg, size);
  else
    return h->chunkfun.plain (size);
}

static void
call_freefun (struct obstack *h, void *old_chunk)
{
  if (h->use_extra_arg)
    h->freefun.extra (h->extra_arg, old_chunk);
  else
    h->freefun.plain (old_chunk);
}


/* Initialize an obstack H for use.  Specify chunk size SIZE (0 means default).
   Objects start on multiples of ALIGNMENT (0 means use default).

   Return nonzero if successful, calls obstack_alloc_failed_handler if
   allocation fails.  */

static int
_obstack_begin_worker (struct obstack *h,
                       _OBSTACK_SIZE_T size, _OBSTACK_SIZE_T alignment)
{
  struct _obstack_chunk *chunk; /* points to new chunk */

  if (alignment == 0)
    alignment = DEFAULT_ALIGNMENT;
  if (size == 0)
    /* Default size is what GNU malloc can fit in a 4096-byte block.  */
    {
      /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.
         Use the values for range checking, because if range checking is off,
         the extra bytes won't be missed terribly, but if range checking is on
         and we used a larger request, a whole extra 4096 bytes would be
         allocated.

         These number are irrelevant to the new GNU malloc.  I suspect it is
         less sensitive to the size of the request.  */
      int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))
                    + 4 + DEFAULT_ROUNDING - 1)
                   & ~(DEFAULT_ROUNDING - 1));
      size = 4096 - extra;
    }

  h->chunk_size = size;
  h->alignment_mask = alignment - 1;

  chunk = h->chunk = call_chunkfun (h, h->chunk_size);
  if (!chunk)
    (*obstack_alloc_failed_handler) ();
  h->next_free = h->object_base = __PTR_ALIGN ((char *) chunk, chunk->contents,
                                               alignment - 1);
  h->chunk_limit = chunk->limit = (char *) chunk + h->chunk_size;
  chunk->prev = 0;
  /* The initial chunk now contains no empty object.  */
  h->maybe_empty_object = 0;
  h->alloc_failed = 0;
  return 1;
}

int
_obstack_begin (struct obstack *h,
                _OBSTACK_SIZE_T size, _OBSTACK_SIZE_T alignment,
                void *(*chunkfun) (size_t),
                void (*freefun) (void *))
{
  h->chunkfun.plain = chunkfun;
  h->freefun.plain = freefun;
  h->use_extra_arg = 0;
  return _obstack_begin_worker (h, size, alignment);
}

int
_obstack_begin_1 (struct obstack *h,
                  _OBSTACK_SIZE_T size, _OBSTACK_SIZE_T alignment,
                  void *(*chunkfun) (void *, size_t),
                  void (*freefun) (void *, void *),
                  void *arg)
{
  h->chunkfun.extra = chunkfun;
  h->freefun.extra = freefun;
  h->extra_arg = arg;
  h->use_extra_arg = 1;
  return _obstack_begin_worker (h, size, alignment);
}

/* Allocate a new current chunk for the obstack *H
   on the assumption that LENGTH bytes need to be added
   to the current object, or a new object of length LENGTH allocated.
   Copies any partial object from the end of the old chunk
   to the beginning of the new one.  */

void
_obstack_newchunk (struct obstack *h, _OBSTACK_SIZE_T length)
{
  struct _obstack_chunk *old_chunk = h->chunk;
  struct _obstack_chunk *new_chunk = 0;
  size_t obj_size = h->next_free - h->object_base;
  char *object_base;

  /* Compute size for new chunk.  */
  size_t sum1 = obj_size + length;
  size_t sum2 = sum1 + h->alignment_mask;
  size_t new_size = sum2 + (obj_size >> 3) + 100;
  if (new_size < sum2)
    new_size = sum2;
  if (new_size < h->chunk_size)
    new_size = h->chunk_size;

  /* Allocate and initialize the new chunk.  */
  if (obj_size <= sum1 && sum1 <= sum2)
    new_chunk = call_chunkfun (h, new_size);
  if (!new_chunk)
    (*obstack_alloc_failed_handler)();
  h->chunk = new_chunk;
  new_chunk->prev = old_chunk;
  new_chunk->limit = h->chunk_limit = (char *) new_chunk + new_size;

  /* Compute an aligned object_base in the new chunk */
  object_base =
    __PTR_ALIGN ((char *) new_chunk, new_chunk->contents, h->alignment_mask);

  /* Move the existing object to the new chunk.  */
  memcpy (object_base, h->object_base, obj_size);

  /* If the object just copied was the only data in OLD_CHUNK,
     free that chunk and remove it from the chain.
     But not if that chunk might contain an empty object.  */
  if (!h->maybe_empty_object
      && (h->object_base
          == __PTR_ALIGN ((char *) old_chunk, old_chunk->contents,
                          h->alignment_mask)))
    {
      new_chunk->prev = old_chunk->prev;
      call_freefun (h, old_chunk);
    }

  h->object_base = object_base;
  h->next_free = h->object_base + obj_size;
  /* The new chunk certainly contains no empty object yet.  */
  h->maybe_empty_object = 0;
}

/* Return nonzero if object OBJ has been allocated from obstack H.
   This is here for debugging.
   If you use it in a program, you are probably losing.  */

/* Suppress -Wmissing-prototypes warning.  We don't want to declare this in
   obstack.h because it is just for debugging.  */
int _obstack_allocated_p (struct obstack *h, void *obj) __attribute_pure__;

int
_obstack_allocated_p (struct obstack *h, void *obj)
{
  struct _obstack_chunk *lp;    /* below addr of any objects in this chunk */
  struct _obstack_chunk *plp;   /* point to previous chunk if any */

  lp = (h)->chunk;
  /* We use >= rather than > since the object cannot be exactly at
     the beginning of the chunk but might be an empty object exactly
     at the end of an adjacent chunk.  */
  while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))
    {
      plp = lp->prev;
      lp = plp;
    }
  return lp != 0;
}

/* Free objects in obstack H, including OBJ and everything allocate
   more recently than OBJ.  If OBJ is zero, free everything in H.  */

void
_obstack_free (struct obstack *h, void *obj)
{
  struct _obstack_chunk *lp;    /* below addr of any objects in this chunk */
  struct _obstack_chunk *plp;   /* point to previous chunk if any */

  lp = h->chunk;
  /* We use >= because there cannot be an object at the beginning of a chunk.
     But there can be an empty object at that address
     at the end of another chunk.  */
  while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))
    {
      plp = lp->prev;
      call_freefun (h, lp);
      lp = plp;
      /* If we switch chunks, we can't tell whether the new current
         chunk contains an empty object, so assume that it may.  */
      h->maybe_empty_object = 1;
    }
  if (lp)
    {
      h->object_base = h->next_free = (char *) (obj);
      h->chunk_limit = lp->limit;
      h->chunk = lp;
    }
  else if (obj != 0)
    /* obj is not in any of the chunks! */
    abort ();
}

_OBSTACK_SIZE_T
_obstack_memory_used (struct obstack *h)
{
  struct _obstack_chunk *lp;
  _OBSTACK_SIZE_T nbytes = 0;

  for (lp = h->chunk; lp != 0; lp = lp->prev)
    {
      nbytes += lp->limit - (char *) lp;
    }
  return nbytes;
}

#ifndef _OBSTACK_NO_ERROR_HANDLER
/* Define the error handler.  */
# include <stdio.h>

/* Exit value used when 'print_and_abort' is used.  */
int obstack_exit_failure = EXIT_FAILURE;


static __attribute_noreturn__ void
print_and_abort (void)
{
  /* Don't change any of these strings.  Yes, it would be possible to add
     the newline to the string and use fputs or so.  But this must not
     happen because the "memory exhausted" message appears in other places
     like this and the translation should be reused instead of creating
     a very similar string which requires a separate translation.  */
  fprintf (stderr, "%s\n", "memory exhausted");
  exit (obstack_exit_failure);
}

/* The functions allocating more room by calling 'obstack_chunk_alloc'
   jump to the handler pointed to by 'obstack_alloc_failed_handler'.
   This can be set to a user defined function which should either
   abort gracefully or use longjump - but shouldn't return.  This
   variable by default points to the internal function
   'print_and_abort'.  */
__attribute_noreturn__ void (*obstack_alloc_failed_handler) (void)
  = print_and_abort;
#endif /* !_OBSTACK_NO_ERROR_HANDLER */
obstack.h 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
/* obstack.h - object stack macros
   Copyright (C) 1988-2024 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   This file is free software: you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation, either version 3 of the
   License, or (at your option) any later version.

   This file is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */

/* Summary:

   All the apparent functions defined here are macros. The idea
   is that you would use these pre-tested macros to solve a
   very specific set of problems, and they would run fast.
   Caution: no side-effects in arguments please!! They may be
   evaluated MANY times!!

   These macros operate a stack of objects.  Each object starts life
   small, and may grow to maturity.  (Consider building a word syllable
   by syllable.)  An object can move while it is growing.  Once it has
   been "finished" it never changes address again.  So the "top of the
   stack" is typically an immature growing object, while the rest of the
   stack is of mature, fixed size and fixed address objects.

   These routines grab large chunks of memory, using a function you
   supply, called 'obstack_chunk_alloc'.  On occasion, they free chunks,
   by calling 'obstack_chunk_free'.  You must define them and declare
   them before using any obstack macros.

   Each independent stack is represented by a 'struct obstack'.
   Each of the obstack macros expects a pointer to such a structure
   as the first argument.

   One motivation for this package is the problem of growing char strings
   in symbol tables.  Unless you are "fascist pig with a read-only mind"
   --Gosper's immortal quote from HAKMEM item 154, out of context--you
   would not like to put any arbitrary upper limit on the length of your
   symbols.

   In practice this often means you will build many short symbols and a
   few long symbols.  At the time you are reading a symbol you don't know
   how long it is.  One traditional method is to read a symbol into a
   buffer, realloc()ating the buffer every time you try to read a symbol
   that is longer than the buffer.  This is beaut, but you still will
   want to copy the symbol from the buffer to a more permanent
   symbol-table entry say about half the time.

   With obstacks, you can work differently.  Use one obstack for all symbol
   names.  As you read a symbol, grow the name in the obstack gradually.
   When the name is complete, finalize it.  Then, if the symbol exists already,
   free the newly read name.

   The way we do this is to take a large chunk, allocating memory from
   low addresses.  When you want to build a symbol in the chunk you just
   add chars above the current "high water mark" in the chunk.  When you
   have finished adding chars, because you got to the end of the symbol,
   you know how long the chars are, and you can create a new object.
   Mostly the chars will not burst over the highest address of the chunk,
   because you would typically expect a chunk to be (say) 100 times as
   long as an average object.

   In case that isn't clear, when we have enough chars to make up
   the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed)
   so we just point to it where it lies.  No moving of chars is
   needed and this is the second win: potentially long strings need
   never be explicitly shuffled. Once an object is formed, it does not
   change its address during its lifetime.

   When the chars burst over a chunk boundary, we allocate a larger
   chunk, and then copy the partly formed object from the end of the old
   chunk to the beginning of the new larger chunk.  We then carry on
   accreting characters to the end of the object as we normally would.

   A special macro is provided to add a single char at a time to a
   growing object.  This allows the use of register variables, which
   break the ordinary 'growth' macro.

   Summary:
        We allocate large chunks.
        We carve out one object at a time from the current chunk.
        Once carved, an object never moves.
        We are free to append data of any size to the currently
          growing object.
        Exactly one object is growing in an obstack at any one time.
        You can run one obstack per control block.
        You may have as many control blocks as you dare.
        Because of the way we do it, you can "unwind" an obstack
          back to a previous state. (You may remove objects much
          as you would with a stack.)
 */

/* Documentation (part of the GNU libc manual):
   <https://www.gnu.org/software/libc/manual/html_node/Obstacks.html>  */


/* Don't do the contents of this file more than once.  */
#ifndef _OBSTACK_H
#define _OBSTACK_H 1

#include <stddef.h>             /* For size_t and ptrdiff_t.  */
#include <stdint.h>             /* For uintptr_t.  */
#include <string.h>             /* For memcpy.  */

#if __STDC_VERSION__ < 199901L || defined __HP_cc
# define __FLEXIBLE_ARRAY_MEMBER 1
#else
# define __FLEXIBLE_ARRAY_MEMBER
#endif

/* These macros highlight the places where this implementation
   is different from the one in GNU libc.  */
#ifdef _LIBC
# define _OBSTACK_SIZE_T unsigned int
# define _CHUNK_SIZE_T unsigned long
# define _OBSTACK_CAST(type, expr) ((type) (expr))
#else
/* In Gnulib, we use sane types, especially for 64-bit hosts.  */
# define _OBSTACK_SIZE_T size_t
# define _CHUNK_SIZE_T size_t
# define _OBSTACK_CAST(type, expr) (expr)
#endif

/* __PTR_ALIGN(B, P, A) returns the result of aligning P to the next multiple
   of A + 1.  B must be the base of an object addressed by P.  B and P must be
   of type char *.  A + 1 must be a power of 2.
   If ptrdiff_t is narrower than a pointer (e.g., the AS/400), play it
   safe and compute the alignment relative to B.  Otherwise, use the
   faster strategy of computing the alignment through uintptr_t.  */
#define __PTR_ALIGN(B, P, A) \
   ((P) + ((- (uintptr_t) (P)) & (A)))

#ifndef __attribute_pure__
# define __attribute_pure__ _GL_ATTRIBUTE_PURE
#endif

/* Not the same as _Noreturn, since it also works with function pointers.  */
#ifndef __attribute_noreturn__
# if 2 < __GNUC__ + (8 <= __GNUC_MINOR__) || defined __clang__ || 0x5110 <= __SUNPRO_C
#  define __attribute_noreturn__ __attribute__ ((__noreturn__))
# else
#  define __attribute_noreturn__
# endif
#endif

#ifdef __cplusplus
extern "C" {
#endif

struct _obstack_chunk           /* Lives at front of each chunk. */
{
  char *limit;                  /* 1 past end of this chunk */
  struct _obstack_chunk *prev;  /* address of prior chunk or NULL */
  char contents[__FLEXIBLE_ARRAY_MEMBER]; /* objects begin here */
};

struct obstack          /* control current object in current chunk */
{
  _CHUNK_SIZE_T chunk_size;     /* preferred size to allocate chunks in */
  struct _obstack_chunk *chunk; /* address of current struct obstack_chunk */
  char *object_base;            /* address of object we are building */
  char *next_free;              /* where to add next char to current object */
  char *chunk_limit;            /* address of char after current chunk */
  union
  {
    _OBSTACK_SIZE_T i;
    void *p;
  } temp;                       /* Temporary for some macros.  */
  _OBSTACK_SIZE_T alignment_mask;  /* Mask of alignment for each object. */

  /* These prototypes vary based on 'use_extra_arg'.  */
  union
  {
    void *(*plain) (size_t);
    void *(*extra) (void *, size_t);
  } chunkfun;
  union
  {
    void (*plain) (void *);
    void (*extra) (void *, void *);
  } freefun;

  void *extra_arg;              /* first arg for chunk alloc/dealloc funcs */
  unsigned use_extra_arg : 1;     /* chunk alloc/dealloc funcs take extra arg */
  unsigned maybe_empty_object : 1; /* There is a possibility that the current
                                      chunk contains a zero-length object.  This
                                      prevents freeing the chunk if we allocate
                                      a bigger chunk to replace it. */
  unsigned alloc_failed : 1;      /* No longer used, as we now call the failed
                                     handler on error, but retained for binary
                                     compatibility.  */
};

/* Declare the external functions we use; they are in obstack.c.  */

extern void _obstack_newchunk (struct obstack *, _OBSTACK_SIZE_T);
extern void _obstack_free (struct obstack *, void *);
extern int _obstack_begin (struct obstack *,
                           _OBSTACK_SIZE_T, _OBSTACK_SIZE_T,
                           void *(*) (size_t), void (*) (void *));
extern int _obstack_begin_1 (struct obstack *,
                             _OBSTACK_SIZE_T, _OBSTACK_SIZE_T,
                             void *(*) (void *, size_t),
                             void (*) (void *, void *), void *);
extern _OBSTACK_SIZE_T _obstack_memory_used (struct obstack *)
  __attribute_pure__;


/* Error handler called when 'obstack_chunk_alloc' failed to allocate
   more memory.  This can be set to a user defined function which
   should either abort gracefully or use longjump - but shouldn't
   return.  The default action is to print a message and abort.  */
extern __attribute_noreturn__ void (*obstack_alloc_failed_handler) (void);

/* Exit value used when 'print_and_abort' is used.  */
extern int obstack_exit_failure;

/* Pointer to beginning of object being allocated or to be allocated next.
   Note that this might not be the final address of the object
   because a new chunk might be needed to hold the final size.  */

#define obstack_base(h) ((void *) (h)->object_base)

/* Size for allocating ordinary chunks.  */

#define obstack_chunk_size(h) ((h)->chunk_size)

/* Pointer to next byte not yet allocated in current chunk.  */

#define obstack_next_free(h) ((void *) (h)->next_free)

/* Mask specifying low bits that should be clear in address of an object.  */

#define obstack_alignment_mask(h) ((h)->alignment_mask)

/* To prevent prototype warnings provide complete argument list.  */
#define obstack_init(h)							      \
  _obstack_begin ((h), 0, 0,						      \
                  _OBSTACK_CAST (void *(*) (size_t), obstack_chunk_alloc),    \
                  _OBSTACK_CAST (void (*) (void *), obstack_chunk_free))

#define obstack_begin(h, size)						      \
  _obstack_begin ((h), (size), 0,					      \
                  _OBSTACK_CAST (void *(*) (size_t), obstack_chunk_alloc), \
                  _OBSTACK_CAST (void (*) (void *), obstack_chunk_free))

#define obstack_specify_allocation(h, size, alignment, chunkfun, freefun)     \
  _obstack_begin ((h), (size), (alignment),				      \
                  _OBSTACK_CAST (void *(*) (size_t), chunkfun),		      \
                  _OBSTACK_CAST (void (*) (void *), freefun))

#define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \
  _obstack_begin_1 ((h), (size), (alignment),				      \
                    _OBSTACK_CAST (void *(*) (void *, size_t), chunkfun),     \
                    _OBSTACK_CAST (void (*) (void *, void *), freefun), arg)

#define obstack_chunkfun(h, newchunkfun)				      \
  ((void) ((h)->chunkfun.extra = (void *(*) (void *, size_t)) (newchunkfun)))

#define obstack_freefun(h, newfreefun)					      \
  ((void) ((h)->freefun.extra = (void *(*) (void *, void *)) (newfreefun)))

#define obstack_1grow_fast(h, achar) ((void) (*((h)->next_free)++ = (achar)))

#define obstack_blank_fast(h, n) ((void) ((h)->next_free += (n)))

#define obstack_memory_used(h) _obstack_memory_used (h)

#if defined __GNUC__ || defined __clang__
# if !(defined __GNUC_MINOR__ && __GNUC__ * 1000 + __GNUC_MINOR__ >= 2008 \
       || defined __clang__)
#  define __extension__
# endif

/* For GNU C, if not -traditional,
   we can define these macros to compute all args only once
   without using a global variable.
   Also, we can avoid using the 'temp' slot, to make faster code.  */

# define obstack_object_size(OBSTACK)					      \
  __extension__								      \
    ({ struct obstack const *__o = (OBSTACK);				      \
       (_OBSTACK_SIZE_T) (__o->next_free - __o->object_base); })

/* The local variable is named __o1 to avoid a shadowed variable
   warning when invoked from other obstack macros.  */
# define obstack_room(OBSTACK)						      \
  __extension__								      \
    ({ struct obstack const *__o1 = (OBSTACK);				      \
       (_OBSTACK_SIZE_T) (__o1->chunk_limit - __o1->next_free); })

# define obstack_make_room(OBSTACK, length)				      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       _OBSTACK_SIZE_T __len = (length);				      \
       if (obstack_room (__o) < __len)					      \
         _obstack_newchunk (__o, __len);				      \
       (void) 0; })

# define obstack_empty_p(OBSTACK)					      \
  __extension__								      \
    ({ struct obstack const *__o = (OBSTACK);				      \
       (__o->chunk->prev == 0						      \
        && __o->next_free == __PTR_ALIGN ((char *) __o->chunk,		      \
                                          __o->chunk->contents,		      \
                                          __o->alignment_mask)); })

# define obstack_grow(OBSTACK, where, length)				      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       _OBSTACK_SIZE_T __len = (length);				      \
       if (obstack_room (__o) < __len)					      \
         _obstack_newchunk (__o, __len);				      \
       memcpy (__o->next_free, where, __len);				      \
       __o->next_free += __len;						      \
       (void) 0; })

# define obstack_grow0(OBSTACK, where, length)				      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       _OBSTACK_SIZE_T __len = (length);				      \
       if (obstack_room (__o) < __len + 1)				      \
         _obstack_newchunk (__o, __len + 1);				      \
       memcpy (__o->next_free, where, __len);				      \
       __o->next_free += __len;						      \
       *(__o->next_free)++ = 0;						      \
       (void) 0; })

# define obstack_1grow(OBSTACK, datum)					      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       if (obstack_room (__o) < 1)					      \
         _obstack_newchunk (__o, 1);					      \
       obstack_1grow_fast (__o, datum); })

/* These assume that the obstack alignment is good enough for pointers
   or ints, and that the data added so far to the current object
   shares that much alignment.  */

# define obstack_ptr_grow(OBSTACK, datum)				      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       if (obstack_room (__o) < sizeof (void *))			      \
         _obstack_newchunk (__o, sizeof (void *));			      \
       obstack_ptr_grow_fast (__o, datum); })

# define obstack_int_grow(OBSTACK, datum)				      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       if (obstack_room (__o) < sizeof (int))				      \
         _obstack_newchunk (__o, sizeof (int));				      \
       obstack_int_grow_fast (__o, datum); })

# define obstack_ptr_grow_fast(OBSTACK, aptr)				      \
  __extension__								      \
    ({ struct obstack *__o1 = (OBSTACK);				      \
       void *__p1 = __o1->next_free;					      \
       *(const void **) __p1 = (aptr);					      \
       __o1->next_free += sizeof (const void *);			      \
       (void) 0; })

# define obstack_int_grow_fast(OBSTACK, aint)				      \
  __extension__								      \
    ({ struct obstack *__o1 = (OBSTACK);				      \
       void *__p1 = __o1->next_free;					      \
       *(int *) __p1 = (aint);						      \
       __o1->next_free += sizeof (int);					      \
       (void) 0; })

# define obstack_blank(OBSTACK, length)					      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       _OBSTACK_SIZE_T __len = (length);				      \
       if (obstack_room (__o) < __len)					      \
         _obstack_newchunk (__o, __len);				      \
       obstack_blank_fast (__o, __len); })

# define obstack_alloc(OBSTACK, length)					      \
  __extension__								      \
    ({ struct obstack *__h = (OBSTACK);					      \
       obstack_blank (__h, (length));					      \
       obstack_finish (__h); })

# define obstack_copy(OBSTACK, where, length)				      \
  __extension__								      \
    ({ struct obstack *__h = (OBSTACK);					      \
       obstack_grow (__h, (where), (length));				      \
       obstack_finish (__h); })

# define obstack_copy0(OBSTACK, where, length)				      \
  __extension__								      \
    ({ struct obstack *__h = (OBSTACK);					      \
       obstack_grow0 (__h, (where), (length));				      \
       obstack_finish (__h); })

/* The local variable is named __o1 to avoid a shadowed variable
   warning when invoked from other obstack macros, typically obstack_free.  */
# define obstack_finish(OBSTACK)					      \
  __extension__								      \
    ({ struct obstack *__o1 = (OBSTACK);				      \
       void *__value = (void *) __o1->object_base;			      \
       if (__o1->next_free == __value)					      \
         __o1->maybe_empty_object = 1;					      \
       __o1->next_free							      \
         = __PTR_ALIGN (__o1->object_base, __o1->next_free,		      \
                        __o1->alignment_mask);				      \
       if ((size_t) (__o1->next_free - (char *) __o1->chunk)		      \
           > (size_t) (__o1->chunk_limit - (char *) __o1->chunk))	      \
         __o1->next_free = __o1->chunk_limit;				      \
       __o1->object_base = __o1->next_free;				      \
       __value; })

# define obstack_free(OBSTACK, OBJ)					      \
  __extension__								      \
    ({ struct obstack *__o = (OBSTACK);					      \
       void *__obj = (void *) (OBJ);					      \
       if (__obj > (void *) __o->chunk && __obj < (void *) __o->chunk_limit)  \
         __o->next_free = __o->object_base = (char *) __obj;		      \
       else								      \
         _obstack_free (__o, __obj); })

#else /* not __GNUC__ */

# define obstack_object_size(h)						      \
  ((_OBSTACK_SIZE_T) ((h)->next_free - (h)->object_base))

# define obstack_room(h)						      \
  ((_OBSTACK_SIZE_T) ((h)->chunk_limit - (h)->next_free))

# define obstack_empty_p(h)						      \
  ((h)->chunk->prev == 0						      \
   && (h)->next_free == __PTR_ALIGN ((char *) (h)->chunk,		      \
                                     (h)->chunk->contents,		      \
                                     (h)->alignment_mask))

/* Note that the call to _obstack_newchunk is enclosed in (..., 0)
   so that we can avoid having void expressions
   in the arms of the conditional expression.
   Casting the third operand to void was tried before,
   but some compilers won't accept it.  */

# define obstack_make_room(h, length)					      \
  ((h)->temp.i = (length),						      \
   ((obstack_room (h) < (h)->temp.i)					      \
    ? (_obstack_newchunk (h, (h)->temp.i), 0) : 0),			      \
   (void) 0)

# define obstack_grow(h, where, length)					      \
  ((h)->temp.i = (length),						      \
   ((obstack_room (h) < (h)->temp.i)					      \
   ? (_obstack_newchunk ((h), (h)->temp.i), 0) : 0),			      \
   memcpy ((h)->next_free, where, (h)->temp.i),				      \
   (h)->next_free += (h)->temp.i,					      \
   (void) 0)

# define obstack_grow0(h, where, length)				      \
  ((h)->temp.i = (length),						      \
   ((obstack_room (h) < (h)->temp.i + 1)				      \
   ? (_obstack_newchunk ((h), (h)->temp.i + 1), 0) : 0),		      \
   memcpy ((h)->next_free, where, (h)->temp.i),				      \
   (h)->next_free += (h)->temp.i,					      \
   *((h)->next_free)++ = 0,						      \
   (void) 0)

# define obstack_1grow(h, datum)					      \
  (((obstack_room (h) < 1)						      \
    ? (_obstack_newchunk ((h), 1), 0) : 0),				      \
   obstack_1grow_fast (h, datum))

# define obstack_ptr_grow(h, datum)					      \
  (((obstack_room (h) < sizeof (char *))				      \
    ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0),		      \
   obstack_ptr_grow_fast (h, datum))

# define obstack_int_grow(h, datum)					      \
  (((obstack_room (h) < sizeof (int))					      \
    ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0),			      \
   obstack_int_grow_fast (h, datum))

# define obstack_ptr_grow_fast(h, aptr)					      \
  (((const void **) ((h)->next_free += sizeof (void *)))[-1] = (aptr),	      \
   (void) 0)

# define obstack_int_grow_fast(h, aint)					      \
  (((int *) ((h)->next_free += sizeof (int)))[-1] = (aint),		      \
   (void) 0)

# define obstack_blank(h, length)					      \
  ((h)->temp.i = (length),						      \
   ((obstack_room (h) < (h)->temp.i)					      \
   ? (_obstack_newchunk ((h), (h)->temp.i), 0) : 0),			      \
   obstack_blank_fast (h, (h)->temp.i))

# define obstack_alloc(h, length)					      \
  (obstack_blank ((h), (length)), obstack_finish ((h)))

# define obstack_copy(h, where, length)					      \
  (obstack_grow ((h), (where), (length)), obstack_finish ((h)))

# define obstack_copy0(h, where, length)				      \
  (obstack_grow0 ((h), (where), (length)), obstack_finish ((h)))

# define obstack_finish(h)						      \
  (((h)->next_free == (h)->object_base					      \
    ? (((h)->maybe_empty_object = 1), 0)				      \
    : 0),								      \
   (h)->temp.p = (h)->object_base,					      \
   (h)->next_free							      \
     = __PTR_ALIGN ((h)->object_base, (h)->next_free,			      \
                    (h)->alignment_mask),				      \
   (((size_t) ((h)->next_free - (char *) (h)->chunk)			      \
     > (size_t) ((h)->chunk_limit - (char *) (h)->chunk))		      \
   ? ((h)->next_free = (h)->chunk_limit) : 0),				      \
   (h)->object_base = (h)->next_free,					      \
   (h)->temp.p)

# define obstack_free(h, obj)						      \
  ((h)->temp.p = (void *) (obj),					      \
   (((h)->temp.p > (void *) (h)->chunk					      \
     && (h)->temp.p < (void *) (h)->chunk_limit)			      \
    ? (void) ((h)->next_free = (h)->object_base = (char *) (h)->temp.p)       \
    : _obstack_free ((h), (h)->temp.p)))

#endif /* not __GNUC__ */

#ifdef __cplusplus
}       /* C++ */
#endif

#endif /* _OBSTACK_H */

entry #8

written by taswelll
submitted at
2 likes

guesses
comments 0

post a comment


a.pl 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
#!/usr/bin/env swipl
p(eo,[],[],[]).
p(D,[D|X],X,[]).
p(D,[' '|X],Z,B):-p(D,X,Z,B).
p(D,['['|X],Z,[A|As]):-p('|',X,X1,C),p(']',X1,X2,B),p(D,X2,Z,As),lo(C,B,A).
p(D,[#|X],Z,[push(N)|As]):-pl(X,X1,N,0),p(D,X1,Z,As).
p(D,[+|X],Z,[add(N) |As]):-pl(X,X1,N,1),p(D,X1,Z,As).
p(D,[A|X],Z,[A|As]):-p(D,X,Z,As).
p(X,A):-p(eo,X,[],A).

pl(X,Z,N):-pl(X,Z,N,0).
pl([+|X],Z,N,N0):-N1 is N0+1,pl(X,Z,N,N1).
pl(X,X,N,N).

lo([push(0)],_,pop).
lo([push(N)],[],pop):-N\=0.
lo([push(N)],[add(M)],aff(M)):-N\=0.
lo([push(N)],B,for(B)):-N\=0.
lo(C,B,loop(C,B)).

i([],S,S).
i([A|As],S,S2):-i(A,S,S1),i(As,S1,S2).
i(add(N),[S|Ss]+M,[T|Ss]+M):-T is S+N.
i(add(N),[]+M,[N]+M).
i(push(N),S+M,[N|S]+M).
i(pop,[_|Ss]+M,Ss+M).
i(pop,[]+M,[]+M).
i(aff(_),[ ]+M,[]+M).
i(aff(N),[B]+M,[T]+M):-T is N*B.
i(aff(N),[B,A|Ss]+M,[T|Ss]+M):-T is A+N*B.
i(for(_),[0|Ss]+M,Ss+M).
i(for(_),[]+M,[]+M).
i(for(B),[I|S]+M,Sf):-I\=0,i(B,S+M,S1+M1),I2 is I-1,i(for(B),[I2|S1]+M1,Sf).
i(loop(C,_),[]+M,Sf):-i(C,[]+M,Sf).
i(loop(C,B),[I|Ss]+M,Sf):-i(C,Ss+M,S1_+M1),(S1_=[]->[]+M1=Sf;S1_=[L|S1],
  ((I=0;L=0)->S1+M1=Sf;i(B,S1+M1,S2+M2),I2 is I-1,i(loop(C,B),[I2|S2]+M2,Sf))).
i(@,[]+M,[B]+M):-g(M,0,B).
i(@,[A|Ss]+M,[B|Ss]+M):-g(M,A,B).
i(!,[]+M,[]+M2):-i(!,[0]+M,[]+M2).
i(!,[A]+M,[]+M2):-i(!,[A,0]+M,[]+M2).
i(!,[A,B|Ss]+M,Ss+M2):-s(M,A,B,M1),!,M1=M2.
i(?,[]+M,[]+M).
i(?,[A|Ss]+M/O,[B|Ss]+M/O1):-O1 is O*(A+1),between(0,A,B).

gg(a(A),_,A).
gg(a(L,_,B),N,V):-N/\B=:=0,gg(L,N,V).
gg(a(_,R,B),N,V):-N/\B=\=0,gg(R,N,V).
ss(a(_),_,V,a(V)).
ss(a(L,R,B),N,V,a(A,R,B)):-N/\B=:=0,ss(L,N,V,A).
ss(a(L,R,B),N,V,a(L,A,B)):-N/\B=\=0,ss(R,N,V,A).
s(a(L,R,B),N,V,A):-N< B<<1,ss(a(L,R,B),N,V,A).
s(a(L,R,B),N,V,A):-N>=B<<1,B1 is B<<1,e(B,R1),s(a(a(L,R,B),R1,B1),N,V,A).
s(A/O,N,V,B/O):-s(A,N,V,B).
g(a(L,R,B),N,V):-N< B<<1,gg(a(L,R,B),N,V).
g(a(_,_,B),N,0):-N>=B<<1.
g(A/_,N,V):-g(A,N,V).

e(0,a(0)).
e(N,a(L,R,N)):-N1 is N>>1,e(N1,L),e(N1,R).

t([],[]).
t([[S|_]+_/O|X],[t(S,N)|Y]):-N is 1 rdiv O,t(X,Y).
t([[]   +_/O|X],[t(0,N)|Y]):-N is 1 rdiv O,t(X,Y).

c([t(S,A)],[A-S]).
c([t(S,A),t(S,B)|As],Z):-C is A+B,c([t(S,C)|As],Z).
c([t(S,A),t(T,B)|As],[A-S|Z]):-S\=T,c([t(T,B)|As],Z).

o([]).
o([S-A|X]):-format('~t~2f~5+% ~t~d~5+~n',[S*100,A]),o(X).

:-initialization(main,main).
main([A|_]):-
  atom_chars(A,B),p(B,C),!,%writeln(C),
  e(1,M),bagof(D,i(C,[]+M/1,D),E),!,
  t(E,F),msort(F,G),c(G,H),msort(H,I),o(I).