The Nineteenth Byte

1:03 AM

@Calvin'sHobbies I've got an idea for a source-layout challenge and I thought I'd ask for some advice from the master of source layout. ;) The core idea is cyclic code: write code, such that as many cyclic permutations of the code as possible are also valid submissions (in fact, the scoring would be to minimise the number of cyclic permutations which are not valid, because otherwise you could probably pad your code to infinity). My problem is deciding what the code should actually do.

I think the problem doesn't need to be hard, because the challenge should be quite tough in most challenges. But I'm not sure if something number- or string-based would be more suitable. And whether different permutations should do different things (because I think otherwise Befunge or something would just win by default).

Calvin's Hobbies

1:30 AM

To make sure I;m on the same page you mean cyclic like this right: codegolf.stackexchange.com/questions/5083/…

@MartinBüttner If so then something simple could be "maximize the number of consecutive integers output in all the possible rotations of your code (possibly starting at 0)". Like if ABCD outputs 3,DABC outputs 3, CDAB outputs 4, and the others erroe, then the score is 2 for [3, 4].

*error

Sp3000

3:36 AM

Hmm sometimes I wonder what percentage of users frequent the sandbox

It seems like sometimes a question is posted, doesn't get many replies/gets replies, fixes accordingly then no more replies come

And so the asker posts the question, thinking they won't get many more replies

And then it gets closed :/

(looking at Under Control)

Calvin's Hobbies

4:14 AM

@Sp3000 I agree that this is an issue, especially for new questioners. Though a lot of the time the specs are just to long to critique...

Sp3000

Yeah, and only about 10-20 people doing the critiquing?

Ah well...

btw @Calvin'sHobbies, what types of languages were you imagining when you wrote the Stack Snippet question? Just out of curiosity

xnor

4:42 AM

there's a lot more eyeballs when something is posted on the main page

also, i find that when I start actually planning real code, issues immediately come up that I'd miss when reading a spec in the sandbox

i agree there's a problem where the sandbox seems to find no issue with a question, but when it's posted, serious problems are found

i can see it would feel frustrating and arbitrary to have a well-sandboxed question be closed

Calvin's Hobbies

@Sp3000 Well ideally it would include everything from C to Java to GolfScript. That would make it easy to write multi-language koth's that everyone could easily test. Just write the base in js and use the interpreters for other languages.I realize that that's not about to happen.

Still, theres a ton of languages on esolangs.org/wiki/Main_Page that would be easy enough to interpret, even if they aren't very useful.

Quincunx

5:38 AM

Ugh. I feel like nobody seems to see my more recent posts. They've had no upvotes (the serious code-golf ones)

Serious code-golf = took effort to make. So not bulgarian solitaire; that didn't take much effort

Sp3000

5:57 AM

@Calvin'sHobbies Now that you put it that way, you could probably make up your own language (based off something else) to use it in a KOTH... But I guess if C/Java were to happen, it'd have to be a multi-person collab for it to work, cos it'd 1) take too long and 2) probably end up being very buggy if the coder doesn't know C/Java well enough

Sp3000

6:24 AM

Ahaha I was wondering if we'd get challenges based on previous answers

Sp3000

7:03 AM

@Quincunx Man, polynomials of Z are hard :(

Quincunx

@Sp3000 Yes...

You can reduce it to solving a system of non-linear equations, though.

Sp3000

Can you? I think the problem with the polynomials question is probably not enough people have the mathematical background to get started (myself included)

It's an interesting question though

Quincunx

Yes

You can

A degree d is composed of a degree k polynomial and something like unto a degree d - k polynomial (I'm not going to do the thinking right now)

example: x^3 + x^2 + x + 2

= (ax^2 + bx + c) (dx + e)

Sp3000

Oh, do you mean the abc = 1, ab + bc + ac = -1, etc. thing?

Quincunx

@Sp3000 not quite; that would be for roots.

Sp3000

7:07 AM

Ah.

Quincunx

At least I don't think it's quite that.

Sp3000

Right yes that'd only work for linear factors

Quincunx

The a/d in my example, though, don't need to be there, b/c the polynomial is monic

I sure hope that polynomial is irreducible over Z, because if it isn't, then I can't remember Eisenstein's Criterion.

Sp3000

Er, p divides everything but (either first or last), p^2 doesn't divide (either first or last)... :/ I only did this earlier this year

Quincunx

Oh oops

I can't remember it that well anymore

I did it about a month ago

p doesn't divide the first

So then x^3 + 2x^2 + 2x + 2 works

Sp3000

7:13 AM

Hm k...

Hmm rather than doing something complex, brute force might actually be shorter...

It's easy for finite fields, but I'd need a way of brute forcing for Z so it doesn't run forever

Quincunx

Yes it's easy to bruteforce finite fields

Uh oh, did I not require that the outputs be given in reasonable time, rather than just proving that the program will eventually produce the outputs?

Reasonable as in <= 2 hours

for the test cases.

Oh duh that must be how you came across this question... I forgot I put a bounty on it...

Sp3000

:P Well actually I had it bookmarked from ages back for "do after I finish my assignments" ... I'm not quite done with my assignments, but it makes for good procrastination

Quincunx

:)

Same, I actually have homework due today (It's 1 AM... I should really get to bed... can you help convince me?)

I need a "parental lock" for the StackExchange network, where I can't access it past 11PM...

Otherwise, I find myself staying up ridiculously late doing things. I've stayed up 'til 3:30AM... again on a school night.

Sp3000

SE is pretty addictive yeah, it's why I'm still doing my assignments anyway

Quincunx

I did pretty well for the ~1 month where I had way too much of a workload to actually participate on this site, other than answer a trivial question and check my reputation. But then I learned to manage my time well and I actually got less time to do assignments because now I'm back to being constantly on SE. Oh and my assignments are mostly boring, except for my math.

Sp3000

7:27 AM

Ahaha well hobbies are good, I think anyway

I've learned more about regexes over a weekend than I'd ever have over several years if it wasn't for Regex Golf

>>> factor([1,4,4,1,0],5)
[[1, 0], [1, 1], [1, 4], [1, 4]]

Quincunx

Nice. I learned my regexes when I discovered how beautiful they are on stackoverflow. Now I love them.

Sp3000

:/ I don't want to print polynomials

Quincunx

@Sp3000 :P sorry I wanted uniform output. I did give you some leniency, though.

Sp3000

Thanks :) (x+0) does help

Quincunx

That was the point

I wanted to let people make it pretty, but still allow for the easy way out :-)

Sp3000

7:32 AM

Does that mean we can do x^3 + 0x^2 + 0x + 2?

Quincunx

@Sp3000 No.

Sp3000

Hm k

Quincunx

@Sp3000 That would be too lazy ;-). It's really not that much harder. Maybe 5 chars with a golfing language, 50 with java, 15 with python. (note: these numbers are from thin air, I hope they are reasonable...)

Sp3000

Do you mean for printing polynomials?

Quincunx

Yes, you can't use that for printing. You could for input. You could also just take a list of coeffs for input.

Sp3000

7:41 AM

I meanted the 5 chars/50 chars/15 chars count

Because, at least with Python, printing a polynomial would take a lot more than 15...

Quincunx

Oh I meant adjusting the output, not printing the output.

Sp3000

Oh, right

Quincunx

@PeterTaylor I thought you were going to answer the question too. It looks like Sp3000 might beat you to it.

(finite field polynomial factoring question)

Sp3000

Well, I've only got the finite fields part - with brute force

(the test cases aren't that big)

Quincunx

Yes

It should be feasible even with the worst possible brute force method I can think of.

Because I don't have a degree 6 polynomial over F5.

I tested the irreducibility of such a polynomial with a little python program I wrote. Then, when I realized it would take a long time, I did the math and found that it should take ~2 days to finish, even though it only took 20 minutes for a degree 4 polynomial.

Worst possible brute force I can think of: generate all smaller polynomials. Multiply together all possibilities. Check to see if our polynomial is one of those.

Although that's only one iteration...

Sp3000

7:47 AM

That's what I'm doing, but recursive :P

Quincunx

Yeah recursion would fix the other iterations.

But come-on, you could easily do a much much faster method

Sp3000

Ahaha maybe if I can think of one - if you wanted fast, why not fastest code?

Quincunx

one way: only iterate through one polynomial, and iterate through the polynomials of degree such that multiplying would be the right degree.

Another way: go through each polynomial and attempt polynomial division.

(this question was actually inspired by one of my homework questions, which was to prove that there is an algorithm for factoring polynomials over finite fields)

(That was a fun problem. I came up with the first method that I described here, except I had the condition that we could stop if we found the polynomial already)

You are doing a poor job of convincing me to sleep. It's 2AM now. And I need to get up for a 9AM class...

Sp3000

Well I'm iterating through all polynomials of degree a, b such that a+b is the degree of the polynomial we're factoring

Oops, er... good night? :D

Quincunx

That's faster than the method I was thinking of. I was thinking of generating all possible smaller polynomials and then multiplying them all together and then checking. And yeah....

Sp3000

7:54 AM

Oh, right I see...

Transcript for