44
votes
38
votes
Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one
Python 3, 102 bytes
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
Try it online!
This is of O(1^n), ...
- 49.6k
32
votes
Give a permutation with no two consecutive integers next to each other
Jelly, 3 2 bytes
ḂÞ
Sorts the integers in [1, ..., n] by their LSB.
Try it online!
- 210k
20
votes
Efficient Bytewise FizzBuzz
JavaScript (Node.js), 145 bytes
Saved 2 bytes thanks to @user202729
Expects a BigInt. Outputs # instead of \n for readability.
<...
- 188k
18
votes
Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one
Perl 5, 82 73 71+1 (for -n flag) = 72 bytes
I'm certain I can golf this (a lot) more, but it's bedtime, I've spent enough time debugging as is, and I'm proud of what I have so far anyway.
...
- 1,949
18
votes
Accepted
Polite Near-Sighted Drunk Bot on a Minefield
Python 2, 65 bytes
def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)
Try it online!
The probability the bot is dead can be expressed as:
$...
- 144k
17
votes
Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one
Actually, 20 bytes
";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"
Try it online!
Input: 5
Output:
rⁿ@╜╖1(;
[0]
5
...
- 49.6k
16
votes
Give a permutation with no two consecutive integers next to each other
Python 2, 32 bytes
lambda n:(range(n|1)*2)[1:n*2:2]
Try it online!
- 58k
14
votes
Write an Incident tokeniser
C (gcc), 324 bytes
The function f takes a null-terminated string and prints the tokens to stdout. All newlines can be removed from the code below.
...
- 31.3k
13
votes
Sum of set bits from 1 to n
K (ngn/k), 45 32 bytes
{+/b*1+(q!'x)+-2!q*<q:2/=#b:2\x}
Try it online!
Golfing ideas thanks to @ngn and @coltim
The OEIS page contains a curious PARI program:
<...
- 73.8k
13
votes
Sum of set bits from 1 to n
JavaScript (ES6), 57 54 53 52 bytes
n=>(i=0,g=b=>b--&&(n>>b&1&&b+i+i++<<b)+g(b))(32)/2+i
Try it online!
This is designed ...
- 188k
11
votes
10
votes
10
votes
Sums of sum of divisors in sublinear time
Ruby, 55 52 bytes
Formula is adapted from this math.SE question. Runs in \$\mathcal{O}(\sqrt{n})\$.
-3 bytes thanks to @dingledooper.
...
- 58k
9
votes
Binning in time
R, 48 bytes
function(n,s)table(cut(n,0:ceiling(max(n)/s)*s))
Try it online!
Once again, table and ...
- 28.1k
9
votes
Project Euler 1: Multiples in constant time
Jelly, 20 bytes
+Ø.÷€AĊc2ḋIɓN;æl¥ƒ-Ḋ
Try it online!
Port of my own APL answer. Trailing ɓ chain trick is indeed strong :P
How ...
- 73.8k
9
votes
Next Special String
Python, 91 bytes (@tsh)
f=lambda s,j=0:f(max(s,f"{int(s[:j]+s[:-j]or s,2)+1:0{len(s)}b}"),j+1)if s[j:]else(s<"1")*s
Attempt This Online!
Previous Python, 98 bytes
f=lambda s,j=0:...
- 16k
9
votes
Maximum of outer product of integer vectors (in linear time)
JavaScript (Node.js), 84 bytes
f=([a,...x],m=1,n=1)=>a?f(x,Math.min(...q=a.flatMap(c=>[c*m,c*n])),Math.max(...q)):n
Try it online!
Keep trace of min and max
- 20.3k
9
votes
Generate a permutation from the high-water marks
Nibbles, 5 bytes
.,@?:-,_@@
Attempt This Online!
Puts the \$k\$ highest numbers at the specified indices in ascending order and the remaining numbers at the ...
- 7,161
9
votes
Sums of sum of divisors in sublinear time
Python 2, 58 bytes
Runs in \$ \mathcal{O}(\sqrt{n}) \$ time.
f=lambda n,i=1:~i*i*(n/-~i-n/i)/2+(i<n and f(n,n/(n/-~i)))
Try it online!
Explanation
Note: @Neil'...
- 22.3k
8
votes
Accepted
A classic sorting code-golf question
Haskell, 87 80 89
s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])
This is merge sort, implemented from the bottom up.
...
- 6,151
8
votes
Circular Limited Sums
Python with numpy, 59 bytes
lambda M,N:trace(mat(tri(M+1)[::-1])**N)
from numpy import*
Try it online!
Uses matrix multiplication to count paths. If float ...
- 144k
8
votes
Give a permutation with no two consecutive integers next to each other
Python 3, 40, 38 bytes
lambda n:[*range(1,n,2),*range(0,n,2)]
Try it online!
This runs in O(n) time.
Thanks to Dennis for ...
- 58.9k
8
votes
8
votes
Project Euler 1: Multiples in constant time
APL (Dyalog Extended), 31 bytes
-/+/(⎕+⍳2)(⊢×2!⌈⍤|⍤÷)\∊(⊢,∧)\-⎕
Try it online!
Full program which takes the list of divisors, and then the ...
- 73.8k
8
votes
An Scalable Event Scheduler That Can Handle Billions of Events
Proof that this challenge is impossible without extra assumptions
I'm assuming here that we can't take advantage of the fact that the range of a Time is limited, ...
8
votes
Compute cumulative means efficiently
APL(Dyalog Unicode), 19 20 bytes SBCS
Added 1 byte to fix handling of trailing integers.
(⌈¯2-/⌊,⊢/)⊢⍤/+\÷⍳⍤≢
Try it on APLgolf!
...
- 58k
7
votes
Accepted
Maximise the squared difference
Jelly, 24 21 15 14 10 9 bytes
RUĖµ«/€ị"
To compute the total squared difference, append µ_ṙ1$²S to the code. Try it online!
...
- 210k
7
votes
Accepted
Symmetric boolean functions as Zhegalkin polynomials
Dyalog APL, 15 bytes
{2|⍺⌹⍉∘.!⍨0,⍳⍵}
Matrix division, basically. Takes input like 0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4 for T4({2,3,4}).
<...
- 21.4k
Only top scored, non community-wiki answers of a minimum length are eligible