The Nineteenth Byte

TheBestOne

20:12

@PhiNotPi I have a bot that beats all current bots. I'll wait for mbomb to finish BOMBER before I post it.

Optimizer

2 moar bytes ...

Martin Büttner

20:32

@Peter can golfscript = not index into a string?

PhiNotPi

20:48

@PeterTaylor How do you tell which new plots to point, though?

Are you doing it the "normal" way?

Peter Taylor

@MartinBüttner It can. Why?

@PhiNotPi Context?

PhiNotPi

You pinged me earlier, talking about my points on a line challenge.

Martin Büttner

@PeterTaylor oh I thought that's why you did 1/ before =, but I guess it's because you need the character in an array

Peter Taylor

21:04

@PhiNotPi Ah. That's not the approach I'm using. I was just supplying the one really reliable relationship between consecutive outputs.

@MartinBüttner Unlike CJam, GolfScript strings are actually a different type, not just a special case in the toString method of an array.

Martin Büttner

that's why I asked

Peter Taylor

And there's no character type.

Without the 1/ I'd get an array of integers, and then it would take ''+ to convert to a string.

PhiNotPi

I wonder, is the line "dense"? Meaning that each pair of points will eventually have a point between them?

Martin Büttner

@PeterTaylor oh right... I was more expecting it to return a one-character string.

(Ruby-1.9-style)

PhiNotPi

I think the answer to my question is no.

Martin Büttner

21:11

why?

I think if your earlier observation is true, at least the first half is dense

PhiNotPi

My earlier observation is not true, based on the CJam answer's output.

Peter Taylor

@PhiNotPi I think so. You insert A' between C and D, and then in every case I've seen B' = D, so you can group the operations by pairing up the points, inserting one between each pair, and then repeating from the last one.

Martin Büttner

oh okay

Peter Taylor

Which would explain the 3/2 increase in points each time n increments.

PhiNotPi

Maybe the answer depends on the starting configuration, maybe here is an example?

sorry about that

TheBestOne

21:18

n = 29 is the first value that can't be computed with my answer.

PhiNotPi

Here's an idea, what is the trend in the number of points each pass-through? (each time the line is wrapped around?)

TheBestOne

@PeterTaylor Thanks for that catch. I was using negative numbers before I golfed everything.

PhiNotPi

....................... ......... 0  0
A...................... ......... 1  1
X...............A...... ......... 1  2
X...............X...... .A....... 1  3
X...............X...A.. .X....... 1  4
X.......A.......X...X.A .X....... 2  6
X...A...X.......X.A.X.X AX....... 3  9
X.A.X...X...A...X.XAX.XAXX...A... 5 14

If you look at the intervals formed by Xs, you will see that every other interval contains a new point A.

Optimizer

are we trying to obtain a formula for this pattern ?

PhiNotPi

Yes.

I guess we are.

TheBestOne

21:33

These are the number of points for n = 0 to 25 counting for each pass-through:

PhiNotPi

If there are N number of Xs at the start of a given pass-through, then there are about N/2 points added that pass through.

When there are an odd number of Xs, then whether you round down or up depends on where the previous pass through ended.

Martin Büttner

@PhiNotPi I think that's what Peter meant

PhiNotPi

Okay.

Martin Büttner

what's the sequence of positions (with and without wrapping) for a given N?

PhiNotPi

I thought he was talking about pair the points D' and B'

Let's say that there are N points before a pass-through, and P is the polarity (odd if the first/third/etc. intervals are filled, even if the second/fourth/etc. are filled).

If N is even, then N/2 points are added and polarity stays the same.
If N is odd and the polarity is odd, then ceil(N/2) are added and polarity flips.
If N is odd and the polarity is even, then floor(N/2) are added and polarity flips.

Peter Taylor

21:41

@PhiNotPi The identification of D with B' is the justification for why the points can be paired up and a new one added per pair.

TheBestOne

The total number of X's is identical to OEIS A061419 all the way to n=25.

PhiNotPi

That's probably a solid match, then.

feersum

Do you guys think there is a (non double-exponential) algorithm for this, or should I make it a code challenge to use the fewest queries?

Optimizer

I doubt that even if we find the pattern, it would not be shorter

PhiNotPi

@feersum That's going to be hard.

Martin Büttner

21:44

@PeterTaylor do you think that explicit formula for the number of iterations might be shorter in CJam?

Optimizer

That formula is useless if you follow my approach

Peter Taylor

@MartinBüttner Doubt it, but since Optimizer's answer uses N% and that's one of the first things I golfed out, I wonder whether a CJam port of my answer would be shorter.

TheBestOne

@Optimizer What's your approach?

Martin Büttner

_(1a{(j3*d2/m]}j

Optimizer

@TheBestOne It's The Best One

Martin Büttner

21:47

I guess the ceiling part can be improved

Peter Taylor

@feersum Are you sure that it's even possible to do better than trying each possible subset in ascending order?

feersum

@PeterTaylor how do you mean?

Optimizer

@TheBestOne basically keep following the spec. keep the last plotted X index on top of array and do a set union of the new index and rest of the array

Peter Taylor

For 3 children, there are four non-trivial subsets, and in the worst case you have to try them all.

For 4 children, I don't think it's possible to improve on trying the 11 non-trivial subsets one by one.

Is there any n for which you have shown that f(n) < 2^n - n - 1?

feersum

This is a good question, I will check

Martin Büttner

21:58

Are there any problems left with the string rectangle challenge?

0

A: Sandbox for Proposed Challenges

The Characters in the String Go Round and Round... code-golfstringascii-art (Needs a better title!) (Inspired by a challenge draft by PhiNotPi.) You're given a width W > 1, a height H > 1 and string consisting of 2(W+H-2) printable ASCII characters. The task is to print this string wrapped in...

(except that it could use a better title)

Martin 1 : Conversation 0

feersum

I typo'd an index in my math formula...when do we get mathjax?

Martin Büttner

@feersum balpha wanted to look into it 2 weeks ago

don't know if he forgot or decided not to activate it

I'm not sure if I should pester him about it again or give it another week or two ^^

Optimizer

you have a base cjam score for this ?

Martin Büttner

no

I'm relying on you to provide one ;)

Optimizer

idea ?

Martin Büttner

22:10

I think there are at least three approaches, but I don't know which would be shortest

the shortest might be to start with the rectangle of spaces, and then prepend the lines of correct length while rotating 4 times

PhiNotPi

I want MathJax.

8

Martin Büttner

we all do

2

Rainbolt

Even Board and Card Games wants MathJax. I can't imagine what for

1

Q: Why isn't MathJax enabled on this site?

MathJax would be handy for formatting things like the formulas in the following abstract: We analyze the most commonly used method for shuffling cards. The main result is a simple expression for the chance of any arrangement after any number of shuffles. This is used to give sharp bounds on t...

Martin Büttner

@Rainbolt theoretical analysis of the games?

feersum

mtg is turing-complete right? must be lots of things for the computation

Rainbolt

22:15

If you have a math heavy theoretical analysis of a game, wouldn't you be better served asking it on a Math site?

I mean, Math majors and experts use the math site. Board Games majors... don't exist. So that just leaves the "experts" board gamers.

Martin Büttner

well the theoretical analysis doesn't necessarily need to be heavy to benefit from MathJax

but you've got a point

PhiNotPi

PPCG can see some... heavy... analysis sometimes.

Rainbolt

Certainly. Settlers of Catan on the other hand...

Martin Büttner

posted the challenge:

0

Q: The Characters in the String Go Round and Round

(Inspired by an early draft of PhiNotPi's fractal line challenge.) You're given a width W > 1, a height H > 1 and string consisting of 2(W+H-2) printable ASCII characters. The task is to print this string wrapped in a rectangle of the given width and height, in a clockwise sense, where the recta...

code-golf ascii-art string

Rainbolt

Well, someone who frequently uses Math in their answers needs to collect their posts and take it to meta. The only possible way we'll ever get MathJax enabled is if someone says "These posts will benefit from it."

Martin Büttner

22:20

you can't end question titles with an ellipsis :(

@Rainbolt we do have such a list

Rainbolt

Hehe I edited your question and it accepted it and the edit disappeared

That is very weird

Martin Büttner

and balpha looked at it and said, that it looks reasonable and that he wanted to ask Jon Ericson how strong his feelings about rejecting our request were

@Rainbolt like synonym renamings

@Rainbolt here is the request meta.codegolf.stackexchange.com/q/2562/8478

PhiNotPi

@Rainbolt I think I saw that. That was weird.

Rainbolt

Lmao. -8 votes

And a deleted answer

I sorted by votes repeatedly and thought the button was broken for a sec

Martin Büttner

the deleted answer just had the list before Joe put it in the question

Rainbolt

22:27

⡀⡀⡀

Meh

Braille dot fail

Martin Büttner

not that I would have been able to read Braille...

Rainbolt

I tried @Martin

Ellipses in braille means ellipses. Isn't that cool?

Martin Büttner

does that just mean that periods are single dots in Braille?

Rainbolt

Braille 2840 looks like
o o
o o
o o
● o

Lower left dot filled in

So the unicode character for it would make a nice substitute for a period

Which I thought you could use in your challenge title

But it became a square instead. Not supported in this font I guess

Martin Büttner

yeah Unicode in titles isn't really a good idea anyway, in case it goes HNQ

Sp3000

22:35

@Doorknob Thanks! Now get ready for more, because there's 5 people on 9-10k :P

Doorknob

Yep, watching the list closely :)

PhiNotPi

I have 6.6k

If that means anything

:) :/ :(

Martin Büttner

:\

TheBestOne

(:v{ >

feersum

(number of answers) / (quality of answers)^2

Martin Büttner

22:45

is that a constant?

feersum

no, what would be a constant?

also, note that I refer to generalized answers (which include questions)

Martin Büttner

:D

PhiNotPi

Ɑ:

feersum

23:04

@PeterTaylor I think it is possible to do better than 2^n-n-1, by starting with ab + cd

if no then you have knocked out 2

if yes then you can confirm ab or cd, which takes care of several 3 or 4 size groups containing them

PhiNotPi

Can MIKGs overlap? (I'm assuming yes)

feersum

yes

Peter Taylor

Yes, you're right.

PhiNotPi

How are they randomly generated?

feersum

that's the hard part..

Martin Büttner

23:15

grrr, empty 2d arrays are freaking me out again :D

feersum

it's odd that no one bothered to calculate any Dedekind numbers for n > 8

Martin Büttner

I think [[]] might work this time though

PhiNotPi

Perhaps uniformly over every unique possibility, although that could be hard.

feersum

it's almost certainly impossible to use that, given my last comment

PhiNotPi

Is there a limit on the number of groups that the class can be split into?

feersum

23:20

no

PhiNotPi

An edge case would be when one particular student is not compatible with any of the other students.

Sp3000

@xnor I wish I exec's scope wasn't so weird so I could do def f(s,w,h,P=print):P(s[:w]);*L,=s[w:];exec('x,*L,y=L;P(y+" "*(w-2)+x);'*(h-2));P(*L[::-1],sep="") but unfortunately that's longer anyway...

xnor

oh, i see, you need the function because of Python 3

my complaint is that you can't do: def f(s,m,n):print(s[:n],*[s[~i]+' '*(n-2)+s[n+i]for i in range(m-2)],s[1-m::-1][:n],sep='\n')

because the * unpacking doesn't allow a non-unpacked argument after an unpacked one

even though it's totally unambiguous

Sp3000

Just wait for Python 3.5 ... just wait for Python 3.5 ...

xnor

oh, is that actually happening?

i thought guido was against it

Sp3000

23:23

PEP 448

xnor

oh, it's accepted

Martin Büttner

my really nice idea of actually starting with a rectangle of spaces and wrapping the text around with a loop that's run 4 times doesn't work because of width/height 2 cases :/

Sp3000

I've been twiddling my thumbs waiting for the golfing opportunities for that PEP D:

xnor

when is it coming out?

Martin Büttner

one day I'll find a solution for this empty matrix business...

Sp3000

23:25

No idea - it's not in 3.5 alpha 3 which is coming March 28, so it might take a while...

@MartinBüttner Should have totally made it a square :P

Martin Büttner

then 2x2 would still not work

Sp3000

How come?

Martin Büttner

because I'd still start with an empty matrix

xnor

@Sp3000 the PEP though took out things like [*item for item in ranges], which I think have the most golf uses :-(

Runer112

I give up, Timtech is beyond reason

feersum

23:28

what is that supposed to mean? @xnor

xnor

it would do [*range(i) for i in range(5)] = [0, 0, 1, 0, 1, 2, 0, 1, 2, 3]

Sp3000

:( yeah... only the comprehensions though. {*L} will be 2 bytes better than set(L) though, which is nice

xnor

in place of sum(...,[])

Martin Büttner

currently, the problem with the empty rectangles seems to be that I can represent a 0x2 matrix, as [[][]] but I can't represent a 2x0 matrix.

Peter Taylor

emis.de/journals/EJC/Volume_4/PDF/v4i2r15.pdf might help with the random generation, but I haven't processed its ideas yet.

Martin Büttner

23:46

@Optimizer fyi I've got 41 bytes but it doesn't work for width or height (or both) 2

feersum

23:57

@PeterTaylor very interesting...I will have to work on this some more in a week or so

Sp3000

@MartinBüttner Is it possible to get S[:n] and S[n:] where S is a string in one go?

In CJam

Transcript for