The Nineteenth Byte

Leaky Nun

05:40

challenge me on lichess.org, my handle is ChEsSn0oBz

or just add me

DJMcMayhem

06:20

Sure, it might be hard to find a time to play though cause of the zone difference

New Main Posts

12:08

0

Q: Golf (6-card) Golf!

Golf Golf! This is my first challenge, so please be gentle! The challenge is to write a program that will output the correct score for a layout in the card game "Golf." The card game Golf has many variations. The house rules I use follow the standard rules for Six-Card Golf given by Pagat, with...

PhiNotPi

17:12

What are some examples of set functions such that, for any three sets X,Y,Z of numbers we have:

f(X union Y) > f(Y) implies f(X union Y union Z) >= f(Y union Z)
f(X union Y) < f(Y) implies f(X union Y union Z) <= f(Y union Z)

The two easiest examples are cardinality and sum.

Also minimum and maximum.

ngn

17:40

@PhiNotPi "cardinality" is not a function

Erik the Outgolfer

why not

El'endia Starman

What do you mean len(x) is not a function??

ngn

there are multiple equivalent definitions of "function", let's take one: a "function" is a set of pairs whose first element is in the domain of the function and whose second element is in the range

so, a function itself is a set

Erik the Outgolfer

cardinality still sounds like a function to me

ngn

but if we have to build a function (i.e. a set) that maps all sets to something, then it becomes larger than the set of all sets

El'endia Starman

17:44

@EriktheOutgolfer I think that, strictly speaking, cardinality is not a mathematical function. However, I think restricting Phi's question to mathematical functions only makes it less interesting.

ngn

from russell's paradox we know that a set of all sets cannot exist. so, cardinality cannot be a function. qed.

El'endia Starman

Meanwhile, over in programmer land, we have functions for cardinality, random numbers, opening files, etc. A function there is basically "a black box that takes some input and produces some output".

dzaima

@ngn that seems to say that no function taking any set as an input can exist, nothing specifically about len(x)

ngn

@El'endiaStarman set theory function ≠ computer science function

@dzaima yes

El'endia Starman

@ngn Yep, I'm agreeing with you. I just think Phi had compsci functions in mind.

PhiNotPi

17:48

@ngn Yeah I think you're taking it to be more mathematical than what I'm envisioning. By "set" I really mean a list of some numbers. And by "numbers" I mean probably positive integers only.

Erik the Outgolfer

an unordered list of numbers at that :P

El'endia Starman

Come to think of it, do min(x) and max(x) also not qualify as mathematical functions?

dzaima

@ngn i know nothing about set theory but that seems like an awful definition of functions due to what you've just explained

ngn

@PhiNotPi ah, ok :) everyone please ignore my little detour into transfinite set theory then

PhiNotPi

@El'endiaStarman technically no, but there's "supremum and infimum"

ngn

17:54

@dzaima it's the commonly used one, afaik

@PhiNotPi the easiest example is f = constant :)

Erik the Outgolfer

tbf, I'm pretty sure we can define a function n : {x <= S : x} -> N

(S is some superset, <= means subset)

and then the formula would be n (S) = {0: S = {}, n (S \ (x s.t. x in S)) + 1: S =/= {}}

dangit markdown

PhiNotPi

18:12

I think I actually technically also want the additional condition that

f(X union Y) = f(Y) implies f(X union Y union Z) = f(Y union Z)

Anyways, the reason I was thinking about this, is that for "functions" with this property, there's going to be a straightforward O(n) algorithm for an associated maximization problem.

For example, "sum" has this property, which gives the O(n) maximum subarray sum algorithm.

Erik the Outgolfer

alright, then we're definitely in CS territory and not maths territory :P

ngn

@EriktheOutgolfer "s.t." = "such that"?

Erik the Outgolfer

yes, maths doesn't really have a better notation for that :(

(well, it does, but it's not representable with pure ASCII :P)

also, that (...) should've been wrapped in {}

ngn

sometimes ":" is used as "such that"

Erik the Outgolfer

yeah that can be very confusing

ngn

18:19

is "\" set difference? i.e. "without"

Erik the Outgolfer

yes, although - is often used, but the latter isn't really encouraged (cue how they use it in our high school system, yuck)

ngn

so, S \ (x s.t. x in S) is like S without S's own elements?

an empty set

Erik the Outgolfer

nope, it represents S with one of its elements removed, especially if bracketed correctly :P yeah, I'm using unusual notation there

that's why I avoided {x in S : x}

ngn

i see

Erik the Outgolfer

and yeah, if I hadn't mistakenly put (), using : instead of s.t. would've been confusing like hell

noɥʇʎԀʎzɐɹƆ

19:49

I have a new way to fairly measure code-golf submissions from different languages
1. The challenge must provide test cases, the more varied the merrier.
2. The score of each answer is Mutate(Program) * ProgramLengthInBytes.

Mutate(Program) is defined as following:
MutationCoverage = 0
Repeat 100,000 times with non-deterministic seed:
   MutatedProgram = Program
   Random index P = random integer between 0 and the length of the program minus one
   Flip a coin, if tails:
      B = random number from 0 to 255
      In MutatedProgram, Insert a byte B after random index P
   Else:
      In MutatedProgram, Delete the byte at random index P
   Run the mutated program against the test suite
   If the mutated program fails the test suite OR the mutated program has a compile error or a runtime error in any test:

This gives languages and submissions that are naturally less dense per byte an advantage. It rewards conciseness.

El'endia Starman

I dunno, I don't think that rewards more-verbose languages. If a program is fully golfed, then there are no characters that can be safely deleted and the only times that inserting a random byte doesn't hurt is if it makes a variable name one character longer.

dzaima

@noɥʇʎԀʎzɐɹƆ I'd be interested to see langs (which don't just ignore specific bytes in the code) for which Mutate isn't always >0.99

and it shouldn't be too hard to make a lang that always gets a score of 0

noɥʇʎԀʎzɐɹƆ

Haskell: main=print[1..]

delete p, and you get a compile error, delete r, same thing, delete i, same thing ...

@El'endiaStarman I don't see what you're saying.

dzaima

@noɥʇʎԀʎzɐɹƆ so Mutate("main=print[1..]") == 1, which is >0.99

my point is, Mutate(prog) is pretty much always gonna be 1 leading to the worst score, except when it's specifically abused, when it's gonna be 0, being unbeatable

noɥʇʎԀʎzɐɹƆ

20:06

I see what you're saying, I think I defined Mutate incorrectly

hmmm, what if it was "If the mutated program has a compile error or runtime error:" instead?

dzaima

@noɥʇʎԀʎzɐɹƆ abusable by making language have no errors

John Dvorak

many golfing languages lack runtime errors

noɥʇʎԀʎzɐɹƆ

"If it runs without errors:" ?

no errors at all => 100%

John Dvorak

Let me clarify: many golfing languages lack any erroring mechanism whatsoever.

noɥʇʎԀʎzɐɹƆ

errors if mutated => <100%, so more benefit to languages like Haskell and Python which have stirct syntax

@JohnDvorak yes, this is supposed to discourage the use of golfing languages simply because they're physically smaller

John Dvorak

20:12

in GolfScript, any undefined identifier is simply a noop

in most languages, adding whitespace is often a noop

dzaima

@noɥʇʎԀʎzɐɹƆ ok, abusable by making all programs be required to have an even amount of bytes, making all insertions/removals error

John Dvorak

case example: base64 brainfuck

or base64 anything

dzaima

+1 byte is a small cost to pay for a score of 0 at the end

John Dvorak

or heck, even a .com file has a fixed size of 256 bytes, not less, not more

Back in the olden DOS days, if you wanted to have a bootable program longer than 256 bytes, you had to read it from the floppy drive yourself. And I do believe that reading from the floppy drive was kind of a pain.

dzaima

tl;dr measuring language conciseness is very hard if not just impossible

noɥʇʎԀʎzɐɹƆ

20:22

RadiationScore(x):
Counter = 1
For each byte:
   num = 0
   modify this byte, over 0..255 that lead to an error:
      add 1 to num.
   (num is at least one, because one of the modifications is the same byte)
   Counter *= num
Return Counter

*Do not lead to an error

Programming language like Jelly with very few errors get low radiation scores

Strict langs like Python get high radiation scores

John Dvorak

Bubblegum gets a perfect score thanks to its CRC32 footer

You can trivially harden any language by adding a checksum

noɥʇʎԀʎzɐɹƆ

We want to reward higher radiation scores, so that means making higher radiation scores translate into lower code-golf score:

(2**(ProgramByteCount*8))/RadiationScore * ProgramByteCount

John Dvorak

yeech

noɥʇʎԀʎzɐɹƆ

@JohnDvorak Hmm, instead of modifying a single byte, modify 8 random bits

or instead of 8, a random number from [1..programlengthinbits], chosen with a decaying distribution

John Dvorak

So... any checksum algorithm that catches any 8-bit error?

Shouldn't be hard to design one

lay out bits in a cube grid, add a parity bit for each 1d slice. Not terribly efficient, but detects any error up to 8 bits

pretty sure there are far better algorithms out there with 8 bit detection guarantees already.

If my intuition is correct, Hamming(15,11) should do just fine - and larger Hamming codes are more efficient anyways.

In other words: lay out bits in a hypercube, bit 0 is omitted, all power-of-two bits are checksums for their respective half-cubes

Should be able to get away with omitting most of the parities even then

The rest of the bits trivially encode a program in (rolls dice) Brainfuck.

dzaima

20:40

@noɥʇʎԀʎzɐɹƆ at that point it wouldn't be much different from just running n random programs and counting how many error

at which point you're facing directly upon the halting problem

John Dvorak

Ah, yes. The Halting problem. Befunge-likes tend to end up in infinite loops if you start randomizing their sourcecode.

dzaima

@noɥʇʎԀʎzɐɹƆ those powers there mean that the score is pretty much determined just by how many static errors there are in the language

e.g. Javas and APLs RadiationScore would differ by, at the very least, 2^len(x), making APL answers >10 bytes never able to beat Java because of the exponential score increase

dzaima

21:15

@noɥʇʎԀʎzɐɹƆ with the correction above that message, no errors means high radiation scores..

Adám

21:37

@UnrelatedString APL operators (J adverbs/conjunctions) can take three or four inputs without joining any into a list: a(b F)c and a(b F c)d

Unrelated String

22:10

Ah, interesting

So it's sort of... currying, almost?

Adám

@UnrelatedString You could say so. What actually happens is that what's inside the parenthesis creates a derived function which is then applied to the outer arguments.

Unrelated String

Yeah

Adám

E.g. 'abc'⎕R'def' is a derived function which replaces "abc" with "def". This derived function can then be applied to one argument (the input doc) and returns the new doc, or to two arguments, the input doc and the output destination file.

I'd think Jelly could do something similar, deriving a new link by feeding atoms to a quick, and this derived link then takes additional arguments and finally produces a result.

caird coinheringaahing

23:31

Hey @totallyhuman! Haven't seen you here in a while!

totallyhuman

hi

been popping in and out because of school

caird coinheringaahing

Ah yeah, lots of users have started doing that recently :P

e.g. Xcoder

Transcript for