« first day (2590 days earlier)      last day (1140 days later) » 
00:00 - 18:0018:00 - 00:00

12:01 AM
Q: Abstract Rewriting Challenge (Cops)

NathanielThis is a somewhat proof-golf-like cops-and-robbers challenge. This is the cops' thread. Cops Your task is to define an abstract rewriting system in which the reachability of one word from another is difficult to prove. You will prepare the following things: A set of symbols, called the alpha...

12:19 AM
Q: Abstract Rewriting Challenge (Robbers)

NathanielThis is a somewhat proof-golf-like cops-and-robbers challenge. This is the robbers' thread; the cops' thread is here. Robbers The cops will post abstract rewriting systems. Your task is to crack their submissions by proving that the target string can be reached from the source string by applyin...

12:49 AM
@DJMcMayhem Oh man, I've been watching some more of his videos. He's the esolanger of the guitar world :-O
1:11 AM
@ASCII-only do you mind if I test installing VSL in charcoal workspace
@LuisMendo Yes he is xP
(that's three different links btw)
1 hour later…
2:38 AM
@Downgoat i don't mind
as long as you don't accidentally rm -rf ~
there's a lot of stuff there not on github
@ASCII-only don't worry only did find / -name "*sheep*" -delete (didn't actually run this)
though didn't actually end up needing to use charcoal because CrazyGuy was able to test on his ubuntu computer
@Downgoat i could have tested on my opensuse wsl too
@ASCII-only if you have LLVM >= 4.0 installed you can still test using npm i -g vsl
@DJMcMayhem what the what is an otamatone
@DJMcMayhem well, if there was an esolanger that was that multilingual
1 hour later…
3:50 AM
hmm still trying to reverse enumerate subsets
4:04 AM
@ASCII-only The thing that Rob plays on :P
@DJMcMayhem it looks like a mix between some kind of color strip thermometer and a semiquaver with a face
@NewMainPosts Why was this closed? It looks like an on-topic question.
4:23 AM
@Laikoni I cast the final vote to open it
4:52 AM
ok so you remember how i was making a 3d thing with cylinders and painting order but then it lagged too much? may not remember the last part but whatever
I'm going to make the cylinders transparent so the drawing order doesn't matter
@DestructibleLemon yes. pls use actual 3d ty.
@DestructibleLemon ...
as they say
@DestructibleLemon ... you don't even have to break cylinders up though...
that was probably the only reason it lagged
@ASCII-only you have to break them up or do z buffering
z buffering?
4:54 AM
as in, you check whether the thing you're drawing is ahead or behind whatevers on the screen per pixel and stuff
@DestructibleLemon no?
drawing stuff in whatever order
just draw farthest ones first?
@ASCII-only doesn't work
@DestructibleLemon also this isn't hard...
4:54 AM
ok so
let me find the image
imagine the green line goes up higher
and lower
you can still draw from back to front?
the red cylinder to the right is in front of the green cyinder
the green cylinder is in front of the red cylinder to the left
and through a staircase, the red cylinder on the left is in front of the red cylinder to the right
see the issue?
just to make sure: you haven't mentioned the middle two right
4:57 AM
ok so
the left is in front of the one a little bit to the right, when looking down at an angle from the right
same with the one a bit to tthe right and the one more to the right
oh hang on. you're looking from the right?
please draw a better drawing ty
ok fine
i'm really not obligated to convince you though
also seriously the only reason drawing by distance is a problem is when a cylinder is somehow simultaneously both behind and in front of another
@DestructibleLemon sure. I'm just saying as far as I can see you're wasting more processing time than you need to by breaking up the cylinders and then drawing each part
white is visibility, yellow is blocking
if something block something else, that means it's in front
i missed one but you can probably see the point now?
wait is the green one going through the red one?
5:04 AM
it's behind it
the staircase sort of curves i guess
hmm i kinda see the point i guess? why would you have to split drawing though
because if you don't, it goes in a loop
can't you determine an order to paint them that gives the correct result
it is true i'm splitting more than necessary though
but figuring what needs to be split is hard
@DestructibleLemon seriously? if you're worried about performance just use GL 3d?
5:07 AM
@ASCII-only no because the splitting makes it laggy
i could split less and lag less
@DestructibleLemon use GL 3d so you don't need to split at all?
i'm gonna just make them transparent and monochromatic
what will transparent cylinders even look like
wait i just realised i can't do that
because pygame outlines look crap
>_> <_<
5:10 AM
why would you implement outlines for something if they just look like total crap though
but what if
I were to use lines to make an approximate ellipse
@DestructibleLemon >_> congratulations, you're remaking GL
just use pyglet gluDisk
i'm still using pygame, but i guess i can switch
1 hour later…
6:14 AM
anyone know how to get the nth subset of a certain list (assuming subsets are lex-ordered)
get all subsets and get nth :P
@HyperNeutrino ... without brute forcing
or, more precisely: the nth subset of a certain length
alternatively, how to do this:
0 -> [0 0 0]
1 -> [0 0 1]
2 -> [0 0 2]
3 -> [0 1 0]
4 -> [0 1 1]
5 -> [0 2 0]
6 -> [1 0 0]
7 -> [1 0 1]
8 -> [1 1 0]
9 -> [2 0 0]
Hmm, they appear to be related to triangular (and tetrahedral etc.) numbers
6:29 AM
@ASCII-only They're numbers in ternary
@Οurous Almost being the key part...
@ASCII-only What do the next ten look like?
ah wait no oops
@Οurous yeah there are no next ten >_>
the third number is the position in the line, the second is the line in the triangle, the first is the triangle in the tetrahedron, largest first
But I'm not sure what a fast way to obtain this programatically would be
6:54 AM
CMC: Given a 2D array representing the top-left corner of a symmetrical rectangular array, return the completed rectangle. Example/Testcase:
1 2 3
4 5 6

1 2 3 3 2 1
4 5 6 6 5 4
4 5 6 6 5 4
1 2 3 3 2 1
@Pavel is return as string allowed?
can we take input as string too
Jelly, 5 bytes: m0Z$⁺
literally just "append the reverse and then zip, twice"
@ASCII-only Sure, whatever
7:00 AM
@Pavel Charcoal, 13 bytes: WS⊞υ⁺ι υ⮌υ‖B→
:/ less golfy than I expected
I posted this challenge on sandbox codegolf.meta.stackexchange.com/questions/2140/…
any feedback? i think it shouldnt be a dupe
7:15 AM
A: Sandbox for Proposed Challenges

Manish KunduIntroduction We know that the factorial notation is valid for all natural numbers. However, Euler had extended it for all real numbers, as well as for complex numbers by defining a function, which is known as the Gamma Function. It is represented by Γ. Challenge You will be given a positive fl...

@ManishKundu Well, hardcoding is basically never the right answer, so you should provide some alternate methods of computation in the post
the integral is the best alternate way
now dont expect me to explain integration in the post.. lol
@ManishKundu Of course not. But at least show the formula
yeah that would be fine
I'd expect a sizeable percentage of people here to already know integration
7:23 AM
also i feel that codegolf should have in-built mathjax support..
Added that formula on the post
1 hour later…
8:52 AM
If you haven't seen it yet, Google published a free course on ML: developers.google.com/machine-learning/crash-course
1 hour later…
9:58 AM
CMQ: Is the Sandbox the most answered question in the entirety of Stack Exchange?
BTW Alex A.'s diamond has been removed
@Pavel apl: ,∘⌽⍨⊢⍪⊖
@Mr.Xcoder You want SEDE
But I don't know SQL
@iBug but can you run a SEDE over the whole SE?
AFAIK, you only specify one site
@NieDzejkob Yes. Someone else did it once.
There exist a "most reputation across the network" query.
You can find it and modify it.
10:04 AM
I would if I knew SQL :P
@Mr.Xcoder You only need to know how to drop a table :)
Q: The greedy cutter

iBugiBug recently got a long bar made of composite, yet valuable materials. The bar is so long that iBug can't easily sell it for credits, so he wants to cut it. The bar is made of such fragile and magic materials that, if a part is broken, all parts of the bar made of the same material will break, t...

10:32 AM
Any ideas why SELECT Title FROM Posts ORDER BY AnswerCount LIMIT 1 is wrong?
Incorrect syntax near 'LIMIT'. is not very helpful...
@NieDzejkob Because SE's SQL flavor (T-SQL) doesn't support LIMIT?
@NieDzejkob SELECT TOP(1) or something
@Mr.Xcoder yes
1 hour later…
11:55 AM
cracks neck
snaps neck
@Mr.Xcoder @NieDzejkob yes
12:05 PM
@ManishKundu Feature request from a long time ago (a few months?), Stack Exchange have not reply yet.
i see
Is there a way to find all messages of some user? (assume I don't know what TNBDE is)
@user202729 no, since you need a search term
12:44 PM
man, I normally don't mind unexplained downvotes, because they're anonymous for a reason, but in the sandbox it's kinda pointless...
1:25 PM
Probably "don't post it, everything is bad" (?)
1:41 PM
Started work on an esolang that acts as a shortened version of Kotlin (at the moment I am making it as a library + a small bit of transformation to a kts file, but I may add preprocessing)
Can users flag their own answer if they have 1 reputation?
hi @ngn
@Lembik hi :)
@ngn thanks for the hafnian answer! I would like to test it but I am not sure what input format you support
I added a comment to your answer to this effect
... I was just going to implement it.
1:54 PM
also, why did you golf it? :)
@user202729 implement what?
@Lembik That's not golf. That's how ngn code normally.
#define R return
that's quite golfy!
(after trying to use that coding style for a while my brain exploded because of meaningless variable names)
@Lembik yeah, as user202729 says
@ngn in any case.. I don't need to read it :) But I do need to test it
but I don't think your code accepts input in the format I am giving, right?
1:55 PM
@Lembik With a single return statement, it would be golfier not to use the macro.
Hafnian challenge, use that exponential-but-not-factorial algorithm.
@Lembik as for the input format, I just read the numbers from it and then try to guess n
@Lembik Seems to work for me.
n = sqrt(how many I've read) / 2
@Dennis oh! Let me try again
1:56 PM
Input comes from STDIN
I don't know, but it seems that some people (especially competitive programming users) like having a bunch of #defines at the begin of their program, something like this:
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
// ... (I hate chat markdown)
@ngn my mistake! It does work
@Lembik about half of my code is input parsing, that's unfortunate
so it's basically instant for n = 14
But this is not code golf anyway. And it's not the bottleneck.
Yes, 2^14 is just 16384.
1:59 PM
@user202729 right, but I'd still like to have as little code as possible
so am I expecting it to fail for n = 16?
@Lembik (just redefine the N and you should be ok)
@Lembik I have a #define for max n = 14
@user202729 it's not as simple as that, ints will overflow
Then... typedef long long I.
@user202729 i'm on a 32-bit machine right now, so I couldn't test with more
2:01 PM
17 mins ago, by user202729
Can users flag their own answer if they have 1 reputation?
(as mods tend to comment with "if you fix your answer feel free to flag it for moderator attention" etc.)
@ngn Assuming I made the proper modifications, it works for 16 as well (and is still instant).
@ngn 32-bit machine doesn't mean there is no long long (or int64_t).
(try compiling with -ftrapv or -fsanitize=undefined and it will error out when numbers overflow)
The b array will get too large for a single memory page though.
@Dennis But then it will only be slower by a constant factor.
also there's room for algorithmic optimisations to reduce memory use
2:03 PM
@user202729 I'm not sure what you mean.
The program will only be slower by a constant factor, which is not too much of a problem.
But why slower by a constant factor? The 32-bit program won't be able to address b peroid.
I really need a nice clean python implementation of the faster hafnian algorithm
I will try to do it later if no one is kind enough to do it first
@Lembik hm, that might be a good idea
@Lembik Why? Also Python is not fast, I doubt anyone would use that.
2:07 PM
@user202729 it might be more efficient with the memoisation - with c I use a large array, larger than I need; with python I could use a dict
@ngn But the dictionary lookup would be slower.
@user202729 true, but if I get get to a higher n, it's worth it :)
abandons lily pads and goes back to hafnians
Finally figured out how to reverse enumerate subsets (good riddance), need to cool my brain with liquid helium now. also I probably need to sleep
@Dennis ... I thought it was 1<<N instead of 1<<(2*N).
Anyone know of a upper bound of the unknowns in case the solution is bounded for linear programming?
(for this) (so that the brute force solution can be valid)
2:22 PM
@ngn Memoization seems to be overkill for test cases this small.
@Dennis But... it reduces the complexity from n! to 2^n.
So? 0.4 seconds for the combined test cases, in CPython.
@Dennis I think I brought the time from 13s to ~2s for one of them (on my humble laptop) thanks to memoisation
I think I should recalculate the time complexity.
@ngn ~2s? The program finishes before I can even blink.
2:24 PM
Without memoization it's n!. With memoization it's 4^n.
So, for n=14...
That can't be true. Python wouldn't handle 14! in a fraction of a second.
... there may be some other overhead too.
Agree, let me check again.
... I'm not familiar with the del statement in Python.
@user202729 According to the help center, no. You need 15 rep to flag
@Dennis that's for one of the small tests; if you blink for that long, you may need some sleep :)
btw, I posted a python answer but I couldn't get farther than about n=13
del copy[:j+1:j]
will delete item 0 and j.
2:29 PM
@ngn Did you click the link I posted here?
@Dennis It appears that your algorithm is much faster.
Am I doing something different?
@ngn It's enough to iterate over one row or column. Are you doing something else?
@Dennis Actually no.
ngn's algorithm store a mask which of the rows and columns had been deleted, and thus take O(N) time to find row 0. Dennis explicitly copy the matrix.
@Dennis I find the first available i and then I iterate over j, I guess that should be "one row or column"
So... the overhead for copying the matrix each time is much smaller than that to iterate the bitmask.
2:33 PM
@ngn It does n=14 in no time at all on my PC.
@Dennis why don't you post it as an answer?
Dennis' "small suggestion" happens to be a huge improvement.
It appears in this case that optimizing for performance is tricky.
@Dennis But... should matrix[0][1] be (matrix[0][1]+matrix[1][0])/2? The matrix is not necessary an adjacency matrix.
> In this question matrices are all square and symmetric with even dimension.
A: Calculate the Hafnian as quickly as possible

DennisPython 3 from functools import lru_cache @lru_cache(maxsize = None) def haf(matrix): n = len(matrix) if n == 2: return matrix[0][1] h = 0 for j in range(1, n): copy = list(matrix) del copy[:j+1:j] copy = list(zip(*copy)) del copy[:j+1:j] h += matrix[0][j] * haf(tuple(copy)) ret...

First had to work on memoization. lru_cache doesn't take lists.
Then use tuple instead. (depends on which is faster) Already.
Sort of what I'm doing. del copy[:j+1:j] doesn't work on tuples.
Made it a lot faster by skipping zeroes.
2:55 PM
Thanks so much for the python answers! That way I can be sure they are not overflowing
CMC: Given n, generate a symmetric matrix with side length n and elements in [-1,0,1]. Main diagonal elements must be 0.
@user202729 Jelly, 15 bytes.
A random matrix?
Yes, random.
@user202729 Jelly, 11 bytes.
3:20 PM
@user202729 do 0 1 -1 have to be equally likely when not on the diagonal?
... Ok, I figured it out myself. No problem.
@ngn Not necessary.
@user202729 oh, in that case an all-zero matrix will do :)
@ngn ... Every matrix must be possible.
(assume the random algorithm is sufficiently good)
3:45 PM
"symmetric" matrix means that it's equal to its transpose
but you seen to want just a random matrix, not necessarily symmetric
"seen to"? "seem to"? And yes, I mean equal to its transpose.
@ngn Not sure if I misunderstood something, but since N = 14, shouldn't your C answer work up to size 28?
@Dennis Yes, correct.
(that's why it takes so much memory)
... wait a minute.
So Dennis' solution is actually slower without memoization. ()
59 mins ago, by user202729
CMC: Given n, generate a symmetric matrix with side length n and elements in [-1,0,1]. Main diagonal elements must be 0.
4:02 PM
@user202729 It's also slower with memoization.
I'm getting different results for certain matrices though, so one of our answers has a bug.
Try using -ftrapv for C?
Also verify the matrix is symmetric.
The Python translation produces the same results.
@user202729 That seems to be the issue. Not sure how that happened tbh.
4:24 PM
Q: What does "unclear" mean?

l4m2This topic was closed as unclear. However, all asked problem in the comment that matter seem answered in the first version statement. 1. The result should be constant when n exceed a constant. 2. Decimal and unary(use the output.length) output allowed 3. No infinity output, but infinite loop al...

@Dennis it's supposed to
@ngn In that case, size 30 works even on TIO.
Much faster locally, since I have more RAM.
@Dennis because you used "-mcmodel=medium"
my compiler says:
a.c:1:0: error: code model ‘medium’ not supported in the 32 bit mode
(I'm on 32-bit)
4:37 PM
But the OP is not, so I think you should change N to 15.
that was gcc; clang says:
a.c:8:28: error: array is too large (1073741824 elements)
(ask the OP if they can run it to be sure)
> The timings will be run on my 64-bit machine.
And yes, that much memory is a lot.
@Dennis well, I'd rather let you win than post something I cannot test :)
4:38 PM
You can test it on TIO. :)
@ngn I think Dennis' solution can't go up to 14 (side length 28). (has it been updated?)
It doesn't matter. My Python answer is a lot slower than @ngn's.
Because there was some misunderstanding what is N and what is 2N.
@user202729 I meant he can post the tio link he just gave me as his own
(also note that using a dictionary is definitely slower because there is about half of the elements (those with even parity) actually being used (am I correct?))
@ngn Dennis said that is slower.
My simplex implementation returned correct result now. Good. (canonical form)
4:42 PM
@user202729 the dictionary contains as keys only values of the bitmask that have actually been used
I should try calculating how many of them are actually used.
@ngn Tips: Try using __builtin_ctz (builtin count trailing zeroes of gcc) to see if it's faster.
Ah, I forgot to mention: both TIO and my local machine use zram. A memoization array consisting mostly of small numbers will be compressed. TIO processes are actually limited to 256 MiB, which is why it's so slow on TIO.
@ngn Can you add a TIO link to your C submission?
@user202729 yeah, I'm sure it will be but I'd rather spend time pondering on algorithmic optimisations
@user202729 ok
It looks like that, for this challenge, the inequalities are already given in canonical form. I just need to tranform z -> z⁺ - z⁻ and done.
Anyone here know the Simplex algorithm?
4:52 PM
I used to, never implemented it though
Which pivoting algorithm do you use?
What are the options?
(I just implemented it, it gives the correct result but I don't know if it will cycle)
(and according to PPCG rule, if there exists a (hypothetical) input for which it will fail, it's invalid, I don't want that)
There was something to do with theta-values which were calculated with a division. I chose the smallest of these to pivot on
But which column to choose? And what if there are multiple equal rows?
4:55 PM
I forget, maybe the least negative non-zero?
My memory is very foggy here
I didn't think simplex was sufficient for integer programming though
I think that the Wikipedia page only mentions simplex and criss-cross.
And, it suffices, actually.
> The method proceeds by first dropping the requirement that the xi be integers and solving the associated linear programming problem to obtain a basic feasible solution.
Why doesn't it obtain an optimal solution?
Sorry can't help here
5:16 PM
@Lembik Did you try timing my submission with CPython? It's a lot faster for me.
@Dennis oh you cpython instead of pypy?
you are right! That's a serious pypy bug
I will report it as well as rerun your tests
PyPy3 isn't that great to begin with.
hmm.. well it's not that much faster
35 seconds instead of 48
let me redo ngn's
5:20 PM
@Lembik That is a lot...
ngn's is faster with PyPy3. No array manipulations.
I am not sure if ngn's C code can be run for n = 34
Of course no.
(that solution requires 2^n memory)
ah yes
oops :)
@user202729 2^(2*n)
5:23 PM
so python is winning ! :)
As currently written, the hardcoded maximum size is 30.
that's a nice status for a fastest-code challenge
that memoisation cache grows unnecessarily large. we can do generations instead - first compute products for pairs, then use them for 4s, then 6s, etc, throwing away everything except the previous generation
that makes sense
it's neat but not so efficient
@ngn your python code is currently in the lead :)
@Lembik yay!
5:30 PM
so... are you ready for a faster algorithm ;) ?
I didn't want to intimidate anyone
@Lembik you want to solve your own challenge? :)
@Lembik I read that yesterday, but I have no idea what it's talking about.
I don't know how to implement it!
@Dennis snap :)
maybe we can solve it using the wisdom of crowds
that is help each other
I'm mainly confused by what 1[{i}] is supposed to be.
which page?
in algo 1 ?
5:38 PM
@Lembik that's so uncapitalist :)
@Lembik Yes. Section 3.2.1.
hmm... good question
@Dennis wild guess: in abstract algebra A[B] is the polynomials with coefs in A and variable in B
But 1 isn't a ring...
5:47 PM
We call the extension rings R[Um] for m a non-negative integer.
An element in R[Um] is nothing more than a vector r ∈ R[m]
, i.e. a vector of 2m elements
from R.
so 1 is the unit vector ?
@Dennis Ok so 1[∅] is the multiplicative identity I am pretty sure
is that helps
@Lembik they say that explicitly: "We write 1[∅] to emphasize the multiplicative identity"
well at least that is right :)
so.. how about this ... 1[{i}] might be the multiplication (?) involving the set containing a single element which is indexed by the variable i
00:00 - 18:0018:00 - 00:00

« first day (2590 days earlier)      last day (1140 days later) »