The Nineteenth Byte

trichoplax

16:00

So we want some sort of compromise where you have to do a few more lookups but don't need to store so much data?

Nathan Merrill

anything below O(N^2) memory, and faster than dijkstras

orlp

@NathanMerrill what does the graph look like?

Nathan Merrill

highly connected

orlp

can any node be connected to an arbitrary amount of other nodes?

ah

Nathan Merrill

yes

a diameter of, say, 10

(the example I'm using is Linkedin, but it could also apply to facebook)

TimmyD

16:02

Are you only looking for a single pair? In that case, BFS is already shorter than Dijkstra's -- O(E+V) vs O(E+VlogV)

orlp

@NathanMerrill what you can do

is split up the graph in k disjoint sets of nodes

Nathan Merrill

oh, my bad. I did mean BFS

orlp

@NathanMerrill then you do the bruteforce algorithm that computes the shortest distance between each pair of the k clusters (k^2)

and stores with each pair the entrance/exit nodes

then when you actually need to compute the distance between 2 nodes, you find which cluster they are in

then look up the distance between the clusters

Nathan Merrill

that's assuming you can find disjoint sets

trichoplax

For cases where there are more than one entrance/exit with the same distance, do you need to store them all?

Nathan Merrill

16:06

for a highly connected graph, I'm not sure those exist

orlp

@NathanMerrill you misunderstand what I mean with disjoint

Nathan Merrill

@trichoplax no. you don't even need the path, simply the length

orlp

just make sure one node is in exactly one sub cluster

how it is connected is irrelevant

trichoplax

@NathanMerrill I see this - but the path length through the cluster will be affected by the choice of entry and exit nodes

Easterly Irk

@Neil It does. THANKS A LOT!!!

orlp

16:08

you turn the question "dijkstra A -> B" into "lookup cluster for A and B (Ac, Bc), lookup distance and enter/exit nodes Ac -> Bc, lookup distance A -> exit(Ac), lookup distance B -> enter(Bc)"

Nathan Merrill

@orlp lets assume that you are able to cluster people such that there are no overlaps (which I'm not sure is possible)

orlp

@NathanMerrill is it really that hard to split up a set of nodes?

trichoplax

@NathanMerrill The shortest path from a node in cluster A to a node in cluster B going via cluster C may use different entry and exit nodes for C than the shortest path from D to E going via cluster C, and the path length through C could therefore be different

orlp

@NathanMerrill I mean vertex disjoint, not edge disjoint

Nathan Merrill

I'm going to be naming nodes A1 to refer to node 1 in cluster A

lets say that the shortest path from A to C is A1 B1 C1

but I want to find the path from A2 to C2

where there's another path, A2, D1, E1, C2

Optimizer

16:12

WTF WE WERE TALKING ON-TOPIC A FEW MINUTES AGO??

damn, I missed it

Nathan Merrill

but your algorithm would give A2, A1, B1, C1, C2

trichoplax

@Optimizer This is the same topic continuing...

Optimizer

ohhhhh

phew

TimmyD

@Optimizer Kittens, politics, isn't this game amazing, oo look xkcd

trichoplax

@Optimizer Did your garden grow anything new?

Optimizer

16:14

as i said.

orlp

@NathanMerrill maybe they do need to be edge disjoint

Optimizer

it resets every 15-20 minutes

orlp

nvm

Optimizer

left it long time back

trichoplax

@Optimizer I had to open mine it a separate browser window to prevent resetting

Optimizer

16:15

i actually did that only

from the start

new chrome window

Sp3000

@xnor I get the feeling... you can drop 6 apostrophes in that Python answer

orlp

@NathanMerrill it can still speed things up though

@NathanMerrill it provides an upper bound on the distance, pruning the search

Nathan Merrill

sure, but if you're doing BFS, I'm not sure if you need a prune

orlp

@NathanMerrill that's why you do DFS

err nvm

but even in BFS it prunes

trichoplax

@Optimizer The other thing you can do is copy the url and then you don't need to leave the browser open - it will keep growing server side and you can just check back in on it using the url

Optimizer

16:16

the url was always the same for me

so it was resetting server side too

Nathan Merrill

sure, but a BFS would find the node before hitting the pruning

that said, providing a prune for a dfs is very useful, because dfs doesn't have the same massive memory requirements

trichoplax

Are you already considering the BFS starting from both nodes simultaneously?

Nathan Merrill

oh, no. that does appear to be more efficient intuitively though

though I couldn't prove it

trichoplax

Should only take X/2 steps instead of X steps for path length X

But checks more nodes each time

Sp3000

@xnor And a pair of parens

Nathan Merrill

16:20

but the branching factor is what matters

(N/2)^X + (N/2)^X < N^X

trichoplax

For a fixed branching factor F you'd have 2F^(X/2) instead of F^X, which sounds better for any but very small X

mınxomaτ

It's really quite ironic that "TheDailyWTF"'s servers are almost less reliable than the hardware the actual WTFs are about.

I find myself reading the site through Waybackmachine more than the actual site.

Easterly Irk

3 hours till the election ends...

@QPaysTaxes In python?

hm

@Doorknob ^^^^^^

xnor

@Sp3000 hmm?

orlp

@NathanMerrill gi-tage.de/archive/2004/downloads/gitage2004/vortraege/…

edge flags

trichoplax

16:24

@NathanMerrill The reason I asked about starting from both nodes is that I was wondering whether a stochastic approach starting from nodes in the middle would give an expected speed up. Even though you'd have no idea if the extra selected nodes happen to be on a shortest path, they'd still speed up finding a path, provided you can then cope with that not being shortest and go from there

xnor

@Sp3000 oh, yeah, you don't need those parens

i thought operator precedence would fail

Sp3000

@xnor I believe lambda s:eval("s"+".replace('%s','')"*4%([],(),{},'<>')*len(s))=='' works, is what I mean :)

xnor

ohhh

that's funny

Nathan Merrill

@orlp oooh

orlp

@Sp3000 crap forgot about eval

@Sp3000 () is a syntax error though

wait

Sp3000

16:26

() is empty tuple

Nathan Merrill

@trichoplax its a good idea. I'm not sure how the "coping" step would work

orlp

it's not?

I've been lied to!

damnit

right, (1,) is a single element tuple so for some reason I thought (,) would be empty tuple

so I tried that and nope

trichoplax

@NathanMerrill Nor me...

Nathan Merrill

@orlp ah, that article solves the problem I was talking about before. It finds the shortest path from each node to each cluster

and the shortest paths from cluster to cluster

xnor

@Sp3000 thanks

Nathan Merrill

16:29

smart

trichoplax

@orlp Python? Can you just use () for an empty tuple? Seems to work

Sp3000

:) it's amusing because the CJam answer also gets to save a few bytes by not having the four brackets in a single string literal

orlp

@trichoplax ye

trichoplax

@orlp I think the only reason for the (1,) notation is because (1) is equivalent to 1. () doesn't cause that ambiguity so it's fine

orlp

@trichoplax not really, try [1, 2,] :)

it's trailing comma notation

(but it has that as a use, yes)

Morgan 'Venti' Thrappuccino

16:31

I'm a liar.

trichoplax

@Morgan'Venti'Thrappuccino Never mind then :)

Morgan 'Venti' Thrappuccino

I'm very surprised that works.

trichoplax

@orlp So you just need to convince them to add leading comma notation and then (,) will work...

@Morgan'Venti'Thrappuccino I wasn't sure myself - I had to go and try it before suggesting it...

Morgan 'Venti' Thrappuccino

Yeah, I had to run type(()) in the REPL.

I would've assumed it was a SyntaxError, or a generator.

trichoplax

I must admit my checking wasn't quite that rigorous...

Optimizer

16:36

^ every developer ever

trichoplax

:)

Nathan Merrill

which is the #1 reason I won't write a language. I hate writing tests

I love assuming that my code works the first time

Optimizer

^ every developer ever

trichoplax

You just need to recruit a ~~new user~~ generous volunteer to write all your tests for you...

orlp

>>> str.__dict__[dir(str)[70]]("   test  ")
'test'

New Main Posts

16:39

0

Q: Permutations of n digits with no repeating digits

Your program must take an input (n for the purpose of description) and output all permutations of a number that is n digits long with no repeating digits, where each of the digits preceding and including its index are divisible by the place in the number that it falls. Rules: No digits may be ...

trichoplax

My plant pot grew 4 stars

Optimizer

your tree grew a pot which grew a plant which grew stars..

what next? earth?

Downgoat

@Optimizer no, mercury.

orlp

HOLY SHIT

MY GARDEN GOT A GOAT

xkcd.com/1663/#ee395688-fb4d-11e5-8001-42010a8e0013

it's perfect, I'm leaving it like that

Optimizer

that's not a goat

orlp

16:49

@Optimizer yes it is

Optimizer

no

trichoplax

a deer?

Morgan 'Venti' Thrappuccino

Optimizer

ears are different

Morgan 'Venti' Thrappuccino

Look at the URL.

orlp

16:49

@Optimizer it's a baby goat

Optimizer

@orlp lol see above

orlp

see?

Optimizer

dude.. even after proof .

Morgan 'Venti' Thrappuccino

http://xkcd.com/1663/art/deer-1.png

Sp3000

I have my goat on an office desk o_O

Downgoat

16:50

@Sp3000 +1

Sp3000

goat-ish thing

orlp

@Optimizer no need to get rude :( I'm just messing around

of course I know it isn't a goat, but it's a meme

goats are popular around here, you know

Sp3000

Deer makes sense, I was wondering what that was

Optimizer

ok

Sp3000

I also have a mini Washington monument it seems

orlp

16:51

honestly it looks more like a llama

Optimizer

-_-

Downgoat

Does anyone know if it is possible to write something like P ::= 'print' (',' E)* in Chomsky normal form without making more than 2 symbols?

Doorknob

@QPaysTaxes golfed? Probably a[1]?a:a[0]. In real code? args = args.first if args.length == 1

orlp

@Downgoat I don't think that does what you want it to, but no

are you sure you want print , 10 , 30?

Doorknob

@QPaysTaxes sure, once I get home today

Downgoat

16:59

@orlp oh :|

orlp

instead of print 10, 30

Downgoat

I meant P ::= 'print' E(',' E)*

orlp

you allow an empty print statement?

Downgoat

no

doesn't python? it does

I think I can write that with only two symbols

mbomb007

I'm so happy that koth exists now. It's so much easier to search for KOTH questions/answers.

New Main Posts

17:02

0

Q: A cycle of quine-like programs

This question asks you to write n programs, such that program 1 outputs program 2, program 2 outputs program 3, ... program n-1 outputs program n and program n outputs program 1. However, not all of these programs have to be the same language. You can use built in quine functions, because I do...

code-challenge quine polyglot

Nathan Merrill

@mbomb007 isn't it king-of-the-hill?

yeah, they are synonyms

mbomb007

@NathanMerrill Yes.

Downgoat

I think this should do it:

mbomb007

The point is that you can now type "koth" instead

Downgoat

P  -> print E P'
P' -> , E P'
      ε

trichoplax

17:03

Somebody golfed the tag

mbomb007

@trichoplax I suggested the synonym. :D

Nathan Merrill

lol

trichoplax

@mbomb007 Good work :)

orlp

@Downgoat not CNF

Nathan Merrill

I got a quote for koth.com

any guesses?

orlp

17:04

P' is not the starting symbol and has a lambda production

trichoplax

$1m?

Nathan Merrill

bit lower. 25K

Downgoat

@orlp it's close enough I think

orlp

sec fixing

@Downgoat no it's not

CNF is rather strict

Nathan Merrill

which, unfortunately, is way out of my budget

mbomb007

17:05

@NathanMerrill Then don't go for .com... Koth.rocks is pretty cheap.

godaddy.com/domains/…

Downgoat

@orlp e ::= 'e' <- looks like evil left recursion

Martin Büttner

I don't understand the 4 close votes on that quine challenge. Can someone explain?

orlp

print_statement ::= 'print' | print elist
print ::= 'print'
elist ::= 'e' | e elist_cont
elist_cont ::= comma elist
e ::= 'e'
comma ::= ','

there, now it should be fixed

Nathan Merrill

I also found this awesome site:

kingofthehill.org

orlp

print, e and comma are just proxy nonterminals

Dr Green Eggs and Ham DJ

17:06

Hello @all

orlp

@Downgoat perhaps you didn't mean CNF?

because CNF is rarely hand-written, and only used in certain constructions, usually

Rainbolt

@MartinBüttner The dupe you found looks like the better dupe target, but if I vote now, it will show both dupe targets.

Downgoat

@orlp no, I didn't... brb checking my terminology...

trichoplax

@NathanMerrill Was not expecting that to be about actual hills...

mbomb007

@NathanMerrill Try king-of-the-hill.com

orlp

17:07

@Downgoat CNF is a special form that is super simple but just as powerful

mbomb007

King-of-the-hill.info is only $2.99

Downgoat

not golfy enough

orlp

a production may only be A -> B C or A -> terminal, and only the start symbol may have a lambda production

Downgoat

ok, got it.

zyabin101

@DrGreenEggsandHamDJ Hello @all/part

@NathanMerrill I found a lot of domains named ppcg koth. Apparently, ppcgkoth.com is free.

Nathan Merrill

17:14

ppcg-koth.ninja

why isn't there a ppcg-koth.pirate

Chris Jester-Young

@NathanMerrill Because pirate sounds like a copyright violator. :-P

@NathanMerrill I incidentally have minesweeper.ninja and I'm launching my product soon. :-)

Nathan Merrill

oooh, there's ppcg.io

which is shorter than ppcg.com

Sp3000

Side garden note: I have no idea what invisible thing the circle's trying to highlight

Downgoat

Language Learning just entered private beta

Dr Green Eggs and Ham DJ

@Downgoat It has 0 questions right now. 0_0

Downgoat

17:20

in Language Learning, 12 secs ago, by Downgoat

Hi

no one's there :/

New Main Posts

0

Q: Tips for King of the Hill challenges

Inspired by this question, what are some tips you guys have for creating king of the hill challenges? What are some things to keep in mind in the planning and implementing of the rules and the controller, and advice on what makes for a good challenge?

tips king-of-the-hill

Dr Green Eggs and Ham DJ

There are exactly 30 users atm.

This might be the only time I have >= downgoats rep.

Downgoat

I want to post the first question...

but I don't want the first question to be closed...

Nathan Merrill

why do domain registrars raise the price according to shorter names

Chris Jester-Young

@NathanMerrill Because you're using a shitty registrar? ;-)

TimmyD

17:23

@Downgoat Who's gonna close it? You said yourself like no one is there.

Downgoat

shorter name = higher demand

^^^ that too

Nathan Merrill

obviously there is greater demand, but if I was a registrar, I could simply undercut them

@ChrisJester-Young I can't find one that doesn't

Downgoat

@TimmyD true, can I post a question from the defintion page?

TimmyD

I've no idea. I only joined SE like 9 months ago.

Chris Jester-Young

@NathanMerrill Are we still talking about ppcg.io?

Nathan Merrill

17:26

yes

Chris Jester-Young

@NathanMerrill My registrar charges $35 for all .io names; not pricier for shorter names.

Nathan Merrill

that's still cheaper than the 60-80 I've been seeing

but to a registrar, .io isn't more complicated than any other domain name, right?

Chris Jester-Young

Shouldn't be.

Nathan Merrill

so, I guess with a free market, you'd have higher prices for parked domains (which makes sense), but you really shouldn't see higher prices for unparked domains

TimmyD

Different registrars have paid for licensing the various domain suffixes

And so charge differing amounts

That's likely why you're seeing .io be more expensive than a similar .com

Nathan Merrill

17:33

hmmm, apparently, .io refers to the British Indian Ocean Territory

its a country code

mınxomaτ

The cheapest TLD atm is xyz (<$3). Of course the best registrar for anything is internet.bs (Yes, I went through Namecheap, Godaddy, etc. pp., I.BS beats all of them, usually in price, but also in customer service and available features).

Optimizer

British Indian Ocean??

TimmyD

thatonenavyshipsailingbyitself.io

Dragonrage

so im back after a busy weekend. and i have a brief reprieve at work.

is there anything i should change about this before posting it as a question?

zyabin101

ppcgkoth.com is available from GoDaddy if you buy a pack of four unrelated domains (five in countries with a national TLD).

Nathan Merrill

17:36

@Dragonrage isn't Unikong deterministic?

Chris Jester-Young

@zyabin101 Why is it only available if you buy more domains?

zyabin101

@ChrisJester-Young Well, I think it's just recommended to buy more domains.

Dragonrage

@NathanMerrill i dont think so?

mınxomaτ

ppcgkoth.com is $8.49 (.xyz is $1.99)

Dragonrage

oh well maybe.

mınxomaτ

17:39

Of course, one could always use one of the freenom domains, which are free

zyabin101

Welcome to chat @TickTock! Sandbox, challenge sandbox.

Anonymous

@mınxomaτ tk domains are free through Freenom, though their customer service is virtually non-existent

Nathan Merrill

why do you want customer service?

I mean, you do it once, and then you're done, right?

Anonymous

~~in case~~ when something goes wrong

mınxomaτ

@Mego All freenom domains are free, not just tk.

Nathan Merrill

17:41

right, but what goes wrong?

Anonymous

@mınxomaτ I didn't know they had other domains than tk

Anonymous

@NathanMerrill Their DNS service is flaky at best

Anonymous

In reality it's just an example of getting what you pay for

mınxomaτ

Your best chance with Freenom is to set an A record (forget about anything else working) and forget about it :-)

Anonymous

Or just don't use Freenom :P

Nathan Merrill

17:43

@mınxomaτ have you tried google domains?

Anonymous

@ChrisJester-Young I tried to register with Slack via the email you sent me, but Slack is just spinning after I clicked next :P

Anonymous

Oh there it goes

mınxomaτ

Wait, the slack link is out?

Nathan Merrill

why are we using slack?

Chris Jester-Young

@NathanMerrill It's a Slack instance for my new company.

Nathan Merrill

17:45

ah :)

Chris Jester-Young

@Mego Try again until it works. :-)

@NathanMerrill Wanna sign up? Email me at [email protected] :-)

Anonymous

That's the approach I used

Chris Jester-Young

:-O

Anonymous

If at first you don't succeed, F5

mınxomaτ

@NathanMerrill $12 a year minimum is way to expensive. Plus some DNS record types are missing, the nameserver cache is too big (ibs doesn't cache, everything applies instantly) and I like to use the free WHOIS protection sometimes ;-)

TimmyD

17:47

@Mego Caching.

Nathan Merrill

I'm looking in the sandbox...there are so many KoTHs being posted

Anonymous

@TimmyD CacheKiller

TimmyD

Fear is the CacheKiller.

mınxomaτ

@ChrisJester-Young Sent you a mail.

Zgarb

@Sp3000 Okay, I was wrong: the rectangle detection challenge is interesting in Grime. I'll post an answer soon.

Sp3000

17:49

:P I was thinking it would be, because of how it constructs rectangles

Dragonrage

@TimmyD shouldiblamecaching.com

Cᴏɴᴏʀ O'Bʀɪᴇɴ

Who's slacking? :P

Anonymous

All of us

Optimizer

every developer ever

Cᴏɴᴏʀ O'Bʀɪᴇɴ

> We all slack. All of us. Not one of you is exempt.

Dragonrage

17:52

@Optimizer "My code is compiling."

Chris Jester-Young

@mınxomaτ Responded. :-)

mınxomaτ

@ChrisJester-Young Re-Responded :P

Anonymous

@Dragonrage I have that shirt :)

Anonymous

'Are you stealing those LCDs?' 'Yeah, but I'm doing it while my code compiles.'

Anonymous

Clipboard why do you keep doing this

Dragonrage

17:55

so i guess since no one has said anything about my proposal, i shall assume it is in an okay enough stay to post as a question

Anonymous

What proposal?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

Arguments from silence are terrible. For example, I have no idea what you are talking about, and you thus conclude that I am okay with it.

Anonymous

^

Dragonrage

20 mins ago, by Dragonrage

is there anything i should change about this before posting it as a question?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

I can die happy: a penguin gave me a caret

Dragonrage

17:56

@CᴏɴᴏʀO'Bʀɪᴇɴ you just stole his nose.

Anonymous

"Because nobody in this empty room has objected to me kicking puppies, I shall go stretch my legs in preparation."

TimmyD

@CᴏɴᴏʀO'Bʀɪᴇɴ It's how a lot of international agreements happen. Silence implies consent.

zyabin101

@CᴏɴᴏʀO'Bʀɪᴇɴ you're back from suspension! \o/

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@zyabin101 yeah! :D

@TimmyD How true... sighs

@Dragonrage oh noes

Anonymous

@Dragonrage Oh that, yeah looks good

TimmyD

17:57

@CᴏɴᴏʀO'Bʀɪᴇɴ Oh nose?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@TimmyD You, sir, are good ;)

@Dragonrage Looks a tad vague, but that's probably just me.

zyabin101

@TimmyD Oh neos

Dr Green Eggs and Ham DJ

What are your favorite/essential vim plugins?

Dragonrage

@CᴏɴᴏʀO'Bʀɪᴇɴ hmm, anything i can do to clarify?

Optimizer

@DrGreenEggsandHamDJ emacs

Dennis

17:58

Why am I getting so much SU rep today?

TimmyD

@Optimizer Ninja'd me by a hair.

Anonymous

Gah I can't upvote anything

Optimizer

@Dennis stumble upon?

Anonymous

Chrome is being crappy

zyabin101

@DrGreenEggsandHamDJ I use vanilla Vim.

Anonymous

17:59

@DrGreenEggsandHamDJ atom

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@Dragonrage I just don't know how to answer your challenge, like how the program will read the variables etc.

Dennis

@Optimizer Super User

Anonymous

@CᴏɴᴏʀO'Bʀɪᴇɴ It's all Javascript

Sp3000

@Dennis Stack Underflow?

Dr Green Eggs and Ham DJ

ಠ_ಠ

Dennis

17:59

Close enough.

Optimizer

old but gold

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@Mego I got that. I looked at the src, and it seems that everything is local--unavailable.

Optimizer

Slack Underflow?

Transcript for