The Nineteenth Byte

5:01 PM

Can I get someone's opinion on this as a challenge concept?

I don't think it's possible to decode a randomly generated string of lowercase letters that has been encoded because there's no way to know if you have the correct input string

It's like trying to crack a one-time pad

Plus the terms encode and decode are very broad and poorly defined. What exactly does that mean? What if my encoding algorithm is replace all inputs with the lyrics to Never Gonna Give you Up?

caird coinheringaahing

@DJMcMayhem That's something I'll have to work out, thanks

@DJMcMayhem Then its really weak, and could be "cracked" very easily

DJMcMayhem

No it couldn't

It's literally impossible to recover the input if that's your encoding algorithm

Because every single input has the same output, you can't possibly recover the input

caird coinheringaahing

@DJMcMayhem ಠ_ಠ Nevermind, I can't read.

DJMcMayhem

You could even have your encoding algorithm be do absolutely nothing, return the input.

Even that is impossible to recover if the inputs are random

caird coinheringaahing

5:08 PM

ಠ_ಠ Looks like I have quite a bit to clear up

DJMcMayhem

Right now, the challenge is basically Given an arbitrary string, determine what input to an unknown algorithm generates this particular output. That's not even remotely possible

caird coinheringaahing

@DJMcMayhem Ergo, I must clear it up a lot

Anonymous

You could add the restriction that encoders must be bijective, which would help

caird coinheringaahing

@Mego bijective?

Anonymous

@cairdcoinheringaahing Each input has exactly one output, and vice-versa

DJMcMayhem

5:11 PM

IIRC, that means that no two inputs result in the same output

Yeah, ninja'd ^^

Anonymous

Surjective means each input maps to exactly one output. Injective means each output is produced from exactly one input. Bijective means surjective and injective.

caird coinheringaahing

So, the original idea for the challenge was based off of two "armies" sending and intercepting encrypted messages, with each army trying to decrypt the other armies messages, which means that messages must have some way of being decoded. I'll make that clearer.

DJMcMayhem

@Mego So all deterministic functions are Surjective by default?

Anonymous

@DJMcMayhem If you mean function in the mathematical sense, yes

DJMcMayhem

I meant in the programming sense

Without randomness, every input has to have exactly one output

Anonymous

5:15 PM

I would think the answer is also yes in the programming sense, but there's probably some crazy construction that would disprove it

DJMcMayhem

Sure

Can a function be Injective if a certain output can't be produced? (produced from exactly 0 inputs)

Anonymous

@DJMcMayhem Yes, because that output wouldn't be part of the codomain

DJMcMayhem

That's what I thought, just wanted to clarify

I still have a hard time remembering those terms

Anonymous

f(x) = 2x is injective, even though there is no z such that f(z) = 1

DJMcMayhem

Exactly

Anonymous

5:17 PM

(assuming ints)

DJMcMayhem

There's also a term for when a function is Bijective, and it's own inverse, such that f(f(x)) = x, right?

Anonymous

@DJMcMayhem I think so, but I don't remember it

DJMcMayhem

Oh

Jul 23 at 17:25, by Wheat Wizard

@DJMcMayhem No it does not, bijective functions must not be their own inverses, as stephen linked that is called an involution.

Anonymous

Yep, involution is the term

DJMcMayhem

I had a CMC that was shortest function that is an involution on all positive integers

But I didn't know the right terms

caird coinheringaahing

5:19 PM

@DJMcMayhem Wouldn't f(x) = x work?

Anonymous

@cairdcoinheringaahing Yep, id is the simplest involution

DJMcMayhem

Hmm

Good point

I originally wrote this:

Jul 23 at 17:16, by DJMcMayhem

CMC: Write a function that is bijective for all positive integers. In other words, for all positive N, f(N) is unique and != N && f(f(N)) == N

But that was because I didn't understand what bijective meant

Anonymous

@DJMcMayhem f(x) = -x

DJMcMayhem

I don't think that works because -x will be outside the range, so it can't be an involution since it can't accept it's own output

Anonymous

Then f(x) = x XOR 1

Erik the Outgolfer

5:22 PM

@DJMcMayhem involution just means f(f(x)) == x afaik not that f(x) is in the same domain as x

DJMcMayhem

Yes, that was most peoples solutions. Except they wrote it as f(x) = x + 1 if x % 2, else x - 1 or something like that, I don't remember

Erik the Outgolfer

actually f(x) = x XOR 1 isn't the same as f(x) = x + 1 if x % 2, else x - 1

muddyfish

I would have expected XOR to be more common

DJMcMayhem

I know.

Erik the Outgolfer

but that can be written as f(x) = (x + 1) XOR 1 - 1

muddyfish

5:29 PM

I think you did a typo there

Or brackets are confusing

Erik the Outgolfer

assuming XOR has higher priority than +/-

Mr. Xcoder

5:41 PM

TIL totallyhuman is i cri everytim

Pavel

Is SNOBOL pronounced snuh-bowl or snowball?

Mr. Xcoder

TIL SNOBOL was a thing.

caird coinheringaahing

@Pavel Snowbol

@Mr.Xcoder TIL what TIL is :P

Pavel

@Mr.Xcoder basically it was the first language to support regex before regex was a thing.

The S stands for string

SNOBOL (StriNg Oriented and symBOlic Language)

The acronym sorta sucks

caird coinheringaahing

@Pavel It could have been SOSL :D

(so-sal)

Pavel

5:58 PM

Or SOASL (Swhasul)

Transcript for