The Nineteenth Byte

emanresu A

00:32

@NewPosts It's been over a week, what are we doing with this?

Mousetail's proposal is at +12/-1, caird's faq-proposed stuff is at +4/-2

lyxal

I'd say both

Bubbler

@Simd Logarithmic time: keep the cumulative sum of run lengths, and use binary search to find the chunk that contains the index x. Constant time: about 85% sure it is impossible, but I don't have a good argument

Unrelated String

01:20

Obviously, you can make it constant time by not compressing it at all

But I feel like there's no way to keep it constant time without the compression only being by a constant factor

Rydwolf Programs

03:40

I hosted a board game party for some of my friends on the same day my roommate hosted a party-party, and we unintentionally made the times overlap, that was interesting

Unrelated String

ahahahaha

Rydwolf Programs

Board game thing is over. Every person there swore we'd meet up again in the two weeks before I leave for college, but idk how many I'll actually see again. Hard to exchange heartfelt goodbyes when drunk people are stumbling around in swimsuits everywhere tho lmao

Rydwolf Programs

04:00

@UnrelatedString same, my intuition is that constant time would be impossible

Rydwolf Programs

04:26

Vague proof: if it was possible, it would imply that you could determine the actual value of the number at index y, by starting the array with a sequence of all possible integers (assuming finite sized integers), then checking them all to find where the algorithm says y is bigger than x (which is constant time if the number of possible values is finite). Under the assumption that finding the nth item in a run-length encoded string in constant time is impossible,

(2/2) it wouldn't be possible

emanresu A

Key words: if the number of possible values is finite

Rydwolf Programs

04:48

Yeah but I can't see changing the values from finite to infinite making it more possible to do it in constant time

emanresu A

True :p

Rydwolf Programs

Also if you can prove a case of the problem with restrictions on it (e.g., the integers are within this range) makes it impossible, you still can't say it's generally possible to do in constant time

I might be missing something subtle from being literally asleep rn tho lol

Just waiting on some potatoes to bake for dinner lol

Got a bag full of potatoes for like $2 best deal ever

Even more cost effective and almost as lazy as canned pinto beans

Except far easier to burn your mouth on lol

Bubbler

05:03

constant compression gang let's go

Simd

05:29

@Bubbler I suppose you can avoid storing a separate array by changing the rle encoding to use the cumulative sum of the run lengths

Bubbler

yes that works

Simd

There are a lot of fancy data structures for compressed data. I just don't know them well enough to know if any would help

Bubbler

05:53

if the length of the sequence is N in RLE notation, and you have M queries in bulk, then you can sort the queries by x (in time M log M, or M if the range of x is fixed) and traverse through the sequence and the queries at once in a manner similar to a merge step in merge sort (in time N + M)

one could argue that this is constant time per query in average

Simd

08:06

That's good idea

mousetail

09:44

CMC A curve that is 0 at X=0.0, 0.5, and 1.0, and 0.25 at X=0.25 and X=0.75. Must be continuous

JS solutions preferred

Bubbler

x=>-64/3*x*(x-0.5)**2*(x-1)

proof by desmos

too lazy to golf

mousetail

Nice! It's a CMC, there is no golfing expectation

l4m2

10:09

What languages are Turing complete with only odd(2k+1) bytes? What even(2k)? What odd-parity? What even-parity?

Adám

10:19

@mousetail f(x) = −21⅓x⁴ + 32⅔x³ − 26⅔x² + 5⅓x found with 0 0 0 0.25 0.25⌹∘.*∘⍳∘≢⍨0 0.5 1 0.25 0.75 in APL.

@l4m2 Probably not what you intended, but an interpretation of your first question is for the code source to have an odd number of bytes (i.e. not the bytes themselves being odd). This is so for the I language because even-length programs aren't even valid.

emanresu A

10:43

Philosophy's just maths sans rigor, sense and practicality

New Posts

11:00

0

Q: Cubic Concatenation

Challenge Given three non-negative integers \$a, b\$ and \$c\$, decide if the sum of their cubes is equal to the concatenation of those numbers, aka: $$ a^{3}+b^{3}+c^{3} = a^\frown b ^\frown c $$ Test cases Truthy (1,5,3) // 1^3 + 5^3 + 3^3 = 153 (2,2,13) (4,0,7) (10,0,0) (10,0,1) (22,18,59) (98...

emanresu A

@NewPosts Sometimes I wish vyxal had a 1-byte dot product

And then I look at my plans for a vyxal 2 fork and never do anything about them

Adám

@emanresuA How would that help?

emanresu A

square, dot product, input, concat, eq?

If I have a hypothetical D dot product, then *D (multiply by self, dot product with self) saves a byte over 3e∑ (cube each, sum)

Adám

Oh, the "self" is implicit when only one arg is provided?

emanresu A

Yeah arities are fixed

Adám

11:10

Then I understand why it'd help.

emanresu A

There's probably a 5 in Jelly with some weird chaining (although idr if jelly has a 1-byte way to concat an int list)

Adám

@NewPosts More interesting problem is how to find such triplets without brute force.

emanresu A

Never mind there's a 4 in jelly

what

I'ma go to sleep now, md5 of my solution is 3e99c8d7e8190c968310de705f803a4b and it's probably unique

lyxal

@emanresuA you sound like the kind of person who'd enjoy vyxal 3

Adám

I've found a truly horrid codegolf JavaScript solution to this:

CMC: Dot product of a given list with itself.

lyxal

11:30

@emanresuA Vyxal 3, 5 bytes: ²ḋ?“=

@Adám Vyxal 3, 1 byte: ḋ

Adám

Right, now do it in JS.

lyxal

Vyxal 3 online interpreter is written in js

QED

You good chat?

Reloading the page fixed it, but it did a very silly

Adám

@lyxal OK, now golf it in JS.

lyxal

The javascript file is minified before publishing

QED

Adám

I'd say that automatic minification of an answer does not constitute a serious contender.

lyxal

11:41

It goes from 186645 lines of code to 163281 lines of code

I'd say that's some pretty good golfing :p

Adám

Why doesn't it inline everything?

lyxal

for some semblance of readability and debugging?

you'd have to ask the people who made scala.js

Adám

Of minified code‽

lyxal

well see it's taken Scala (not javascript) and transpiled it to JavaScript (definetly javascript)

it's not 100% unminified (putting it into a unminifier expands it, and there are some funky names and so on)

keep in mind I'm submitting the entire interpreter as my submission :p

@Adám but if I'm not being silly: f=>f.map(x=>2*(x**2)).reduce((x,y)=>x+y)

(I don't javascript very often)

Adám

11:58

@lyxal What's the 2* about?

lyxal

multiplying by 2

obviously

wait

that's not how dot product works is it

att

all that comes to mind for me is a=>a.map(b=>c+=b*b,c=0)|c

Adám

I have a (horrible, horrible, never ever do this) 19 byte (not counting a=>) solution.

Unrelated String

12:23

@Adám Needless to say, ḋ for 1 in Jelly, but now I'm wondering if there's also a single-builtin solution in some stats praclang like R

Adám

+.×⍨ in APL, btw.

mousetail

/+×. in Uiua

att

12:39

mathematica is #.#&

Neil

13:47

@emanresuA 2i of course

mousetail

So there exists an E programing language. This means only GILMNOUWXY are left counting F#, Q#, and Z3

noodle person

@mousetail M is a Jelly derivative

I is an array language made by the guy who made BQN

mousetail

If it doesn't have a wikipedia page it doesn't count

Neil

@Bubbler I came up with x=>x*(1-x)*(1-x-x)**2*16/3, very similar but just the one byte shorter

Bbrk24

@mousetail The I programming language was just mentioned earlier in the conversation, I just read the backlog

mousetail

13:57

I didn't notice but it may have subconciously influenced me to make this list

noodle person

do .o files count as an O programming language? :P

Unrelated String

🤔

lyxal

2 mins ago, by mousetail

If it doesn't have a wikipedia page it doesn't count

noodle person

they have a wikipedia page Object file

lyxal

mousetail

13:59

@noodleperson If it not listed as a programing language on wikipedia it doesn't count

noodle person

Ok fair lol

It's just listed as a file format, not a programming language, afaict

Neil

I also tried x=>.25-Math.abs(Math.abs(x-.5)-.25) which is too long and x=>Math.sin(x*Math.PI*2)/4 which isn't exact

noodle person

with(Math)f=x=>.25-abs(abs(x-.5)-.25) ?

Neil

probably x=>.25-(a=Math.abs)(a(x-.5)-.25)

Bbrk24

@lyxal I had already typed the message by the time he sent that

Unrelated String

14:05

@emanresuA ...I came up with two (trivial variations) and it doesn't seem like either of them have that hash :P

I was using ⁼ instead of = since it was a modification of Jonathan Allan's posted answer

mousetail

14:20

> DWARF is a widely used, standardized debugging data format. DWARF was originally designed along with Executable and Linkable Format (ELF), although it is independent of object file formats.[1] The name is a medieval fantasy complement to "ELF" that had no official meaning, although the name "Debugging With Arbitrary Record Formats" has since been proposed as a backronym.

I love how programmers name things

Adám

@mousetail Q exists.

noodle person

Q (programming language from Kx Systems)

Q is a programming language for array processing, developed by Arthur Whitney. It is proprietary software, commercialized by Kx Systems. Q serves as the query language for kdb+, a disk based and in-memory, column-based database. Kdb+ is based on the language k, a terse variant of the language APL. Q is a thin wrapper around k, providing a more readable, English-like interface. One of the use cases is financial time series analysis, as one could do inexact time matches. An example is to match the a bid and the ask before that. Both timestamps slightly differ and are matched anyway. == Overview... ==

mousetail

Oh no! 3 unrelated Qs

Simd

15:28

Have we ever had a challenge on Elias-Fano encoding?

antoniomallia.it/….

noodle person

@mousetail What's the third? There's Q#, and there's Q for kdb+

mousetail

Pure (programming language)

Pure, successor to the equational language Q, is a dynamically typed, functional programming language based on term rewriting. It has facilities for user-defined operator syntax, macros, arbitrary-precision arithmetic (multiple-precision numbers), and compiling to native code through the LLVM. Pure is free and open-source software distributed (mostly) under the GNU Lesser General Public License version 3 or later. == Overview == Pure comes with an interpreter and debugger, provides automatic memory management, has powerful functional and symbolic programming abilities, and interfaces to libraries...

mousetail

16:00

Q is listed as being influenced by the other language named Q somehow

Simd

16:23

@mousetail I think Q is used in banking

The_AH

esolangs.org/wiki/Digitial

First esolang I have made with a wikipage. :)

Do not ask why the page name and language name don't equalize.

mousetail

16:39

Nice! Welcome to the club

The_AH

Thanks for the compliment.

My next idea is a stack-based language where there is only an instruction to go forward in the tape and the tape is of limited scope, and whence you reach the end it goes back to the beginning. Does minimize number of instructions but would be hard to use.

Honestly I have a lot of ideas but most of them are not worth pursuing.

mousetail

@The_AH Interesting, though that wouldn't be Turing complete

RubenVerg

@The_AH this gave me an idea for a joke esolang, probably been done before

The_AH

How come?

RubenVerg

it starts with python, you replace byte with a string of ord(byte) of the same character

after that you do RLE

and then you notice the actual characters in the RLE aren't needed, only the fact that two sequence are different

The_AH

16:54

I was asking mousetail.

About the turing-complete thingy.

RubenVerg

then you notice all RLE lengths are at most 255 so you can encode them as bytes

and boom! you're back to python!

The_AH

@RubenVerg Interesting.

RubenVerg

@The_AH yeah just wanted to explain it to know if it's already been done

seems like a dumb joke so surely it's been done?

The_AH

I'll search for it.

And let you know if I find anything.

mousetail

@The_AH You'll have only a finite amount of storage, and increasing it would break every program

The_AH

16:57

It says nothing about an infinite set of tape.

mousetail

Unlike say BF which could be implemented with any arbitrary amount of storage and programs will behave the same

The_AH

I mean the first Turing machines themselves would probably have had a finite amount of tape.

mousetail

Turing machines are a hypothetical concept, they can't be built

The_AH

That's what we're going by "Turing complete" though, something that works like the original Turing machines. That's where it gets it's name from.

@mousetail I'd say it's a metaphor.

I mean a computer is just a fancier Turing machine.

mousetail

No, that's not what Turing complete means. A language is turing complete if it can simulate a hypothetical Turing machine. Not some real device

The_AH

16:58

I meant the concept.

As originally thought by Alan Turing.

But I don't get how that helps your argument in particular.

mousetail

@The_AH Wouldn't you need ">" as many times as your tape length to get back? So wouldn't that mean you require a finite length of tape

And every program would break if you change the size of that tape

The_AH

If you change the size that would be a completely different language.

Since it wouldn't match the spec.

Actually.

mousetail

Exactly

The_AH

I think allowing you to yourself set the tape size...

mousetail

So it's impossible to implement a language that follows the spec and is Turing complete

The_AH

17:00

might keep it Turing complete.

Though it would add more instructions.

mousetail

@The_AH That wouldn't be enough, a Turing machine needs to be able to simulate any arbirary other Turing machine. So a program needs to be able to simulate a program with a larger tape size

The_AH

One minute.

I feel like I am not understanding this correctly but..

That doesn't seem to make sense?

It's like saying if we have an array x in one program.

And that array x is restricted to ten items, it wouldn't be Turing complete?

I know that's a poor comparison.

But that's the best I can put it into words.

mousetail

That's correct. You couldn't implement any language that uses more than 10 items in that

The_AH

But in C for example you need to allocate memory beforehand.

You could practically implement that.

And now you're saying C wouldn't be Turing-complete?

mousetail

You can allocate memory at runtime in C with malloc, or just by pushing more stack frames

The_AH

17:05

But say if this instruction would exist

By the terminology isn't it implied you could change the tape size in runtime?

I mean there isn't anything limiting that by my definition of the instruction.

And then what difference is there from the array in C example?

mousetail

If you can increase the tape to an arbitrary value based on the input it may be Turing complete

But if a program needs to specify it in advance then it is not

The_AH

Okay for example take this hypothetical code:

set tape size to 50
move by one
add one
set tape size to 100
move by two
add one
blah blah

Would this make it Turing complete?

@mousetail I interpret this as you being able to run it multiple times as you wish in runtime.

mousetail

If it's possible to create a program like t = input(); set_tape_size(t) and there is no limit to the size of t

The_AH

That would be possible.

The size of t itself would not be limited.

mousetail

Then it might be Turing complete

The_AH

17:09

One thing, if you would lower it, the variables now out of scope would be wiped.

mousetail

Might I suggest creating a increase tape size by instead of set tape size? Seems way more convenient. You could or could not support negative values but I doubt that would be useful

The_AH

What would engativr values even do?

mousetail

Decrease the tape size by that amount

The_AH

Oh.

Set seems simpler and more convenient honestly.

mousetail

I imagine more complex programs would create a type of "ladder" where at regular intervals you have some information about the data that follows and you can loop by jumping N steps until you find the data frame you are looking for, in a way that works regardless of the current tape size

The_AH

17:21

Yeah probably.

I'd do increase the tape size actually.

Ooh.

It would be cool if I/O operations were specific tapecells.

For example we could have a range of negative tapecells.

Cell -1 is output, -2 is input.

mousetail

How can you reach negative cells if you can't go left?

The_AH

Actually yeah.

I am stupid.

Okay then we're gonna do cell 1 and 2 be special.

And you start at tapecell 3.

Actually no.

Ohhh.

The most efficient way is...

Actually that might not work too.

mousetail

That sounds like hell but I guess that's why it's an esolang

The_AH

Let me think.

Okay solution.

If your tape size is 100 for example.

We add special I/O cells.

101 and 102 are output and input respectively.

mousetail

That's exactly the same as above

Since you don't know what tape cell you are on

The_AH

17:25

How come?

You can still reach them by going right.

@mousetail You're on one by default.

It doesn't take too much thinking to calculate where you currently are.

After a set of operations.

There's no if-else in this language remember.

mousetail

Yes, but if you start at 3 then do 97 steps and land at 1 it's the same as starting at 1 doing 97 steps and landing at 98

The_AH

That would land you at cell 100.

The first example.

mousetail

/97/98/g

The_AH

We can make a variable to store the current amount if it's really needed.

Like a variable n to store which tapecell you are on.

And move n+100 cells.

mousetail

That's possible

The_AH

17:28

That actually removes the need for looping in that case.

mousetail

It's not necessary but would make the language more convenient.

Though it might be more fun to make your location on the tap not matter at all, a true circle

The_AH

I suppose I would want some practicality.

@mousetail ooh.

mousetail

Adding to the tape always adds at the current position

The_AH

You mean single-item tape?

@mousetail But you can move.

mousetail

Yes, if you move then add to the tape it will add to the new location

The_AH

17:29

And I think it's implied adding to the tape would always add at current position.

mousetail

I mean when you expand the tape and add new cells

The_AH

Oh.

Honestly we could just get off with the moving and do t[n]=number.

An esolang based around variable declarations and assignations.

Though that's too wild from my current idea, probably best implemented in a separate esolang.

mousetail

That's the fun of creating esolangs :)

The_AH

Yeah.

I haven't had such a good conversation in so much time.

I should really be here more often.

DLosc

19:05

@The_AH If you want to discuss esolangs and esolang development, we also have a dedicated chatroom for that: The Tarpit

Nothing wrong with discussing it in TNB, but The Tarpit could use some more traffic. ;)

emanresu A

19:37

@UnrelatedString Maybe I messed things up with the hashing, I had ḋ²=V

Sandbox Posts

20:27

0

A: Sandbox for Proposed Challenges

Print self Write a shortest progam, that will output itself to STDOUT without referencing itself (for example via file). Standart IO rules applied

Unrelated String

@emanresuA ...Oh, it looks like chat ate the message in between where I explained that I did find one with that hash :P

I tried ḋ²⁼V and ²ḋ⁼V first

emanresu A

The second one chains correctly? huh

And yeah I forgot Jelly had two eq builtins (I don't know why I did, vyxal does too)

Rydwolf Programs

22:46

emanresu A

22:56

THE RETURN

Unrelated String

YOOOO

@emanresuA It's monadic

Seggan

so im building a compiler to chef and i have a sort-of assembly language to it already

now im building a lisp for it, but im kinda stuck on how i should implement arrays/lists/strings

because chef doesn't have any form of random access structure, just a bunch of (statically accessible) stacks

Unrelated String

You can use a pair of stacks for random access in linear time

Rydwolf Programs

You can make a tape with two stacks, which can work as (highly inefficient) random-access memory

ninja'd lol

Unrelated String

lol

Seggan

23:07

yeah i thought of that solution too i just thought yall might have better ideas than me :P

Rydwolf Programs

If you had a known finite number of stacks that's greater than two, you could maybe do some complicated towers of hanoi stuff to keep multiple hot addresses near the tops of the stacks

Seggan

hrm

how have i never heard of this "towers of Hanoi" thing

Unrelated String

Wait, can you also use the "stir" instruction(s)?

Seggan

yeah that is one of my best weapons for going around chefs limitations but sadly negative rotations are undefined and rotation > stack size simply are floored to the stack size

Unrelated String

Ah

Seggan

23:11

tbf im already relying on undefined behavior such as assuming decimals and negative numbers are a thing

but every interpreter ive seen allows that

not so with rotations

Rydwolf Programs

Is there no way to check if the index is negative/out of bounds?

Seggan

checking stack size is not a thing and checking negatives takes a ton of code

Rydwolf Programs

'cause unless I'm misreading it it seems like the stir instruction would allow logarithmic-time accesses

Unrelated String

Oooh true you could rotate it back pretty smartly that way

Rydwolf Programs

(not constant since you still need to be able to index correctly after the rotation occurs)

Seggan

23:14

*edited the "not" into my message :P

Unrelated String

@Seggan You don't really need to do that, especially if the lists are only an internal construct

Rydwolf Programs

@Seggan could you not track the stack size separately?

Unrelated String

Hell you can even track the yeah that

Seggan

@RydwolfPrograms yeah i could

@RydwolfPrograms how?

still seems O(n) to me

Rydwolf Programs

wait yeah the rotation's the opposite direction as I initially read it as

O(1) insertion operations tho :p

Seggan

23:18

*assuming its at the end

my ultimate intention is basically to build a GP language on top of chef, and for that i need at least some sort of heap

Rydwolf Programs

You could maybe take advantage of the fact that most uses of lists work with the items sequentially, and stirring essentially turns the stack into a looping iterator

Seggan

yeah was thinking of that optimization

i suppose i could do it like repeat (size - index) { rotate size; } *reading stuff goes here* repeat (index) { rotate size; }

Rydwolf Programs

You might even have to like, decompile lower-level constructs assuming constant-time pointer accesses into higher level things that stirring/tapes allow more efficiently

Seggan

yeah

or just add those operations into the language already optimized :P

user

23:35

@RydwolfPrograms Wait is tanks making àcomeback? Please say yes

Seggan

hrm wait what if i use @emanresuA's strat of making memory a giant integer

problem is theres no mod operation for chef :/

Transcript for