The Nineteenth Byte

New Main Posts

00:29

0

This is inspired by the excellent Visualize Visual Eyes challenge. It is posted with permission from and credit to @Jordan We are going to create an ASCII art approximation of the Xeyes challenge but without worrying about the actual mouse movements. Just the positions. Overview In all cases t...

code-golf

totallyhuman

01:11

is a challenge author allowed to accept an answer that's not the shortest on a code-golf

DJMcMayhem

@totallyhuman No, but theoretically there's nothing stopping them

ATaco

Often times the accepted answer isn’t the objective winner due to answers after the OP has given up on the challenge

Leaky Nun

01:45

hi everyone

MD XF

@Mego self-nominations allowed?

Anonymous

@MDXF Last sentence of the second paragraph on the post

MD XF

@Mego Aha thanks, sorry about that

Does anyone have a handy SEDE query to find the top, say, 50, highest voted answers on the site?

totallyhuman

...or you can use codegolf.stackexchange.com/search?q=is%3Aa+&tab=votes

MD XF

02:07

...oh

CMC (I will award a +50 bounty to the top post of whoever solves this first): Read a Cubically cube-dump (e.g. the one in the debug section here) as input and print the same cube in the input format of this challenge.

user202729

@MDXF CMC can't be awarded...

MD XF

@user202729 I'm saying that if someone manages to solve this, I'll give them rep on the main site

Unihedron

02:26

is there a bounty on Quine in Seed

user202729

I don't think so, but if you succeed then it's likely that someone will give you a bounty.

HyperNeutrino

@Unihedron If you make one I'm sure several people would put a bounty on it. I definitely would lol

MD XF

@Unihedron Do you have one??

user202729

Basically the only way to write a quine is to write the seed decoder from befunge program in befunge.

Unihedron

comrade salute

@MDXF I'm trying

MD XF

02:27

Ah. Are you anywhere close?

Unihedron

I made a plane, but our destination is the moon

user202729

... which will not work because I can't even write the seed decoder in any language.

HyperNeutrino

lol

user202729

and I didn't know Befunge.

MD XF

Do you know how 2d languages work?

Unihedron

02:29

I know befunge and I've been making progress with the decoder, but I need a system to reduce the time it takes to try decoding

it's not like ><> where you have 0-9a-f, it's just 0-9

MD XF

@Unihedron I've got a fast cloud server I could run some code on for you if that would help

Assuming that's what you meant by system

Unihedron

comrade thank

I actually meant an algorithm, so far the hard part has been crunching the right maths and getting ~~the stars~~ the maths to line up with the seed

Anonymous

@Unihedron Decoding? I might be able to help you in a little bit

user202729

Does Befunge have big integer?

Anonymous

Don't think so

Anonymous

02:33

Well, it depends on the implementation

MD XF

@Unihedron Ah. In that case I'm less useful :P good luck though!

user202729

looks for a permutation that support big integer

learn Befunge first

Anonymous

PyFunge might

Anonymous

Since Python does

Anonymous

And Seed on TIO uses PyFunge

user202729

02:34

@MDXF Suggest @NewInfiniteBounty.

MD XF

You mean the meta thread for bounties with no deadline?

Riker

why does wikipedia let you pick comicneue as a font? -.-

user202729

So the bot's name is [New Bounties With No Deadlines]...

Yes.

Riker

MD XF

@user202729 How would that work though? It's not a challenge, just a CMC

user202729

02:36

... then ... how are you going to award the bounty in the first place?

Bounty are supposed to be put on answers, not users.

Οurous

Putting a bounty on a user sounds a touch mercantile for PPCG.

user202729

Reading (some of) the past challenges is painful.

(when our rules were different, there were no such things as non-observable behavior)

MD XF

@user202729 I'd just give it to their best answer. I asked Dennis once if I could give him a bounty on his top answer because of something he did in chat, he said it was fine as long as it was an answer I found worthy of a bounty

user202729

... that feels cheating. I suggest having a main challenge for the CMC.

MD XF

It's such a localized challenge though, it will only be useful to me in the development of Cubically and a cube solver

user202729

02:40

For example, my most upvoted answer is a 5-byte Jelly, which is both FGITW and is a method that many people used (and thus linked to).

MD XF

Then again...

Unihedron

I think prioritizing a bounty on certain users is fine as long as it's not the decisive factor. "This answer is made by a user who did something impressive" is just not the same as "This answer is impressive"

MD XF

@user202729 It wasn't his most upvoted answer. It was his favorite one.

Οurous

@MDXF Most challenges aren't even useful, so you've already beaten them there.

3

MD XF

Ok that's completely true

user202729

02:41

What... now there is cubically.

MD XF

Yep, we have some challenges exclusively for the language

user202729

I don't have any favorite answer TBH.

MD XF

I do, I think it's my most impressive/interesting/hacky answer

Unihedron

wonder if I can knock out two birds with one stone

MD XF

Ok so putting this challenge in the sandbox... what would I even title it?

user202729

02:44

.... now with all requirements must be observable rule, we don't get that many good answers...

Οurous

"Of Dumps and Cubes, and Structured Nonsense"

MD XF

Wow. Remind me to ping you when I need help naming my useless languages

Οurous

Sure.

user202729

... not if it's downvoted and closed.

MD XF

I find that unlikely-ish... it's not trivial, it'll have a clear spec and it'll be on-topic

Οurous

02:48

And isn't that what the sandbox is for anyway?

MD XF

Yep

user202729

I intend to have a language with program structure looks like this...
https://tio.run/##7ZZBDsMgDATv@wp@4Cf13jf47zRqkQpJ1grykkNVpIjLgFGYFX7WWvh4tFHCMUeBI@bjrKF4QSs@zCKKFrT2n6xEW81TtOC23jfo/fGt5qmgoDXWSrTVJAVmnFuPqigwlfyDuoXCTVIIbGPRylDgsrFo5ShQ2Wi0chSYbDxaOQrMtkO0RBSYb/toiSgw43bRElFgKo3RElEIbOuiJaPAZeujpaNAZRsOqKPAZBtPqKP@AfzVAOoehVsegtCq7/IUhcikbnmGwi1d1vLOalWHv6yTX9axr@rMw1s/VfkKheimz@W9QKHWFw

MD XF

Fun fact: My three least voted challenges were the only ones that weren't in the sandbox.

Οurous

I'm pretty sure my only challenge was before we even had the sandbox.

MD XF

Wow idk how I'd (how do you strikeout text in chat) ever write challenges without the sandbox

user202729

03:13

~~abc~~

With ---abc---.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Of Dumps and Cubes, and Structured Nonsense code-golf cubically rubiks-cube Your challenge is to translate a Cubically cube-dump to the format specified in this challenge. Input The input, which you may take via any standard means, will represent a Rubik's Cube, formatted how Cubically prints ...

MD XF

@Οurous @user202729 it's in the sandbox

quartata

@Οurous Definitely not, your PPCG account is newer than the old sandbox

First iteration of the sandbox is as old as 2011 if I'm not mistaken

user202729

Hey, Cubically now have function!

MD XF

@user202729 I pretty much added those so it could do this, they're really useful though

user202729

03:29

I failed to be the first to answer that...

Why don't you just find a cube that's easy to solve?

MD XF

What do you mean?

user202729

43 e 18... that's about 43 e 9 seconds, assuming computer can perform 1e9 moves per second.

So that's about a century. A month is impossible.

I mean, the program will immediately exit after the cube is solved, right?

MD XF

Yeah

user202729

So find a cube that is solvable in a small amount of moves. That's easy.

MD XF

@user202729 Well the way Cubically's interpreter rotates the faces is extremely inefficient (and I completely forgot how it works), were I to optimize that I'm sure it could get a much better moves-per-second time

@user202729 You mean get the inputted cube to a different cube that's easy to solve?

user202729

03:32

The lower bound is a century, trust me.

Yes.

MD XF

How is that any easier than just getting it to the solved cube?

user202729

Why is 0x20 newline?

(it should be a space, and 0x0A a newline)

Unihedron

0x20 is device control 4

MD XF

Because I think I accidentally filled 0x0A in the codepage, and the new parser automatically strips out all spaces anyway

@Unihedron not in Cubically's SBCS

user202729

I think you didn't.

Unihedron

03:34

soz didnt know

user202729

(you indeed didn't)

MD XF

Oh look at that it's empty

Meh, not a big enough concern at the moment, feel free to open an issue if it bothers you and I'll change it eventually

user202729

Let me try to generate a cube which will take only a little time to solve...

MD XF

I'm still curious how getting a randomly generated cube to an easy-to-solve cube is any different than getting the same randomly generated cube to the solved cube

user202729

I mean, feed a easy to solve cube to your program for TIO purpose.

MD XF

03:38

Aha I see what you mean

The easiest cube to solve for that devil's algo is probably one rotated simply with F'

Actually I have no idea which turn is executed first...

user202729

The Cubically interpreter forgot to revert my terminal color...

MD XF

https://tio.run/##rZNLjhMxEIb3c4rsDGLTLj@6m2XL8sorSz4AjFQS0qxALDgBe47IRUJV/R06MMooaFDSX9e7yuXk8evHT48fnp6@nc8/v/@oharrrlAfRtOHe1AX@2pCM6nB6EQ2gUQgczvITZXiLKKYo7sqT5Fno@Z6kafKM2ivulyqds1aakfbpV5aLdZqtCHiaPtcQ@YdokuhfZAFgxT2qThMoaJJpJK5RyX5FtdooyETlUaiiiJHRoCMSqOI6@/w4jqNvocPQsDW3DbI9icrIzRpsgCrruORnIssTfKLvCxNKm1WqGuUNri0lC3p8sWsa7IxC8E94L/OtFm1Wd0HKtpvqKtqcx1b2@Mge77mOZxCtmjDNbLDoULTXmLso1llTehmKTqILQbNiy1mO4aXWxaT68rLBrd9PKX20Qnsws1SOlZsy@k2Lu6hqmG0vaum/r4juxGU0001HGnviGKD7IotxM436t6WvX5MIg7zATMFDssBM0UO6wEzJY7TATNljv6AmWaOdMBMC8dgME0qRgPmmjgmELrnmEHoxHEGoQeOCwg9clxB6InTBELPnDwIfeZEIPSFUwC…

Easiest cube to solve via the devil's algorithm I'm using is one scrambled with F2. It solves immediately ^

I ran the interpreter offline with the p flag which prints the cube moves as it executes them, the first move executed was F2

Leaky Nun

is sharing allowed/encouraged here?

user202729

Sharing... what?

MD XF

@LeakyNun sharing what?

ninja'd

Leaky Nun

03:44

knowledge, I guess

user202729

Yes, and hopefully someone will want to listen.

Leaky Nun

so we want to enquire about the natural numbers. We will use the logical operators "for all", "there exists", "and", "or", "not", "implies", as well as our operators on natural numbers +, *, <

user202729

... number theory again?

Leaky Nun

no, computability

user202729

Ok.

Leaky Nun

03:46

"n is even" will translate to "exists k, k+k=n"

so we can make all kind of questions about the natural numbers, including famous conjectures such as goldbach conjecture and Collatz conjecture

(the formulation of Collatz conjecture will be harder, as you would need to encode a sequence in a single number, but it is not impossible (see this challenge for an example))

user202729

Yes I suppose everyone had seen that answer.

Leaky Nun

so "for all" and "exists" are called quantifiers

and bounded quantifiers are of the form "for all n < m", "exists n < m", where m is something defined earlier in the context

so actually we can write "n is even" entirely with bounded operators: "exists k < n, k + k = n"

note that "n" is free in the sentence, i.e. not mentioned by any quantifiers before it, bounded or unbounded

we call such sentences 1-parameter sentences

now, we will introduce a sort of hierarchy to parametrized sentences (the number of parameters doesn't really matter, again see the link above for an encoding)

if a parametrized sentence is equivalent to one entirely with bounded quantifiers, then we say that it is a Δ0-sentence

if it is equivalent to a sentence that starts with unbounded "exists" followed by a parametrized Δ0-sentence, then the sentence is in Σ1.

if it is equivalent to a sentence that starts with unbounded "for all" followed by a parametrized Δ0-sentence, then the sentence is in Π1.

so Δ0 is a subset of Σ1, as well as Π1.

We call Δ1 the intersection of Σ1 and Π1.

A parametrized sentence is in Σ2 if it starts with unbounded "exists" quantifier and is followed by a parametrized Π1 sentence, i.e. it looks like "exists n1, exists n2, ..., for all m1, for all m2, ... [a Δ0 sentence]"

and the hierarchy continues onward

theorem: for a sentence φ, there is a program that proves φ or disproves φ, if and only if φ is in Δ1.

Heeby Jeeby Man

Do you mean ∑1 instead of ∏1?

Leaky Nun

where?

Heeby Jeeby Man

3 mins ago, by Leaky Nun

A parametrized sentence is in Σ2 if it starts with unbounded "exists" quantifier and is followed by a parametrized Π1 sentence, i.e. it looks like "exists n1, exists n2, ..., for all m1, for all m2, ... [a Δ0 sentence]"

Leaky Nun

04:01

no, because ∑1 would just be another bunch of "exists" quantifiers

maybe I should clarify that there can be more than one "exists" quantifiers in a row, and it doesn't affect the hierarchy

the same with "for all"

user202729

(because multiple integers can be represented as a integer)

Leaky Nun

precisely

Heeby Jeeby Man

Oh I see you are missing a s on the quantifier.

Leaky Nun

yes, sorry

Heeby Jeeby Man

Ok, I read that and then saw two exists (ignoring the elipse) and jumped to a conclusion.

Leaky Nun

04:05

let φ be Δ1. So, φ is equivalent to some sentence that begins with exists, and its negation is also equivalent to some sentence that begins with exists (negation of "for all x, P(x)" is "exists x, not P(x)")

so the program is simply to try substitute the variable quantified by 0, and then do the same on the negation, and then substitute 1, and then do the same on the negation, etc until either the sentence or its negation becomes "true"

for an example, let's forget for a moment that "n is even" is actually Δ0 (Δ0 is a subset of Δ1 anyway). Then, "n is even" can be written as "exists k, k+k=n", while its negation is "exists k, k+k+1=n".

So the program simply tries k=0 on the positive, k=0 on the negation, k=1 on the positive, k=1 on the negation, etc.

The other direction is harder to prove, and the proof involves essentially tracing what the program actually does and writing a sentence based on the program

Heeby Jeeby Man

Curry Howard correspondence?

Leaky Nun

@HeebyJeebyMan that's more like "proofs and programs correspond to each other"

Post's theorem.

more terms for reference:
if the defining parametrized sentence for a set of natural numbers is ∑1, then it is recursively enumerable, i.e. there is a turing machine that halts exactly on those numbers (and runs forever otherwise)
if it is Π1, i.e. its negation is ∑1, then it is co-recursively enumerable
if it is Δ1, then it is recursive

Classification of sentences:

- the four colour theorem (ignoring the fact that it is proved) is Π1.
- the fermat's last theorem (ignoring the fact that it is proved) is Π1.
- the Riemann Hypothesis is Π1.
- the twin prime conjecture is Π2.
- the Collatz conjecture is Π2.

note: some day maybe they will rank lower in the hierarchy. this is just up to our current knowledge.

here's the scary bit about arithmetical hierarchy: one can define a real number as an equivalence class of cauchy sequences of rational numbers (I will explain this later). Thus, let f and g be two cauchy sequences of rational numbers, i.e. a function from N to Q, which can also be a function from N to N. Assume that f and g are in Δ0. Then, the sentence "f and g represents the same real number" is actually Π3. It's even above most open conjectures.

conclusion: real number equality is super-undecidable

maybe I won't explain it, since it's more about the construction of real number, so it's more pure maths than CS

btw the sentence "f and g represent the same real number" is "for all rational epsilon > 0, exists natural N, for all natural n > N, |f(n) - g(n)| < epsilon"

Heeby Jeeby Man

04:32

Well shouldn't that make sense? I mean intuitively if we are defining real numbers with a Dedkind cut we would expect that determining the equality of two real numbers to be similar (but not identical) to determining if two unaccountably large sets are equivalent.

Leaky Nun

I think you get Π1 when using Dedekind cut, but I'm not sure

that's assuming the two numbers in question (two sets of rational numbers in equation) are recursive, i.e. Δ1.

Heeby Jeeby Man

I'm not sure if that is the case, but I don't know.

Leaky Nun

maybe the two sets can even be Δ0 (e.g. sqrt(2)), then still Π1 for Dedekind cut

p/q < sqrt(2) iff ((p < 0 and q > 0) or (p > 0 and q < 0) or (p*p < q*q + q*q))

Heeby Jeeby Man

I really don't think that is the case.

Leaky Nun

that looks Δ0 to me

Heeby Jeeby Man

04:39

Oh for that specific example yes

sorry I thought we were talking in general

Leaky Nun

3 mins ago, by Leaky Nun

that's assuming the two numbers in question (two sets of rational numbers in equation) are recursive, i.e. Δ1.

in general it doesn't work

we can only consider the real numbers that are actually in the hierarchy

Heeby Jeeby Man

Ok that would have been my suspicion

Leaky Nun

(there is only countably many Dedekind cuts that are in the hierarchy)

this is so horrifying

like we usually only use Π3 or below

Heeby Jeeby Man

Of course, because our statements are spanned by a finite grammar

Leaky Nun

but there are numbers that are not even Π100, not Π10000000000

and they are "real" numbers

New Main Posts

05:03

0

Q: Majority Gates for boolean functions

The majority function is a boolean function which takes three boolean inputs and returns the most common. This question concerns writing boolean functions as compositions of majority functions. An example of a 5-ary composition of majority functions is (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)...

code-golf logic-gates logic

Anonymous

CMC (Chat Mediocre Challenge): implement a Toffoli gate in Game of Life (B2/S23). Smallest bounding box wins.

user202729

Anyone can find a meta for include?

0

A: Find The Rank Of A Word

C++, 121 bytes void R(string s){int n=1;auto p=s;sort(begin(p),end(p));do if(p==s)cout<<n;while(++n,next_permutation(begin(p),end(p)));} I am always unsure when using C and C++ what counts towards the byte total. According to Program, Function, or Snippet? the answer is still vague (as long as...

We do need a definite boilerplate list for every languages.

... I waste too much time here ...

Anonymous

05:22

@user202729 So do we all :P

quartata

@Mego Interesting -- this could replace the ANT gate setup

I'm assuming that's why you're interested

Anonymous

@quartata That, plus it was a random thought that popped in my head :P

Anonymous

Toffoli gates seems more natural for the QFT computer, because we have to deal with stuff like conservation of energy :P

quartata

I think the QFT room is destined to die for another year until Pong, that seems to be how this works

Anonymous

Haha yep :P

quartata

05:34

also we never cleaned up the repos

remind me to remind phi to remind me to remind phi

not necessarily in that order

On the bright side we do at least have a list of things to do, we're not totally directionless

user202729