The Nineteenth Byte

Geobits

3:47 AM

Huh, just got my first tag-badge (discussion) on a meta site. Yay?

New Sandboxed Posts

4:02 AM

0

A: Sandbox for Proposed Challenges

Possible resistances from resistors code-golf electrical-engineering Meta: Note this is far from done; just putting this idea out so that I can continue working on it. IE way work in progress. I need to specify a lot more of this and I'm putting this here because I know I won't end up working o...

Martin Büttner

8:01 AM

I feel like I have to have this conversation on every single code golf challenge I post: codegolf.stackexchange.com/questions/44333/…

@Geobits Congrats?

Lembik

8:12 AM

hi

Martin Büttner

hi

Lembik

I got a comment from Peter Taylor saying " I suspect that this may be more trivial than you think.."

not sure what to do with that as I can't find an answer online

0

A: Sandbox for Proposed Challenges

An input with many outputs Consider two binary strings A and B of length 2x-1 and x, respectively. Now consider a binary output array Z of length x where Z[i] is 1 if B = A[i,...,i+x-1] and 0 otherwise. For a given fixed B, there are a number of different possible output arrays Z. You can find...

he may be right.. I can't tell

Martin Büttner

@Lembik for a start, you could write a brute force reference and test it on small n to see if there's an obvious pattern

This sounds like a pretty interesting challenge:

6

Q: Partitioning with constraints on subsets

Given the following data: constraints = {{11, 2}, {11, 3}, {11, 4}, {11, 6}, {11, 9}, {1, 6}, {5, 6}, {2, 5}}; weights = {3, 7, 3, 2, 4, 2, 2, 2, 3, 2, 1}; I wish to partition the integers from 1 to 11 into subsets such that: each integer from 1 to 11 appears exactly once the sum of weights...

@PeterTaylor any idea if an efficient solution is possible?

Sp3000

@Lembik Oh right, I forgot to ask - can you put up an example?

For the sandbox question

@MartinBüttner Well let's just hope nobody brings up the "Brainfuck should be 3 bits" problem... :P

Martin Büttner

@Sp3000 If you can show me a codepage which encodes 8-tuples of brainfuck characters in 3 bytes, then I'm all up for it.

feersum

8:23 AM

Given the hundreds of derivatives on esolangs.org, surely there is one that uses only 3 bits?

Sp3000

Hmm, maybe - closest one I know is Golunar, not quite

feersum

that's only a very slight compression

like 20%

Sp3000

If only it used base 95 at least :P

feersum

here's a 50% compression: esolangs.org/wiki/Binaryfuck

Sp3000

Base 32, hmm

feersum

8:32 AM

oops, 32 is not 64

Sp3000

@MartinBüttner From what I gather from the chat log, Nathan's CnR doesn't need cops to have a solution ready, right?

Martin Büttner

@Sp3000 nope

Sp3000

Awesome.

Peter Taylor

@MartinBüttner Can't be, surely? With minor tweaks to the values you get a case where every partition of n into pairs is an answer, and that's n! / 2!^(n/2) ~= (n/(e \sqrt 2))^n which is superpolynomial.

Martin Büttner

@PeterTaylor Hm yeah, it's not possible in general, but I'm wondering if the right constraints allow for some substantial speedups.

Lembik

8:42 AM

@Sp3000 sure

Peter Taylor

I can see how to encode the first part as exact multiset cover, but the forbidden constraints are an issue. For practical solution, I would start by finding the legal subsets and then try an exact cover with them.

Lembik

@PeterTaylor very interesting comment!!

@PeterTaylor let me check

@PeterTaylor I mean re: my sandbox question.. I may have just had a bug :(

Peter Taylor

I can make a heuristic argument for why a string of all the same bit should be optimal, but I don't have a proof.

Lembik

assuming your code is correct, maybe one of the many formuations at oeis.org/A000124 would give a proof

I am just checking my clearly broken code

or maybe my problem should be added there :)

Peter Taylor

8:58 AM

@MartinBüttner Well, the constraint {2, 5} is forbidden can be eliminated because it has a total weight of more than 9...

Lembik

@PeterTaylor you are right. the sequence is "The number of length n binary words that have no 0-digits between any pair of consecutive 1-digits. - Jeffrey Liese, Dec 23 2010"

@PeterTaylor I'll change the challenge :)

thank you

Sp3000

10:55 AM

@Optimizer How fast is the Java CJam implementation? I haven't tried it myself

Optimizer

pretty fast

download it and try

plus, the main time taking part is printing of those many digits on a web page

Sp3000

kk will do, now where did Java go...

Optimizer

HTML is not good at handling huge string displays

Sp3000

Ah that makes sense

Oh that's much faster, thanks

Optimizer

11:33 AM

I got such big output that java is not able to handle it

Sp3000

:P I don't think Java will handle mine any time soon either

Sp3000

12:30 PM

java.lang.RuntimeException: Unhandled char after ':': # :(

Optimizer

are you doing :# ?

I am afraid that kissing is not allowed in CJam

Sp3000

Damn, there goes my ,:(:# plan :P

Optimizer

being sad or happy is allowed, not kissing though

at least 1 form of it ..

nhahtdh

Can someone judge whether this cracking attempt is correct or not: codegolf.stackexchange.com/a/44469/6638

It was kinda messy

Sp3000

12:46 PM

Looking, gimme a sec

Well here's the relevant doc for the print statement

But was the newline part added in after the crack?

(tbh the newline doesn't majorly change the solution, so I don't think it should matter too much)

Optimizer

2:56 PM

I liked the idea of user23013's submission, have a hash code that depends on previous character so that you cannot remove any character

The thing that he missed out was the code to convert that hash back to original had so much golfing scope :P

LOL, @ sidebar, the latest what-if of xkcd makes @Geobits a sad panda

2

Geobits

The starred message about it does, though, since the newest one isn't as epic as the one that post was about :(

floating bowling balls < moon swimming

Optimizer

@Geobits of course I know that the message about it does

Optimizer

3:33 PM

want this - youtube.com/watch?v=2iZ0WuNvHr8

Geobits

I love that they have smartphone controls among the other methods. "Yea, there's an app for that."

Optimizer

"You can take down all your enemies with one smile"

that's the best feature of any gadget ever

Geobits

Just don't jump off it when disembarking. That is ill-advised.

Sp3000

3:57 PM

Hmmm does CJam take a modulo before applying range?

Optimizer

what is the question ?

Sp3000

I was trying to do AD#A*48*156#C\7+*,

If you take out the , it's a large number but once you put in the , the range is small

Optimizer

so not all are printable, right ?

adding another , to get the actual length of the range

Sp3000

I get 84 for the length o_O

Optimizer

oh yeah, arrays have a range limit

so yours is modulo that

Sp3000

4:03 PM

... damn

Optimizer

somehow wrap that big number in an array

and multiply it

Sp3000

Hmm that's a good idea

Sp3000

4:19 PM

Hmm I feel silly, this isn't what I want to do at all, I'm exponentiating the wrong way around

Optimizer

you are powering up the wrong way

Sp3000

Yeah :/

Not hard to fix though, at least

Lembik

hi all

I am back after the humiliating defeat of my last sandbox challenge

Optimizer

good good

that's the spirit

Rainbolt

I need to clean out the garbage half written specs I have posted in there

If they were good ideas I probably would have finished them by now

Optimizer

4:31 PM

probably

Martin Büttner

5:04 PM

@Doorknob We'll probably delay posting of the current weekly challenge until Monday. Should we start the next round anyway? Or should we just accept that fornightly challenges make more sense on PPCG?

Optimizer

this will not be fort night challenge

Geobits

I accept that "fortnightly challenge" sounds way cooler than "weekly challenge", regardless of the practicality of either.

Optimizer

yeah , it will miss 2 weekend days

but still, its weekly only.

Martin Büttner

@Optimizer I don't get your point.

My suggestion is to select a new theme only every other week.

Optimizer

but why ?

Martin Büttner

5:08 PM

whether the new challenge is then ready after a week, ten days, or two weeks doesn't matter

Optimizer

because you think we missed 1 week ? (this week ) ?

Martin Büttner

@Optimizer Because the first challenge took two weeks. The second challenge could have used more than one week to write a reference implementation. And this one didn't meet the single week deadline either.

But I guess my actual answer is "why not?"

Optimizer

because "weekly challenge"

Martin Büttner

...

it's not like the entire concept is ruined because you make it every other week.

Optimizer

but .. but .. "Weekly Challenge"

Rainbolt

5:11 PM

@Optimizer It doesn't specify which week the weekly challenge falls on.

Optimizer

weekly means every week, no ?

Rainbolt

Not necessarily. The adverb "weekly" could also be meant to specify how long the challenge runs for.

Martin Büttner

isn't that a week-long challenge?

Optimizer

yeah ^ . weekly as an adverb still means once a week

week-lee and week-long

Rainbolt

The traditional usage of weekly does mean once per week.

Geobits

5:15 PM

I've checked a couple dictionaries online, but can't find one where weekly is listed as having a "week long" definition. That being said, using it this way doesn't really bother me.

Rainbolt

Gladly doesn't mean once per glad. There's obviously some room for interpretation there.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

A regular expression homework on StackOverflow (Source: http://stackoverflow.com/questions/27988149/find-regular-expressions-of-a-language) code-golf Write 10 regular expressions for the 10 tasks below, each with a different regex flavor. No code execution is allowed in the regex. One of the ...

Geobits

I'm pretty sure that's a bad comparison :D

Optimizer

wow. such example. much relation

so wow.

Rainbolt

♪ This was a triumph ♫

Optimizer

5:16 PM

triumph fail

Sp3000

Damnit CJam, why won't you do what I want :(

Optimizer

because you dont write CJam, CJam makes you write it.

Geobits

wat

Sp3000

84 84 84## gives 1 :(

Optimizer

in Java interpreter too ?

JS has limits, you know right ?

Sp3000

5:21 PM

...oh point

Optimizer

just try this in the JS one 84 84 d 84##

Sp3000

Nope in the Java interpreter too :/

Optimizer

then I think operations on BigInt are not BigInt based

(in CJam)

Martin Büttner

@Sp3000 wat

Optimizer

Byte Overflow

Sp3000

5:25 PM

Well...

Hm.

Well I guess I'll have to figure this out tomorrow, it's getting late over here

Optimizer

You can revert for sure

Sp3000

Damn and I thought I was finally up to up-arrow notations :/

Optimizer

better than leaving it like that

Sp3000

kk, will do

Martin Büttner

@NathanMerrill I preferred the Lunar Swimming what if (or did you post that link before he posted the bowling ball?)

Optimizer

5:37 PM

yeah he did b4

Martin Büttner

ah okay

Optimizer

tries to see if all answers can fit in 3 characters. question-answer code-golf

Geobits

Wow, I was ninja'd hard on that one. It was there whole minutes before I answered and didn't see it :D

Optimizer

what did you two delete ?

Geobits

I answered Martin's question about the sidebar post. Late.

Optimizer

5:52 PM

why does hovering over a deleted post still highlight the related reply to post ?

Geobits

They're not hard-deleted (I think mods can still view them), so I guess they just didn't bother to clear/invisify the "repliedTo" field or whatever.

Optimizer

yea

Geobits

Someone ruined your comment about the sidebar. Now apparently sandbox comments make a sad panda :(

Optimizer

what doesn't make you a sad panda ?

Geobits

Oven-baked macaroni and cheese?

2

Optimizer

6:01 PM

1 more upvote to the makes me a sad panda message ...

or the LOL one.

Geobits

I would, but apparently "You cannot star your own messages". Very insensitive to narcissists on SE's part.

A few more stars and some time will push it below the weekly challenge invite :)

Optimizer

lol

hmm, weird..

Geobits

6:45 PM

Is there anything wrong with the following approach to the current cop challenge? 1) Golf the crap out of a program, but make sure you use a single variable 11 times. 2) Inflate the name of that variable to something ridiculously long

Assuming you golfed it well, there shouldn't be any way to shorten it in general, and changing the variable name would ensure a distance of >10, right?

Just curious before posting. I've got a program that I'm tweaking, so far up to 9 necessary uses of the variable.

Martin Büttner

@Geobits I swear there used to be a rule that variable names can't be longer than 3 characters, but I don't see it

Geobits

Obviously it's a bit boring, but it seems like it would work (if you make sure it can't be golfed further beside that single name).

Hmm, I've actually got ten uses. Trying to find a way to add it in somewhere else....

Martin Büttner

@Geobits just add it anywhere. removing it also costs more than 10 edits

Geobits

Yea, but commenting it out wouldn't. You could add // and remove 8 chars from the name to get edit distance 10. It needs to be used.

(Or /**/ anyway, since no line breaks)

Martin Büttner

ah fair enough

Optimizer

7:01 PM

wow, this is the longest time I have ever taken to get 1000 rep.

Martin Büttner

like... two weeks?

Optimizer

still not done , so no idea.

Geobits

Your chart looks relatively steady ;)

Mine is very bumpy by comparison.

Optimizer

10 days and only 800 points :(

Martin Büttner

life is hard

Optimizer

7:08 PM

and look at that. Martin is again ahead of me for the month !!!!!!!

Martin Büttner

@Optimizer and your bounty total for the month is +50, mine is -150 :P

Optimizer

yeah!

:'(

Martin Büttner

also, I'm only ahead because I post challenges... you should try it too :P

Optimizer

I am not a creative thinker

my last challenge did not even hit 25 yet.

Martin Büttner

@Optimizer it's not like it can't be practised ;)

Optimizer

7:14 PM

practice being creative ? My brain is not made that way ...

I mean my brain does not work properly unless there is a challenge. And it is smart enough to figure out loopholes, so I cannot challenge myself to create a good challenge

Rainbolt

7:29 PM

@MartinBüttner Winky face in conjuction with double negative is just mean.

Martin Büttner

heh

@Rainbolt I probably have asked you this before, but how come you've never posted an MtG-based golf challenge?

Rainbolt

I started writing a controller for one actually

The plan was to actually get bots to play MTG against each other

Martin Büttner

a KotH?

that's crazy

Rainbolt

Bots play chess against each other in order to get better at playing chess. It isn't all that crazy, but it's a bit too large for PPCG

I imagine that you could get quite a few good ideas for "learning" challenges from here youtube.com/view_play_list?p=A89DCFA6ADACE599

The first lecture really hooks you. I strongly advise watching it.

Martin Büttner

7:46 PM

@Rainbolt I've taken Ng's lecture on Coursera.

I found his lectures on youtube during a multimedia analysis seminar a few years ago... he's amazing.

Rainbolt

I'm only through the first two lectures. And I'm not "taking them" as much as I am watching them lazily.

I never thought someone could drone on for so long and remain interesting the entire time.

Martin Büttner

well yeah, if you do it on coursera there's a bit of coursework as well

Optimizer

nice nice

Geobits

Geez, becomes a room owner and just spams a wall of (removed) :P

Martin Büttner

I managed to hold a little monologue in the wrong room

Geobits

7:54 PM

I managed to find 11 places to stash a variable.

Unfortunately, I can only use alphanumeric (and _) to pad variable names in Java.

Otherwise I could get pretty close to the 9500 max

Rainbolt

8:43 PM

We keep getting burned by Microsoft Word when we copy and past text to code.
She said, “Hello world!” – and here is a dash. // Word
She said, "Hello, world!" - and here is a dash. // Notepad

There should be some sort of feature whereby copying text from Word copies it as the rest of the world would normally write it.

Martin Büttner

@Sp3000 Intrigue was back in stock... just ordered it :)

VisualMelon

@Rainbolt is there no Paste Special for your requirement?

or is that only Excel... I've not used either for ages

Rainbolt

9:01 PM

@VisualMelon I was looking for a Copy Special

Geobits

Hmm. Are you sure it's Word's fault and not Notepad's? Notepad mangles non-ASCII text well enough on its own in my experience.

Rainbolt

Notepad has no issue with the angled quotes.

The top line was originally typed in Word, copied to Notepad. The bottom was typed in Notepad.

Geobits

Oh, I thought the issue was that the angled brackets didn't copy over.

Then yes, I agree. But I'd also say anyone writing code (to later be copied) in Word is just wrong. It's for more documenty things where angled brackets and emdashes are more common.

VisualMelon

@Rainbolt ah, ok

Rainbolt

I guess I didn't explain the issue. Customer gives object a name. Developer copies name into code. Name makes it's way into the database. Developer updates code and, in the process, changes long dash to be short dash. Names don't match, and data with the old name is now lost.

And actually that was backwards. More often the case is that we wrote the code with normal characters, and then they complained that it doesn't match exactly so we copy and paste what they wrote straight from Word.

Either way, the characters get out of sync and it's a huge mess.

Geobits

9:09 PM

Sounds like fun.

VisualMelon

rather

Rainbolt

You remember sitting in database class thinking "Why does everything have an ID?" Now we know.

Geobits

For indexing, obviously :P

Rainbolt

That too

Or rather, primarily that

VisualMelon

all I remember from the Database stuff I've done is "Any non-prime attribute must tell you about the key, the whole key, and nothing but the key, so help me Codd"

which would be useful, if I could remember which Normal Form it applied to

Geobits

9:12 PM

I saw a database once where primary key was name, with the format Last,First. Even thought it was a small table that made collisions unlikely, I died a little inside.

Rainbolt

If users log into the system with their name, then it makes sense.

Geobits

It was a list of customers :(

This was some years ago, though.

@Rainbolt So have you given up on your tumbleweed or are you just very patient? ;)

Martin Büttner

@Geobits he got it on another site I think

Rainbolt

^

If this site ever dies I will be here waiting for my tumbleweed.

Martin Büttner

@Rainbolt I'd love to see you post a tips question for the purpose getting tumbleweed though... seems to be the most reliable way

Geobits

9:25 PM

Cool

Rainbolt

I would inevitable get a comment like "I've never heard of this language before." despite the fact that I posted a link to it.

Martin Büttner

tumbleweed it's s such a weird badge

Rainbolt

I posted a really difficult challenge once. Some geezer just decided to post his thoughts as a freaking answer.

Martin Büttner

it also has a couple of upvotes...

Rainbolt

As a side note, I think it is really strange that the challenge got 21 upvotes and only one real answer.

I usually equate hard with unpopular.

Martin Büttner

9:31 PM

let me check what my hardest challenge with a lot of upvotes is

possibly codegolf.stackexchange.com/questions/38450/…

ah no. definitely codegolf.stackexchange.com/questions/36361/domino-circuits

Rainbolt

Haha I meant to upvote that one the instant it left the sandbox.

Optimizer

my latest challenge has 24 upvotes and 1 answer.

that too because i put bounty.

VisualMelon

Domino Circuits was definitely the most interesting thing I did in 2014

thanks Martin ;)

Martin Büttner

heh, thanks... I wish more people would have found it that interesting... would have been nice to see a few different approaches

Rainbolt

It's strange when you put so much work into a challenge and one other person gets something out of it. It's almost like you are connected.

VisualMelon

9:36 PM

I maybe killed it by posting an answer to quickly

Rainbolt

You did start with "huge, ugly, slow, painful, naughty" to encourage others to post a better solution

VisualMelon

(it having been in the works for a while before the question was posted)

@Rainbolt I tried!!

I wonder just how strong the correlation between gif content and upvotes is

Rainbolt

I can tell you now that crudely drawn pictures do not make you famous.

VisualMelon

it's just because it's not a gif, you should have made is jiggle or change colour or something

Rainbolt

The art my brother drew for this one got some positive feedback in the comments. But he has a bachelor's degree in Graphic Design from SCAD.

New Sandboxed Posts

9:55 PM

0

A: Sandbox for Proposed Challenges

Equivalent move sequences on the Rubik's Cube code-golf puzzle-solver A move sequence is a sequence of moves (turns) on a Rubik's Cube (for the notation loow below). For each move sequence, you can find infinite other move sequences, that cause the same results as the original one. In other wor...

Martin Büttner

10:18 PM

@nhahtdh how come you deleted the regex proposal?

Optimizer

@Geobits ;)

Nice try though

err

Martin Büttner

@Optimizer are newlines legit?

Optimizer

that's not the issue here. but yeah, if you count them to distance ..

I did not even check if mine is shorter.

Martin Büttner

lol

@Optimizer "Your modified code must only have printable ascii."

Optimizer

so what if the original code had newlines and I did not change any of them ?

that rule is as absurd as the others ;)

Martin Büttner

10:28 PM

@Optimizer the original code isn't allow to have newlines either

"Only printable ASCII characters are allowed."

nhahtdh

@MartinBüttner: I can't think of anyway to make it interesting

Optimizer

this is invalid entry - codegolf.stackexchange.com/a/44569/31414 ?

Martin Büttner

@nhahtdh hm fair enough... I was actually thinking about doing a "golf course" of several regex problems before, but I never bothered coming up with interesting problems that have nice solution which aren't known are pretty short.

when is POPCORN coming then? ;)

@Optimizer I guess, although I think it was posted and cracked before Nathan added the word "printable" to the spec.

nhahtdh

@MartinBüttner Currently, the solution is going to be more or less the same for any flavor. There are only 2 variations - with lookaround/backref and without lookaround/backref

Optimizer

hmm, back to ground zero.

Martin Büttner

10:32 PM

square one?

nhahtdh

@MartinBüttner Tomorrow, probably

Peter Taylor

@Geobits I remember our database lecturer at uni talking about an organisation which sent her stuff intended for someone else with the same name. She discovered that they were using name as a PK. I can't remember now exactly which organisation it was, but I think it was the ACM. Certainly a computing organisation which should have known better.

Martin Büttner

@nhahtdh kk :)

nhahtdh

@MartinBüttner: Is the new bonus fine? (also @PeterTaylor)

Martin Büttner

@nhahtdh not using built-in sort?

nhahtdh

10:35 PM

Yup

Martin Büttner

it's a nice idea, but I'm not sure it'll be worth it in the golfing languages. at least I haven't been able to come up with a nice implementation that wouldn't be substantially longer than the naive approach.

Peter Taylor

@nhahtdh I'm not sure what I should be looking at

Martin Büttner

also, people might just do something like "a = minby(list,bitcount);drop(list,a);print(a)" in a loop to avoid the sorting

nhahtdh

That will be slow, for millions of elements

I need some timing data, though

To make sure all O(n^2) solutions go down to the drain

Martin Büttner

well, that's my point. there is no mention of a time limit right now, so what's stopping people from using O((2^n)^2) approaches? (I'd love to see an O(n^2) solution btw :P)

Peter Taylor

10:46 PM

Which question are you two talking about?

Martin Büttner

POPCORN

Peter Taylor

@nhahtdh For GS it's not worth aiming for the bonus, but hey.

Martin Büttner

@PeterTaylor I'm not sure how the easy-to-invert implies that it's trivial to obtain a sequence of moves from two states of the cube.

Peter Taylor

To find the shortest sequence of moves which is equivalent to XYZ, you start from the solved cube, apply the inverse of XYZ, and then solve.

So it's just the older question with a different input format.

Well, actually the older question didn't ask for optimal solutions.

Finding optimal solutions in a reasonable time is quite tough.

Martin Büttner

my point was that you don't have XYZ... or did you actually mean XYZ symbolically, and "then solve [for XYZ]"?

oh

never mind

I get your point

Peter Taylor

10:58 PM

Ok, "equivalent" might have been the wrong word.

There's an easy reduction one way.

Martin Büttner

yeah I was thinking you wouldn't want to do the reduction this way though

because if you already have the move sequence, why go back to a situation where you only have information about the cube states

so I think for golfing this might not be that relevant

Peter Taylor

The move sequence doesn't give you much more than the cube states. This isn't the worst-case situation of the word problem on groups (undecidable) because the group is finite, but there's no a priori reason to expect that any other approach will be better than the reduction.

Martin Büttner

fair enough

Sp3000

11:19 PM

@MartinBüttner Huzzah, have fun with Intrigue :D

Martin Büttner

thanks :)

Transcript for