The Nineteenth Byte

Basset Hound

01:26

What's the syntax for the CJam while loop (w)?

Dennis

{condition}{block}w

0{_10<}{_p)}w; prints the numbers from 0 to 9.

Basset Hound

Ah.

Thank you @Dennis

It freezes the online interpreter?

Dennis

It doesn't.

@AlexA. Makes sense. I wonder which one works in IE (if any).

Basset Hound

Alright.

In while loop blocks, do things put onto the stack stay on the stack?

My code is giving me a no.

Alex A.

@Dennis I have a Windows VM on my Mac and the first thing I did when I set it up was uninstall IE. :D

Dennis

01:36

They do. But be aware that, after the first block is executed, one item is popped from the stack to check if it's truthy.

Basset Hound

Alright.

Dennis

@AlexA. Probably not an issue for a VM, but you can't install CorelDRAW without IE. I learned that the hard way.

Alex A.

What's CorelDRAW?

For whatever reason, Visual Studio also requires IE. It wouldn't let me finish the installation until I reinstalled IE. But I reuninstalled it after VS.

Dennis

Graphic design software.

The CD installer requires IE to display the EULA. But doesn't say so. Just hangs.

Alex A.

Haha awesome.

if (browser.name != "IE") { wait(100000000000000000000000000000); }

Dennis

01:44

Yup, that was a fun afternoon.

Alex A.

Was it an urgent work-related venture or were you installing it for home use?

Dennis

02:06

For my sister in law. She's studying graphic design.

BrainSteel

02:20

I have been summoned in the most delightfully confusing manner.

Dennis

03:31

Why is this challenge so unpopular?

-1

Q: Magic Square Challenge

A magic square is a square where the rows, columns, and main diagonals all add up to some number n. Your Task Create a solver that given an unsolved square as a list and some number n on stdin will print the solved square as a list. You should be able to put any solvable square in it and get a...

code-golf

Three downvotes and one vote to close as too broad...

Dennis

05:07

@RetoKoradi Yes, that's correct. I'm not sure what is going on there. As far as I can tell, the answer uses i for base conversion, which should downright refuse to interpret "15" as a base 5 number.

Reto Koradi

@Dennis My "solution" gives [3 8 10] for that input. But it doesn't handle the invalid cases at all, and is already 40 bytes. So I'll probably not finish it. At least it seems mathematically correct.

On the magic square: I didn't vote, but it's very confusing because it changed so many times. Maybe that's why people downvoted. At some point, it said that it would only have to deal with single "failures". Now it says again that it should solve all cases. Also, while that's probably insignificant, I don't understand why some numbers are bold in the output at the bottom.

Dennis

@RetoKoradi Right now, it says with at most one wrong number in each row and column. The bold numbers are those that have been relocated.

Reto Koradi

Yes, I had just figure out the bold numbers.

Dennis

That's probably worth adding to the question. It took me a moment to figure that out as well.

The edits pretty much left a mess, but I think the votes should be based on the current state of the question, not it's history.

Reto Koradi

Right, it does say "at most one number...". While I should have seen it, it would be nicer if it were listed as part of a clear input spec.

Your first version would work for all solvable inputs? Or only for the ones with at most one wrong number per row/column?

Well, I guess I could try it. :)

Dennis

05:24

Only for those.

Reto Koradi

Yes, doesn't seem to work if I swap two more numbers in the input.

Solving the "real deal" would be more interesting in some way. Not sure how efficiently it can be done. Might be more suitable for a performance challenge if there's no efficient way that is still reasonably easy.

Dennis

I've made a few edits to highlight the things we talked about.

Reto Koradi

Thanks. That should help those of us who apparently have trouble reading long sentences. ;)

Dennis

I have no idea how to approach the "real deal". A fastest code challenge would probably be interesting. 20x20 square, n entries in incorrect cells, solving for the highest n in x minutes wins.

It's pretty easy to overlook these things, especially if you've read the question before the edit.

Reto Koradi

That would be one option. I was thinking completely arbitrary order in the input, and solving for largest n wins.

Dennis

05:34

Or that.

I'm incapable of writing fast code, so I'm not very good at designing fastest-code challenges.

Exhibit A would be my rather broken domino tilings challenge.

Exhibit B, which nobody has even answered so far:

8

Q: Fastest Longest Common Subsequence Finder

Your task is to solve the Longest Common Subsequence problem for n strings of length 1000. A valid solution to the LCS problem for two or more strings S1, … Sn is any string T of maximal length such that the characters of T appear in all Si, in the same order as in T. Note that T does not have ...

string fastest-code subsequence

Sp3000

Are answers like these allowed? I'm not that familiar with Javascript, but my understanding of this answer is that something like W3000 would fail

Reto Koradi

I enjoy solving them. Even though they are often very time consuming compared to golf challenges. I'm still fairly proud of this one: codegolf.stackexchange.com/questions/52193/…. n=156, after people initially posted solutions that made it to n=5. And the resulting number is about the number of atoms in the universe, squared.

Reto Koradi

05:55

@Dennis Not sure why nobody went for that longest subsequence problem. I don't see anything bad about it. I think what stopped me (apart from probably having a few other half finished solutions to other performance challenges) was that it looked like it might be a fairly standard problem, where the best approach might be to look for literature, and implement a published algorithm. I don't know if that's actually the case, but I don't generally enjoy doing that very much.

Sp3000

^^ That's probably exactly why, actually

Dennis

@Sp3000 I don't think they are. If your language can't handle arbitrarily long strings, that's one thing. But arbitrarily limiting the supported input to save bytes...

Sp3000

Hm... well I left a comment

I guess one of the major differences between PPCG and, say, anarchy golf is you can't do tricks like these since there's more than just a few set test cases

Dennis

@RetoKoradi I haven't seen a lot about the LCS for n > 2 strings, so I hoped it would be a bit more difficult than that.

Reto Koradi

06:10

@Dennis One thing that might help the challenge would be better test data. You show how to generate data, but for development people would probably want an example where they know what the correct result is, so that they can validate their algorithm. The two 6 letter strings are kind of minimal.

Dennis

@RetoKoradi The problem is that there is no single correct result. At most, I could include the correct length of the output.

Reto Koradi

I think that would be very helpful already. Say an example with at least 3 strings of at least a few dozen characters. Enough to exercise an algorithm, and give reasonable confidence that it works correctly.

I guess another "minor" obstacle for me is that I don't know how to solve it... I'm slightly familiar with sequence alignment algorithms, and it sounds at least somewhat similar to that. But those already get much more complicated with more than 2 sequences, as far as I remember.

Sp3000

The standard dynamic programming LCS can be extended easily, but it explodes with the number of dimensions

But yeah, there should be a lot in the literature about multiple LCS/multiple alignment ... that sort of thing

Lembik

07:05

hi @Sp3000

Sp3000

Hi Lembik

Lembik

what I like about ppcg is that no one seems to sleep :)

3

Sp3000

Yeah, about that...

grovesNL

Instead of sleeping at 2am it seems like a great idea to work on my own Code Golfing language. Why...

2

Peter Taylor

07:49

@Dennis In an ideal world. But despite the recent comments, most participants in the site do sleep, and don't spend all of their waking hours on PPCG, so even if the downvoters do feel that the raft of edits have rescued the question you should expect some delay before they change their votes.

New Main Posts

08:11

-1

Q: Selection problem

A Grandpa hits his kid with following problem: His grandpa tasks him with a problem - he says that he will give him as many candies as he wants (N) of all distinct flavours for as many students in his school (K) if he can tell him the sum of the following: 1 The number of ways there are to choos...

java

Sp3000

^^ Super speedy Martin

Optimizer

^^ You should really sleep

Sp3000

Who should?

Lembik

of course what people should really be doing is posting answers to codegolf.stackexchange.com/questions/54354/… :)

Sp3000

08:31

Not with such a lame brute force

Lembik

@Sp3000 isn't your method a little cleverer than naive brute force?

I say that because it is much much faster than my brute force

Sp3000

It's just generates all strings to give a list of possible vertices, then recursive backtracker on the following: Pick first vertex, keep mismatches

I'd call that naive brute force :P

Lembik

well my version runs "max independent set" from a library

and is very very slow :)

I can't do n = 5!

so you are definitely winning :)

Sp3000

I can't either, the numbers I've been saying are intermediate outputs

Lembik

09:11

good point

Peter Taylor

I can get an easy conjectured upper bound based on a conjectured independence number of a tensor power of a graph. But the actual graph obtained is a subgraph of the tensor power G^n where G is the graph of matching single-element vectors, and it's not obvious how that will affect the independence number.

Lembik

@PeterTaylor for my puzzle?

Peter Taylor

Yes

Lembik

cool!

how high is the upper bound?

I mean how does it grow with n?

Peter Taylor

\alpha(G)^n

It's not a closed form, but it reduces the independent set calculation to a much smaller graph.

Lembik

09:13

how does alpha G scale?

oh I see

this could be useful for people doing some sort of optimization so they have a feeling for how far they might be from the optimum

as well as just being interesting in its own right

Beta Decay

10:06

@Geobits Do you mind if I go ahead with this?

3

A: Sandbox for Proposed Challenges

Is it a bird, is it a plane? code-challenge image Challenge Supplied an image, you must determine if the subject of the image is a bird, a plane or Superman. Further information All images will be the objects in flight. The images of planes and birds will be against blue backgrounds (in som...

Martin Büttner

@BetaDecay do you have those 30 pictures yet?

Beta Decay

10:18

@MartinBüttner Ugh, I can't believe I forgot that :P

New Main Posts

0

Q: Cryptic Kicker //

Cryptic Kicker A common but insecure method of encrypting text is to permute the letters of the alphabet. In other words, each letter of the alphabet is consistently replaced in the text by some other letter. To ensure that the encryption is reversible, no two letters are replaced by the same le...

code-golf cryptography

trichoplax

@BetaDecay I don't know for certain but this sounds fairly different from @Geobits' sandbox post despite the similar concept. Yours sounds like it has much more opportunity for little heuristic tricks, rather than being a full recognition challenge. I'd expect them to be interesting in sufficiently different ways to not be duplicates (not my decision though - ask around...).

Beta Decay

@trichoplax Oh okay. I'll see what other people have to say just to be sure

Peter Taylor

10:47

@BetaDecay I don't get the point. The Superman ones can be identified by testing whether the background is white, so they're trivial to distinguish. The interesting bit is distinguishing birds from planes, but that's the part which is furthest from the window-dressing of the question.

And IMO blind classification questions should get closed for lacking an objective scoring method.

Beta Decay

@PeterTaylor I realised that identification of Superman is trivial, but I kept it to keep a theme in the question

Peter Taylor

I guessed that. But if it's a choice between a strong theme or a good question, it's worth sacrificing the theme.

3

Beta Decay

11:03

What would a good replacement for the Supermen be then? Helicopters?

Peter Taylor

Birds vs planes could be a good question with a good scoring method.

Beta Decay

Oh okay. So you're saying that the scoring method I have now should change?

Peter Taylor

Yes. I should be able to tell whether my answer is better than the existing ones before I submit it.

Beta Decay

I see. So that could be remedied by allowing people to see the test images.

trichoplax

11:20

This does now mean that the question is nearer to duplication with @Geobits' sandbox question.

Beta Decay

Tricky...

orlp

12:43

Raspberry Pi Midi-Keyboard

►

lol

BrainSteel

12:57

@Dennis Do not despair! I'm working on improving my fastest longest common subsequence code. Hopefully I can come up with something clever, it's not ready yet :D

New Main Posts

13:24

0

Q: GolfScript, CJam, or Pyth?

I'm not really sure if this is on topic, as it isn't really specified, but I thought I would ask it here anyways. Which is better, Pyth, CJam or Golfscript? In asking this, I do not mean which has a prettier syntax or which has the most useful commands, I mean overall, which one is usually the ...

golfscript pyth cjam

Doorknob

^ oh I am totally going all science on this one, with the data dump

orlp

@Doorknob to complement you, good sir, I gave my random guess without any data to back it up in the comments :)

Sp3000

13:47

Hm... I'm not sure how to feel about this comment...

Pietu1998

The first solution I came up with for Cryptic Kicker only requires 10^4 yottabytes of memory. Looks good.

Sp3000

@trichoplax Might want to award that bounty to orlp before it auto-awards half the amount :P

Sp3000

14:10

@Dennis @Doorknob I thought so... I wasn't exactly sure what to say, but I'd have preferred these types of questions be asked in chat

I'm not sure how you guys feel about the on-topicness of the question though

Martin Büttner

It's not really answerable, is it?

Doorknob

It's answerable:

golfscript is shorter than pyth 6 times (~13.043%)
golfscript is shorter than cjam 16 times (~20.513%)
pyth is shorter than golfscript 39 times (~84.783%)
pyth is shorter than cjam 59 times (~60.204%)
cjam is shorter than golfscript 57 times (~73.077%)
cjam is shorter than pyth 31 times (~31.633%)

Looks like Pyth is the winner.

Sp3000

I'm more concerned about the fact that whatever answer's given will be completely outdated once Pyth, CJam continue development

Dennis

I don't either. I think that if asking for golfing advice is on topic (which I still do not agree with), questions like this one should be too.

Martin Büttner

@Doorknob what about challenges that don't have answers in more than one of the languages? there could be a lot of selection bias. and who says the submissions are particularly well golfed?

it's also completely ignoring that APL and J can be very competitive

NicoA

14:15

Thanks for the scientific analysis Doorknob :P

Doorknob

@MartinBüttner Yeah, it's definitely not perfect. I only chose challenges that had answers in at least two of the languages in question though, and the fact that there are percentages makes that point moot anyway.

I threw in J as an experiment. Even GolfScript handily beat it.

Martin Büttner

@Doorknob "I only chose challenges that had answers in at least two of the languages in question though" that's my point.

There might be certain types of challenges where the other two languages don't ever bother trying.

Doorknob

APL seems to be > GolfScript though.

@MartinBüttner Ah, I see. Yeah, again, not perfect, but overall Pyth seems to perform better.

Sp3000

There's a lot of challenges where one of the two is clearly better, and nobody tries the other language

Doorknob

As a general-purpose language, I guess you could say.

golfscript is shorter than ostrich 1 times (~100.0%)
pyth is shorter than ostrich 1 times (~100.0%)
cjam is shorter than ostrich 1 times (~100.0%)
ostrich is shorter than golfscript 0 times (~0.0%)
ostrich is shorter than pyth 0 times (~0.0%)
ostrich is shorter than cjam 0 times (~0.0%)

:'(

Sp3000

14:19

Ostrich only lost to CJam by 1 question!

3

[/bad statistics]

NicoA

@Doorknob is ostrich the golfing language you are developing? (Kinda new here :P)

Doorknob

@NicoA Not really developing it anymore, but yes.

NicoA

Yeah, I tried to develop my own golfing language, I abandoned it because it was just never beating anything.

So I know now that Pyth is the shortest, but do you think it should be the one I learn? I mean, I have never really messed with "golfing languages" before, and I am afraid I will go into this and not understand any of it. Any prerequisites for learning Pyth? (Besides, obviously, knowledge of Python)

Doorknob

I'm no Pyth expert, but I'm pretty sure you can learn Pyth without knowing Python.

steveverrill

@Orlp: "I'm more concerned about the fact that whatever answer's given will be completely outdated once Pyth, CJam continue development" I see absolutely no problem with that, provided the answer is dated, which it will be. I think it would be interesting to come back in a few years time and see if it needs revision.

Sp3000

14:24

You can learn Pyth without knowing Python, but knowing Python sometimes helps understand why things work the way they do

NicoA

Oh thats awesome! I know Python, but not that deeply. I'm more of a Lua guy.

Dennis

@BrainSteel Does it handle at least two strings? If so, please post it. Might kickstart the question.

Martin Büttner

@NicoA I think CJam is the more fun language, but that's obviously personal preference ;)

steveverrill

@Doorknob, your data is very interesting. If you feel chat is the best place I won't argue, but I encourage you to post it as an answer to that question (and my preference was to leave it where it is)

NicoA

Oh ok, so I shouldn't delete the question?

@MartinBüttner I don't think programming Cjam, Golfscript, Pyth or any of those wil lever be as fun as an actual language with syntax. I mean, when I look at some of those answers it seems like someone just banged their head against a keyboard repeatedly...

Sp3000

14:28

@steveverrill I'm assuming that ping was for me, but I just thought that this type of question is best discussed, and I'm not sure SE's the best place to do that (I could imagine the comments getting long)

Dennis

@NicoA Are you @TreFox?

NicoA

@Dennis Yeah, this is my younger brothers account which I have no idea how to log out of.

Martin Büttner

@NicoA how come? I personally think it's more fun than programming in "an actual language". CJam is stack-based, and switching to an uncommon paradigm makes you think outside the box much more than you usually have to.

if it wasn't more fun, then why would you bother learning it? winning code golf contests really isn't that important ;)

Dennis

Personally, I love stack-based languages. They are written and executed in reading order.

NicoA

@MartinBüttner Well, I guess I'll have to give it a shot before making judgements, I just feel like I don't want to be limited by not actually understanding any of the code I write

Although I guess it becomes much more readable once you know the language well enough

Martin Büttner

14:30

@NicoA any language is illegible until you learn it ;)

Sp3000

@NicoA All golfing languages look like gibberish before you learn it. Once you do learn it it still looks like gibberish... with structure.

3

It's a bit like learning a foreign language, adding a new word to your vocab and going "Oh q~? I know what that means!"

BrainSteel

@Dennis I'm going to test my solution on your random script (I'm not so hot with scripting, still figuring it out) some more. It's derived from that golfed code, so it is in dire need of some prettiness, too. Hopefully I'll have something worth posting by the end of the day.

NicoA

@Sp3000 Now I want to create a country where everyone speaks CJam...

Btw, does anyone know how to log out in chat? I'm stuck on this account and chat.stackexchange.com/logout doesn't do anything for some reason...

Dennis

If nothing else helps, delete some cookies.

NicoA

I think the problem is that this account was actually deleted... but someone it still survives in chat

If you go to my profile and click my parent user the page can't be found

*somehow

Dennis

14:36

So that's while your profile gives a 404.

Doorknob

Yeah, what's weird is that your PPCG account is linked to the account you're currently chatting on though.

Dennis

Which browser are you using?

NicoA

Chrome

Wow... how did my younger brother rack up 1.8k rep :O

BrainSteel

It seems like this recent CJam vs Pyth vs GS question has sparked quite the kerfuffle. Personally, I consider it in league with tips questions, but perhaps we should make an answer to the relevant meta question for a clear consensus?

NicoA

Yay I sparked a kerfuffle

I always wanted to do that

Doorknob

14:37

@Dennis It's not a browser issue. It's something wrong with how SE handles chat / main accounts when dealing with account deletion. (We had a similar issue before with Calvin's sock.)

NicoA

How did they get rid of calvin's sock?

Sp3000

... I think I might have been okay with the question if it was a bit better specified

"Usually the shortest" seems quite broad

Doorknob

Oh hey chat's about to go down for a few minutes.

NicoA

In what way? I can edit it

Martin Büttner

nooooo, chat outage imminent... can't breathe...

BrainSteel

14:38

How will we survive?!

NicoA

I'm going to go huddle in a corner and pray for mercy while its out.

Sp3000

Maybe something like comparing the languages and asking why and when one language does better than another

... that was a short outage

BrainSteel

I feel the question primarily boils down to this: As a community, do we want questions about comparisons of programming languages as they are relevant to the challenges on this site?

Doorknob

aaand we're back!

NicoA

@Sp3000 None of them are really specialized to a certain area though, so would there really be a "When does Pyth beat CJam" ?

Peter Taylor

14:45

@BrainSteel Regardless of the consensus about that point in principle, questions for which the only available answers are speculation are not on topic on any SE site.

NicoA

:(

I'm going to go delete some cookies and try to get myself out of this account

Doorknob

@NicoA hang on a second, I think I found the problem

NicoA

Ok, I'll be fine with whatever you do to this account

Test

Doorknob

I changed your parent site to PPCG. Now at least your parent site link isn't 404'ing.

BrainSteel

@PeterTaylor Solid point. However, I think the question could be posed to remove the speculation. @Doorknob showed that we have objective data that can be used to answer these kinds of questions.

TreFox

14:48

Ok, now when you click on my account it takes you to TreFox, but I still display as NicoA. Do I have to do something else to get my actual name to show up?

Doorknob

@TreFox try refreshing the chat page

Martin Büttner

@TreFox you show up as TreFox now

TreFox

Oh wait, I'm TreFox now. Thank you!

Doorknob

@BrainSteel Well, as @MartinBüttner mentioned, the data is far from accurate anyway. It's just a general... guess in the right direction, really.

Dennis

I've logged out of chat and now I can't get back in. :(

TreFox

14:48

How could a deleted account still be able to talk in chat though?

Doorknob

@TreFox shouldiblamecaching.com

Main site is down now.

TreFox

@Doorknob I think that is the most useful site I have ever seen

BrainSteel

@Doorknob True, it is not necessarily good data.

Sp3000

@TreFox Whenever Pyth has a builtin which CJam doesn't is a good starting point

TreFox

"*Advice may be invalid due to caching" xD

Doorknob

14:50

@TreFox :D

Sp3000

@trichoplax Why the accept?

TreFox

I'm not an expert at any web stuff but a quote from some guy who works at the stack exchange (Yes I peer into my brothers email account every once in awhile. Mostly for espionage reasons but we won't get into that), "We have had no choice but to delete all records of your account from the stackexchange"

Doorknob

Huh what? I've never heard of anything like that having to happen.

TreFox

He was too young for the stackexchange

Doorknob

Oh, that makes sense then.

TreFox

14:53

Luckily I just passed the age barrier :D

BrainSteel

We have an age limit?

TreFox

Because of the Childrens Online Protection Agreement they are not allowed to collect any data (Email, name, etc.) From children under 13.

Doorknob

@BrainSteel Yes, for legal reasons.

TreFox

There is a meta thread about it, I'll try to find it.

@BrainSteel meta.stackexchange.com/questions/61770/…

Doorknob

Main site now in read-only.

TreFox

14:54

Why are they moving their database?

Doorknob

stackstatus.net/post/126135656099/…

BrainSteel

Ah, thanks for the references! Makes sense.

TreFox

@Doorknob Colorado? I fear their database will die of boredom.

Sp3000

And we can write now, whee.

Doorknob

Back out of read-only.

TreFox

14:57

Oh and @Doorknob what happened to your background?

Doorknob

My what?

TreFox

Your profile picture background. It used to be purple (or maybe green, can't remember) didn't it?

Doorknob

Oh, haha, yeah, this was the original version though.

TreFox

What is the difference between the "hot" and "active" tab?

trichoplax

@Sp3000 If you didn't want bounty and acceptance, why did you post a shorter string? :P

Sp3000

15:07

Well I think accepting only a few hours after an improvement has been made seems a bit fast, since orlp appears to be still trying

I won't question the bounty though, that part doesn't matter

trichoplax

@Sp3000 I did remember what you said about the bounty, and weighed my decision carefully, but I decided that since your latest string started from scratch at length 500, and since you've made impressive improvements, I wanted to award the bounty to your answer.

Sp3000

For which I thank :)

(although I haven't made that many improvements though)

trichoplax

@Sp3000 Oh - the acceptance tick I didn't put any thought into. It's had over a week so I accepted the top of the leaderboard. It will be changed back and for as C++ and PyPy battle it out ;)

Sp3000

I dunno, maybe it's just me but I like my "accept answer after <some time period>" to start counting from the last non-trivial answer edit

trichoplax

I don't know if it affected everyone, but where I am the site went down with 20 minutes left to award the bounty - it came back up just in time to avoid the amount being halved...

Sp3000

15:15

Yeah I thought you might have been trying :P SE was doing stuff ^^ see a little bit back in chat

trichoplax

@Sp3000 I would follow that approach if I was going to assign a final acceptance, but I posed this question hoping for open ended improvements, so I'll leave it assigned and switch if new answers/updates come in.

randomra

@Sp3000 on the maze exit challenge did you try to have a fitness function for the strings or do you only deal with perfect (i.e. correct) solutions?

Sp3000

My very first attempt was a GA where the fitness function was the number of mazes solved. It did pretty terribly

randomra

only because of speed or otherwise too?

Sp3000

This one only deals with solutions which solves all mazes, but since some essential mazes are left out they're not quite perfect (although I've only ever seen at most 12 errors)

I'm not sure what fitness function I'd add tbh

(and yeah not having to count the total number solved helps a lot for speed)

(although mine hasn't been optimised with speed in mind as well as orlp's has :P)

randomra

15:26

mazes solved seems to be good fitness function, but you might not want to check all, just sample it

if that makes sense in your implementations

Sp3000

The problem with mazes solved is that most mazes are really easy, and it's the few hard ones at the end which ruin everything

My current one only deals with one string though, so it's less of a GA and more of a random walk

randomra

so you think a string which solve 90% of the mazes helps almost nothing to find one which solves 100%?

Sp3000

It depends which 90% is solved

randomra

the easy part

Sp3000

If you sample uniformly, then yes it wouldn't help much

randomra

15:30

hill climbing/random walk is often disappointingly effective compared to GA... :/

Sp3000

Yeah hill climbing was very disappointing :( Are you trying?

randomra

no, I don't have time in the next weeks, I'm just thinking :)

and reading, this and the game show questions are both fun

Sp3000

To put it in perspective, NESWSEENWNWSSWNNEENWWSESESWWNNESESNNE solves 93% of the mazes

That's length 37.

randomra

I see, but it still could be a useful core for the 100% solution despite their length difference

Sp3000

Hmm not sure about that... that one's from a greedy algorithm, which would solve all the easy ones first. This would mean that all the mazes with long or tricky solution paths are left, and I'm not sure 40 or so moves is enough to solve them all

randomra

15:51

the 37 length string should be broken up with insertions but that would mean a big temporary decrease in fitness, maybe adding weights to mazes based on difficulty could help but that might be a bit too complicated to actually work

Sp3000

Well it might work for all you know :P Sounds like it'd help a lot over the naive approach at least

randomra

the advantage of just thinking and not doing :), you mean the naive fitness-based version?

Sp3000

Well the naive #number of mazes version, yeah

I'm just thinking and not doing atm as well :P

79's looking really likely to me atm, but I'm not sure how long it'll take to get it

trichoplax

Or who'll get it first :P

I didn't expect to see C++ and PyPy neck and neck like this. It's interesting

Sp3000

I'd try seeding orlp's solution with an 80 and seeing what happens but I'm not sure how

trichoplax

16:09

Just needs a standard vector of 0,1,2,3 instead of N,S,E,W

I'd have tried myself but I'm trying to focus on the Computer Graphics private beta for the next week or so

Martin Büttner

huh, somehow I was unable to log into chat for the past 20 minutes or so

trichoplax

Just need to check which number goes with which direction

@MartinBüttner I had that earlier when main went offline

Martin Büttner

it was probably related to that

trichoplax

Made me panic as I had a bounty with minutes left before disappearing...

Sp3000

16:25

@trichoplax Got it, thanks

Dennis

17:01

@MartinBüttner You too? I've deleted all cookies and local stotage and still couldn't. Maybe it will work now.

Yes! I'm back!

(On my desktop, that is.)

randomra

17:39

@Sp3000 if there was a fixed goal cell it would be fun to find sequences by hand as you can visualize the superimposed states of all remaining labyrinths pretty well after a prefix is given in

it could work with the current setup too but less nice and clear the superimposed situation is

it's like a labyrinth game with (somewhat) invisible walls and multiple heros (controlled together)

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

The hue of a color You are given the RGB values of a color. Your task is simple: to calculate the hue, in the simplest definition. Say the channels with highest, middle and lowest value are X, Y, Z (which are either red, green or blue) and their values are x, y, z. The hue of this color is (h(X...

trichoplax

18:25

@randomra That sounds like an interesting challenge too. Finding strings that get all the heros to the destination without killing any of them.

randomra

18:41

@trichoplax there must be a flash game like this

Optimizer

thechive.com/2015/08/06/youre-not-fooling-anyone-27-photos

Vioz-

19:11

@aditsu Do you remember where you got that watch from? I talked to a few people and asked about it, they seem to think it was either given away/sold at a trade show or sold internally

Lembik

20:07

hi @Vioz- @Sp3000

@PeterTaylor am I right in thinking that all your answers for n >= 6 may not be optimal?

@PeterTaylor amazing answer by the way!

Peter Taylor

@Lembik I make no guarantees about optimality.

Lembik

we know the first 5 are optimal

Peter Taylor

To be precise, the greedy algorithm is known to approximate to within a certain ratio which depends on other properties of the graph, and I can't be bothered to look up the details and work it out.

Lembik

@PeterTaylor do you have any feeling for how the value scales?

it's hard to guess by plotting it

ah another value :)

Peter Taylor

By eye it looks subexponential, but it's not something I have an intuition about.

The number of vertices in the graph definitely grows exponentially (there are easy lower bound of 2*3^n and upper bound of n*3^n), but the size of the cliques in G grows too.

Lembik

20:28

@PeterTaylor if you plot it on logscale it looks subexponential as well

but how knows.. it might be subpolynomial too?

Peter Taylor

20:45

Nah, there are easy polynomial lower bounds. A linear lower bound is completely trivial, and a quadratic one isn't much harder.

Alex A.

21:25

@Vioz- Out of curiosity, why is there a trailing dash on your username?

Vioz-

I don't remember, exactly.

Alex A.

Is there a meaning behind "Vioz"?

BrainSteel

It's clearly "Zoiv" backwards.

Alex A.

If you rearrange the letters in "Peru," you can spell "Europe."

BrainSteel

Well, you can get at least to "Eurp." Which is basically the same.

Alex A.

21:32

"Urep" is phonetically close.

BrainSteel

That's Peru backwards! The conspiracy unfolds!

Alex A.

Illuminati confirmed.

BrainSteel

Peru is four letters long... But is only one country. 4 - 1 = 3. HL 3 confirmed.

Alex A.

Aw shit. GabeN is getting tricky naming countries.

Martin Büttner

22:02

@Dennis Awwww, thanks for mentioning Retina in your language comparison :D

Transcript for