« first day (2589 days earlier)      last day (2259 days later) » 

1:00 PM
Hmmm I'm puzzled now
 
is there a n = 2m problem here somewhere?
as in are we doign something over n/2 where it should be over n?
or the other way round
 
I don't think so, the definitions are equivalent.
[very off-topic] Anyone willing to help me verify the results of a nice inequality? I don't want to use wolfram to check...
 
well something is clearly wrong
with the reference implementation
 
@Lembik You have forgotten to add a leaderboard and I don't think Low level information about my machine is needed at all
 
@Mr.Xcoder I put it in because people ask for it but I will delete it until they do :)
the leader board is there.. just blank because there are no entries yet
 
ngn
1:06 PM
@Lembik if the hafnian is "the number of" something ("the number of perfect matchings in the graph" as written in wikipedia), it seems it should be integer
 
@ngn that's only when it is an adjacency matrix, right?
but the equivalent formula is just a sum
so must give an integer when the elements are integers
 
You can't invalidate any of the current submissions (to the CG challenge) anyway
 
ngn
@Lembik right, sorry
 
so far I can't make another matrix with a fractional answer
ok got a good exampple
take [[1,2],[1,2]]
what is the hafnian of that?
the ref impl says 1.5
 
1
Q: Compute the Hafnian as quickly as possible

LembikThe challenge is to write the fastest code possible for computing the Hafnian of a matrix. The Hafnian of an 2n-by-2n matrix A is defined as: Here S2n represents the set of all permutations of the integers from 1 to 2n, that is [1, 2n]. The wikipedia link also gives a much faster looking fo...

 
1:11 PM
which must be a bug
 
ngn
@Lembik I think you should withdraw the challenge temporarily until this is sorted out
 
Hmm my Pyth solution says 2
^^
 
@Mr.Xcoder ok .. do you agree the ref impl says 1.5?
 
Let me check
Hmm nevermind my Pyth solution says 1.5
 
thanks
 
1:14 PM
So does the ref
 
@ngn done
ok so that must be a bug right?
 
Not sure
 
ngn
@Lembik that's what I get with the ref impl too: 1.5
 
Let me do check with the other answers too
 
so let's do it by hand
 
1:15 PM
The stax solution says 1 >__>
Jelly says 1.5 too
 
I am working through the formula by hand
we have m= 1 and n = 2
so we will give by 2 in the end
 
So am I now
 
the two permutations are 1,2 and 2,1
and there is one term in each product it seems
 
MATL also reports 1.5 and uses a different algorithm as far as I can tell
 
ngn
@Lembik or 0,1 and 1,0
 
1:18 PM
@ngn yes
hmm.. seems to be 3/2??
 
Ok I'm solving it by-hand now too to confirm
 
could someone else check this please
thanks!
 
I get 3/2
So there's no bug in the reference implementation, but the formula may be flawed
 
ngn
@Mr.Xcoder I see no bug either
 
That's why I avoid linear algebra on PPCG ¯\_(ツ)_/¯... Some stuff is just not well-documented
Maybe that formula only holds for adjacency matrices...
 
1:29 PM
Ooh are you guys doing linear algebra :D
 
Yup
 
cool :D
 
@Mr.Xcoder that's why I avoid linear algebra at all. It's evil.
 
@Mr.Xcoder ah.. can we just check it is meant to be defined for complex matrices?
 
@J.Sallé D: linear algebra is great D:
 
1:30 PM
@Lembik I have no idea how we could go about that
Like, there's no relevant source only.
Perhaps it's worth a shot on Math.SE
 
see section 2.1 of arxiv.org/pdf/1601.07518.pdf
 
wait what's the problem?
 
I am asking on math.se :)
 
@HyperNeutrino We're getting 1.5 for the hafnian of an integer matrix :|
 
@HyperNeutrino the problem is that the two formulae for the hafnian give different answers for the matrix [[1,2],[1,2]]
 
1:32 PM
What two formulas?
I mean, how did you test that against the second formula?
 
In mathematics, the hafnian of an adjacency matrix of a graph is the number of perfect matchings in the graph. It was so named by Eduardo R. Caianiello "to mark the fruitful period of stay in Copenhagen (Hafnia in Latin)." The hafnian of a 2n × 2n matrix is computed as haf ⁡ ( A ) = 1 n ! 2 n ∑ ...
those two
 
Yeah I know which
 
@Mr.Xcoder the second one just adds products of matrix elements
so we know it is an integer
unless I am misreading it??
 
@Lembik D: I was already writing it too
 
:)
 
1:33 PM
Let's see who asks first :P
 
ngn
it looks like the first formula should always return an int for a symmetrical matrix (I haven't tried, I just stared at it)
 
@HyperNeutrino s/great/evil
 
@ngn ok.. so are we allowed to compute the Hafnian is a non-symmetric matrix?
maybe that isn't allowed
ahh....
I have a feeling that's the answer
I think the wiki page is missing the word symmetric
 
Are all adjacency matrices symmetric?
 
yes if the graph is undirected
no otherwise
 
1:40 PM
I think you meant graph?
 
but the word symmetric is in books.google.co.uk/…
I did :)
so I think that is the mistake in the wiki page
I just updated the wiki page :)
 
Ok so I guess no Math.SE question
 
ngn
in the description of the second formula (in wikipedia) they talk of partitioning the permutation into sets of size 2, which means they ignore the order of indices, and it sounds like a hidden assumption that a[i][j]==a[j][i]
 
@ngn thanks
 
1:50 PM
Yes, 1.5 is expected. Why not?
 
We were extremely dumb...
In this case, is the Stax submission invalid?
It returns 1 instead of 1.5
 
@tfbninja If it's at the beginning of the code, 7224ǰƖ is shorter
 
ngn
@Mr.Xcoder try [[1.0,2.0],[1.0,2.0]] as input, not [[1,2],[1,2]]
 
2:07 PM
Anyone want to solve the ILP challenge and take the +50 bounty?
 
ngn
@user202729 integer linear programming is way harder than linear programming...
 
I know, I was reading about some algorithm.
(on the other hand it's easier to brute force, if you know how)
 
ngn
@user202729 iterate over a generous superset of all possible solutions, return the best one hopefully before the heat death of the universe? :)
 
But this is .
 
2:28 PM
@ngn solution: make a quantum annealer
using too many million dollars
 
@ASCII-only we can just ask DARPA to do that, I'm sure they have the budget.
 
I mean there are already a bunch of annealers but it's not like any of us can access one
 
Wooo! My first good question badge!
 
just fixing the hafnian examples
 
2:44 PM
@user202729 Is editing every condition in an if statement and removing one condition considered a "small modification"? — OCDkirby 6 mins ago
Sandbox revision needed for ^.
 
Hafnian examples now all replaced and hopefully more sane
as in all the matrices are now symmetric
let me fix the sandbox ones which will be integer valued
 
@Lembik How did you obtain those values?
I am pretty sure [[0, 4.7, 4.6, 4.5], [4.7, 0, 2.1, 0.4], [4.6, 2.1, 0, 1.2], [4.5, 0.4, 1.2, 0]] should result in ~17
 
@Mr.Xcoder argh! Let me check
 
0
A: Sandbox for Proposed Challenges

ZgarbSort by shuffling blocks code-golf sorting optimzation Block shuffle sort The block shuffle sort is a (rather artificial) method of sorting a list. It works as follows, illustrated by an example. [6, 1, 0, 3, 2, 4, -2, -1] Break list into contiguous blocks [6][1,...

 
@Mr.Xcoder I don't know what happened. can you take another look?
I mean I updated the calculations
I found the bug in my code :)
quite embarrassing
ok.. should all be ok now at codegolf.meta.stackexchange.com/a/14941/9206
if anyone could take a look I would be very grateful
 
3:10 PM
This seems interesting, and not too hard to implement.
 
@user202729 yes!
and... Hafnian challenge reposted!
 
Can't you wait for a while?...
(don't you have a leaderboard snippet?)
 
@user202729 I have to run the code myself
so that won't help
it's a fastest code question
unless I misunderstood you
so I will make the leaderboard by hand
 
3:25 PM
The ILP challenge bounty has 15 hours left and 24 hours of grace period. So I have about a day.
 
If I use += then the variable keeps the old reference or a new object is created?
in Python
 
depends on the object apparently
 
what's the type of the object you're applying that to?
 
int is immutable anyway.
 
3:28 PM
ah, ok
 
snap
 
Also - depends on whether the object has __add__ or __iadd__.
 
I wonder why no golfing language has had two encodings instead of one (for those various ones that have encodings.) say, one 8 bit encoding and one 9 bit encoding. With the right instruction set, some tasks could take huge advantage of being able to quickly access another 256 functions
or at least, i know of none
 
The problem is we can't think of that many built-ins.
Feb 27 at 14:55, by H.PWiz
Yes, the more built-ins, the more boring
 
True :p
 
3:32 PM
>The game has ended and the winner is...
>Press any key to continue . . .
My amazing game .-.
 
General purpose builtins are hard to come up with beyond the first 100 :p
 
1
Q: Calculate the Hafnian as quickly as possible

LembikThe challenge is to write the fastest code possible for computing the Hafnian of a matrix. The Hafnian of a symmetric 2n-by-2n matrix A is defined as: Here S2n represents the set of all permutations of the integers from 1 to 2n, that is [1, 2n]. The wikipedia link also gives a different loo...

 
> Jelly finally got n-dimensional array indexing.
But... why is it capitalized? But it's dyadic? @Dennis (I think it should be œị instead of Œị)
 
yes, it's dyadic
> arity = 2
 
3:55 PM
@Pavel hm ok
 
dum dum dum
 
why do they doubt me
my username is clear as day
9
 
Don't you hate it when that happens?
 
3:59 PM
@Blue when posting a solution to a challenge, that has the power to potentially reverse the order of a FGITW...
 
https://codegolf.stackexchange.com/questions/156849/halting-problem-for-simplified-hexagony
I wonder if this is solvable using the 1024 bytes of ram in the R16K1S60
 
Yes.
For code-golf, everything is possible.
(I have to learn simplex algorithm first)
 
I mean, some things might take a fair bit of space. the R16K1S60 has a very small RISC instruction set, so it struggles with some things.
the 'program is a hexagon with a hexagon neighborhood' could be a small problem
6 cases for most instructions in the challange, maybe 3 if you find a way to reflect it
May as well wait for LBPHacker's new computer before trying the challange on a computer built inside a falling sand game
which can, of course, simulate a smaller falling sand game (I wrote a quick program that does that, just for the meta joke)
 
@moonheart08 LBPHacker?
 
He's the guy who designed the R16K1S60, a computer built inside The Powder Toy
 
4:08 PM
now I get to hold my breath until the first answer... fastest-code challenges always take a while until someone answers
 
fastest code you say? prepares shoddy x86 assembly skills
 
@moonheart08 that would be awesome!
4
Q: Calculate the Hafnian as quickly as possible

LembikThe challenge is to write the fastest code possible for computing the Hafnian of a matrix. The Hafnian of a symmetric 2n-by-2n matrix A is defined as: Here S2n represents the set of all permutations of the integers from 1 to 2n, that is [1, 2n]. The wikipedia link also gives a different loo...

 
Doing it in the R16K1S60 would be pointless (The speed at which it executes is entirely dependent on the host's computer), so i'll just do a x86 one instead
 
I will be very impressed
 
For , is a very important part.
 
4:11 PM
Yup. Just gotta find a fast algorithm first. That's going to be troublesome.
 
@moonheart08 I know where the fastest algorithm is
 
The code should be the fairly easy part, just use registers as much as physically possible
 
but it will take a little work to understand
depends on how much you rate yourself :)
 
does anyone have access to a cpu with full avx-512 instruction set? I remember the fastest permanent challenge transformed into a fastest accumulator
 
@miles I would start with the second algorithms from the wiki page
 
4:12 PM
I'm not even in highschool yet. lol. @miles i have most of it on my laptop.
 
as it's quite simple
 
1
Q: Count stacking sequences

user1502040Given a list of stack heights, calculate the number of ways those heights could have been arrived at by stacking blocks one at a time. Shortest code wins. Test cases: [2, 2] 6 [3,3,3] 1680 [1,5,9,1] 480480 [] 1 [10] 1 [2,2,2,10] 720720 Reference Python implementation: def stacking_count(stac...

 
@moonheart08 don't discuss your age online ever
please
99.999% of people are not insane psychopaths.. but 0.001% of 7 billion is quite a lot of people
 
True
 
@mudkip201 thanks yes, it is at the beginning, that helped
 
4:14 PM
yeah I saw that today when I got up, I could have recommended that as a 19 byte improvement to dylan instead of 22 but didn't know you could deduplicate to remove the factorial, great that that was found and added to the wiki
 
But it's a good reference point on how difficult this algorithm will be to understand for me. Doubles up the challange. This'll be intresting.
 
@moonheart08 cool!
I look forward to your answer(s)
 
@Lembik ...?
 
does your laptop have avx 512 vbmi?
 
@user202729 this was in relation to why you shouldn't discuss your age online
 
4:15 PM
Mine? Leme see. What flag would that be?
there's a large list of flags for modern CPUs, it's hard to remember them all
 
maybe it might just say vbmi as a flag
 
grep says no 'vbmi' in /proc/cpuinfo
rip
oh, huh, i was mistaken. no avx512, just avx and avx2. Misremembered lol
 
@Lembik Seems ok now
 
@Mr.Xcoder hooray!
 
I don't even understand the description of the Hafnian. Can someone break it down for me? :p
 
4:23 PM
@Mr.Xcoder am I right in the thinking one could implement the second wiki algorithm using itertools.combinations?
 
Yes you are right
 
@moonheart08 does the reference implementation in python help?
@Mr.Xcoder that should be a lot faster I think already
 
Yea, a bit. I'll just go with that version first.
 
ok
 
I don't actually know how to program in python, but i sure can read it
 
4:24 PM
@moonheart08 Intuitively or rigorous definition?
 
if someone (cough) wanted to make a nice simple implementation of the other wiki formula I could include that too
 
Intuitively, please :p
 
Ok, for an adjacency matrix (all elements are 0 or 1, and a[i][j] = a[j][i]), it's number of perfect matching.
 
so the number of a[i][j] = a[j][i] match cases?
 
Nope
 
That would make the challenge much easier
 
does that page make sense to you?
 
Wikipedia's explanation of perfect matching is, as per usual for it's math pages, confusing. I'll look over it Lembik, i'm literally picking up new knowledge to do this challange
 
is that better?
 
I like Brilliant :)
 
4:28 PM
that's brilliant :)
 
I'll try implementing the python example. Maybe i can figure out a bit more from that
 
sounds good
 
> Radeon HD 4250
We all know someone is going to GPU accelerate this
so wait, the only values in the matrix is 1, 0, and -1?
 
@moonheart08 Nope, that’s what the hafnian is defined for, but you should handle any matrix
 
so how should values that are not those be handled? An error?
 
4:32 PM
No...
The formula given works for any real entries
I can break the formula down for you in a few minutes
 
mk. Thanks a ton @Mr.Xcoder
@Lembik do i have to be able to handle arbitarily sized numbers, or can i just use a 32bit or 64bit float?
 
So, let's start with the beginning: 1/(n!2^n). Do you understand this part?
 
Yup, ! is factorial, correct?
 
Yes
 
@moonheart08 are we talking about the fastest-code challenge? If so you only need ints for the output
 
4:35 PM
oh, yay
 
and the input
and there is a formula on the wiki page that does no division
 
2n is the size of the matrix, where n is some positive integer.
 
@Lembik i was plenty prepared just to have my code choose from two versions of the code at runtime based on if you use decimal points are not.
Mk.
so, the matrix is always a power of 2
that could be useful
 
@moonheart08 no.. not a power of 2
 
Nope, the size is a multiple of 2
 
4:37 PM
err
multiple of 2
had a brainfart there
i should know that :p
 
Now, S_{2n} means the set of permutations of the integers from 1 to 2n.
 
@Lembik I feel that the brilliant wiki only handles adjacency matrix.
 
mk.
so it would be 1..2n if you look at it like most language's ranges.
 
A slang for umkay which is a slag for okay
@moonheart08 Yes, that's correct
@moonheart08 You take each permutation σ in the set of permutations
 
so σ is just a standard variable (for each in 1..2n) or is it something special.
 
4:40 PM
And then take the sum ( denotes summation) of the following for each of the permutations σ
@moonheart08 Yes.
 
Just a variable.
 
@user202729 true
@user202729 but that whole conversation about perfect matching relates to adjacency matrices
which what I think is being discussed here
 
ngn
what's the smallest data type we can use for the hafnian without risk of overflow?
 
@ngn that's unclear to me. I would try 32 bit and see when you overflow
 
Yup, i have a general idea of what Sum is. (I'm all over the place)
 
4:42 PM
first you need an algorithm that runs in less than infinite time for n = 16 :)
 
@moonheart08 The is the symbol for product. You iterate with a variable j from 1 to n and take the product of all the entries in the matrix A at row σ(2j-1) and on column σ(2j).
 
@ngn which formula are you using?
 
CMC: show off your rice
 
@totallyhuman ?
 
ngn
@Lembik neither one, I'm just planning how to solve it
 
4:44 PM
Intuitively, with each permutation sigma, you try the matching sigma(2j-1) - sigma(2j) to see if it's possible.
 
@ngn ok
 
@ngn which language, out of interest?
 
For an adjacency matrix, a product is 1 if all of the factors are 1 (all the edges are present, i.e., perfect matching), otherwise it's 0. The idea generalizes to other types of matrices.
 
@totallyhuman ಠ_ಠ... tha... nks...
 
ngn
4:45 PM
@Lembik are you sure you don't want to specify an input format? people might submit solutions with very diverse inputs, which means a lot of work for you
@Lembik c, of course
 
@Mr.Xcoder hmm?
 
Anyway parsing input should not be the bottleneck.
 
@ngn I am going to say that ideally they can read in matrices exactly as I have them in the question
thanks
 
@totallyhuman The name of the post...
 
@Mr.Xcoder oh the subreddit name? it's used for everything :P
 
4:47 PM
Yeah.....
 
foodporn, earthporn, etc.
 
ngn
@Lembik json, sounds good. If you hadn't said that, I'd have used binary :)
 
the vulgarity of a word comes from the speaker
 
Yeah I am not very familiar with reddit's "culture"
 
4:48 PM
@ngn I added something to the question. [[1,2],[2,-1]] for example
 
@Lembik Well that'll be unfun. I'm bad at making parsers.
 
I guess it's just like brainfuck...
 
yeah
 
Maybe allow alternatively taking in hex?
 
@moonheart08 well if you want a different input format, you just have to ask nicely :)
 
4:49 PM
brainfuck in itself isn't vulgar
 
as I will have to write code to produce it
 
@totallyhuman Let's move to another topic...
@moonheart08 Again, it should not be the bottleneck.
You can ask someone else to write parser for you, it should run very fast.
 
@moonheart08 Recap: For each permutation P (sigma) of the range [1 ... 2n], you take the product of the the matrix entries with the coordinates (<the 2j-1th element of P >,<the 2jth element of P), for each j in [1 ... n]. Then you sum the results and divide the whole thing by n! * 2^n
Understood?
 
@user202729 hmm?
 
In this, the variables can be positive or negative, correct?
 
4:53 PM
Yup, pretty much.
 
@Mr.Xcoder Yeah, ____-porn is a super common term on Reddit (and sometimes outside of Reddit too)
 
I have so many things to learn about The Internet I guess
 
@DJMcMayhem Stop please.
 
Sorry, I just logged on
whistles
 
CMC: generate all permutations in any order of [1..n] (or [0..n-1]) without using permutation builtins
 
4:56 PM
Hi @miles
 
@Lembik will you be using multiple 'arguments', or will you feed the input in as one single string in a single argument?
 
hello xcoder
 
@moonheart08 neither :) I was going to feed it in on standard input
 
hum
Shouldn't be too hard
 
it's easier that way
 
4:57 PM
parsing numbers will be the most difficult part, and i think that's in the c standard library
 
argument get parsed by the shell which can be a pain
@moonheart08 I really wouldn't focus on that part
@moonheart08 just take one of my example, hard code it in your code and see if you can get the right answer
worry about the parsing later
 
Oooh, new Jelly atom :D
 
I'm working on a controller for my new KOTH challenge where bots play a kind of an turn-based idle/clicker... Is this a good idea?
 
Ok.. So the matrix is symmetric, so i only need to store a single word for size.
 
5:10 PM
This winter sucks. We skipped the snowy bit and went straight to -18C (0F) and a migraine-introducing amount of sunshine.
 
It's not too bad here. All my lectures got cancelled but apparently not too far away, there's up to 50cm of snow
 
We got a good 20cm of snow, all other schools got closed and we had to attend both yesterday and today ಠ_ಠ
 
There's no snow here. Just the cold.
 
@Lembik I'd reduce the size of the formula in the "hafnian" challenge, would you mind if I adjusted that?
 
ngn
I'm thinking of a better formula...
does something like this look more promising than enumerating all permutations?
haf(A) = sum( A[i][j] * haf(A without row i and col j) )
 
5:19 PM
@flawr please do!
@ngn yes I like that
 
@Lembik edited it:)
 
ngn
@Lembik according to my quick, informal and possibly wrong analysis it should be computable in O(n 2^2n) time as opposed to O((2n)!) in the other formulas
 
@ngn yes... that is right
@ngn except you can actually do even better
@flawr thanks
but 2^2n is already a huge improvement
 
        # fingers start hurting at 250 clicks
        if bot[0].finger > 250:
            bot[0].hurt = True  # Make them ~~hurt~~ suffer
            bot[2].hurt()       # Tell the bot his fingers hurt
            continue
        # fingers will continue hurting 'till  hurt == 100
        if bot[0].hurt:
            bot[2].hurt()       # Tell the bot his fingers still hurt
            bot[0].finger -= 2  # Decrease pain
            if bot[0].finger <= 100:  # Fingers suffered enough
                bot[0].hurt = False
Part of my controller python file XD
 
oh. so that's what permuations does in python. RIP me
I honestly think this challange might be a bit above my skill level
RIP
 
5:36 PM
We need a golfing challenge that takes the amount of snow and the country and prints what is closed XD
 
@moonheart08 RIP seems a little morbid!
 
5:50 PM
"How do I hide children of a disabled parent?" is a very different question in any other S.E. than StackOverflow...
7
 
PPCG: "Make the children as small as possible"
IPS: "Don't hide them, talk to the parent"
Mathematics: "Differentiate the children, then integrate the parent"
7
 
No matter where you look, it's a diffrent question.
 
@HyperNeutrino bash + jq, 273 bytes: echo $((`date +%s`-`date -d "$(curl http://ppcg.starmaninnovations.com/runcode -d "query=SELECT*FROM\"transcriptAnalyzer_message\"WHERE+markdown+LIKE'**CMC**%25'ORD‌​ER+BY+id+DESC+LIMIT+1&javascript="|jq -r .results_json|jq '.[0]|{date,time}'|cut -d\" -f4|sed 1d\;4d)" +%s`))
 
Why is Telnet so hard to find clear documentation on? The RFCs work, but they often give you a lot of information you're not intrested in
 
@moonheart08 seriously? telnet? it's just like netcat
 
5:55 PM
telnet has it's own little things. see the telnet IAC codes
 
What telnet feels like:
>https://xkcd.com/927/
 
It's really annoying to find all of the little codes so you can properly handle them. Some act in intresting ways
 
6:13 PM
CMM: Is there any challenge on PPCG where bot/program's fingers can hurt? :P
 

« first day (2589 days earlier)      last day (2259 days later) »