The Nineteenth Byte

I would have thought you tried the following if you already have a string *** and wanted to check how much you can overlap ab (which does not depend on the orientation of ***):

  ***      ***
ab       ba

  ***      ***
 ab       ba

  ***      ***
  ab       ba

  ***      ***
   ab       ba

  ***      ***
    ab       ba

Dennis

@Optimizer Doesn't matter.

Second test case terminated.

Optimizer

yeah.. figured. 70 bytes after corrections

Sparr

1:12 PM

@MartinBüttner good point about the empty program and stripping the leading 1.

Optimizer

@Dennis oh. for me, it was running since 5 hours. (although it had the result)

Martin Büttner

you don't need the empty program though

Sparr

@Sp3000 golfing help would be appreciated. Like I said, I'm not really practiced in python golf.

I know I don't need the empty program, but stripping the leading 1 is a lot shorter than my current method for generating inverted programs

Sp3000

Well for starters, semicolons saves on indents

Optimizer

Now, I have a choice of golfing it further to 60 bytes, only to require a RAM of 30GB+, vs posting 70 byte version that runs in 4 gb ram.

Sparr

1:13 PM

indent once, semicolon the whole block?

Sp3000

And you can use x+=y instead of x.extend(y) (also x+=y, for x.append(y))

Dennis

@Optimizer I use non-standard memory limits for the JVM. THat might help.

Sp3000

You won't be able to do the whole block (like while/for/if/etc)

Optimizer

@Dennis I gave it all of my 8 gb. Still the 60 bytes one gave OOM

randomra

@MartinBüttner I don't go through the whole boggle-string, just try to push in from the two sides

Sp3000

1:14 PM

But

b=bin(g)[2:];p=[[0],['',''],[b],b];c=''.join([str([1,0][int(c)]) for c in b]);q=[[0],['',''],[c],c];P.extend([p,q]);g+=1;N=list()

is a start

Martin Büttner

@randomra oh okay

Sp3000

(also list() can just be [])

randomra

yours might have been a little simpler

Sparr

@MartinBüttner 98 byte BCT interpreter in CJam is pretty much exactly what I predicted from that challenge. Good job.

Dennis

@Optimizer I give it 16 GiB.

Martin Büttner

1:15 PM

@randomra if you did, that might help a lot with adding in smaller strings later

Optimizer

@Dennis let me give you the shorter one to run then.

Sparr

01101000010000101 is the largest slashes program I've identified that halts

Martin Büttner

@Sparr I was gonna do /// first, but escaping is annoying.

randomra

yeah, a couple more points maybe

if I will put some logic in it might as well think about it beforehand... like can I find the optimal 1d solution

Martin Büttner

@Sparr I would really like to see the output from the BF submission

Sparr

1:17 PM

can't you run it?

Martin Büttner

laziness

Sparr

@Sp3000 the most annoying thing for me in python is the inconsistent reference vs value behavior

randomra

In 1200 letter I will probably only find the length 2 word

Sp3000

What do you mean?

randomra

(actually that isn't in the input again, so probably not even that)

Sparr

1:19 PM

I'm trying to manipulate the contents of the list during the loop

for [a,b,c,d] in P:

I want to modify P[0][0] by modifying a

but if P[0][0] is an immutable type then I can't, because a becomes a copy, not a reference

but if P[0][0] is a mutable type, like a list, then a is a reference, and I can write into it

the easiest workaround I've found is to make a itself be a one-item list

Sp3000

I guess you could do for x in P: and then modify x[0]

Sparr

right now what I'm trying to do is replace P as a list of a,b,c,d with P as a dict of d:a,b,c

Sp3000

1:35 PM

P={d:(a,b,c)for a,b,c,d in P}

Martin Büttner

in a TC system... if I remove a finite number of possible inputs and/or a finite number of programs, it should still be TC, right?

Optimizer

@Dennis can you try this one ? lelS%_Sf++:D;r{el[_:XS+\\]:e!:+La\Dm*{~.=_YYb-!\0e=2<*}=W=Xe|Sr}h

Sparr

@Sp3000 nah, I'm trying to build it as a dict in the first place. It's working now

P[b] = [[0],['',''],[b]]

I'm just annoyed that I have to put 0 and b in a list

so that I can easily modify them in the loop later

Sp3000

Hmm I'm not sure what you're doing exactly, unfortunately

Sparr

then later for d,[a, b, c] in P.items():

I want to be able to modify c inside that loop

and a

Sp3000

1:40 PM

Is the unpacking in the for line necessary?

Sparr

I have to unpack it somewhere

otherwise I'll be referencing into the list repeatedly

Dennis

@Optimizer Running (a lot slower).

Sp3000

Well you could unpack it the line after, so for x in P.items():d,[a,b,c]=x

Optimizer

@Dennis of course :P

Sp3000

Longer, but it should allow you to modify x then, right?

Oh wait

Optimizer

1:42 PM

@Dennis in previous one, I calc 1 perm at a time and exit early. in this, I calc all at once.

Sp3000

If it's a dict you can just modify P[d]...

Sparr

sure, but then I've got to write it that way

Dennis

@Optimizer Not enough memory.

OpenJDK 64-Bit Server VM warning: INFO: os::commit_memory(0x0000000634980000, 907542528, 0) failed; error='Cannot allocate memory' (errno=12)

Sparr

and modifying P[d][0] is even longer than modifying a[0]

Sp3000

Er... I'm assuming if you did P[d] you wouldn't need to put things in a one-element list any more

Sparr

1:44 PM

right, but a would be P[d][0]

if P[d] is [a,b,c]

Sp3000

... oh, I see, right...

Sparr

anyway, it's working with the dict

which shortens it a lot

I'm gonna re-golf and post an update

Sp3000

If you're using it that much, you could set a=P[d] then modify a[0] that way?

Optimizer

@Dennis figured...

Sparr

still won't be even remotely close to the cjam solution :/

Sp3000

1:46 PM

Er... actually rather than that, just for d,a in P.items():

Sparr

then the old a[0] is now a[0] again... AND b and c are now a[1] and a[2]

@Sp3000 posted a new version, down from 640 to 500 bytes, thanks for all the tips and help

Sp3000

Well it depends on how you want to use them. If you need to use b and c in arithmetic a lot, then you can do for d,L in P.items():a,b,c=L

But for modification, either way you would need to do something like L[0]=x, but by doing this you don't need the one-element lists

Sparr

check out the new version

Dennis

@Optimizer I think I got a solution with 76 bytes. Still a lot longer than yours.

Optimizer

@Dennis I don't think I can post 63 one. And the other one is 71 now.

Sp3000

1:58 PM

@Sparr I mean something like this (not sure if I missed any, but take a look)

Sparr

Is that shorter?

Dennis

@Optimizer Not sure. The question doesn't specify time or memory limits.

Sp3000

Assuming I did it right, yes

Sparr

hmm

I mean, I have ,[a,b,c] in one place

and you have a,b,c= in another

I'm assigning to a[0] and you're assigning to L[0]

I guess you've trimmed a bit off my c[0] and s juggling?

Sp3000

Stuff like if a[0]: becoming if a: get trimmed, and also with s yes

Sparr

2:03 PM

thanks, I'll try to incorporate that

although I'm less motivated now that @MartinBüttner's CJam solution is in

Martin Büttner

:/

you're supposed to compete with other Python submissions, not with CJam :P

Sp3000

^^ that

Also Javascript

(Damnit Javascript...)

Dennis

@Optimizer Got down to 72 with some sloppy golfing.

Optimizer

posted mine

Dennis

Just saw it.

Optimizer

2:10 PM

the 71 byte one can be golfed a lot. I am doing a lot of variable initializations in there

Dennis

Yeah, me too.

Martin Büttner

hm, if I encode BCT in weird syntax I can shave off 6 more bytes

but then instead of 101 0 programs look like [[[1 0 1] [0]]]

randomra

@Dennis an input for which your algorithm gives suboptimal result:

axabababa
abababaxa

although there might not be similar situations in the actual test cases

Sparr

@MartinBüttner well, I think I'm doing OK with my subleq entry, then

I need to golf the subleq entry with @Sp3000's tips

p.append(defaultdict(int,enumerate(list(int(x)for x in reversed(str(g))))))

Dennis

@randomra Thanks. I'll see if I can fix that.

Sparr

2:18 PM

I hate that line

Sp3000

The fact that you're using defaultdict itself is pretty suspicious

Even in the worst case, the builtin functions dict.get and dict.setdefault should suffice

Dennis

@Sparr Looks like you're opting for an automatic award. :P

Sp3000

But usually it's actually shorter to check if the key is in the dict in the first place

Sparr

I had to use get or in 14 times without defaultdict :/

Martin Büttner

@PhiNotPi "You are also allowed to create a language to test, as long as you can show why it is Turing-complete." That's a bit dodgy. I could define a new language that is a string substitution of BF, where each character is replaced by the CJam code interpreting that character.

(Also, the optimal subset for BF only needs either - or +)

Sparr

2:25 PM

I don't think that would work

Martin Büttner

why not?

Sp3000

You don't look like you index that often though...

Sparr

are you also trickily defining the alphabet to be multi-bytes?

Martin Büttner

oh

Sparr

otherwise, you'll have more valid programs than just the BF programs

you'll have many valid cjam programs :)

Martin Büttner

2:26 PM

wait

Sparr

@Sp3000 p[i+p[i+1]]-=p[i+p[i]]; if p[i+p[i+1]]<=0:a[0]+=p[i+2]

Martin Büttner

but I'm defining a language that just has 5 multi-character tokens

Sparr

yeah, multi-character tokens are a serious stretch

Martin Büttner

any CJam code that cannot be split into these specific tokens is not a valid program in the new language

@Sparr right, but they aren't normally

any non-esoteric language has multi-character tokens

Optimizer

@Dennis Your latest version seems to just print the first line (dictionary) as is.

Sparr

2:27 PM

ahh, defining "print" and "int" as two distinct tokens, rather than 5 and 3 tokens?

Martin Büttner

@Optimizer did he golf it down to l?

Optimizer

@MartinBüttner sadly, no

Sparr

@Sp3000 7 right there in those two lines

Martin Büttner

@Sparr yes. or think of them as keywords goto and while

Sparr

like TI-BASIC where they really are one byte tokens :)

Sp3000

2:28 PM

#5 and #6 happen after #1 and #2, so there's really only 5

Martin Büttner

@Sparr it's not even like TI-BASIC... it's like python... unless you define new variables you can't just put any string in your code without getting errors

you can only use known names or define new ones

Sparr

@Sp3000 why don't 5 and 6 count?

I've got it down to 269 bytes still using defaultdict. I'll try removing it...

Sp3000

It's just p[i+p[i+1]] again, so if you've already set it, it can't be nonexistent the second time

PhiNotPi

The CJam-BF language would also be allowed under the "Turing-complete subset of a language" rule

Martin Büttner

oh yeah, and that

so is stuff like that actually legit for the challenge?

Sparr

2:31 PM

ok, so using in doesn't seem like a savings

I end up with something like if i+1 in p and i+p[i+1] in p:

PhiNotPi

Turing-complete subsets would definitely have to be allowed, wouldn't they?

Martin Büttner

because that really seems to defeat the point of finding a Turing tarpit that can be interpreted as easily as possible

Dennis

@Optimizer Rolled back, thanks. Shouldn't post these things when I'm in a hurry.

Martin Büttner

@PhiNotPi you could just disallow eval maybe... that should hopefully close this loophole

PhiNotPi

I guess I'll do that.

Sparr

2:32 PM

disallow eval'ing anything taken from the target program

allowing eval of a codeblock from your interpreter's code seems valid

Martin Büttner

yeah that

Sparr

like the python bf that has python code in a string

Martin Büttner

that still means I can change the language's syntax to match the string representation of my code's internal representation of the program though, right?

Sparr

@Sp3000 also, I can't use -= if I'm using .get

Martin Büttner

(as I said about "instead of 101 0 programs look like [[[1 0 1] [0]]]")

Sparr

2:34 PM

we do that all the time for 'define your own input' challenges, right?

eventually someone needs to make a standard list of examples for that sort of thing

I think in one of my recent challenges I said that delimiters were fine, but no operators

Martin Büttner

@Sparr that's true actually

Sparr

(ignoring that [] is an operator in some esolangs)

Sp3000

Hm point... would it be okay if you posted what you have so far?

Sparr

5

A: Output every halting program (write a parallel interpreter)

subleq OISC in Python, 317 269 bytes import collections g=0 P={} while 1: P[g]=[[0],collections.defaultdict(int,enumerate(list(int(x)for x in reversed(str(g)))))] g+=1 for o,[a,p]in P.items(): i=a[0] p[i+p[i+1]]-=p[i+p[i]] if p[i+p[i+1]]<=0:a[0]+=p[i+2] ...

Sp3000

Just a side note/rule of thumb for imports: > 6 or so bytes means from collections import* is shorter

Sparr

2:38 PM

good point

will take advantage of that if I can't eliminate defaultdict

269 is a size I'm rather happy with, though

this solution still has the one-item-list-for-referencing

I looked at bitbitjump but it's not turing complete

I learned a lot more about different computational classes while looking through the esolangs wiki

randomra

hmm, didn't know you can assign hierarchically like a,[b,c]=1,[2,3]

it works with * too a,[*b]=1,[2,3]

Sp3000

I knew about the first, but I didn't know about [*b] until a few weeks ago

Sparr

what does [*b] do?

Sp3000

In the above example, unpacks the [2,3] into b (Python 3)

Sparr

it irks me that I can't do a=(b+=1) in python

Sp3000

2:47 PM

Programming-wise I'm grateful for that actually, but it does make things annoying for golf...

randomra

and you can't assign in condition, the same applies to it ^

Sparr

there's a whole duplicated p[i+p[i+1]] in my code that I wouldn't need in C

randomra

I actually got sloppy with writing sometimes writing = instead of == as I haven't had to fear of the consequences...

not sure if it's good or bad (for me)

Martin Büttner

@Sparr it's even more fun in Ruby, where you can do a+b=c

Sparr

@Sp3000 I'm not going to use from collections import * for the stupid reason that I don't want to figure out how to tell the pylint plugin for my editor to ignore the unused import warnings

Martin Büttner

2:50 PM

(sets b to c and then yields a+b)

Sp3000

Er... is it possible to switch that off somehow? pylint's going to be pretty annoying if you have it on while golfing...

randomra

@MartinBüttner is it like C, but with different precedence?

a+(b=c)

Sp3000

@Sparr Before we go any further, can you take a look at this and see what you think?

Martin Büttner

@randomra yeah pretty much

randomra

and in declarative languages you can write a+b=c+d and it does what a non-programmer would expect

Sparr

2:54 PM

@Sp3000 yeah, that change to use of L matches what you did in the slashes program. Looks mostly good.

Sp3000

3:06 PM

Hmm... well here's one further: link

Sparr

ooh, nice use of map

I've gotta go offline for a bit. Will incorporate these changes with credit later.

Dennis

@Optimizer Your latest version doesn't correct dnger.

Sp3000

Hmm yeah the -= makes throwing out defaultdict a bit trickier, but surely...

Dennis

@Optimizer Also, dargen gets corrected. Only adjacent characters may be swapped.

Sparr

I wish python had references :(

and now I'm really going

New Sandboxed Posts

3:43 PM

0

A: Sandbox for Proposed Challenges

Entropy Golf This is a scoring system without a challenge. My idea is to score entries based on the total Shannon entropy contained within them. This provides an incentive to both use fewer unique characters and to have a shorter program overall. Given a string of characters, the score is c...

Calvin's Hobbies

3:55 PM

@PhiNotPi It's not letting me add you. Probably because of this. I'll look for a workaround

@PhiNotPi Added you (by disabling online mode)

@Sp3000 Sorry if I kicked you off just now, had to restart

Sp3000

Ahaha no probs, these cows are a pain to herd I can't be bothered

Tell me when it's back up?

Calvin's Hobbies

Right now! (should be)

Sp3000

It says I'm not whitelisted :(

Calvin's Hobbies

Hmm, try now

Sp3000

Hmm nope :(

Calvin's Hobbies

4:07 PM

That's weird. I can't get on either. Though it says we're all whitelisted

It works when I reenable online mode. I'm not sure Phi will be able to get on now though

PhiNotPi

Hmm....

Maybe it uses online mode to check the whitelist.

:/

Calvin's Hobbies

Yeah, looks like it :/

PhiNotPi

I might just be motivated enough to buy the game now.

Calvin's Hobbies

I was about to suggest that :P It's not like it's a ripoff

PhiNotPi

But... I actually have to leave right now... bad timing with my schedule. Maybe in 6 hours or so.

Bye!

Calvin's Hobbies

4:20 PM

Hope to see you in Minecraft!

Sp3000

@Calvin'sHobbies Hey Calvin, would it be okay if you hopped on an told me your coords?

Calvin's Hobbies

Sure, one sec

Sp3000

nvm I fell

Calvin's Hobbies

X=60 Z=240 if still needed

Sp3000

saves message permalink to bookmarks

Martin Büttner

4:38 PM

are you guys working on anything specific or just doodling around?

Calvin's Hobbies

4:54 PM

@MartinBüttner Kinda doodling, but I'm up for something more ambitious.

@MartinBüttner Join us :D

Martin Büttner

I'm afraid :D

Calvin's Hobbies

Even if you're a noob, your PPCG fame will keep you revered

Well, respected

@MartinBüttner ^

Martin Büttner

5:10 PM

@Calvin'sHobbies no I mean I'm afraid of how much time I'll spend on that :P

(and I don't really have that time over next few weeks while I'm moving back to Germany)

Calvin's Hobbies

Well I can kick you off if you play too much :P

Martin Büttner

:D

New Main Posts

5:28 PM

-2

Q: Make HTML page as complex as possible

<!Doctype html> <html> <head> </head> <body> <p><b>Challenge!</b></p> </body> </html> Take this simple page above and make it as comlicated/hard to read as possible without changing the output. Rules: The output has to look like the page above It must be written in a browser based langua...

Martin Büttner

Perverse SE Incentives, #372. If I revoked my upvote and turned it into a downvote, I'd get a gold.

Sparr

wow, -2 before the bot saw it

Calvin's Hobbies

@Sp3000 Is that building with the redstone and hoppers meant to be a autofarm of some kind?

Cuz I want to work on an iron golem farm but don't want to redo something you're already planning

Sparr

I want redstone codegolf challenges...

minecraft players already try to minimize circuit size, especially for circuits that get reused in blocks

Calvin's Hobbies

@Sparr Want to join our new PPCG minecraft server?

Sparr

5:34 PM

probably not

I'm delaying getting back into MC

PhiNotPi

@Calvin'sHobbies Can I change usernames after I purchase a copy?

Calvin's Hobbies

@PhiNotPi On the server? Sure. I'll just whitelist your new username

PhiNotPi

No, like my legitimate minecraft username, after I set it.

Calvin's Hobbies

Oh. Yes you can. I've done it. Though there are limits to how many times etc.

PhiNotPi

once every 30 days.... that's fine

Calvin's Hobbies

5:38 PM

help.mojang.com/customer/portal/articles/…

PhiNotPi

What's the IP address?

for the server?

Calvin's Hobbies

167.114.158.78

PhiNotPi

1.7.10?

Calvin's Hobbies

Vanilla 1.8.7

(latest version)

PhiNotPi

Oh, it had a version number next to the server with a red X

port number?

maybe?

Calvin's Hobbies

5:51 PM

Sorry what's the problem? I don't see any numbers next to the server listing. You will need to update your home game to 1.8.7

PhiNotPi

I found the port number above, when I added it, it connected, but I wasn't white-listed.

Username "PhiNotPi"

I have to leave now anyways... Bye!

Calvin's Hobbies

@PhiNotPi I'll try re-whitelisting

It should work now

PhiNotPi

Still not whitelisted

Calvin's Hobbies

That's weird.. try now

PhiNotPi

What's the port number?

Calvin's Hobbies

6:01 PM

25932

PhiNotPi

167.114.158.78:25932

Not whitelisted.

Calvin's Hobbies

Try now? Not sure what's going on :/

PhiNotPi correct?

It's weird that when I do /whitelist add PhiNotPi your name shows up on the list as phinotpi, but Sp and my names still have their capital letters

PhiNotPi

Yes, PhiNotPi

Actually must leave now....

Alex A.

I need a feature on my browser that will disable Stack Exchange whenever I need to get something done.

Calvin's Hobbies

@PhiNotPi Ok. My only thought is that you need to change username because it already saw the illegitimate PhiNotPi trying to log on

@PhiNotPi Tell me when you're back and I can work on it more

Alex A.

6:11 PM

I kind of want to just buy Minecraft for him to avoid the configuration weirdness.

Martin Büttner

we could set up a Kickstarter campaign

Calvin's Hobbies

As I understand it, he did buy it (if no then I don't think there's a way to be whitelisted)

Alex A.

No he didn't

He told me yesterday

@MartinBüttner Or since it's not that expensive I could just do it. :P

Martin Büttner

he did earlier today

Alex A.

Timezones

Calvin's Hobbies

6:12 PM

2 hours ago, by PhiNotPi

I might just be motivated enough to buy the game now.

Alex A.

Oh!! See, I'm so far out of touch with reality that I don't know when Phi makes purchases.

How is the server going, @Calvin?

Calvin's Hobbies

@AlexA. Good. Come help me get cows and brewing stands

Alex A.

4 mins ago, by Alex A.

I need a feature on my browser that will disable Stack Exchange whenever I need to get something done.

Applies to Minecraft too ;)

And so of course I'm on Stack Exchange and have just logged into Minecraft.

@Calvin: Says I can't connect to the server.

Calvin's Hobbies

@AlexA. Seriously? ...

Alex A.

Yeah

Calvin's Hobbies

6:18 PM

I'm not seeing your connection attempts in the console

Alex A.

In the Play Multiplayer screen, it says "Calvin's PPCG Server\nCan't connect to server" with a red X over the signal strength.

167.114.158.78:25932

Oh

wtf

It just let me join anyway

Holding tab just shows me though, I assume at least you're on too.

Calvin's Hobbies

Yeah, it says you joined

Martin Büttner

> Whirl was designed with the following state-of-the-art features in mind:

- Inheritence
- Simplicity
- Ease of use
- XML
- Maintainability
- Polymorphism
- Flexibility
- Power
- Subtraction
- Grilled Chicken

Unfortunately, none of those things made it into the final product.

Alex A.

@MartinBüttner Hahaha

Calvin's Hobbies

7:01 PM

Maybe this will entice @Martin

Martin Büttner

:D

randomra

7:24 PM

in the wumpus game it seems like the number of humans killed by wumpus/hunters doesn't increase at all if you increase the round number

Total rounds: 715000
Humans killed by arrows: 3
Humans dead by starvation: 356699

does anyone know why?

Alex A.

7:41 PM

@randomra Clearly the wumpus and hunters are too busy eating all the food.

randomra

@AlexA. that's a bit counter intuitive based on the number of starved to death hunters

Alex A.

8:00 PM

@randomra Okay, the wumpus was eating all the food.

(I don't remember the challenge spec at all)

feersum

Maybe they used genetic algorithms to evolve arrow-resistant hides?

Dennis

8:41 PM

I think implementing the Burrows-Wheeler Transform and its inverse would make a nice code golf. Has that really not been done before?

Alex A.

@Dennis I don't know what that is. Does it go by any other names?

If not it might be safe to claim that it hasn't been done before on PPCG.

And as an aside, I dislike the fact that our icon says PCG rather than PPCG.

trichoplax

As soon as we get our questions per day up to 10 we can change all that

Alex A.

To get there, either we need more good users to post challenges or a bunch of riff raff to post crap.

trichoplax

Yeah, but I think it'll only work if we get good questions...

Alex A.

I don't think we're in danger like Beer.SE. I joined that close to its debut in public beta. I haven't visited in quite a while and as I understand it's become something of a ghost town.

trichoplax

8:56 PM

We're in no danger at all, we just have to live with an icon that says PCG. I can deal with it... :)

Alex A.

I CAN'T DEAL MAN.

I'M GOING NUTS

trichoplax

Would it help to have some suggestion of what challenge types (tags?) people would like to see more questions for?

Alex A.

I think code golf is our bread and butter.

trichoplax

Yes, but is that what we're short of?