45

Python 2, 323 319 bytes exec u"def I(s,a,b=1j):c,d=s;d-=c;c-=a;e=(d*bX;return e*(0<=(b*cX*e<=e*e)and[a+(d*cX*b/e]or[]\nE=lambda p:zip(p,p[1:]+p);S=sorted;P=E(input());print sum((t-b)*(r-l)/2Fl,r@E(S(i.realFa,b@PFe@PFi@I(e,a,b-a)))[:-1]Fb,t@E(S(((i+j)XFe@PFi@I(e,l)Fj@I(e,r)))[::2])".translate({70:u" for ",64:u" in ",88:u".conjugate()).imag"}) Takes a ...


42

Python 2, 98 97 91 84 bytes s=input();L=1 for _ in`s`*8:s+=1098*int(str(s).translate('0011'*64));L*=10 print s%L This does I/O in decimal. The integers have to be separated by the non-alphanumeric character +. Thanks to @xnor for golfing off 2 bytes! Try it on Ideone. How it works In Arithmetic in Complex Bases, the author shows how to add and multiply ...


34

Python 2 + sympy, 72 bytes from sympy import* n=sqrt(5) print'7'+`((.5+n/2)**1e9/n).evalf(1e3)`[2:] Try it online! -10 bytes by removing the practically-0 term thanks to Jeff Dege -1 byte (1000 -> 1e3 thanks to Zacharý) -2 bytes by removing the unnecessary variable thanks to Erik the Outgolfer -2 bytes by moving to Python 2 thanks to Zacharý -3 bytes by ...


28

Mathematica, 79 bytes Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉& Explanation I couldn't be bothered to implement the algorithm in the challenge, so I wanted to look for a shortcut to the solution. While I found one, unfortunately it doesn't beat the Mathematica answer that does implement the algorithm. That said, I'm sure ...


28

Python 2, 106 bytes a,b=0,1 for c in bin(10**9): a,b=2*a*b-a*a,a*a+b*b if'1'==c:a,b=b,a+b while a>>3340:a/=10;b/=10 print a Try it online! No libraries, just integer arithmetic. Runs almost instantly. The core is the divide-and-conquer identity: f(2*n) = 2*f(n)*f(n+1) - f(n)^2 f(2*n+1) = f(n)^2 + f(n+1)^2 This lets us update (a,b) = (f(n),f(...


27

x86 32-bit machine code (with Linux system calls): 106 105 bytes changelog: saved a byte in the fast version because an off-by-one constant doesn't change the result for Fib(1G). Or 102 bytes for an 18% slower (on Skylake) version (using mov/sub/cmc instead of lea/cmp in the inner loop, to generate carry-out and wrapping at 10**9 instead of 2**32). Or 101 ...


22

Jelly, 7 6 bytes ;_/!:/ Look ma, no Unicode! This program takes a single list as input, with n at its first index. Try it online! or verify all test cases at once. How it works ;_/!:/ Input: A (list) _/ Reduce A by subtraction. This subtracts all other elements from the first. ; Concatenate A with the result to the right. ! Apply ...


21

Haskell, 83 61 bytes p(a,b)(c,d)=(a*d+b*c-a*c,a*c+b*d) t g=g.g.g t(t$t=<<t.p)(1,1) Outputs (F1000000000,F1000000001). On my laptop, it correctly prints the left paren and the first 1000 digits within 133 seconds, using 1.35 GiB of memory. How it works The Fibonacci recurrence can be solved using matrix exponentiation: [Fi − 1, Fi; Fi, Fi + 1] = [...


20

CJam (56 bytes) q~4@:Nm*:$_&{:+1$\-N),&},f{1$1$:+-\0-:(_e`0f=+++:m!:/}:+ Online demo This is an optimised version of the reference implementation I wrote for the sandbox. Note: I use N in the code because in a Real Combinatorics Question™ the parameters are \$n\$ and \$k\$, not m and n, but I'll use \$M\$ and \$N\$ in the explanation to ...


20

JavaScript (Node.js),  578 ... 433  431 bytes f=(n,T=[B=[N=0,0,0,1,1]])=>!n||T.some(([x,y,q,m])=>B.some((p,d)=>m>>d&1&&((p=x+~-s[d],q=y+~-s[d+2],t=T.find(([X,Y])=>X==p&Y==q))?(q=t[3])&(p=D[d*3+t[4]])^p?t[f(n,T,t[3]|=p),3]=q:0:[0,1,2].map(t=>f(n-1,[...T,[p,q,-p-q,D[d*3+t],t]])))),s="2100122",D=Buffer("160).(...


18

88 Cities, 341 seconds runtime on NEOS In a recent paper we constructed a family of hard to solve euclidean TSP instances. You can download the instances from this family as well as code for generating them here: http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html The 88 city instance from this family takes Concorde on the NEOS server more than ...


16

Rust, 929 923 characters use std::io;use std::str::FromStr;static C:&'static [i32]=&[-2,-1,2,5,10,15];fn main(){let mut z=String::new();io::stdin().read_line(&mut z).unwrap();let n=(&z.trim()[..]).split(' ').map(|e|i32::from_str(e).unwrap()).collect::<Vec<i32>>();let l=*n.iter().min().unwrap();let x=n.iter().max().unwrap()-if l&...


16

Python 3, 443 158 155 154 134 131 128 124 117 116 115 bytes c=d=C=D=0 for e in input():v='[<>,.-+]'.find(e);d=d*8+v;c+=c<0<6<v;c-=d>1>v;C,D=(c,C+1,d,D)[v>6::2] print(-~D*8**C) Several bytes thanks to Sp3000 and Mitch Schwartz :D How this works: This maps all valid BF programs into all possible, valid or invalid, BF programs, that ...


16

Pyth, 34 bytes _shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ Try it online: Demonstration or Test Suite (takes quite a while). It should satisfy the time restriction though easily, since the online compiler is quite slow in comparison with the normal (offline) compiler. Explanation: My algorithm is basically an implementation of addition with carrying. But instead ...


16

Pyth, 24 bytes L-b*/bJ+3^T11Jy*uy^GT11Q Test suite This uses the fact that a^(p-2) mod p = a^-1 mod p. First, I manually reimplement modulus, for the specific case of mod 100000000003. I use the formula a mod b = a - (a/b)*b, where / is floored division. I generate the modulus with 10^11 + 3, using the code +3^T11, then save it in J, then use this and ...


16

JavaScript (ES7),  59 ... 44  43 bytes Saved 1 byte thanks to Titus Expected input: 1-indexed. n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n Initially inspired by a formula for A004738, which is a similar sequence. But I ended up rewriting it entirely. Test cases let f= n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n console.log(f(1)) // -&...


15

sed, 339 338 bytes I know this is an old one, but I was browsing and this piqued my interest. Enough to actually register as a user! I guess I was swayed by "I would quite like to see a full sed solution – Nathaniel"... s/[1-9]/0&/g s/[5-9]/4&/g y/8/4/ s/9/4&/g s/4/22/g s/[37]/2x/g s/[26]/xx/g s/[1-9]/x/g :o s/\( .*\)0$/0\1/ /x$/{ x G s/ .*/\...


15

Raku, 14 12 11 bytes 0+|*/.98334 Try it online! Since we know the bounds of the input, we can substitute a constant operation and a floor on the input in base 60. That number by the way is around 1358/1381, which is the maximum the input differs from the output in base 60. There may be a smaller constant, or at least a smaller way to represent it. For ...


14

MATL, 2 bytes :p Explained: : % generate list 1,2,3,...,i, where i is an implicit input p % calculate the product of of all the list entries (works on an empty list too) Try it online!


14

Mornington Crescent, 1827 1698 chars I felt like learning a new language today, and this is what I landed on... (Why do I do this to myself?) This entry won't be winning any prizes, but it beats all 0 other answers so far using the same language! Take Northern Line to Bank Take Central Line to Holborn Take Piccadilly Line to Heathrow Terminals 1, 2, 3 Take ...


14

Mathematica, 247 225 222 p=Partition[#,2,1,1]&;{a_,b_}~r~{c_,d_}=Det/@{{a-c,c-d},{a,c}-b}/Det@{a-b,c-d};f=Abs@Tr@MapIndexed[Det@#(-1)^Tr@#2&,p[Join@@MapThread[{1-#,#}&/@#.#2&,{Sort/@Cases[{s_,t_}/;0<=s<=1&&0<=t<=1:>s]/@Outer[r,#,#,1],#}]&@p@#]]/2& First add the points of intersection to the polygon, then ...


13

Python 2, 157 bytes def f(s,o=0,d=0,D={}):T=s,o,d;x=D[T]=D[T]if T in D else~o and 0**o+sum(f(s[1:],cmp(c,"[")%-3-~o,d or cmp(c,s[0]))for c in"+,-.<>[]")if s else~d<0==o;return+x Still looks pretty golfable, but I'm posting this for now. It uses recursion with a bit of caching. Annoyingly, D.get doesn't short circuit for the caching, so I can't ...


13

APL (Dyalog Unicode), 193 bytes {G←{⍵⊃⍨⊃⍋(+/' '=,)¨⍵} G{s←,30-⍳,⍨61 G,⊢∘⊂⌺30 30⊢((≢a)/⍪' '~⍨,x)@(B∘.+a)⊢''⍴⍨(⍴b)+⊃⌈/a←(⊢-⌊/)(⊃+/)¨s×⊂⍵}¨o/⍨(⍱/X∊⍨+/,-/)¨o←,∘.,⍨⊂¨∪{⍵/⍨0<2⊥¨×⍵}(,B∘.-⍸b<(1∊⊢)⌺3 3⊢b)~X←,B∘.-B←⍸b←(⍉0,⌽)⍣4⊢' '≠x←⍵} Try it online! A monadic dfn that takes a matrix of characters and returns the 30-by-30 matrix of a possible tiling with ...


13

Jelly, 29 28 26 24 21 20 bytes DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ This does I/O in decimal. The integers have to be separated by the non-alphanumeric character +. Try it online! or verify all test cases. Background In Arithmetic in Complex Bases, the author shows how to add and multiply complex numbers in bases of the form -n + i. For base -1 + i, addition is done ...


13

Python 2, 69 67 bytes f=lambda a,b:a*a+b*b^58and 2*f(a*b%2*6,f(a/2,b/2))|a+b&1if a else b I/O is done with base 2 integers. -2 thanks @Dennis.


13

Pyth, 16 15 bytes f-1m.^T/tQdQPtQ Test suite If p is the input, we know that g^(p-1) = 1 mod p, so we just need to check that g^a != 1 mod p for any smaller a. But a must be a factor of p-1 for that to be possible, and any multiple of an a with that property will also have that property, so we only need to check that g^((p-1)/q) != 1 mod p for all prime ...


13

Python 2, 275 271 264 249 bytes Saved four bytes by replacing -1 with H and removing one slicing operation ([:]). Saved seven bytes thanks to Halvard Hummel; removing yet another slicing operation ([:]), using multiple-target assignment to give a visited entry a value v not in "01" (S=S[1:];M[y][x]=H; -> S=M[y][x]=S[1:];) and switching from a ternary if/...


12

SageMath, 31 Bytes N=input() print N,"=",factor(N) Test case: 83891573479027823458394579234582347590825792034579235923475902312344444 Outputs: 83891573479027823458394579234582347590825792034579235923475902312344444 = 2^2 * 3^2 * 89395597 * 98966790508447596609239 * 263396636003096040031295425789508274613


12

Javascript ES6, 738 bytes ((V,C,L,r,k,n,A,G,F,e,i,j,q)=>p=>{p=p.map((p,i)=>({i:i,x:p[0],y:p[1]}));A=(f,p,a,b,v,i)=>{for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))return 1};G=(p,i,a)=>{for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=(p,s,l,f,a,b,v)=>(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A((a,b)=>C(a,b)?0:a.x&...


12

Retina, 100 bytes r+`(.*)(\d|(?!\4))( .*)(.?) $2$4:$1$3 T` 0 +`1:11(1*:1*)11 :$1 ^:* ::: }`:(1*:1*:)11 1:1$1 (1)*: $#1 This takes the input separated with a comma. The output always starts with three leading zeroes. Try it online! I really wonder if there's a shorter solution for the first stage...


Only top voted, non community-wiki answers of a minimum length are eligible