melonmouse

vorig jaardiscuss

Great idea! It also works on the side of the board, I couldn't help building it out: https://onemillionchessboards.com/#4363,6

melonmouse

2 jaar geledendiscuss

The linked proof for that median of medians is O(n) feels counterintuitive to me. Here's a (simpler?) alternative.

  T(0) = 0
  T(1) = 1
  T(n) = n + T(n/5) + T(7/10*n)

We want to prove that:

  T(n) ≤ C*n

It is intuitive that T(a+b) ≥ T(a) + T(b), or in other words, T is superadditive. That can be shown by induction:

Induction base: it holds for all a+b < 1, the only case being a=0, b=0:

  T(0+0) = 0 + T(0) + T(0) ≥ T(0) + T(0)

Induction step: suppose it holds for all a+b < k. Let a+b = k.

  T(a+b) = T(k)
         = k + T(k/5) + T(7/10*k)
         ≥ k + T(a/5) + T(b/5) + T(7/10*a) + T(7/10*b)
         = [a + T(a/5) + T(7/10*a)] + [b + T(b/5) + T(7/10*b)]
         = T(a) + T(b)

Because T is superadditive:

  T(n) = n + T(n/5) + T(7/10*n)
       ≤ n + T(n/5 + 7/10*n)
       = n + T(9/10*n)

Now we can apply the master theorem. Or to write out the proof (using a geometric series):

  T(n) ≤ n + T(9/10*n)
       ≤ n * ∑ᵢ₌₀ᶦⁿᶠᶦⁿᶦᵗʸ (9/10)^i
       = n * 1/(1-9/10)
       = 10*n

So, we have shown the algorithm is O(n) with C=10 (or less).

melonmouse

4 jaar geledendiscuss

As a joke, I made a webpage where you can do attribution to ALL GitHub repositories:

http://thanksforthecode.com

It scrolls past all the repos movie-credits-style. Doing it that way takes several days! It shows how abstract and absurd giving contribution to such a large body of works is.

melonmouse

4 jaar geledendiscuss

Who should we thank for the code written by Copilot? In a way, we should thank everyone in the training data. That includes: everyone with a public Github repository.

Context: https://github.com/usewits/ThanksForTheCode

You can customize it like this: thanksforthecode.com?name=PROJECT_NAME

melonmouse

4 jaar geledendiscuss

Another funemployed xoogler here! I've been making games for the last year, and one thing I would definitely love to explore is designing a deep but easy to learn game using learning techniques. We should talk!

You can reach me on: [email protected]

melonmouse

5 jaar geledendiscuss

> This is factually wrong, looks at CO2 emissions per capita, USA has carbon footprint double that of France.

It's closer to 3x: USA 15.7 vs France 5.2 tonnes of CO2 per capita per year (2017, not accounting for other gasses that contribute to warming) [1]

[1] https://en.wikipedia.org/wiki/List_of_countries_by_carbon_di...

melonmouse

5 jaar geledendiscuss

I made a game about polyominoes: https://melonmouse.itch.io/polyominoes

If you try it out, please let me know what you think :)

P.S. work on that led to a sequence on the Online Encyclopedia of Integer Sequences: https://oeis.org/A239658

melonmouse

Submissions

A way to do attribution when using GitHub Copilot

Checkface: Represent hash as StyleGAN2 face, to make comparing hashes easy

16th place: Our bugs and strategy at Hashcode 2021

comments