The Nineteenth Byte - 2014-10-07

« first day (1347 days earlier) ← previous day next day → last day (3500 days later) »

12:31 AM

I'm trying think of a way to encode 3SAT problems in codegolf.stackexchange.com/questions/38576/…

I feel like it should be possible

2

Q: What to do with the "favorite code golf" question?

The question in question. What should we do with it? It's clearly not a "proper" question for the Stack Exchange network (highly opinion-based and a "big list"), but it's CW and nobody's had a problem with it so far. We could... Close it (primarily opinion based, too broad, etc.) Delete it (p...

discussion specific-question

4 hours later…

4:45 AM

0

Q: Unsatisfied Bounty

My bounty on Coating Every Pancake expires shortly but no one has answered the question in the Pancake Stack language which was the goal of the bounty. Should I just let the bounty run out and award it to the best existing answer? Can I request an extension? Are there other options?

discussion bounty

3 hours later…

Martin Büttner

7:40 AM

@EricTressler let me know if you figure that out :)

3 hours later…

10:32 AM

hi

10:56 AM

hi

11:37 AM

hi

2 hours later…

1:14 PM

Why did we have to open a meta question just to close a question? Are we so far removed from voting like normal that we have to get everyone to agree with us before we cast a vote?

The meta question is even slanted with Doorknob's bias, so it won't get an unbiased answe.

githubphagocyte

@Rainbolt I see the meta question as being for the people who aren't sure. The people who are sure can just go ahead and close vote.

@githubphagocyte I think that's a good view to hold

githubphagocyte

@Rainbolt I agree it would be inefficient if people got the impression they couldn't go ahead and close vote until they'd waited for meta. The idea of close voting is to do it as soon as possible to avoid wasting answerers time.

It seems like a good idea to check if the community agrees with your opinion on a question if you're not too sure

especially if a specific type of question hasn't been adressed yet on meta.

githubphagocyte

1:30 PM

@overactor I agree. If you're not sure, ask. If you are sure, close without asking.

@overactor To be honest, I'm a little more polarized than most people. I have trouble seeing shades of grey.

@Rainbolt I believe Doorknob wanted to make sure of the community's opinion before hammering it. Since there was a bounty on the question, it couldn't be close voted in the normal way and needed mod intervention.

Is there a bounty limit on questions? Could I repeatedly bounty something to keep it alive?

@Rainbolt how many shades of grey can you differentiate?

@Rainbolt You could, if you timed it right. I've seen something similar on SO, but if it's obvious what's going on a mod usually steps in :P

1:33 PM

@overactor Only three: my way, your way, and stuff I don't care about

I don't see shades of grey, but I see many shades of gray ;)

@Rainbolt you'd need to offer up more and more rep too, I think

Are you making fun of my correct spelling? :-(

Guess I better get started on my KotH factory so I can farm rep for the ultimate bad, immortal question.

So no one is sinking to my level of puns relating to literary porn for frustrated middle-aged women?

Not at all, my good sir. I spell it with the 'e' most of the time.

1:38 PM

I spell it with an 'a' most often, but only because that's the title of the wikipedia article "Gray_Wolf"

Wikipedia even spells it two different ways within the same article: en.wikipedia.org/wiki/Castle_Grayskull

I wish TFS had a way to block work items that threw an alarm for everyone else. Apparently, someone else was waiting on me to finish a task so they could complete theirs, but I had no idea anyone was waiting on me.

2:01 PM

TFS?

@EricTressler Team Foundation Server

I've never seen that many Wikipedia warnings on an article lol

it does sound kind of like ad copy

2:29 PM

@Geobits Not only that: it was a mod who put the bounty on the question, and when even the mods don't agree on whether a question is a good one or not there's definitely a case for seeking opinions from the community.

@PeterTaylor The mod who put the bounty on the question is biased because he created the question.

@PeterTaylor True, but I didn't see who'd placed the bounty at first because I was looking at the question in the mobile app. It wasn't until I was at a desktop that I noticed that, but I couldn't close-vote it either way.

I'm just glad we have two active mods. I just looked at Gnibbler's profile and he apparently has been asking and answering a lot.

And he said he was going to bring back some of the older questions from SO that were deleted. So that's exciting.

1 hour later…

Martin Büttner

3:57 PM

@Geobits I always thought "grey" == BE, "gray" == AE?

@MartinBüttner When I Googled it, I eventually found some article that said grey was becoming more prevalent in AE

Martin Büttner

I see

thanks

NGrams for American and British

It's not a hard and fast rule, but it's generally more used the way you describe.

I'd tend to believe the ngram over what I just said.

I just like 'grey' better. Other Britishisms like the extra u in 'colour' are just absurd :P

4:04 PM

why is that absurd?

levelled or leveled?

Because I'm American, obviously ;)

leveled is right, but so is travelled. I'm nothing if not inconsistent.

:)

math and maths bother me

but I have to admit to having a soft spot for movies as in talkies

books.google.com/ngrams/…

I see the americans swapped over around 1915

I cringe every time I hear 'zed', but I watch a fair bit of British TV, so I'm used to hearing most things both ways.

That and most English-speakers I met in Japan spoke closer to British than American.

What is zed?

Z

Z (named zee /ˈziː/ or zed /ˈzɛd/) is the twenty-sixth and final letter of the ISO basic Latin alphabet. == Name and pronunciation == In most dialects of English, the letter's name is 'zed' /ˈzɛd/, reflecting its derivation from the Greek zeta (this dates to Latin, which borrowed Y and Z from Greek, along with their names), but in American English, its name is 'zee' /ˈziː/, analogous to the names for B, C, D, etc., and deriving from a late 17th century English dialectal form. Another English dialectal form is izzard /ˈɪzərd/. It dates from the mid-18th century and probably derives from Occitan...

Martin Büttner

4:10 PM

lol

I love the Spanish pronunciation of the letter 'y', "ee-gree-ay-guh"

Martin Büttner

the German pronunciation is close to "epsilon"

They started off so simple. "Ah, Beh, Seh, Cheh, Deh, Eh, [...] Doh-bleh-veh, Eh-kees, ee-gree-ay-guh, zeh-tah"

I guess they ran out of simple names halfway through

In English, duh-bull-yoo is three times more complicated than every other letter

Martin Büttner

yep

funnily, just today, I had a Spanish lecturer whose handwritten W actually did look like two u's

oh, btw Icelandic also does the double-u thing, just with v

it's "tvöfald vaff"

4:25 PM

Spanish calls it double-v (uve doble).

Martin Büttner

@PeterTaylor regarding the apollonian circles... if it turns out that really no one has looked in to that parameter space, do you think a thorough analysis of that might be publishable?

also, do we have any indication that the unbounded packing we've got is the only one that exists? i.e. every point in the parameter space that never converges will be found somewhere in that tiling?

If no-one has published anything on it, a thorough analysis would certainly be publishable.

@MartinBüttner It isn't. math.columbia.edu/~staff/RTGPapers/UnboundedPackings.pdf contains examples of others.

Martin Büttner

ah, thanks

Martin Büttner

5:04 PM

@PeterTaylor btw, are you actually going to post the JS code you had for the apollonian gasket challenge?

@Geobits I have the opposite problem. Every time I see "EZ-something" I first automatically translate it to Eee Zed Something... And La-Z-Boy becomes "Ell Ay Zed Boy" ?!?! ;-)

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Play Your Cards Right code-challenge Game Rules Play your card right is a game played with a pack of 52 cards (no jokers). At the start the deck is shuffled and the dealer will lay a single card on the table. The player then has to decide if the next card is higher or lower than the card on t...

@Rainbolt Similar to French ee-grek, I think. Literally "Greek I"

Great. Now I won't be able to stop seeing ee-zed on signs :P

New Sandboxed Posts

5:21 PM

0

A: Sandbox for Proposed Challenges

2D Collision Detection code-golf geometry This challenge is based on actual collision I had to write for a simple game once. Write a program or function which, given two objects, returns a truthy or falsy value depending on whether the two objects are in collision (i.e. intersect) or not. You...

Martin Büttner

I was thinking about a two (or more) phase KotH today, in some form of bottom-up fashion: in the first round everyone writes drones in some "normal" KotH fight (which would probably need some interesting feature to make it worthwhile)... but this would in principle be just something like Wolf or CodeBots or Battle Bots etc. Then in the second KotH you get to write a coordinator which can use the drones you wrote in part 1, and can give them some form of commands.

Are you restricted only to the drones you wrote in the first part? If you could create a team of mixed drones from other people, that could be interesting.

Martin Büttner

yeah I was wondering about that too

Soham Chowdhury

@MartinBüttner Meta-Koth be with you.

On the same token, if your drone ended up badly in the first one, it wouldn't be worth it to even enter the second.

Soham Chowdhury

5:33 PM

What about continuing that? As in, a third round and so on?

Martin Büttner

yes, that might be possible... but it might also get either dull or just infeasible after round two

there might also be other ways to do multi-part koths by just doing a continued story line and/or using the last KotHs bots as mobs for the new KotH

Soham Chowdhury

5:56 PM

Has anyone here heard of GGP?

General game playing?

Martin Büttner

yes

I know someone who does (did?) research on that

Soham Chowdhury

Cool!

I did half of the GGP course on Coursera back when I was in eighth. From what I remember, it might make for a fun KotH series.

Which brings another idea to mind.

What about having a persistent KotH?

Martin Büttner

persistent in what sense?

Soham Chowdhury

There's a persistent leaderboard.

Every week, there's a contest.

Martin Büttner

well that requires new submissions to come in

I'm pretty sure some of the existing KotHs are still open

e.g. Rainbolt doesn't usually put a deadline on his KotHs

Soham Chowdhury

6:00 PM

Three are chosen from the top three from every week in a month.

hi @SohamChowdhury

Soham Chowdhury

@user2179021 Hey!

Speaking of which, I keep meaning to update my Hunger Gaming leaderboard... I should set an alarm or something.

@SohamChowdhury any thoughts on the dots and boxes koth?

Soham Chowdhury

Yeah.

6:02 PM

cool!

Soham Chowdhury

I've been playing a bit by myself, to get a feel for the game.

Remind me, what was the controller written in for your question?

@SohamChowdhury there was no controller :( codegolf.stackexchange.com/questions/30313/…

@SohamChowdhury but had there been one, I would have written it in python :)

Soham Chowdhury

Ah. That's nice.

@rangu code was pretty amazing by the end

Soham Chowdhury

Let's see. Progress will be slow - I'm very busy right now, but I'll try to squeeze in as much as possible. :)

6:04 PM

@SohamChowdhury I mean the code of rangu

@SohamChowdhury surely there can't be anything more important?!! :)

Soham Chowdhury

I agree, but everyone and everything else disagrees.

:)

Martin Büttner

6:32 PM

added test cases to the collision detection proposal

0

A: Sandbox for Proposed Challenges

2D Collision Detection code-golf geometry This challenge is based on actual collision I had to write for a simple game once. Write a program or function which, given two objects, returns a truthy or falsy value depending on whether the two objects are in collision (i.e. intersect) or not. You...

7:04 PM

@MartinBüttner I can't say I understand
Ell's amazing solution sadly

this one codegolf.stackexchange.com/questions/38466/…

Martin Büttner

it does make sense to me

imagine an infinite pyramid with n sides

@MartinBüttner would you mind helping me to undestand it

sure

Martin Büttner

now take n (unit, if you want) vectors from the apex along each of the edges

now add those. you'll always get a point inside the pyramid

ok that I completely get

thank you

but not the next bit

ok let me be more accurate

I can see you can look at each pair of planes and find where they intersect

and I understand that you took the lines of intersections of planes and summed them you would get a point inside the region bounded by them

but then what does he do?

this part

"The program recursively partitions the space by incrementally adding planes and subdividing the currently-explored region, while keeping a track of vectors along the lines of intersection and eventually taking their sum."

take the first 3 planes, one at a time. We add one plane and do nothing, then another and record where they intersect, then another and record all the intersections. Now what do we do?

Martin Büttner

7:21 PM

I'd just ask him to elaborate on that part

but I imagine he keeps track of the regions and just figures out which ones are intersected by a new plane

ɐɔıʇǝɥʇuʎs

7:35 PM

You know what's lovely?

When things work.

(Pdb) 12 in J('i.40')
True

Martin Büttner

very true

ɐɔıʇǝɥʇuʎs

Also: hi, it's been a long time!

Martin Büttner

I was just gonna say!

ɐɔıʇǝɥʇuʎs

Finally got my J bindings for Python working, and it's quite a bit of fun to use, I must say

Unfortunately, it's a huge mess...

I mean, this is an actual line of code:

result = self.i(JFunc('{.@:,', self.i)(self))

Oh well, it's still better than the actual J source code

Using J must've poisoned their minds, making them golf code everywhere...

Martin Büttner

what's J written in?

ɐɔıʇǝɥʇuʎs

7:49 PM

C & C++

Martin Büttner

k

ɐɔıʇǝɥʇuʎs

github.com/openj/core

Opening a random file, random function:

static A jtscubc(J jt,A z,A i1,A p){A a,q,s,y,y1;B*qv;I c,d,h,j=-1,m,n,*sv,*u,*v;P*zp;
zp=PAV(z); a=SPA(zp,a); n=AN(i1); h=AN(a)-n;
if(!h)R mtm;
GA(s,INT,h,1,0); sv=AV(s);
d=1; u=AS(z); v=AV(a); DO(h, d*=sv[i]=u[v[n+i]];);
RZ(y=repeat(p,SPA(zp,i))); m=*AS(y);
RZ(y1=take(v2(m,n),y)); v=AV(y1);
GA(q,B01,m,1,0); qv=BAV(q);
if(m){memset(qv,C0,m); DO(m-1, if(ICMP(v,v+n,n)){if(d>i-j)qv[i]=1; j=i;} v+=n;); if(d>(m-1)-j)qv[m-1]=1;}
RZ(y1=repeat(q,y1)); c=*AS(y1);
if(!c)R mtm;
R less(stitch(repeat(sc(d),y1),reitem(sc(c*d),odom(2L,h,sv))),y);

They must've skipped those classes on "Descriptive function names".

*Variable

not function

those are somewhat descriptive, sometimes.

Martin Büttner

oh my god, who does that

ɐɔıʇǝɥʇuʎs

The people who make J :S

Me, constantly: "I know, I'll just look it up in the source!" 2 seconds later: "No wait, I won't."

Martin Büttner

:D

It's like when I was implementing my own ES5-compliant regex engine... "I know, I'll just look up this edge case in the spec!" 2 seconds later; "No wait, let's just do some thorough testing in all browsers and see what they do."

ɐɔıʇǝɥʇuʎs

7:53 PM

Well, ES and regex, that can only be a fine combination...

Martin Büttner

Well I chose it because it was the simplest common one. And because I was writing the engine in JS, so I could easily test my engine and the browser's side-by-side.

ɐɔıʇǝɥʇuʎs

Hmm, I see

I'd also choose it over PERL's...

Martin Büttner

I agree though, it's my least favourite (popular) flavour

ɐɔıʇǝɥʇuʎs

Python's is the only one I know somewhat-ish (as in "I might be able to hack something together with re.DEBUG")

Martin Büttner

python's is the only one that just doesn't have anything particularly good or bad I think :D

except the proposed new one, that one is just mad :D

ɐɔıʇǝɥʇuʎs

7:58 PM

Proposed new one?

Martin Büttner

this one: pypi.python.org/pypi/regex

ɐɔıʇǝɥʇuʎs

I think I'll just keep writing code to describe what I want to do, thank you very much.

@MartinBüttner No, I'm going to post some GolfScript code, so I was leaving a bit of time to let other people answer before I scare them away.

Martin Büttner

@PeterTaylor are you writing some simple graphics format like ppm or how do you do graphics with GS?

@ɐɔıʇǝɥʇuʎs well, I find regex more legible than J for instance :P

ɐɔıʇǝɥʇuʎs

@MartinBüttner But J is pure art! avarage =: +/ % # (pronounced "Sum divided by lenght")

Martin Büttner

8:05 PM

so is regex :P

It outputs svg. Although I am thinking of maybe doing a rastering version with output in netpbm as well.

ɐɔıʇǝɥʇuʎs

Hmm, yeah

Martin Büttner

@PeterTaylor ah I see

well in that case, I might bounty it, and if there are still no answers in a week, you can post yours to grab it

Ok. That way only the people who read chat will be scared off ;)

Martin Büttner

:P

well, answering a bountied question would probably still get them a decent amount of upvotes

you could post the JS one to get the ball rolling though (and then add the GS version later) ^^

8:11 PM

hey

Martin Büttner

but I guess you can't be bothered to golf that one down as well (which is understandable)

do we have a problem for taking a dictionary and finding a chain of words between two words?

Martin Büttner

@EricTressler going back and forth you mean?

@EricTressler, yes.

i.e., uh.. hang->hand->hard->shard->shark

Martin Büttner

8:12 PM

oh that

@PeterTaylor do you happen to remember the title or anything of it?

Martin Büttner

I was thinking 2-language dictionary

17

Q: 1P5: Word Changer

This was written as part of the First Periodic Premier Programming Puzzle Push. The Game A starting and ending word of the same length are provided. The objective of the game is to change one letter in the starting word to form a different valid word, repeating this step until the ending word ...

code-challenge word-puzzle 1p5

8

Q: Word Spinner Puzzle

This is a word puzzle. Your program should accept two words on the standard input. Word one is the start word. Word two is the end word. From the start word you have to reach the end word changing/add/remove one letter at a time. After each modification it must form a new valid word. Added lett...

code-golf word-puzzle

okay. Thanks

I thought of it while I was driving and thought it would make a nice golf challenge. I guess it did

@PeterTaylor are you magical, (inclusive) or good at searching SE?

Martin Büttner

8:14 PM

@VisualMelon I think he's just been here from the beginning and has a very good memory ^^

ɐɔıʇǝɥʇuʎs

@VisualMelon I love that you can make that sort of remarks here, everywhere else you'd just get blank stares

I probably should have searched for word puzzle before I bothered everybody

@ɐɔıʇǝɥʇuʎs I couldn't decide if I needed the bracketed part or not ;)

It could be fun to take a single word, perform BFS, and then put the result into graphvis

@VisualMelon, I found the first one by searching for a reference to Lewis Carroll, and because it wasn't the one I remembered I searched for "heap", as I remembered commenting on the exotic heap I used in my solution.

8:18 PM

@PeterTaylor I was reading your solution before I realized it was yours; I was very interested in the worst-case scenario, because it would be kind of fun to submit it to a newspaper puzzle column or something

just to screw with people

ɐɔıʇǝɥʇuʎs

Just realized I may have added a few too many debug flags to my bindings:

(Pdb) J('12')**J('12')
[D] query : REPR =: 5!:5 <('TMP')
[D] shape : 41109300
[D] type : 2
[D] pos : 41109304
[D] rank : 1
[D] shape : [2]
[D] datalen : 2
[D] ctype : <class 'ctypes.c_char'>
[D] ctypesize : 1
[D] shape : [2]
[D] shape_i : 2
[D] query : REPR =: 5!:5 <('TMP')
[D] shape : 41109492
[D] type : 2
[D] pos : 41109496
[D] rank : 1
[D] shape : [2]
[D] datalen : 2
[D] ctype : <class 'ctypes.c_char'>
[D] ctypesize : 1
[D] shape : [2]
[D] shape_i : 2
[D] arg1 : 12
[D] arg2 : 12
[D] Diad
[D] query : (12) (^) (12)

It would be especially interesting to find two words with small edit-distance, but a really long shortest path

so that it looks like it should be easy, but in fact it's horrible

ɐɔıʇǝɥʇuʎs

@EricTressler Could be an interesting challenge

It's not objective to minimize edit distance and maximize shortest path, and any function of those two will lead to the same solution, so it will have to be code golf

so it would be a duplicate

at least, roughly a duplicate

ɐɔıʇǝɥʇuʎs

Possibly koth on a private testing wordlist

8:22 PM

I guess I'd like something like max(max shortest path - (edit distance)^2)

I might just code it myself to see. I could steal @PeterTaylor's code and modify it

The other trick you could use to make a hard puzzle is to pick a pair which necessarily involves the path going through a rare word that people won't know.

ɐɔıʇǝɥʇuʎs

@PeterTaylor f(a,b,c), check if a>b goes through C

*c

@PeterTaylor that's true, but I mostly had in mind something that would make people sort of angry when they see how long the shortest solution is, even though the two original words are similar

ɐɔıʇǝɥʇuʎs

You're also putting J at an disadvantage then, because it requires more than 3 arguments

*more than 2

I guess I just want to prank Will Shortz

8:25 PM

Actually the rare word idea ties into the subject of vertex-connectivity, which hasn't been asked.

Although as a golf it's quite boring. I'm not sure offhand what the known bounds on complexity are.

ɐɔıʇǝɥʇuʎs

@PeterTaylor The tag of vertex-connectivity?

K-vertex-connected graph

In graph theory, a graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected. == Definitions == A graph (other than a complete graph) has connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. Complete graphs are not included in this version of the definition since they cannot be disconnected by deleting vertices...

"Polynomial" - not very descriptive. Might be an interesting fastest-code

ɐɔıʇǝɥʇuʎs

@PeterTaylor Huge.

well... 1-connectivity is pretty trivial to check, though the naive way is |V|^2

temporarily remove a vertex, and floodfill to check for connectivity. repeat for each vertex

ɐɔıʇǝɥʇuʎs

No, wait, I was thinking of a different question

8:30 PM

so k-connectivity is trivially O(|V|*(|V| choose k))

@EricTressler Which is why I said it would be boring as a golf.

yeah. but I wonder... you might be able to use Ford-Fulkerson or something to identify cut-vertices and reduce that

it's probably the case that all potential cut-vertices have max flow across them, with a suitable source and sink

ɐɔıʇǝɥʇuʎs

@PeterTaylor I was thinking of this one:

1

A: Longest mathematical expression in a grid

Python + networkx (Bruteforce, checks about 10000 paths per second on my machine) It's not fast, but it works at least. Checks literally every path. Amount of cycles necessary can be found here. This program solved a 5*6 in half an hour. TODO: replace eval by something less terrible. Done. ...

I believe I guessed O(A!*B!*AB!), but I'm not sure if that's remotely correct

Martin Büttner

@ɐɔıʇǝɥʇuʎs I never finished converting my code to use bigints :/

ɐɔıʇǝɥʇuʎs

@MartinBüttner :(

8:34 PM

@ɐɔıʇǝɥʇuʎs Sorry, I can't work out which previous post you're referring to.

Martin Büttner

I've got a list of 10 optimisations to considerably prune the search space, but I was never able to try them out unfortunately ^^

ɐɔıʇǝɥʇuʎs

@PeterTaylor Mouseover :D The one about the complexity of vertex-connectivity, but I realized that is was a different problem

You must have a higher screen resolution than me :P

ɐɔıʇǝɥʇuʎs

Unlikely

I just have 3 cheap 1080p's, so I only have 1080 in height

Martin Büttner

@PeterTaylor you know you can click the little reply arrow?

8:36 PM

i have one that's 1440x900 native, but my vision is so bad that i run it considerably lower :(

oh, huh. i'm running it at native resolution now. oh, I remember, that's from when I learned that you could zoom in within a browser

Wow I am really tired. I opened Windows explorer and started Googling for something that I needed.

2

1 hour later…

10:12 PM

@Rainbolt You booted up Windows? Wow, you must be really tired.

:P

« first day (1347 days earlier) ← previous day next day → last day (3500 days later) »

Transcript for

Oct '147

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