« first day (3162 days earlier)      last day (1695 days later) » 

New Main Posts
New Main Posts
6:39 AM
-1
Q: A really inefficient calculator

iireluChallenge: Add two numbers. In O(n^m) time, where n and m are the two numbers given. Sleeping, or your language equivalent, is not allowed. Input: Two integers, separated by a space. Output: The sum of the two integers. Additional notes: The exact timing doesn't matter, as long as the input 10...

code-golf restricted-complexity
 
New Main Posts
New Main Posts
6:59 AM
0
Q: Simple Calculus

asmgxOne of the Calculus rules in differentiation is f(x) = aX^N + b d f(x)/dx = aNX^N-1 Example f = 2X^8 + 3 df = 16X^7 another example f = X^4 - 3X^2 + 7X + 8 df = 4X^3 - 6X + 7 you need to build a code to do differentiation the input is an equation like this X^4 + 3X^2 + 7X + 8 ...

code-golf
 
ngn
ngn
7:15 AM
@flawr because of the principle of computational equivalence. a little complexity in the computational mechanism almost always leads to maximum complexity in what can be computed. when he doesn't advertise mathematica, sometimes wolfram is right.
 
xnor
xnor
@mbomb007 Thanks!
 
New Main Posts
New Main Posts
0
Q: ✂ Split string using rules 🚀

Kamil KiełczewskiI have following example input string (it can be arbitrary) Lorem ipsum dolor sit amet consectetur adipiscing elit sed doeiusmod tempor incididunt ut Duis aute irure dolor in reprehenderit in esse cillum dolor eu fugia ... Splitting rules (A-E) by example (the // in line means comment) ...

code-golf
 
 
3 hours later…
flawr
flawr
10:39 AM
@ngn intersting read, thanks
 
 
3 hours later…
Anush
Anush
1:27 PM
hi all
I was wondering.. you can compute the number of inversions in an array of length n reasonably easily in n log n time
 
ngn
ngn
1:39 PM
@Anush inversions? is that pairs i<j such that a[i]>a[j]?
 
Anush
Anush
@ngn yes
 
ngn
ngn
@Anush can the array contain duplicates?
 
Anush
Anush
@ngn No.. I was considering only permutations
so I thought a fun challenge might be for input value b, compute the number of permutations with inversion number less than b
Assume the input has some fixed length
 
ngn
ngn
@Anush i think i know how to solve the first problem (compute the number of inversions in n log n time). the second one sounds like more fun.
 
Anush
Anush
@ngn right!
so what sort of challenge could I make this?
the risk with code-golf is you just get a crazy brute force solution
which isn't very interesting
 
ngn
ngn
1:51 PM
@Anush fastest-code or fastest-algorithm. personally i prefer fastest-code because it's easier to measure time than to prove complexity.
with fastest-code there's an expected error margin, so you know the results can't be too wrong. with fastest-algorithm a small mistake in the proof could make the result totally wrong.
 
Anush
Anush
@ngn sounds good... now people will want lots of test examples ... which sounds tricky :)
maybe there is a sequence on the OEIS?
 
ngn
ngn
@Anush technically that's not a sequence, as there are two inputs: b (the inversions limit) and n (the size of the permutation)
 
dzaima
dzaima
@ngn if i'm understanding it correctly, fastest-algorithm should be used together with a tie-breaker, so with it you'd need a second scoring system anyways
 
Anush
Anush
@ngn yes that is true
@dzaima I would just put the first answer for that I think
any help making sample answers greatly appreciated!
I will make it fastest-code as fastest-algorithm is not very granular. I mean how many different complexities will there likely be?
 
ngn
ngn
@ngn (technically a sequence of sequences can be cantor paired into a single sequence but let's ignore that now...)
 
dzaima
dzaima
2:00 PM
@Anush i was gonna ask that hoping you'd know as you want to make a challenge out of it :p
 
Anush
Anush
@dzaima I think you can compute the entire distribution in O(n^3) time
and naive is exponential
so there is at least a gap :)
 
dzaima
dzaima
@Anush also that's why i was suggesting using a non-trivial tie-breaker for fastest-algorithm so that good algorithms are awarded always but improvements other than the algorithm can be made
 
New Sandboxed Posts
New Sandboxed Posts
0
A: Sandbox for Proposed Challenges

simonalexander2005Title: Score my Tarok hand Inspired by this challenge In Slovenia (and elsewhere in central Europe), the card game Tarok is very popular. See here for a complete list of rules, but essentially it is a trick taking game, played in teams that change per round. This challenge is a code-golf chall...

 
Anush
Anush
@dzaima I worry that fastest-algorithm won't be popular. A lot of coders are very unclear about big Oh complexity
and worry about all sorts of practical questions
 
Poke
Poke
2:45 PM
..?
programmers should not be unclear about big o
it's important
 
John Dvorak
John Dvorak
3:02 PM
I'm well aware of the Big Oh. It's a nice idea, but it sometimes gives the wrong results.
 
AdmBorkBork
AdmBorkBork
Big Oh? Is that a chain of donut shops?
 
Poke
Poke
3:27 PM
@JohnDvorak can you explain what you mean by this
 
John Dvorak
John Dvorak
One fairly known example is that insertion sort is faster than quicksort for arrays smaller than 10 elements
 
Poke
Poke
big o isn't meant to be applied like that
 
John Dvorak
John Dvorak
exactly
 
Poke
Poke
so i wouldn't say it's wrong
that's just misusing it
it's a bounding function as n approaches infinity
 
John Dvorak
John Dvorak
I didn't say it's wrong, I'm saying it's not always right.
 
Poke
Poke
3:31 PM
...
how is that any different
 
John Dvorak
John Dvorak
Furer's algorithm has better asymptotic complexity than Karatsuba. It's useless for numbers less than 2^64 bits in length.
 
Poke
Poke
and?
 
John Dvorak
John Dvorak
and if you can't use asymptotic complexity to help you choose an algorithm to implement, what do you use it for?
 
Poke
Poke
you have to cater your algorithm to your problem
there isn't always a one size fits all solution
 
John Dvorak
John Dvorak
Therefore you can't use rely on the Big Oh. Heck, sometimes you'll grab an exponential complexity algorithm because it runs once in a blue moon, always at nighttime, and the polynomial time alternative would make your code reviewer's brain pop.
 
Poke
Poke
3:38 PM
if you're saying you can't only rely on big o, then sure... but i wouldn't say that means it gives the wrong results. that just means you're not doing your due diligence in choosing an algorithm.
 
John Dvorak
John Dvorak
Theory: Quick sort is the best, never settle for a quadratic time algorithm
Practice: r = []; (r << a.min; a.delete_at(a.find_index(a.min))) until a.empty?
@Poke I'm not entirely sure what you're saying, but I believe you're trying to say the same thing I do
 
Poke
Poke
I'm saying that I disagree with your statement that big o "sometimes gives the wrong results". Big o is a bounding function for the time/space complexity of your algorithm. There's nothing "wrong" about that. If you're trying to compare two algorithms solely based on their big o complexity, then you're wrong in doing so.
I don't think that makes it confusing
but people can absolutely be confused
 
John Dvorak
John Dvorak
Let me reword: Big oh sometimes suggests that you use an algorithm that you shouldn't use.
 
Poke
Poke
It does not.
Your interpretation does.
 
John Dvorak
John Dvorak
Okay then... big oh doesn't suggest algorithms, and trying to use it for that purpose sometimes gives the wrong results?
 
Poke
Poke
3:45 PM
Sure
 
AdmBorkBork
AdmBorkBork
> In theory, there is no difference between theory and practice; but in practice, there is.
 
John Dvorak
John Dvorak
What does it do right, that is actually useful in practice, then?
 
Poke
Poke
As I've said... it is a bounding function for your algorithm. You know that time/space complexity will not grow faster than <big o>
 
John Dvorak
John Dvorak
How's that useful in practice?
 
Poke
Poke
Let's say you're trying to find a majority element in an infinite list with infinite unique elements
 
John Dvorak
John Dvorak
3:48 PM
I never do that
 
Poke
Poke
okay well instead of infinite unique elements let's say it's just a very large set
 
John Dvorak
John Dvorak
Fine then.
 
Poke
Poke
By using an algorithm that uses O(N) space complexity you know that you may need a very large amount of memory
in order to determine the majority
but no more than the total number of unique elements
 
John Dvorak
John Dvorak
An algorithm that stores 100kB per element is still O(N)
 
Poke
Poke
the amount of space per element doesn't matter
it's the growth
 
John Dvorak
John Dvorak
3:51 PM
False. In practice I only care about the actual sizes.
 
Poke
Poke
maybe you do
here's a real world example of the above usecase: request ips seen by a firewall
if you're trying to prevent a DOS
 
John Dvorak
John Dvorak
I'll rather run an algorithm that costs four bytes for each pair of elements than an algorithm that costs four MB per element.
 
Poke
Poke
as the amount of elements grows the difference between 4b and 4mb doesn't matter
at least not as much
 
John Dvorak
John Dvorak
By the time I have 1000000 elements, both algorithms have vastly exceeded the amount of storage available to me. Until then, the quadratic one is better than the linear one.
Do you have a 4TB hard drive just laying around?
 
Poke
Poke
yes
my desktop computer has 6.5tb iirc
but regardless of that
 
John Dvorak
John Dvorak
3:56 PM
It seems I have a measurement error due to the way my environment allocates memory. The linear algorithm actually consumes 8MB per element.
now it's useless even to you.
 
Poke
Poke
but i still know the upper bound in both cases
 
John Dvorak
John Dvorak
neat. So?
 
Poke
Poke
the worst case scenario
if you know exactly all the parameters then why are you using a bounding function
big o is in terms of an unknown variable that is expected to approach infinity
 
John Dvorak
John Dvorak
My point is, what do you use big oh for? If you use it to choose an algorithm, sometimes you'll make the wrong choice.
 
Poke
Poke
you use it to limit your worst case scenario
not optimize your best case
bubble sort is O(N) best case (list is sorted already)
but worst case it's O(N^2)
that's why many programming langs use quicksort or timsort
as their default built-in sorting algorithm
 
John Dvorak
John Dvorak
4:03 PM
Let's say a black box linear-space algorithm consumes 4 MB then tested with 100 elements, and I'll be running it with 1 000 000 elements. Does that mean I'll be fine with 0.5 GB of RAM?
 
Poke
Poke
sigh
i'm going to eat lunch
 
John Dvorak
John Dvorak
Most programming languages don't use Quicksort. Some use a combination of quicksort and insertion sort. It's because Quicksort's asymptotic complexity means nothing when you only have ten elements.
And sometimes the worst-case complexity doesn't matter until, let's say, 2^64-bit numbers.
 
ngn
ngn
@JohnDvorak big oh is useful in the analysis of algorithms. algorithms in computer science are usually described in a form independent of any specific hardware, or specific programming language.
 
John Dvorak
John Dvorak
@ngn Sure. But that's theory.
 
ngn
ngn
@JohnDvorak no claims about practice are made in the definition of big oh
 
John Dvorak
John Dvorak
4:09 PM
and that's exactly my point.
 
ngn
ngn
if a function f is in a big oh class better than that of a function g, this only means that there's some n (usually the size of the input) beyond which f will outperform g
that n may be extremely large
 
El'endia Starman
El'endia Starman
My approach to Big O in practice: don't pick an algorithm that's O(2^N) or worse (if possible).
 
John Dvorak
John Dvorak
@El'endiaStarman So, how do you find the shortest path between two points? :P
 
DJMcMayhem
DJMcMayhem
My approach to Big O: Hmm, is this fast enough? tests it
 
El'endia Starman
El'endia Starman
@JohnDvorak implements A* Good enough.
 
J. Sallé
J. Sallé
4:11 PM
I never actually learned big O notation so I just pretend I understand it >.>
 
ngn
ngn
@JohnDvorak but you're saying "it's not useful". it is useful in CS theory.
 
DJMcMayhem
DJMcMayhem
@J.Sallé If you've got a basic understanding of algorithms and programming, it wouldn't be too hard to learn.
 
El'endia Starman
El'endia Starman
@J.Sallé O(log N) == very good. O(N) == pretty good. O(N^2) == fine. O(2^N) == bad. O(N!) == VERY BAD.
 
John Dvorak
John Dvorak
@J.Sallé It's easy. You just pick a nice-looking function and if you can multiply it by a big enough number that it correctly tells you that your code won't run longer than that, it fits the Big-O definition.
 
caird coinheringaahing
caird coinheringaahing
I've been sat here with no clue what on earth "Big Oh" is O.o
 
DJMcMayhem
DJMcMayhem
4:12 PM
@El'endiaStarman You forgot O(N) == very very good
And O(1) == ideal
 
El'endia Starman
El'endia Starman
@DJMcMayhem I have O(N) as "pretty good". :)
Oh yeah, O(1) is the beeeest.
 
John Dvorak
John Dvorak
Big-oh is useful. But you can't rely on it because what it actually gives you isn't quite the same thing as you want.
 
ngn
ngn
@JohnDvorak again, no claims are made about "actually", only about "eventually" (for large enough n)
 
Anonymous
@cairdcoinheringaahing It's the sound you make when you realize what people are talking about
 
John Dvorak
John Dvorak
You can use big-oh to pick an algorithm just fine. And it is a great idea. But you can't end there because sometimes it makes you pick the wrong one.
@cairdcoinheringaahing It's easy. You just pick a nice-looking function and if you can multiply it by a big enough number that it correctly tells you that your code won't run longer than that, it fits the Big-O definition.
 
DJMcMayhem
DJMcMayhem
4:16 PM
@cairdcoinheringaahing @J.Sallé Here's the basic idea: int f(int a, int b) return a + b; is constant, because as a and b get bigger, f won't take any longer to run. But for something like int f(int a) int sum = 0; for (int i = 0; i < a; i++) { sum += i; } return sum; , then as you increase a, the runtime will get longer. This is linear because for a=10, you'll run through the loop 10 times. If you double a, it'll take roughly twice as long. And that doesn't really change even as a gets absurdly big
 
Anonymous
@JohnDvorak Truth. Those leading scalars and trailing terms become important when N is small :P
 
caird coinheringaahing
caird coinheringaahing
@DJMcMayhem So is that O(N)?
 
DJMcMayhem
DJMcMayhem
The second one would be O(N), yes
 
John Dvorak
John Dvorak
Algorithms with good Big-Oh guarantees tend to be good. But sometimes even algorithms with Big-Oh guarantees are useless in practice.
 
DJMcMayhem
DJMcMayhem
If you graph the execution time of that function, it'll look very similar to graphing N
 
ngn
ngn
4:17 PM
sometimes big oh is useful in practice too. for instance almost any tiny progress made on the algorithms for factoring large integers translates to real progress in practice, because we tend to use super large inputs for rsa and the best known algorithms are almost exponential.
 
DJMcMayhem
DJMcMayhem
(as in y=x)
 
caird coinheringaahing
caird coinheringaahing
And how do you calculate the O for a given function?
 
John Dvorak
John Dvorak
@ngn sometimes, yes. Usually, yes. Always, no.
 
Anonymous
@DJMcMayhem Come on man, you at least have to teach them that complexity analysis is with regard to some elementary operation and not overall time.
 
DJMcMayhem
DJMcMayhem
By seeing how much increasing the size of the input slows the execution down
 
ngn
ngn
4:18 PM
@cairdcoinheringaahing you compute a given limit
 
Anonymous
@cairdcoinheringaahing You pick some elementary operation and see how many loops it's wrapped in, and what the end conditions of those loops are
 
caird coinheringaahing
caird coinheringaahing
Yeah, I hate this already :/
 
DJMcMayhem
DJMcMayhem
It doesn't have to be that complicated
 
John Dvorak
John Dvorak
@cairdcoinheringaahing Usually you eyeball it. You don't have to provide a tight upper limit after all, just an upper limit :P
 
caird coinheringaahing
caird coinheringaahing
I say we use TIO notation: TIO(1) means it runs in 60s, TIO(0) means it doesn't
4
 
Anonymous
4:20 PM
The easiest way to learn complexity analysis is to look at sorting algorithms
 
ngn
ngn
actually O(f) is the class of functions that "grow" like f, so we usually pick the simplest f, e.g. O(2x^2 + 5x - 3) ≡ O(x^2)
 
John Dvorak
John Dvorak
you mean, on a machine available in 1969?
@ngn like f or slower
 
Anonymous
e.g. Bubble sort is O(N^2) because the algorithm looks like for(int i = 0; i < a.length; ++i) for(int j = 0; j < b.length; ++i) doAComparison(i,j);
 
ngn
ngn
@JohnDvorak ah, right
 
John Dvorak
John Dvorak
If you want to provide a lower bound as well as upper bound, it's called theta
 
ngn
ngn
4:25 PM
given a function, it's relatively easy to guess or compute its O class, but analysing code in order to find how long it takes as a function of the input size could be very difficult sometimes, unfortunately
 
John Dvorak
John Dvorak
or even impossible
 
ngn
ngn
right. for some algorithms we don't even know if they can finish or not
 
Anonymous
Like bogosort - unless you know that your PRNG is capable of outputting the value that corresponds to the sorted permutation of the input, you can't be certain that it will ever terminate
 
Anonymous
Bogosort is the best example of how big-O notation can be misleading - on paper, it's O(1), because the runtime does not depend on the input list's length
 
John Dvorak
John Dvorak
actually, it isn't O(f) for any f, because finite functions don't work and infinite functions don't count.
 
Anonymous
4:41 PM
If we're counting comparison ops (which is normally how sorting algos are compared), there are 0 comparision ops done in bogosort, so it's O(1)
 
John Dvorak
John Dvorak
You do comparisons when you check if each new permutation is correct
 
DJMcMayhem
DJMcMayhem
^
 
Anonymous
Oh, true, nvm
 
Anonymous
Don't try to reason about complexity analysis on dayquil, kids
 
John Dvorak
John Dvorak
Anyways, my favorite algorithm for theoretical analysis is LSB-first bucket sort. O(1) in theory, but never actually used.
Although, my favorite overall is Batcher's odd-even mergesort.
 
Adám
Adám
4:49 PM
CMC: Given a three-digit MMD or MDD number, return the dates (month,day) it can represent, e.g 321→[[3,21]]; 123→[[1,23],[12,3]; 110→[[1,10]]; 101→[[10,1]]
Actually, should I allow returning two unique values for whether it is ambiguous or not?
 
John Dvorak
John Dvorak
Extend it to 2-digt and 4-digit numbers as well and submit it to codekata
just the list of valid parses will do
10 -> []
99999 -> []
 
Adám
Adám
@JohnDvorak Isn't that a bit boring? 5-digits is never valid. 2-digit is valid iff there is no 0.
 
John Dvorak
John Dvorak
You still have to test for the cases. Useful in katas.
 
Adám
Adám
@JohnDvorak 201211→[[2012,1,1],[2020,12,11]] :-)
 
John Dvorak
John Dvorak
Do we have to test for dates predating the gregorian calendar?
 
Adám
Adám
5:01 PM
@JohnDvorak Go proleptic!
 
John Dvorak
John Dvorak
In which case I adopt a 13-month lunar calendar and renumber everything according to it
Still not sure what notation I should give to the leap day
 
 
1 hour later…
Anush
Anush
6:21 PM
hmm.. so about inversions.. given a permutation of length 20, say, we can compute the number of inversions fairly easily in n log n using geeksforgeeks.org/counting-inversions
but how can we count how many permutations have fewer inversions than the permutation you are looking at?
 
John Dvorak
John Dvorak
6:57 PM
You could compute the number of permutations that have each given number of inversions. Not sure how though.
 
New Sandboxed Posts
New Sandboxed Posts
7:43 PM
0
A: Sandbox for Proposed Challenges

AdmBorkBorkFrom Plate to State code-golf kolmogorov-complexity This is essentially the inverse of Generate a US License Plate Challenge: Given a string that matches one of the below license plate formats, output all possible states that match that formatting. In the below table 0 stands for a single digi...

 
Anush
Anush
8:25 PM
@JohnDvorak That would be cool if possible.
 
John Dvorak
John Dvorak
Time to prod OEIS?
 
Anush
Anush
@JohnDvorak I did try but it's not obvious to mehow
because there are two variables. The length of the permutation n and the number of inversions
 
John Dvorak
John Dvorak
Calculate the sequence of inversion count counts for each permutation size (this is going to be a pain); input each sequence into OEIS. If there is uncertainty about which parts of each subsequence should be included, leave them out.
 
Anush
Anush
@JohnDvorak right.. I have no idea how to do the first part for anything except trivially small permutations
 
John Dvorak
John Dvorak
I'm hoping that five elements will be big enough for search (remember, there are quadratically many inversions!) but small enough to enumerate by hand. If not, time to get coding.
 
Anush
Anush
8:31 PM
oh I was never going to do it without code!
but even with code, it's a pain
 
John Dvorak
John Dvorak
Ruby has built-in for permutations. Let me hack up something.
 
Anush
Anush
thanks!
 
John Dvorak
John Dvorak
def inversion_count_histogram(n)
  r = Hash.new {|h, k| h[k] = 0}
  [*1 .. n].permutation{|x| r[x.combination(2).count{|c| c[0] > c[1]}] += 1}
  p r.values.join(", ")
  p r.values.sum
end
3 => 1,2,2,1
4 => 1,3,5,6,5,3,1
5 => 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1
And, ladies and gentlemen, that last row alone was enough to nail down the search results to just three results!
 
Anush
Anush
hmm..
can we do 6? :)
 
John Dvorak
John Dvorak
1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1
7: 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1
 
Anush
Anush
8:41 PM
aha!
 
John Dvorak
John Dvorak
irb(main):036:0> inversion_count_histogram(8)
"1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, 3017, 3450, 3736, 3836, 3736, 3450, 3017, 2493, 1940, 1415, 961, 602, 343, 17
4, 76, 27, 7, 1"
irb(main):037:0> inversion_count_histogram(9)
"1, 8, 35, 111, 285, 628, 1230, 2191, 3606, 5545, 8031, 11021, 14395, 17957, 21450, 24584, 27073, 28675, 29228, 28675, 27073, 2458
4, 21450, 17957, 14395, 11021, 8031, 5545, 3606, 2191, 1230, 628, 285, 111, 35, 8, 1"
362880
 
Anush
Anush
oeis gives the same 3 each time!!
 
John Dvorak
John Dvorak
This one actually took a couple of seconds
 
Anush
Anush
they are in the OEIS up to 6
which is quite intriguinh
 
John Dvorak
John Dvorak
irb(main):038:0> inversion_count_histogram(10)
"1, 9, 44, 155, 440, 1068, 2298, 4489, 8095, 13640, 21670, 32683, 47043, 64889, 86054, 110010, 135853, 162337, 187959, 211089, 230
131, 243694, 250749, 250749, 243694, 230131, 211089, 187959, 162337, 135853, 110010, 86054, 64889, 47043, 32683, 21670, 13640, 809
5, 4489, 2298, 1068, 440, 155, 44, 9, 1"
More terms are going to take longer
This one took over a minute. 11 should be ... possible?
 
Anush
Anush
8:43 PM
right but now we have to understand the OEIS entries!
or just pose it as a PPCG challenge!
 
John Dvorak
John Dvorak
More terms should be possible if you pose it as the width profile of the Cayley graph of the permutohedron of the correct size... which is exactly as easy as it sounds :P
 
Anush
Anush
:)
 
John Dvorak
John Dvorak
I mean, not the describing a Cayley graph bit; the finding out the width profile bit
I feel Math.se might like the question
 
Anush
Anush
good point.. posed!
 
John Dvorak
John Dvorak
Commencing f(11) computation
 
Anush
Anush
8:48 PM
:)
 
dzaima
dzaima
copying code from OEIS seems to just work
 
Anush
Anush
where did you copy it from?
 
dzaima
dzaima
@Anush the first result's mathematica code section :p
 
Anush
Anush
aha.. so what is that code in a "normal language"?
 
John Dvorak
John Dvorak
Oh hey, there is an explicit formula for that!
The graph view shows some 20k numbers!
 
Anush
Anush
8:52 PM
" Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i), where k ranges from 0 to A000217(n-1). Also enumerates permutations by their major index." is brilliantly hard to understand!
so the main challenge now is to implement this in a language without mysterious built in functions!
if anyone could translate it into Python, what would be awesome
 
John Dvorak
John Dvorak
T(1, 1) = 1, T(1, k != 1) = 0,

T(n, k) = Sum_{j=0..n-1} T(n-1, k-j),

T(n, k) = T(n, k-1) + T(n-1, k) - T(n-1, k-n). (End)
This seems very translatable
 
Anush
Anush
it does now!
err.. actually there are two lines with T(n, k) =
 
John Dvorak
John Dvorak
Perhaps both are true?
 
Anush
Anush
but which do we implement?
do you mean T(n-1, k-n) ?
 
John Dvorak
John Dvorak
Vague guess, ignore the second line?
 
Anush
Anush
8:56 PM
instead of T(n-1, n-k)?
 
dzaima
dzaima
@Anush the first alone seems to work fine
 
Anush
Anush
@dzaima which of the three lines did you implement?
numbers 1 and 2?
 
John Dvorak
John Dvorak
@dzaima I suspect the third line is just a faster version of the second line
 
dzaima
dzaima
@Anush yep
 
Anush
Anush
but is it really T(k-n)?
 
John Dvorak
John Dvorak
8:57 PM
I'm just copy/pasting from OEIS!
 
Anush
Anush
:)
 
dzaima
dzaima
@JohnDvorak aren't we all? :p
 
Anush
Anush
Major index
In mathematics (and particularly in combinatorics), the major index of a permutation is the sum of the positions of the descents of the permutation. In symbols, the major index of the permutation w is maj ⁡ ( w ) = ∑ w ( i ) > w ( i + 1 ) i . {\displaystyle \operatorname {maj} (w)=\sum _{w(i)>w(i+1)}i.} For example, if...
hmm
 
John Dvorak
John Dvorak
I'll give the formula a shot in Ruby
 
dzaima
dzaima
9:23 PM
@JohnDvorak seems to be the case - 4s for first 100 rows (166750 numbers returned total) for the lazy impl + memoization (code)
(it's hitting precision limits very early on as Dyalog uses 64-bit floats though)
 
Adám
Adám
@dzaima Switch to 128-bit decimal floats.
 
dzaima
dzaima
@Adám that hits the limits at the 32nd line too though
originally one of the things i wanted for sure to have in dzaima/APL was a toggle for infinite precision but now that's pretty much impossible to add
 
John Dvorak
John Dvorak
def inversion_count_table(n)
  res = Hash.new do |h, (n, k)|
    # puts "evaluating [%d, %d]" % [n, k]
    h[[n, k]] = if n == 1
                  (k == 1) ? 1 : 0
                elsif k < 1
                  0
                else
                  res[[n, k-1]] + res[[n-1, k]] - res[[n-1, k-n]]
                end
    # puts "res[[%d, %d]] = %d" % [n, k, res[[n, k]]]
    res[[n, k]]
  end

  p (1..).lazy.map{|k| res[[n, k]]}.take_while{|r| r > 0}.force
end
f(100) takes a couple of seconds, and the output is bloody long
or rather... a second or so
uses infinite precision arithmetic
 
 
2 hours later…
New Main Posts
New Main Posts
11:23 PM
0
Q: Determine the Winner of a Game of Australian Football

StephenIn Australian Football, goals are worth 6 points and behinds are worth 1 point. Scores may include the number of goals and behinds, as well as the total score. Given the number of goals and behinds for two different teams, determine which team won the game. Take four integers g1, b1, g2, b2 as i...

code-golf decision-problem integer game
 

« first day (3162 days earlier)      last day (1695 days later) »