The Nineteenth Byte - 2015-08-27 (page 2 of 3)

« first day (1671 days earlier) ← previous day next day → last day (3171 days later) »

1:00 PM

Which is less time efficient, O(2^n) or O(n^2)? I'm thinking of imposing a time limit on the Fourier strings challenge

2^n grows much faster for large n

Compare 2^1000 to 1000^2

Oh yeah

So is O(n^2) a reasonable limit?

Seems a bit restrictive

Haven't seen the challenge, so no idea ;)

Depends on the requirements of the challenge. Is it in the sandbox?

1:02 PM

1

A: Sandbox for Proposed Challenges

Golfing strings in Fourier code-challenge Challenge Given a string as input, output the shortest possible Fourier program to output that string. In Fourier there is no easy way to output a string: you have to go through each character code and output that as a character. Fourier The languag...

Minor quibble: You cannot map a program to 0. — Dennis 12 mins ago

:(

0 is unnatural :)

That text file, my goodness

:D

@Beta Do you need to limit it by big-O at all? With a text that long, I think as long as they can produce the output, it's efficient enough for a challenge.

1:06 PM

Okay thanks

What do you think of the challenge as whole?

You may want to get a second opinion. I haven't looked at it that deep, but that's the impression that I get. I don't see anyone straight-brute-forcing it.

To be clear, +x would only work when 0 <= x <= 9, correct?

Who's the time complexity expert around here?

I forgot the Fourier spec

@Shebang Nope, it can be any length

Or 0

1:07 PM

Ah, i see

Seems okay. It's similar to a "get to this number by adding or doubling" kind of thing, but repeated a bajillion times.

Hmm. Oh wait a sec. I was looking at it wrong.

I'm guessing since division is int division, x can't be a float either?

Oh, no good point

Somebody correct me if I'm wrong: Since there's no character-to-character link except n to n+1, this should just be O(numOperators*n), right? Totally bruteable.

For the Fourier sandbox post?

1:12 PM

Yes.

I was thinking it was a tree at first, but it's not really.

Or it's a mini-tree at each character anyway, not a big wide tree for the whole thing.

^

I don't really follow how the language works, but if you just need to take the accumulator from the number of the previous character to the number of the current character each time, then that seems O(n)

You could even preprocess a map from each ascii to each other one to make it O(n).

Oh :P

I think I'm missing a lot of the subtleties of the restrictions, but I'm not sure restricting the complexity is adding to the challenge

Is there a specific approach you are trying to rule out?

1:16 PM

Brute forcing it really.

If you're going to use reasonably long test cases then you could just put a really generous time limit on it (like an hour).

Brute forcing it is going to be really fast at O(n), though.

It would have to be a hell of a test case (much much longer than the current one) to take an hour I'd guess.

Yeah. So being a code challenge as it is, is just going to broil down to a code golf...

I'll cut out the intermediate and revert it back to golf

Like, the program making the Fourier program's byte count, or the Fourier program's byte count?

Because the former is very trivial

I think the latter is much more interesting :P

You could spec it to "output the shortest Fourier program for input t".

1:31 PM

@TheNumberOne Quick question while you're fixing your submission: Which program would output n = 65?

Currently: <[<]

@Shebang I've added a second text file to make it even more interesting

@TheNumberOne Looks like a shifty-eyed guy with a monocle.

user image

2

Someone call for a monocle?

Oh wait sorry - I forgot I added 1 to each number to make it more like the spec - what about 64?

1:34 PM

<[[]]

Ah, so it doesn't prioritise by length, right :)

Nope

@BetaDecay Oh christ

@Shebang Tsk tsk blaspheming whilst talking about the Bible

Double whammy

@Sp3000 I added an explanation if you want to look at it.

1:36 PM

I saw - I just didn't really get it

Wait, so is the Fourier challenge required to give the shortest now that it's a golf, or not?

Yeah, it's supposed to give the shortest Fourier program

Does it qualify as a golf question if it is looking for shortest output?

@Sp3000 I have a 1-to-1 mapping of valid BF programs to all (valid or nonvalid) BF programs.

Well I added golf because of the tiebreaker

1:37 PM

Is it required to be the shortest possible to be valid, though?

If so, you don't need really long test cases, or the combined scoring. Just pure golf.

Nope

Okay, so we're looking for the point at which golfing it more makes it longer than we'd save?

With texts that long, I imagine it'll boil down to brute-force golf.

Uhh... Yes

I was thinking that with long test cases, there's going to be more variation amongst programs

So not everyone has the same score

If program A gives shorter output than program B, does program A automatically win regardless of its length?

@BetaDecay Not if it's easy to find an optimal score.

1:39 PM

@trichoplax Yes.

Then I'd say it's metagolf

@Geobits Would a large number of shorter test cases be better?

@TheNumberOne So... [[+-]+[-+-]] <-> +-]+[-+-]?

If you can easily brute force an optimal score, the test cases don't really matter much. Everyone will end up with the same score on any of them, so only the golfitude matters.

@Sp3000 yes

1:43 PM

Ah k - that sounds a lot simpler :P

gtg

@Geobits I'll keep it as a code-challenge for now, just because I don't know what the optimal outputs are

@BetaDecay Working on that as we speak :P

@BetaDecay for the first text file I think the optimal length is 652,212 bytes.

It's going to take a wee bit for the second, cause that starts at 4MB :P

@BetaDecay codegolf.stackexchange.com/questions/55293/… is actually the top "Hot Network Question" right now

2:05 PM

@jrenk Hm I'm surprised

@Shebang Oh cool.

I might have been wrong, I found a bug :P

Yep, it's actually 662,363 bytes :P

You know I'll keep it as a code-challenge

I did just notice the file has 2 trailing newlines, should these not be counted?

@jrenk Hopefully that'll get some more traffic flowing into the question :D

i.e. the source file

2:09 PM

@Shebang Nah, count all characters in the file

Ok, then yes, I'm 99% sure optimal is 662,363 bytes

@BetaDecay It already moved down to the middle :/

@jrenk I just noticed :P

this.... doesn't use jquery at all — Dan Pantry 4 hours ago

:D

@Shebang Is there only one optimal solution?

@TheNumberOne that's fixed just by adding 1 at the very end

there's definitely more than 1

Think about it: any +2a can be replaces with ^^a

with no byte change

likewise for -2a and vva

2:14 PM

@MitchSchwartz I know. I'm still not going to fix it until I'm done golfing.

I'd show you, but I can't find anywhere to upload a 647KB text file :p

@Shebang onedrive or google docs

It's alright :)

I've edited it to prevent you having to output too many optimal programs

drive.google.com/file/d/0ByOXB0wf04iyQ0JHSVB4Sk96NTg/…

^ Example solution

Hm. Android Chrome always gives me an SSL error when trying to access Drive files

Unable to make a secure connection to the server. This may be a problem with the server or it may be requiring a client authentication certificate that you don't have.

2:20 PM

Is it because your time and date settings are not correct?

That's the most common cause.

Otherwise it might be credential storage

Well it seems all correct

Time and date, that is

Has Chrome's 'data' been wiped? (Settings > Apps > Chrome > Clear data + Clear cache)

Sneaky peeky:

user image

If you're not syncing Chrome with Google it will delete your history and passwords!

@Sp3000 How would you golf this (other than shortening names and removing whitespace)? pastebin.com/rXVQCpAm

2:24 PM

I like how Fourier prints :P

@georgeunix Haha already done it :P

@Shebang In which way? :)

Each character at a time, it's fun to watch :P

Have you got credential storage enabled?

(i.e. does Android force you to have a PIN/password/pattern etc.

to unlock your device)

Both

That's why.

2:27 PM

Ahh. I solved the problem by opening it through the Google Drive app anyway

[Re-enter Ghost.]

Thanks anyway George

It's making me actually read Shakespeare by watching it print out :P

A certificate has been stored in credential storage which is declaring itself to be necessary to connect to drive.google.com

Oh, OK, yw :)

@TheNumberOne Switch to Python 2 and use cmp

Oh wait...

2:29 PM

If your organisation (school, uni, job) requires you to keep a certificate to allow you to connect to their service, don't delete your CS!

;)

Haha well they haven't told me anything technical about the school network, but I'll keep that in mind :D

@Shebang I could sell it like Scratch as an educational language :D

@TheNumberOne f+=(c=='[')-(c==']')*(f!=0) maybe?

Well, if you haven't downloaded it, then it should be fine

What values can facingforward be?

My grandparents had credential storage enabled for some reason on their tablets!

xD

@BetaDecay I'm an enemy of the IT department xD

They don't like other people proposing things that make it better

2:33 PM

@Sp3000 That should work, thankyou :)

Still, at least they offer Computer Science as a course at my school.

But I wouldn't call it Computer Science

@TheNumberOne One more golf: (c==']') -> (c>'['). What values can facingforward be though? That's important

[0,)

Then f!=0 -> f>0

I call it Python print() Science

Because that's the only function they've used

pretty much

OK, maybe input()

Thank gosh I'm not in that course!

user image

2:37 PM

@Sp3000 Thank you :)

^ anyone used PEG.js before?

parser generator?

Never heard of it

It's actually pretty cool.

I've been messing around in it

Never used a parser generator!

Wow

That's pretty cool

and very intuitive

just use { /* js */ } to use Javascript

Expect an Esolang ;)

The sandbox freezes after a bit though

2:46 PM

didn't think about that possibility (an Esolang)

It's like Eclipse Xtext.

@georgeunix Dabbled in it once, trying to get a Stack Snippet to interpret Python. The parser used up 40% of my SE chars allowance, so I gave up :/

Haha

You could probably port an Esolang which does not have a JS interpreter

repl.it

Well... it was for this challenge

Jison. Wow. Imaginative name. I wonder what that program was influenced by...

zaach.github.io/jison

@Sp3000 Ah, OK

2:53 PM

Alright, I'm going to post this, and go offline for an hour or so

2

Q: Golfing strings in Fourier

Challenge Given a string as input, output the shortest possible Fourier program to output that string. In Fourier there is no easy way to output a string: you have to go through each character code and output that as a character. Fourier The language is based upon an accumulator, a global var...

code-challenge metagolf

3:23 PM

@BetaDecay I've got a partially working mini–fourier.js with peg.js now!

That didn't take long at all

And it returns the correct answer

He should add it as a stack snippet to the post :)

I think it might be to big

To add to an SE post

@Shebang I haven't verified it with the interpreter yet, but I'm getting 625647 for Hamlet.

@TheNumberOne Semicolon the for-loop and you'll be ahead :)

@Geobits Really? Wow, that seems kinda small

3:33 PM

*too.

@TheNumberOne Also .find instead of .index

btw why the leading zero in the int?

Ah, I see why that might be

@Sp3000 So that empty program doesn't cause error.

If you were in Python 2 you could swap out int for eval, but 0o doesn't save anything in 3 :/

Instead of starting c = 0, can you start c = len(a)-len(b)?

Then do -= instead of +=

3:48 PM

@Geobits I thought it was because I didn't account for numerics values.. even that only gets me down 662022

I haven't done numerics either, but am about to.

D:

Here's my basic map:

	void createMap(){
		for(int from=0;from<128;from++){
			for(int to=0;to<128;to++){
				if(to<10||from<1){
					map[from][to] = ""+to;
				} else if(to==from){
					map[from][to] = "";
				} else if(to-from==1){
					map[from][to] = "^";
				} else if(to-from==-1){
					map[from][to] = "v";
				} else if(to>99){
					if(to%from<1){
						map[from][to] = "*"+(to/from);
					} else if(to>from&&to-from<10){
						map[from][to] = "+"+(to-from);
					} else if(from>to&&from-to<10){
						map[from][to] = "-"+(from-to);

Then just loop through the bytes in the file, using map[n][n+1].

I see

@Geobits you call yourself a code golfer with 8 space indentation????!!!!

3:54 PM

Those are tabs.

nvm, I don't think that applies here

@Optimizer Like Dennis said, those are tabs. Like they should be :P

@Geobits still!

I could see the objection if this was golfed code... it's not. It's work-in-progress Java, what exactly do you expect? ;)

4 space tabs!

3:56 PM

I'm not using a map right now, I'll test and see what I get. :P

@Optimizer That's the browser showing wide tabs... on my IDE or any editor it isn't like that.

Can you upload an output for the first one? I want to check if it works :P

I checked the first 1000 bytes or so in the interpreter, but if you'd like I can upload the full thing. Just finished adding numerals, it's at 625,458 now.

For the bible one I've got 13,722,626.

My program never finished the bible :P

not religious enough!

4:04 PM

Use a map ;) Mine does in maybe a bit under a minute.

Martin Büttner

@BetaDecay your challenge seems contradictory. the first part says you need to output all optimal solutions. then the scoring says it's metagolf and you're scored by the length you did output. so what is it?

its -15

@MartinBüttner I thought he meant that the best output was measured?

(i.e. the output produced by that program with the least bytes)

Martin Büttner

well that's what the scoring section says

but before that he says we should find the shortest possible solution and output all solutions if there are several with the same (optimal) length

@TheNumberOne i think this is a working 140 byte version of your algorithm:

4:07 PM

Well, like the comments say, "output all optimal" isn't really even possible :(

a=input().strip('[')
b=a.rstrip(']')
c=d=0
for e in b:d=d*8+'[<>,.-+]'.find(e);c+=(e=='[')-(e>'[')*(c>0)
t=8**(len(a)-len(b)-c)
print(d*t+t)

@Geobits exactly

unless you've got the time

I'm not sure Earth has that kind of time...

It might.

Well, for consecutive characters two ASCII points apart, you can branch on ^^ and +2, just as an example. Not even counting other optional branches, that's going exponential very fast. For a 4MB file, I don't see it being possible at all.

Martin Büttner

4:10 PM

@Geobits the challenge says you should always use +2 and -2 in that case

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Write a Foo-immune program In The Programming Language Quiz, Foo has quickly become one of the most annoying languages. Ever. Various people have started to "immunize" their code to avoid it being valid Foo. Now, here's the challenge. You need to write a polyglot. A polyglot that appears to wor...

Didn't see that, so less branches but still too many. Like the pair Hi is either +33 or 105. That's 2^1301 branches in the bible just on that pair of letters.

If he wrote which option to use in all these cases, it would be fine. But then there would only be one optimal output, so "all optimal" would be irrelevant.

I can't make a working map :(

Here's that hamlet you wanted for verification, let me know if you see any problems: drive.google.com/open?id=0B73QYv2Zz0SiRDE1dnhoamN0SjQ

I sent an access request :P

4:24 PM

Stupid Drive... ok, should be public-viewable now.

I've got it :)

And now I think I figured out what was wrong.. :P

The real problem with having to output all optimal solutions is that for a long input, there will be more optimal solutions then there are atoms in the universe. ~ issacg

He isn't wrong.

@TheNumberOne 136 bytes with print(-~d*8**(len(a)-len(b)-c))

But can't you limit how big the program would be

and therefore decrease the possibilities?

hehehe

I need to verify my answer, but that text file helped more than you know Geobits :)

YES!

601,397 :)

without numerics, too

4:35 PM

Nice :D

What am I missing?

and I didn't have to change to a map :P

I'm not sure what you're missing, but what I was missing was that, for example, 101a88a is shorter than 101a-13a and vice-versa

Ah, right. That's why the >99 check was there.

Do we really not have a contest for interpreting Malbolge?

Were you able to speed it up to handle the bible better?

Haven't tested with the Bible yet, will do once I put numerics back in

4:40 PM

Numbers slowed my bible down a lot, from <10 seconds to around a minute. But I'm parsing them in a naive expensive way.

I'm not doing them much better :P I mean, it's not slower than the rest of the code, but it wasn't fast to start with

Hmm. Trying to figure out how I'm 24k higher than yours, I noticed the file I saved has \r\n newlines. Is yours the same? I might have saved it wrong.

Mine is saved exactly the way it's shown on the site (i.e. open page, ctrl+s). Not c+p.

Wow, parsing numerics did not bring the count down as much as I thought it would

Guess Shakespeare was not into numbers ;)

isaacg just posted 601222 for Hamlet ;)

how...

Oh, lol

Oooh!

I'm 601215 for hamlet!!

4:50 PM

I just got 601207 by saving the file right :P

D:

dammit

So did you leave the trailing newlines in?

Wait a sec, having some issues here.

@TheNumberOne we could also get 136 in py2 with c+=(e=='[')-(c>0<e>'[') and removing the parentheses around print, to make up for raw_

@Shebang Can you show a snippet of your hamlet start? <1000 bytes or so?

i've seen in some problems that answerers require the input to be surrounded in quotes to avoid raw_, but i don't know if that's within the rules for this problem

4:54 PM

@Geobits I assume of the Fourier file, right? :p

oh, 135 in py3 with c+=(e=='[')-(c>0!=e>'[')

Yep

pastebin.com/7UdHpBza

Can anyone tell me what the fuss about foo is about? Does just any string compile to a valid program?

Basically, the only interpreter for it that was found didn't treat invalid operations as exceptions to end it, instead just as noops

5:01 PM

Weird. I get a lower score for hamlet than isaacg, but 150 higher for the bible.

That's odd

I don't know why, but python reading the bible is so much slower to process

It's not using windows-style line endings, but that shouldn't make a difference.

5:33 PM

I figured it out. A bit of extra number-work got it under his by a single character.

Posted :D

@Dennis i remembered seeing one that was closed for improper spec, and it was apparently deleted, but i found a copy here programming.nullanswer.com/question/24063096

there's a link to source codegolf.stackexchange.com/questions/5466 (page not found)

Yes, it was closed/deleted for not having a winning criteria (by Dennis, among others ;)

That explains why I thought I had seen it. :)

5:49 PM

0

Q: Who is the rightful ruler?

Who will rule the realm? Your challenge is, given a JSON object containing the data of the current ruler, its sex, its date of birth and of death, and a list of its sons/daughters, determine who will rule the realm in which order. The succession rules are the following: When a king dies the re...

@Geobits since I sent my last message the output has gone up from ~300KB to ~2.8MB.. I can't figure out why this is so slow for the large one

The small one takes ~7 seconds, and the large one is only ~21.5 times larger

I don't know enough about how python handles strings (or your algo) to say why, but that does seem a bit slow.

I got mine down to a couple seconds for the bible one.

New Sandboxed Posts

6:05 PM

0

A: Sandbox for Proposed Challenges

Golf a game of Nim Similar to my previous Write the shortest game of Alak challenge, this time you have to golf another simple game - Nim. You may already know how to play, but if you don't, here are the rules: In Nim, two players take turns removing objects from heaps (piles). Each turn, one...

6:17 PM

Yeah, I'm not sure what would cause such a drastic slow-down.

Once I actually get a result I'll see if I can get some help from other Python-ers

I thought Python users were (unfortunately) called "Pythonistas."

I like Pythonarians.

Pythonians?

You freakin Pythophile!

"Pythonistas" sounds more like they serve espresso than like they use Python.

Pythophile should be the name for Pyth users :P

6:20 PM

@Geobits I like that as well.

You could also call them gluttons for runtime punishment ;)

Haha

After looking up 'gluttons' even I got the joke=)

Now sitting at 5,066,752 bytes

So about 37% through if it's close to your results

What are you doing?

6:22 PM

10

Q: Golfing strings in Fourier

Challenge Given a string as input, output the shortest possible Fourier program to output that string. In Fourier there is no easy way to output a string: you have to go through each character code and output that as a character. Fourier The language is based upon an accumulator, a global var...

code-challenge metagolf

Should be pretty close, it was only a few bytes difference on hamlet.

@flawr My program for it has become incredibly slow, so I've been waiting to post for a while now so I can figure out my results :P

I'm back

No, you are Beta Decay

@BetaDecay Hello back

@Optimizer "Is this the Krusty Krab?" "No, this is Patrick."

No, this is Patrick

6:36 PM

Spongebob, how can you watch this??

I grew up with Spongebob, broseph.

with squishy eyes

Squishy?

Squishy

Squishy...

6:39 PM

I shall call him Squishy and he shall be mine, and he shall be my Squishy.

user image

Scented squishy bread case

It looks so sad...

How could you squish that with its face looking like it does? D:

user image

Like that

Ugh babies

Would you rather change gender every time you sneeze or not be able to tell the difference between babies and muffins?

4

6:47 PM

@MitchSchwartz Sorry, I was away from keyboard, I'll look over your suggestions. Thank you :)

Does that mean I eat babies or I cuddle muffins? :P

@AlexA. I'd rather be deaf on one eye.

@BetaDecay It means you can't tell which is which, so you could end up cuddling a muffin or biting someone's baby.

Martin Büttner

(or your own)

@BetaDecay already does this anyway.

6:48 PM

Oh God. That's terrible

I couldn't cuddle a muffin :O

But you could bite a baby?

I have to admit I really like the gender swapping idea=)

As someone with bad allergies, I think I would find it too existentially confusing to be switching all the time.

It is perhaps just slightly unpleasant when you have to sneeze while peeing at an urinal.

Haha

6:50 PM

Or what if you sneeze when having sex 0.o?

Nosepeg

@flawr Dust the house and take a bunch of antihistamines first.

So far one answer: flawr would sneeze swap. Any other takers?

I have no strong feelings about babies or muffins, so they might as well be the same thing to me anyway. I'd go with that option.

On the other hand, babys wouldn't be so annoying if they are muffins, and if you then still find a baby you know that you can bite it anyway.

So that can be an advantage too.

This is getting inappropriate. Remember that there are young people (under 18) that use this chat.

As long as there are no muffins.

6:56 PM

Or babies.

@TheNumberOne In what way is it inappropriate?

It's just a silly question.

@Geobits That would make the world a simpler place.

@AlexA. In about 120 years it would be a much simpler place.

Haha

Did anyone read The knife of never letting go (and the sequels) by Patrick Ness?

« first day (1671 days earlier) ← previous day next day → last day (3171 days later) »

Transcript for

Aug '1527

The Nineteenth Byte

The Nineteenth Byte: General discussion for codegolf.stackexc...

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile