The Third Stack

quartata

00:31

@DJMcMayhem Writing n choose k function. I'll see how well I can do

DJMcMayhem

00:42

OK cool

quartata

What's the shortest current stack safe multiplication?

Actually since it's n * (n -1) I bet n^2 - n is shorter...

Wheat Wizard

01:05

@quartata use Triangle * 2

Oh wait n*(n-1) not n*(n+1)

@quartata brain-flak.tryitonline.net/…

quartata

Unfortunately I think I need to bust out actual multiplication for this

quartata

01:23

I want to modify multiplication so that it also pushes a copy of the second operand - 1 on top of the result but I can't really read the multiplication code well enough to figure out where to place it

I think I've got everything else figured out

Wheat Wizard

@quartata I'll take a stab at it

brain-flak.tryitonline.net/…

quartata

Whoa that was fast

Wheat Wizard

@quartata This one is a little better: brain-flak.tryitonline.net/…

quartata

01:39

All right. That should give me an 86 byte answer, I'll post it (I think there was a main challenge for this) later

Thanks

PhiNotPi

05:40

@WheatWizard made some nice progress on the interpreter

Wheat Wizard

@PhiNotPi Nice. In Java right?

PhiNotPi

yes

input     (({}()))(([{}<>()])())
processed (((){}))(()([(){}<>]))
Left input arity 1
 [1, 1]
Right input arity 0
 [-1, -1] [-2, -1]

^ output from my program. Each set of numbers in square brackets represents a single number on the stack.

The numbers in the list are coefficients.

It turns out that, ignoring the {n} and [] commands, it is extremely easy to tell if two snippets are identical.

Wheat Wizard

Ok I think I'm starting to understand how this works

PhiNotPi

05:55

I have stacks of expressions instead of stacks of numbers. Expressions are defined by a list of numbers representing coefficients. An expression of [7] represents the number 7, an expression of [0, 5] represents 5*A, [0, 0, 9] represents 9*B, etc.

The stacks are initially empty. Each time an empty stack is popped, it returns a new expression of the form [0, 0, ..., 1] representing a new variable never before seen.

Expressions can be added or negated, which is really easy to do by just adding the lists of numbers together item-by-item.

Wheat Wizard

What do you mean by coefficients?

PhiNotPi

The numbers indicate how much each variable is multiplied by in that expression.

Wheat Wizard

can you get A+1

?

PhiNotPi

A+1 is [1, 1]

Wheat Wizard

oh ok

so it a tuple representing a linear relation

PhiNotPi

06:04

yes

Wheat Wizard

so what does ({}{}) output?

PhiNotPi

Left input arity 2
 [0, 1, 1]
Right input arity 0

Wheat Wizard

Wow this should make it quite easy to find replacements

PhiNotPi

Here's my proposed auto-golfing method for simple snippets: interpret the snippet like the above examples to figure out exactly what it does, and then the auto-golfer attempts to find other snippets that do the same thing.

Wheat Wizard

Yeah we just need to make a good algebra engine.

PhiNotPi

06:15

The first step will be brute-forcing a lot of short programs to build up a decent table. Then, there are probably intelligent ways to attempt to combine short snippets so that they give the target snippet.

Wheat Wizard

How does it handle push order?

PhiNotPi

Give me some example code and I'll run it.

Wheat Wizard

e.g. what does ({}<({}<>)<>>)<>({}<>) output?

PhiNotPi

Left input arity 2
[0, 0, 1] [0, 1]
Right input arity 0

the left-most list should be the top of the stack

Wheat Wizard

what do the two separate lists represent?

PhiNotPi

06:18

the two values on top of the stack

Wheat Wizard

That program should reverse the order of the top two stack items

PhiNotPi

What this snippet does is swap the top two items on the stack.

ninja'd

Wheat Wizard

ok

PhiNotPi

[0, 1] [0, 0, 1] is what the output would be if it didn't swap them

Wheat Wizard

I am still a bit fuzzy on the notation but the concept seems to make sense to me

ok what about (({})<(([{}]({})))>)({}{}<([{}]{})>) ?

PhiNotPi

06:23

Left input arity 2
 [0, 0, 1] [0, 1, 0]
Right input arity 0

it does the same thing

Wheat Wizard

ok thought so

seems really good all thats left to make a quite decent golfer is the program finder

PhiNotPi

I need to catch some sleep.

I'll keep working on it tomorrow.

Good night!

Wheat Wizard

good night

ASCII-only

Looks like the easiest way to brute force is to convert to binary, pad to a multiple of 3 bits, and taking three bits at a time, take two bits to select paren type, one bit to decide whether to put it beside or inside

Wheat Wizard

@ASCII-only I think we want to be a little more delicate than that. There are lots of ways we can really narrow the scope

ASCII-only

06:34

@WheatWizard Like golfing numbers as well and adding numbers as a possibility for the brute forcer?

Wheat Wizard

For instance we can shuffle the braces around a little so that {...} and [] are represented by the same type of brace and then ignore that brace.

DJMcMayhem

15:15

@PhiNotPi Wow, the progress you've made looks really nice! I have a couple quick questions. 1) Is the code on github or something similar yet? I'd like to look at it. 2) I think I understand the array syntax you're using, but I'm not positive. What does (({}){}) output? (Double the TOS) what about (()()())?

PhiNotPi

@DJMcMayhem I haven't made a GitHub yet.

Left input arity 1
 [0, 2]
Right input arity 0

retval [0, 2]

I've added "retval" to represent the return value of the expression. Two arbitrary snippets typically need to have the same return value to be equivalent, but in some cases (like inside <n>) the return value doesn't matter.

for the second snippet:

processed (()()())
Left input arity 0
 [3]
Right input arity 0

retval [3]

I think I have a cool idea as to how to represent these operations (once again, ignoring [] and {n}): as matrices.

DJMcMayhem

Now I think I'm more confused. What does the first 0 represent?

PhiNotPi

The first number in each list is a constant, all others are variables.

DJMcMayhem

15:31

So [a, b] represents a + TOS * b?

Does that mean (({}){}()()) would return [2, 2]?

PhiNotPi

input     (({}){}()())
processed (()()({}){})
Left input arity 1
 [2, 2]
Right input arity 0

retval [2, 2]

yes

[a, b, c, d] = a + TOS * b + 2nd TOS * c + 3rd TOS * d

But... wow, these operations are literal matrix multiplication.

DJMcMayhem

How does that work across multiple stacks? What would ({}<>) give?

PhiNotPi

input     ({}<>)
processed ({}<>)
Left input arity 1

Right input arity 0
 [0, 1]
retval [0, 1]

DJMcMayhem

Hmm, OK. It makes sense now, but it seems like there needs to be a way to distinguish which stack the retval goes to. Because the TOS in the retval is the top of the left stack, but it's pushed on to the right

PhiNotPi

yeah... there's actually a few more pieces of state information that aren't currently given in the text output.

DJMcMayhem

15:40

And you could have something like (({}()())<>[()])

Which has multiple retvals on multiple stacks

PhiNotPi

input     (({}()())<>[()])
processed ((()(){})<>[()])
Left input arity 1
 [2, 1]
Right input arity 0
 [1, 1]
retval [1, 1]

retval is the return value of the entire snippet

so there's only one

DJMcMayhem

Ooooooh I get it know

PhiNotPi

What I'm going to do next is create a Class file specifically to hold the output above and additional state information.

DJMcMayhem

But the right output is 1 + 1 * LA not 1 + 1 * RA (a == TOS)

PhiNotPi

That is what is shown. As displayed, there's not a label as to which coefficient represents which stack.

DJMcMayhem

15:50

Oh okay. What if you used that syntax for displaying? [1, 2la, 3lb] etc.

PhiNotPi

Yeah, I probably should.

Hmm... I'm trying to figure out the best way to represent this information.

Because, given two results, I want a way to combine them to give the result of concatenating the two snippets together.

PhiNotPi

19:41

Right now I'm screwing around trying to get hashCode() to work right.

finally

PhiNotPi

20:18

()()()
()(){}
()()<>
()(())
()[()]
()<()>
(()())
[()()]
<()()>
(){}()
(){}{}
(){}<>
()({})
()[{}]
()<{}>
((){})
[(){}]
<(){}>
()<>()
()<>{}
()<><>
()(<>)
()[<>]
()<<>>
(()<>)
[()<>]
<()<>>
(())()
(()){}
(())<>
((()))
[(())]
<(())>
[()]()
[()]{}
[()]<>
([()])
[[()]]
<[()]>
<()>()
<()>{}
<()><>
(<()>)
[<()>]
<<()>>
{}()()
{}(){}
{}()<>
{}(())
{}[()]
{}<()>
({}())
[{}()]
<{}()>
{}{}()
{}{}{}
{}{}<>
{}({})
{}[{}]
{}<{}>
({}{})
[{}{}]
<{}{}>
{}<>()
{}<>{}
{}<><>
{}(<>)
{}[<>]
{}<<>>
({}<>)
[{}<>]
<{}<>>

I found a way to iterate through all simple snippets.

Wheat Wizard

@PhiNotPi Looks nice. Do you have any filters for bad programs? e.g. <<...>>

PhiNotPi

I need to add filters.

Also, to clarify, I am generating the program in tree form, and then converting to string for output, not the other way around.

PhiNotPi

20:34

Unfiltered gives 135 programs, for reference.

DJMcMayhem

20:55

FWIW, <<>> is also redundant, since <> already evaluates to 0

Which makes me wonder, is {{...}} ever not redundant?

PhiNotPi

I've already filtered for stuff like <<>>, now I'm working on eliminating <><> and also choosing a single ordering when multiple orderings are identical, like ()<> instead of <>().

I've gotten the 135 down to 82 length-6 snippets.

I'm pretty sure {{...}} is totally redundant.

But I'm not generating any looping code right now.

I'm bumping it up to length-8 snippets for testing... 1134 unfiltered.

length-10 has 10206 unfiltered

reduced to 3333 when filtered

actually 2258 now

Wheat Wizard

21:25

The number of programs of length n should be 3^n * catalan(n)

Catalan number

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894). Using zero-based numbering, the nth Catalan number is given directly in terms of binomial coefficients by C n = 1 n + 1 ...

PhiNotPi

wouldn't it be 3^n * catalan?

Wheat Wizard

yes my mistake

PhiNotPi

21:39

I think I have length-10 down to 2122

Wheat Wizard

Are you filtering out <>(...)?

PhiNotPi

I'm filtering out (<>...) instead

PhiNotPi

22:16

@WheatWizard current filtering results for short snippets:

1 'empty'
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 ()[()] CHECK AGAINST 'empty'
*28 ()<()>
29 (()())
30 [()()]
*31 <()()>
*32 (){}()
33 (){}{}
34 (){}<>
35 ()({})
36 ()[{}]
37 ()<{}>
38 ((){})
39 [(){}]
*40 <(){}>
*41 ()<>()
42 ()<>{}
*43 ()<><>
44 ()(<>)
*45 ()[<>]
*46 ()<<>>
*47 (()<>) POSSIBLE UNIQUE
*48 [()<>] POSSIBLE UNIQUE
*49 <()<>>

The asterisk means that it is filtered out. The "check against" means something got through the filter that shouldn't have (although there is a slim chance of hash collision). The "possible unique" means that something may have been incorrectly blocked. Most of those "uniques" are actually duplicates of snippets that hadn't been tried yet.

looks like I need to implement [...<>] == [...]<> and <...<>> == <...><>

1000000000

22:43

Craneflak v1.0.0 is out github.com/1000000000/CraneFlak

1000000000

23:57

Doing some benchmarks on CraneFlak on my crappy netbook, it looks like it runs about 8 times faster than the Ruby Brain-Flak interpreter once initialization time becomes small enough compared to the overall running time.

DJMcMayhem

Doesn't surprise me

Transcript for