Stack Exchange
log in

Steven H.

 The Nineteenth Byte

The Nineteenth Byte: General discussion for codegolf.stackexc...
9
Steven H.
Mar 10, 2018 03:37
@ConorO'Brien I think that's an old version that got saved... derp. fixed version is 46 bytes
Steven H.
Mar 9, 2018 02:20
@ASCII-only Because I actually figured out how brainflak debug options work and took the time to verify
Steven H.
Mar 9, 2018 02:14
This one's definitely stack-clean
Steven H.
Mar 9, 2018 02:13
@ConorO'Brien 44 bytes
Steven H.
Mar 9, 2018 02:02
/s
Steven H.
Mar 9, 2018 02:02
implying there's programming other than code golf
Steven H.
Mar 9, 2018 02:01
@ASCII-only I mean, comparatively to non-esolangs hexagony is really hard to golf in
Steven H.
Mar 9, 2018 01:59
I'm bad at Brain-flak though so I'm not sure how to tell if it's stack-clean, and I lost track of stacks halfway through making it
Steven H.
Mar 9, 2018 01:58
@ConorO'Brien 56 bytes, but it might be more golfable than DJ's solution: Try it online!
Steven H.
Mar 9, 2018 01:51
@ConorO'Brien I wasn't planning to go too in-depth, but rather just describe the concept of golfing esolangs and some of Jelly's builtins as examples... not as much how said builtins interact in chains
Steven H.
Mar 9, 2018 00:34
@ConorO'Brien Duplicate as in (a b c) -> (a a b b c c), or (a b c) -> (a b c a b c)?
Steven H.
Mar 9, 2018 00:34
Befunge is a good idea, I'll definitely do that
Steven H.
Mar 9, 2018 00:30
I'm trying to compile a list of neat ideas that esolangs have put forth but that can be easily explained. I want to present kind of a "best of esolangs" to my coworkers... Any suggestions for specific languages to talk about? So far, I'm planning to bring up Hexagony, Jelly, and Brainflak (as examples of languages that are designed to be hard to program in, golfing languages, and turing tarpits respectively)
 

 Ordinality?

Trying to understand extraordinarily large numbers.
Steven H.
Jan 17, 2018 13:28
if it still doesn't make sense I can try to explain it with diagrams now that I actually am back at my apartment and winter break is over so I have access to my desktop
Steven H.
Jan 17, 2018 13:22
@SimplyBeautifulArt Hopefully that makes some sense?
Steven H.
Jan 15, 2018 05:46
I can make the result of the entire function a lot bigger if I make N something else... but I can't think of any good cheap functions of arbitrarily many elements
Steven H.
Jan 15, 2018 05:43
Reads out the 1100000000000_2 and returns it
Steven H.
Jan 15, 2018 05:42
N just kinda undoes that
Steven H.
Jan 14, 2018 17:13
We add each group as children to the first breadth-first-search-wise node we haven't added children to yet. That means "100" is added as the root node's children, then 000 is added to the child 1, then 000 is added to the first child 0, and then 000 is added to the second child 0, and then there's no groups left to add
Steven H.
Jan 14, 2018 17:09
We split these up as 1 100 000 000 000
Steven H.
Jan 14, 2018 17:06
so now we have 1100000000000_2
Steven H.
Jan 14, 2018 17:04
The first one that we could fill this to is two levels, which requires length 4, but that would put a 1 in the last level so we need to pad to 13 instead
Steven H.
Jan 14, 2018 17:03
More in depth on t(3,3): we first represent 3 as its binary representation, 11_2. That has length 2, which can't possibly fill all 3 children. The lengths of flat representations of valid trees are sums of all powers of 3: 1, 1+3^1=4, 4+3^2=13, 13+3^3=40, etc
Steven H.
Jan 14, 2018 16:55
All of these work off the binary representation: t(x,3) uses the binary representation of x
Steven H.
Jan 14, 2018 16:54
I can get a diagram for that when I get home
Steven H.
Jan 14, 2018 16:53
t(3,3) returns a tree with three layers: the top node has value 1, its first child has value 1, and all the other nodes have value 0
Steven H.
Jan 14, 2018 16:52
t(2,3) returns the same exact tree as 1,3
Steven H.
Jan 14, 2018 16:51
t(1,3) returns a tree with tree.v == 1 and tree[0] == tree[1] == tree[2] == (leaf node with v==0)
Steven H.
Jan 14, 2018 16:49
t(x,y) translates a number into a tree of 1s and 0s with y children for each node. It pads enough 0s so that the last row is all 0s and that the tree is full (all filled out ot the same level). t(0,x) = [0], which denotes a tree node tree with tree.v == 0 and no valid values for tree[i] because it's a leaf node.
Steven H.
Jan 13, 2018 21:48
Eventually, the only 0s will be on leaves, which will replace themselves and then execution will terminate.
Steven H.
Jan 13, 2018 21:46
Starting to generalize, a replacement will make future branches larger but will make future replacements smaller and smaller until they become nonexistent. Since it only affects future branches, there's no way to make recursion infinite.
Steven H.
Jan 13, 2018 21:44
Now for a slightly more complicated case, with one branch 0. It will replace all the leaf nodes after it in traversal order with 0s, but after that the tree becomes one with only 0s as leaves again.
Steven H.
Jan 13, 2018 21:42
(the above is why I do replacements with t(x,3) before recursing, so I can guarantee to not get stuck like that and miss out on growth.)
Steven H.
Jan 13, 2018 21:40
In a tree with 0s only as leaves, it is also trivial to see that no expansion of the tree occurs, and execution will terminate.
Steven H.
Jan 13, 2018 21:39
In the simplest case, where there are no 0 nodes, it's trivial to see that traversal will complete; the tree gets read as a large series of nested for loops.
Steven H.
Jan 13, 2018 21:37
Traversing through a branch node with value 0 at index i will cause the number of 0s in D to increase by C_i * (d_i-1) -1. Leaf nodes will cause a decrease of 1 to the same quantity.
Steven H.
Jan 13, 2018 21:25
And let the number of 0 nodes after this node in traversal order be C_i. Traversal order means any 0 node that is a child of any node to the right of the i'th node and to the right of the i'th node's ancestors.
Steven H.
Jan 13, 2018 21:21
Let the depth-first search of nodes in the tree be D = [1, ..., 0,0,...0]. Let d_i denote the number of 0 nodes that are children of the node represented by D's ith element.
Steven H.
Jan 13, 2018 21:18
I can guarantee that this terminates, by the way. Recursion depth that replaces the tree is limited by x, which only strictly decreases, so it suffices to show that traversing each individual tree terminates:
Steven H.
Jan 13, 2018 21:11
let me know
Steven H.
Jan 8, 2018 00:42
That's fine. I'm going to be out of town on a trip, so no worries if it takes you a bit to get through this.
Steven H.
Jan 7, 2018 19:35
but they work to translate
Steven H.
Jan 7, 2018 19:35
pyth.herokuapp.com/?code=ius.esFbk.g%2BIk%5B%29GQ%292 And likewise for N; copypaste output from t into N and it'll be larger by a fair amount because they're more worried about largeness than correctness
Steven H.
Jan 7, 2018 19:14
pyth.herokuapp.com/… If you're having a tough time visualizing how t works, here it is in program form!
Steven H.
Jan 7, 2018 19:07
g(1) = h(1, t(1,3),t(1,3))

t(1,3) pads the 1 so that it has three `0` children, making the bitstream 1000 and the tree itself [1,[0],[0],[0]]. N(t(1,3)) = 8

h(1,[1,[0],[0],[0]], [1,[0],[0],[0]])
I'll call the reference to the original root `a` for convenience
m += 8
a = [1+8=9, [0],[0],[0]]
now iterating 9 times:
a = [9, [m],[0],[0]]
m += base2(1001100100) = (in the first iteration) base2(1001101100)
Now we get to fun stuff that starts to get grotesquely big, and I start to lose track.
I'm just going to go through the first iteration.
Steven H.
Jan 7, 2018 19:07
And, since we love examples, let's do a few (meaning one and a little bit):

g(0) = h(0, [0], [0])

m += N([0]) = 0
[0].v == 0, so we go down the first path
After we replace the 0 with 1, there's no 0 nodes in Root, and m = 0 to begin with so we don't go through this for loop at all ._.
g(0) = 0
Steven H.
Jan 7, 2018 19:07
h(x, Tree, Root) =
	m += N(Root)
	if x >= 0:
		if Tree.v == 0:
			Tree.v = m or 1
			if Tree.n > 0: # i.e. this is not a leaf
				R(Root,Tree)
			for i in range(m):
				m += N(Root)
				j = R(t(m+1,3),t(x,3))
				h(x-1, j,j)
		else:
			Tree.v += m
			for i in range(Tree.v):
				for a in range(Tree.n):
					h(x,Tree[a], Root)
				if Tree.pn + 1 < Tree.p.n:
					h(x,Tree.p[Tree.pn + 1], Root)
	return m
Steven H.
Jan 7, 2018 19:07
g(x) = h(x, t(x,3), t(x,3)) where
Steven H.
Jan 7, 2018 19:07
Then let m be a global value, and:
Steven H.
Jan 7, 2018 19:06
Also, define a function R(ReplaceIn, ReplaceWith) to replace all nodes with a value of 0 in ReplaceIn but not in or depth-first-search-wise preceeding ReplaceWith with ReplaceWith, copying the children of the original 0 node to every leaf of the replacing ReplaceWith.