The Nineteenth Byte

not YET! :)

@MartinBüttner I want to make a feature request but I want a mod's feedback first

A comment thread started out on topic but has slowly drifted to extended discussion that belongs in a chat room. The button to migrate them hasn't appeared yet.

I think it would be cool if regular users could preempt the "move to discussion" prompt

4:21 PM

@Sparr I wonder if a clever algorithm would be capable of finding the entire sequence (up to 80 moves). 16! is about 2.1e13

Doorknob

@Rainbolt You can cast a custom "other" flag.

And if all involved in the discussion accept the prompt, automatically migrate the comments to the chat

@Doorknob The point being that no moderater intervention is required

Self moderating comments. Everyone participating says "Yea, we've started an extended discussion." or "No, my comments are directly relevant to the question."

I don't have a good grasp of the actual feature I want to request yet. Maybe a prompt that appears somewhere near the comments, just like the one that appears when comment threads start to get too long? I wonder if I can propose an idea and let others on meta come up with actual implementation details.

Regarding the Strategic Voting KOTH, I think it would be interesting to convert raw scores into z-scores. Since a purely random strategy could produce a wide range of scores, it would be helpful to be able to determine when a bot's score is statically significantly better or worse than a random score.

@MartinBüttner Yeah, I checked OEIS :( There's a related one for 8-puzzle, though.

New Main Posts

0

Q: XKCD Bracket Probabilities

Today's XKCD is a sports-tournament style bracket, where the contestants are well-known names, put into groups of possibly confusing names. Give the probability that a given contestant will win the entire tournament, based on each contestant in a given round having an equal chance of winning tha...

4:26 PM

@Rainbolt It's probably worth a shot, although I'd be surprised if it hasn't ever been requested before.

90% of my feature requests on meta have been requested before

Thanks for the script! Useful :)

@MartinBüttner I don't know which problem that OEIS discussion was about :(

number of positions you can reach from a solved 15-puzzle with N moves

ahh

that definitely seems OEIS-worthy...

4:31 PM

after 80 moves it should remain constant at 16!/2

A: Sandbox for Proposed Challenges

2

Permutations of the Fifteen Puzzle (Title to be determined) Consider the following diagram of the Fifteen Puzzle in its solved state: _____________________ | | | | | | 1 | 2 | 3 | 4 | |____|____|____|____| | | | | | | 5 | 6 | 7 | 8 | |____|____|____|____| | |...

^

because you can reach every position in 80 moves?

I think so

yes

Here is Wolfram's page on it

4:32 PM

or, equivalently, every position is solvable in 80 moves

Is it constant just because 80 is the max length solution? Or is there a position that's solvable in fewer, but not exactly 80?

There are several positions that are solvable in fewer than 80.

I know that, but what about exactly 80? I know all can be solved in 80 or less.

I don't understand your question

@Geobits there are probably positions that can be solved in 79 moves but not 80 moves. That doesn't affect the trait of the sequence that Martin was referring to above

4:35 PM

there are positions that need exactly 80 moves, and there are positions that need less than 80 moves (obviously).

oh

Every position can be reached in 80 moves or less. But the challenge isn't that, it's to find which can be reached in exactly n moves.

oh, good point

very good point

well, each move changes parity

so you can only access half the states in each move

I see what you're saying now.

but you can access the same states again two moves later

hence, constant at 16!**/2**

4:36 PM

so, there are 16! possible positions. 16!/2 of them are reachable in 80 moves and 16!/2 of them are reachable in 79 or 81 moves

@Sparr yep

@BrainSteel the two "different" outputs are both half of 16! :)

^

Ohhhh, I gotcha now.

There aren't 16! valid positions, though, are there? I thought only 16!/2 were ever reachable(due to parity). So wouldn't it be 16!/4 for exactly 80 and 16!/4 for 79/81?

4:37 PM

They're different positions, but there's the same number of them.

the sequence for the sandbox question should definitely go on OEIS

even if we can't calculate it all the way to n=79

it's a nifty sequence even just for 0<n<10

I soon want to start the catch the cat assymmetrical koth challenge, and have a few questions: How should I make the controller files available?

@flawr github repo if you accept submissions in multiple languages. code snippet if you're only accepting javascript.

It is java only, and I cannot use github

(already wasted hours on trying to get how github works...)

wow, java only?

4:40 PM

@flawr How many lines/files? For short (~200 lines or less) single file controllers I just paste into the post.

And the controller consitsts of two packages -> cannot use gist.

if you don't want to use full github, put it in a gist

why can't you use gist? gist does multiple files.

Yes java only, I am not fluent enough in other languages.

Hm the chat did not accept my last messages

The conrroller consists of two packages

and you usually have them in different directories

is this possible to do in gist?

@Geobits oh yeah, there's that as well

I believe gist filenames can contain slashes

4:46 PM

Ah thanks I am gonna try this.

ahh, nope

they explicitly cannot

so, err, why not github?

I mean, sure, figuring out git can take a long time for some people, but if you just use the github gui client and the github website then you don't need to learn all of that

Until something goes wrong at least :P

@MartinBüttner Can I link your script for generating the test cases? (It's significantly less than the C code I would have to paste somewhere)

so it is possible to upload directly to the github website?

@BrainSteel sure

4:54 PM

@flawr no. you have to use a git client. but github has a gui client you can download from their site.

I don't mean for this to sound condescending, but you should probably learn some version control system. It doesn't have to be git. If you learn subversion or mercurial or monotone then there are hosting sites for those too.

well i had to use subversion at a time.

at some point i was able to use that one but never really got it, but git seems to be so much more difficult

I mostly get by with about 5 commands in git, it's only when people start using branches and shouting at me for creating merge commits that it falls down

git is only difficult if you do difficult things with it. if you're the only developer on your project and you don't actually care about branches and history, you can just do 'git commit -a; git push;' after you make a local change and that change will show up on github.

@MartinBüttner Thanks! I've updated the spec a bit. It'll probably be ready for posting in the near future.

I've rewritten it in Mathematica... that should give us slightly larger N in a reasonable amount of time

food now... I'll send you some results later

5:00 PM

I had a partial solution in C that could do up to N = 20 fairly reasonably, but I realized it's actually broken.

What's the proper algorithm for dividing 100 objects "uniformly" randomly into 3 bins?

My current method is selecting two random integers from 0 to 100 (inclusive), and the first bin gets min(a,b), the second gets max(a,b)-min(a,b) and the third gets 100-max(a,b).

But, that doesn't seem to work (?)

Oh, the objects are identical?

Ok, so for the 15-puzzle: for odd n, f(n) is the sum of all even entries in this sequence. For even n, it's the sum of the odds. Now, how do we generate that sequence easily? ;)

Yes, they are identical.

I probably should have mentioned that.

Haha, isn't @AlexA. our probability and statistics guy? How poor are your results, Phi?

@Geobits I'm not sure that sequence is any more easily generated than the first one :P

5:09 PM

It depends on the number of objects.

@BrainSteel I was thinking the same :(

If there are two objects, then the expected values should be 2/3, 2/3, 2/3.

Instead, they are 5/9, 8/9, 5/9.

Hmm...

For 100 objects, it's not that bad.

Did you get those results experimentally? How many runs?

5:11 PM

33.8, 34.3, 33.8, but that's still obviously incorrect.

I calculated them exactly with Mathematica iterating over all possible combinations of random integers in the range.

Oh, okay.

I think the mistake is in the "edge" cases of when there are no objects in a bin.

In the case of two objects, in order for the first bin to be empty, either A or B must be zero. In order for the middle bin to be empty, both A and B must be the same. The first is more likely than the second.

Ah, indeed.

If I were dealing with real numbers instead of integers, this method should work fine, but I'm not.

@PhiNotPi longer slower algorithm would be 3 counters, incremented randomly 100 times

int counts[3]; for x in 1..100 { counts[random(3)]++ }

5:24 PM

I guess that could work.

Would there be a way to calculate the standard deviation of the resulting numbers (I could always estimate it, but exact numbers are always nice).

mean and variance are what you want, I think

@BrainSteel I heard my name.

@PhiNotPi Assign each a random integer.

Assuming the random number generator is uniform, that should be what you want.

That's the same thing Sparr just suggested.

Oh, sorry. Didn't read anything.

Which works, but I was hoping there would be a simpler way, since the objects are identical.

5:32 PM

So you have 100 identical objects but you want to put them randomly in 3 distinct bins?

Yes.

What kind of objects are we talking about here?

Vectors? Turtles?

"points"

How are you currently storing your points?

A group of objects can be represented just by a single integer that tells how many there are.

5:37 PM

If the objects are identical, why does randomness matter?

Think of it as splitting a pile of rocks into smaller piles, randomly sized.

Or picking three random integers that add up to 100.

Does this work for you? math.stackexchange.com/a/1276225/116990

@PhiNotPi choosing things randomly isn't always as simple as it sounds. en.wikipedia.org/wiki/Bertrand_paradox_(probability)

@sparr i am trying it now with the windows gui. i created and added a repository called catch_the_cat, but it does not appear on github.com can you tell me what I have to do now?

5:40 PM

@flawr: Commit.

git commit ...

@flawr you did all that in the gui, nothing on github.com yet?

@Sparr, yes, I know.

cannot find any button for that?

exactly

they guy is blank only on the left side there is a little gray entry 'catch_the_cat'

look for a button that says 'publish'

you might have to select the repository first

i cannot find a button that says so: it looks like this atm:

also checked the right-click-menue

5:45 PM

What's in there if you open the repository in Explorer?

@flawr when you created that project, it made a new folder somewhere in your filesystem.

you need to...

A) copy your project files into that folder

or

B) re-create the project in the github client and point it to the project folder that already exists

ok I copied my files into that folder

nothing happened

everything is still the same

They don't show up in the GUI?

nope

double check that the folder you copied to has a .git subdirectory?

5:47 PM

Might have to do Right Click > Properties > Show hidden files and folders (can't remember if .git is hidden by default)

yes it automatically created a folder 'catch_the_cat' that contains a '.git' folder, and a '.gitattirbutes' as well as a '.gitignore' file

i copied my files into the catch_the_cat folder

In the GUI, click the triangle next to master at the top. What's in there?

Is there Local branch or something?

no there is just that little window

with a bar where you can create/filter 'branches'

should there be anythign special?

close the github client, reopen it

that's a popular solution in windows world, right? :( :) :/

on the right side you SHOULD see a list of new files, modified files, etc

where it currently says "no local changes"

it still looks exactly the same

5:56 PM

Format your hard disk and check again ?

You have to git add them somehow but I don't know how to do that in the GUI. :/

for me, new files show up in the gui to be added

@Optimizer What, wipe all existing files and start your computer over from scratch?

@AlexA. yes, that is the second most popular solution in the windows world, but the first which actually helps.

@Sparr I use a combination of Tortoise GIT, Tortoise GIT integration into my IDE, and Command Line (under windows)

5:58 PM

I just use cmd from inside IntelliJ

(it has a terminal tab)

when I say combination, I mean I used them depending on who I'm trying to not annoy, they all work fine on their own

and of course the git integration of IntelliJ is handy

@People_discussing_Fifteen_Puzzle Has anyone managed to compute N = 16 yet? I've been running for 8+ minutes now.

8+ minutes is not that long

Well, N = 15 came out in two minutes. My algorithm is not particularly quick.

6:00 PM

I use the command line git tools

Jakube

How do you extract an array in CJam?

@flawr try #github on freenode irc

what is freenode irc

?

irc is internet relay chat

freenode is a network

ah i just found it

6:04 PM

webchat.freenode.net

the channel you want is #github

thanks

they can probably tell you what's up with the client

@Jakube as in ?

it should be super simple from where you're at

what does "Extracting an array" mean ?

6:05 PM

it seems there are tons of people online but nobody is writing????

Jakube

@Optimizer Dennis already gave me the answer: ~.

unwrap ..

is the word

Jakube

Yes

this is the correct link isn't it? irc.lc/freenode/github

6:17 PM

@BrainSteel I can probably go up to 20 or so

N = 16 gives 313392

are you doing it via brute force?

that took 22 seconds (given the results from N = 15). it roughly increases by a factor of 2 per N.

@Sparr yes

@MartinBüttner Uh-oh, it looks like we have different numbers.

sorry

my N is off by one

that was N = 17 already

160159 for 16

Oh, okay, sweet! How do you bruteforce it in 22 seconds?

Wait, nevermind, I see what I did.

I'm an idiot.

6:22 PM

well this is pointless... I'm never gonna get further than that related OEIS sequence like this

aborted at N = 20: 2244884

What do you get for 18 and 19?

@MartinBüttner which sequence are you comparing to? the one that says it caps at 80?

the one geobits linked

@BrainSteel goo.gl/VPZmVe

(The results agree with my Mathematica brute force)

here's a version that also displays N: goo.gl/enPcI6

Well, that works. I doubt anyone is going to go through that many N.

what are the inputs there, Martin?

6:31 PM

oeis.org/A089484

Martin is not the input

Q: what are the common challenges to develop on AWS platform?

ahh, got it

New Main Posts

0

o the developer community out there: what are the common challenges to develop on AWS platform?

python java php

@NewMainPosts Quit posting off topic questions :P

ok i give up

gonna make a gist...

6:44 PM

or you can post it to sourcefogenet ... :P

can you manually upload files there?

that was just a joke..

well then

ig you still want github.

delete the .git folder

start a new repo in that folder

should work.

you wanna say it just didnt work because of the '.git' folder it automatically created itself??

6:50 PM

no, but your head might be messed up.

Would it be okay to post Strategic voting as a Java-only competition?

@PhiNotPi Link to sandbox post?

Nevermind, found it: meta.codegolf.stackexchange.com/a/5301/18487

@Optimizer 'failed looking for head in this repository' (just deleted the .git folder)

no i am really giving up now

gist.github.com/flawr/7f2ad5d6f20e84e9d52b

this is waht it looks like nwo

@flawr why would it even look for head .. I asked you to delete the .git folder and git init again .. -_-

@PhiNotPi I can write a Java class that interacts with non-Java submissions. You require all non-Java participants to supply a command that will run their program, and then you download a billion compilers when you want to test it.

6:56 PM

you do not have to ask me anything relating to git

@PhiNotPi Or you can not download a billion compilers and just limit it to Java

@Rainbolt I think I have one of those floating around somewhere.

Actually, I would want something that interacts with other programs through STDIN.

I don't have one of those.

Or you could even compromise. Require any of Java, C#, Python, or JavaScript.

I want to take the people who designed Java and Python packages, with their dependency on filesystem directory structure, and force them to use a system where they can't make subdirectories for a while.

2

Is that the same as "I force you to not use trees."?

Or are you specifically concerned with trees made of files?

And why stop there? Why don't we eliminate Queues and Stacks and Heaps and a ton of other useful data structures.

7:01 PM

lets eliminate arrays

and ints and chars

@Rainbolt I'm concerned with parts of the language not being usable without directory trees.

I want that to be outside the scope of language design. Language features should not depend on my filesystem.

your code is on your filesystem

it doesn't have to be. it could be on punch cards :)

although you could call those files, and the folders containing them a file system, I guess :)

It's a pain in the ass when someone names a package a.b.c.d.e.f and I have to dig down a billion (slightly exaggerated) folders to find a file.

I am not sure why are you trying to find that file anyways.

and if you really are, why are you doing that in the filesystem and not in your IDE

A: Does Java directory/package hierarchy enforcement allow for jar files to be platform independent?

7:03 PM

It looks like a JAR can have an internal filesystem regardless of whether the platform it runs on does or does not.

1

But then a jar file packaged using that system wouldn't be compatible with one that did use the filesystem hierarchy setup because java wouldn't know where to look. I am taking that as the actual question, and it is not correct. A JAR file is a platform-independent entity, based on the ZIP f...

@Optimizer ? Every now and then I have to do something outside an IDE...

:O

^ blowjob face

^ you would love that, won't you ? :P

@Optimizer the context of this discussion is that @flawr is trying to put a java project into a gist, which doesn't allow a folder structure.

7:06 PM

My bigger gripe is how IDEs default their run location (looking at you, Eclipse) to be different than the output folder.

Hmmm. When I got here, I felt confident posting "^ blowjob face". Now, in the year 0 PS (Post StackEgg) I am less confident. Seems like flags fly far too often these days.

So If I read a file "input.txt" within my IDE, it need to be in the main project folder. If from the command line, it needs to be in the /bin folder, or the executable needs to be moved.

@Rainbolt Make sure you post in maximum five-minute intervals the rest of the day so we know you didn't get banned.

So exactly how platform independent should a language be in order to satisfy sparr?

@Rainbolt is it odd that I had no idea what stackegg was referring to until I googled it?

We eliminate anything dependent on a file structure

7:09 PM

@Rainbolt He's not really complaining about platform independence.

Oh, then why are we eliminating file structure dependencies again?

He's complaining about the folder structure of the source files being required to match the package naming.

@Sparr That day will live on in infamy.

@Geobits it does mean you can slap all the data files in one dir, and have separate Debug/Release output directories, which I like

I mean, insofar as gist is a "platform" for hosting source files, you could describe my complaint here as one of platform independence

7:11 PM

(on the other hand, it's not alot of work to copy the data files to the Release dir when you start using it)

if a language required source files to have names at least 100 characters long, that would stupidly exclude platforms with shorter filename limits. that's how I view Java and Python's dependency on folder structures.

@VisualMelon True, it's just an annoyance of mine.

So maybe not my biggest gripe ;)

I like how JS on browsers has a very nice structure of dependency and package managem.. oh wait.

no no, I appreciate your disdain, using Eclipse is not something I wish to ever do again

Well, the VisualMelon component of VS is surely better.

7:15 PM

@Sparr This might sound dumb, but I was confusing Java with the compiled code (that runs on any platform). Java is really the collection of class files written by a human. I get what you're saying now.

I'll likely post the fifteen puzzle challenge in an hour or so, seeing how much attention it got. Here's your chance for last-minute feedback!

Is there a list, if it's not empty, of contributions to Real Math that PCCG posts have made? Has anyone here ever extended a known OEIS entry? Established a new lower or upper bound for something? These guys over here may have actually done some New Math, which inspired me to ask: reddit.com/r/math/comments/36jq0k/a_curious_property_of_82000

Peter fixed an OEIS entry recently

maybe I should ask this on meta?

I think I've heard Peter (some time ago) talking about a paper based on something (either from here or Puzzling), but I can't remember what.

7:20 PM

was the spies throwing stones, I think

he was working on something based on Puzzling

yes that

Yep, that was it.

I wonder how big the next number is (that's entirely zeros and ones in bases 2, 3, 4, 5, and 6)

paper in which area ?

maths ? CS ?

computational mathematics .. ?

The puzzle was this: puzzling.stackexchange.com/q/625/1563

But I don't know the specifics.

7:24 PM

I think he posted a draft of the paper in here

Several OEIS fixes came out of Evolution of OEIS. I don't know if any of that counts as new math, though.

@Rainbolt there's a probabilistic argument in the reddit thread that there is no such number for 2 3 4 5 6, and no such number for 2 3 4 5 that's higher than 82000

Peter and I found a (potentially new) fractal when analysing Apollonian gaskets

Q: What contributions has PPCG made to the fields of math or computer science?

0

Most of the content on PPCG involves clever applications of existing algorithms, or just-fast-enough-to-pass solutions to problems that supercomputers have found millions of answers/digits/etc to already. However, somewhere among all of the brainpower we spend on these challenges, surely someone ...

discussion

and I might post a challenge soon to extend an OEIS entry (it only has a handful, and I'm quite confident that a fastest code challenge would beat that limit)

Q: What contributions has PPCG made to the fields of math or computer science?

7:34 PM

Which one? :D

New Meta Posts

1

Most of the content on PPCG involves clever applications of existing algorithms, or just-fast-enough-to-pass solutions to problems that supercomputers have found millions of answers/digits/etc to already. However, somewhere among all of the brainpower we spend on these challenges, surely someone ...

discussion

diamond tilings :P ... no ascii art for this one though ;) (and I'll wait a bit after people forgot the other two ;) )

@Geobits this one specifically: oeis.org/A066931

Hmm, I didn't expect it to be 20k with only side length 4.

counting all symmetries it's already 232k

it's a permutational problem

consider how many triangles a hexagon is made of

or diamonds

the answer is vaguely related to that, I think

7:42 PM

This guy is really pushing to get all developers to attend a workshop after hours on Unit Testing

I can't help but wonder why it has to be after hours

It doesn't have to be, it's just more fun that way.

Or something.

@Rainbolt after hours workshop... I bet your developers are salaried.

I love Unit Testing, and I'd be happy to spend a half day of the company's time learning proper techniques and getting all developers aligned on how we want to implement it.

We are salaried. And I stay late when we have a product to deliver

I'd be hard pressed to attend a Unit Testing workshop even during hours ;)

In fact, now that were are sprinting, we know that we are behind schedule before the night of a drop. So we often stay late in the middle of a sprint just to catch up.

So it's not like we are strict "5:00 time to run away" people.

But this is a process improvement thing. It needs to happen on the clock.

7:45 PM

I have, a couple of times, gone to office at 5 PM :P

I bring my lunch every Thursday to attend a Lunch and Learn workshop. It's an hour long and we learn a lot. Seems like he could just do the same on Wednesday, so I suggested that.

That was last week, and it sounds like he ignored my suggestion.

We watch videos from Pluralsight on Thursdays

@Sparr oeis.org/A201168

he never ended up writing an answer for this one though

but he discovered the mistake while searching for sequences to be used for EOEIS

@MartinBüttner that seems like a valid answer for my meta question

I'll make a CW answer for where people can edit in all new/fixed/extended OEIS sequences. doesn't seem like it's worth to have a separate answer for each.

I've determined a rough formula for the relationship between the number of KotH submissions and the length of time I procrastinate compiling/running them, but it still needs a bit of work. Will submit for publishing soon.

I still need Rainbolt's input on that one, I need to run the numbers for GvE to see if they fit the trend.

8:03 PM

I spent three weekends from roughly 12:00 AM to 4-6:00 AM downloading entries and compiling and running them. Actual tests ran for maybe 12 hours each, so I also had to implement logic to recover in the event that some stupid submission decided to crash when I wasn't at home.

K, I'll plug that in. If nothing else, I'll just make my model conform to the data anyway. It's what the greats do, right?

There are no such things as outliers.

Abdou Abdou

why this is still unanswered ?

Because you haven't answered it yet ;)

Abdou Abdou

8:18 PM

i ll try when i have plenty of time

i think i have rare kind disease called sudoku obsession :p

@aditsu what do you think about implementing ArrayList i by implicitly doing si?

what if the array has non numeric characters ?

the same as when you do "3!()*"i

lol, just read this from twitter : "In Transylvania, it's your Count that votes."

:D

8:37 PM

@Optimizer reminds me of this

awww

he just got it..

do you guys know of any versioning system that reuses the old version of a file/thing/json if the md5 matches to a previous version's ?

I'm working on the scoring system for strategic voting. One thing I'm trying to do is figure out a way to determine how many trials should be run to get a meaningful result.

Can you provide more context?