| Bytes | Lang | Time | Link |
|---|---|---|---|
| 164 | APLNARS | 250120T214428Z | Rosario |
| 460 | Axiom | 170827T152956Z | user5898 |
| nan | 150620T170150Z | Abr001am | |
| 092 | Pyth | 150619T215713Z | Jakube |
APL(NARS), 164 chars
{(a b n)←⍵⋄(g x y)←{(u v)←⍵⋄v=0:u,1,0⋄(g x y)←∇v,v∣u⋄g,y,x-y×⌊u÷v}a b⋄0≠g∣n:,0⋄h←(⌊¯3+a÷⍨y×m)⌊∣⌊b÷⍨x×m←n÷g⋄0=≢z←z/⍨×/¨0≤¨z←((b×h..h+10)+x×m),¨(-a×h..h+10)+y×m:,0⋄z}
If a solution exist, it from the ten integer (positive and negative) x,y solution of ax+by=n search some solution where both x>0 and y>0 and return those in one array of array. If no solution it is find, it return ,0.
The problem is center the interval in the way it gets all both positive solution, and return only them
because find one solution in the integers positive and negative, is more easy:
{(a b n)←⍵⋄(g x y)←{(u v)←⍵⋄v=0:u,1,0⋄(g x y)←∇v,v∣u⋄g,y,x-y×⌊u÷v}a b⋄0≠g∣n:0⋄(x×n÷g),y×n÷g}
test:
q←{(a b n)←⍵⋄(g x y)←{(u v)←⍵⋄v=0:u,1,0⋄(g x y)←∇v,v∣u⋄g,y,x-y×⌊u÷v}a b⋄0≠g∣n:,0⋄h←(⌊¯3+a÷⍨y×m)⌊∣⌊b÷⍨x×m←n÷g⋄0=≢z←z/⍨×/¨0≤¨z←((b×h..h+10)+x×m),¨(-a×h..h+10)+y×m:,0⋄z}
q 99 78 1
0
q 99 78 3
0
q ¯2 3 11
2 5 5 7 8 9 11 11 14 13
q 3 ¯2 11
11 11 9 8 7 5 5 2
q 2 3 11
1 3 4 1
q 3 2 11
1 4 3 1
q 1152921504606846883x ¯576460752303423433x 1x
1865020080981664048 3730040161963328151 1288559328678240615 2577118657356481268 712098576374817182 1424197152749634385 135637824071393749 271275648142787502
q ¯1152921504606846883x 576460752303423433x 1x
440822928232029684 881645856464059381 1017283680535453117 2034567361070906264 1593744432838876550 3187488865677753147 2170205185142299983 4340410370284600030 2746665937445723416 5493331874891446913 3323126689749146849 6646253379498293796 3899587442052570282 7799174884105140679
Axiom, 460 bytes
w(a,b,x,u)==(a=0=>[b,x];w(b rem a,a,u,x-u*(b quo a)))
d(a,b,k)==(o:List List INT:=[];a=0 and b=0=>(k=0=>[1,1];[]);a=0=>(k=0=>[[1,0]];k rem b=0=>[1,k quo b];[]);b=0=>(k=0=>[[0,1]];k rem a=0=>[k quo a,1];[]);r:=w(a,b,0,1);q:=k quo r.1;(y,x,u,v):=(q*(r.1-r.2*a)quo b,q*r.2,b quo r.1,a quo r.1);m:=min(80,4+abs(k)quo min(abs(a),abs(b)));l:=y quo v;x:=x+l*u;y:=y-l*v;for n in -m..m repeat(t:=x+n*u;z:=y-n*v;t>=0 and z>=0 and t*a+z*b=k=>(o:=cons([t,z],o)));sort(o))
ungolf and some test
-- input a b and k for equation a*x+b*y=k
-- result one List of List of elments [x,y] of solution of
-- that equation with x and y NNI (not negative integers)
-- or Void list [] for no solution
diopanto(a,b,k)==
o:List List INT:=[]
a=0 and b=0=>(k=0=>[1,1];[])
a=0=>(k=0=>[[1,0]];k rem b=0=>[1,k quo b];[])
b=0=>(k=0=>[[0,1]];k rem a=0=>[k quo a,1];[])
r:=w(a,b,0,1)
q:=k quo r.1
(y,x,u,v):=(q*(r.1-r.2*a)quo b,q*r.2,b quo r.1,a quo r.1)
m:=min(80,4+abs(k)quo min(abs(a),abs(b)))
l:=y quo v -- center the interval
x:=x+l*u; y:=y-l*v
for n in -m..m repeat
t:=x+n*u;z:=y-n*v
t>=0 and z>=0 and t*a+z*b=k=>(o:=cons([t,z],o))
sort(o)
------------------------------------------------------
(4) -> d(0,-9,0)
(4) [[1,0]]
Type: List List Integer
(5) -> d(2,3,11)
(5) [[4,1],[1,3]]
Type: List List Integer
(6) -> d(2,3,2)
(6) [[1,0]]
Type: List List Integer
(7) -> d(2,3,1)
(7) []
Type: List List Integer
(8) -> d(1152921504606846883,-576460752303423433,1)
(8)
[[135637824071393749,271275648142787502],
[712098576374817182,1424197152749634385],
[1288559328678240615,2577118657356481268],
[1865020080981664048,3730040161963328151],
[2441480833285087481,4882961666570175034]]
Type: List List Integer
In the other 'solutions' possible there was a bug because it tried to save the infinite solutions in one List; now it is imposed the limit of 80 solutions max
- after Dennis' remarks, that made my previous idea upside-down, i had to change the code from its roots and it took me long term debugging, and cost me twice n° of bytes :'(.
Matlab (660)
a=input('');b=input('');c=input('');if((min(a*c,b*c)>c*c)&&a*c>0&&b*c>0)||(a*c<0&&b*c<0),-1,return,end,g=abs(gcd(a,b));c=c/g;a=a/g;b=b/g;if(c~=floor(c)),-1,return,end,if(c/a==floor(c/a)&&c/a>0),e=c/a-b;if(e>0),e,a,return,else,c/a,0,return,end,end,if(c/b==floor(c/b)&&c/b>0),e=c/b-a;if(e>0),b,e,return,else,0,c/b,return,end,end,f=max(abs(a),abs(b));if f==abs(a),f=b;b=a;a=f;g=0.5;end,e=(c-b)/a;f=(c-2*b)/a;if(e<0&&f<e),-1,elseif(e<0&&f>e),for(i=abs(c*a):abs((c+1)*a)),e=(c-i*b);if(mod(e,a)==0)if(g==0.5),i,e/a;else,e/a,i,end,return,end,end,else for(i=1:abs(a)),e=(c-i*b);if(e/a<0),-1,elseif(mod(e,a)==0),if(g==0.5),i,e/a,else,e/a,i,end,return,end,end,end,-1
- Well , i know its not golfed, since that type of languages isnt adapted for code length reduction, but, i can ensure that time-complexity is at its best.
Explanation:
the code takes three invariants a,b,c as input, these last ones are subdued to couple of conditions before proceeding to calculate:
1- if (a+b>c) and (a,b,c>0) no solution!
2- if (a+b < c) ,(a,b,c<0) no solution!
3- if (a, b) have common opposite signs of c : no solution!
4- if GCD(a,b) dosnt divide c, then no solution again! , otherwise, divide all variants by GCD.
after this , we have to check another condition out, it should ease and shorteb the way to desired solution.
5- if c divide a or b , solution s= (x or y)=(c-[ax,yb])/[b,a]=C/[b,a]+[ax,yb]/[b,a]=S+[ax,yb]/[b,a] where S is natural so ax/b or by/a would have henceforth non-negative direct solutions which are respectively x=b or y=a . (notice that solutions can be just nil values in case previous arbitrary solutions are revealed negatives)
when the program reaches this stage, a narrower range of solutions for x=(c-yb)/a is swept instead, thanks to congruence, of sweeping larger ranges of numbers ,which is come accross repetitively by regular cycles. the largest search field is [x-a,x+a] where a is the divisor.
TRY IT
Pyth, 92 bytes
I!%vzhK%2u?sm,ed-hd*ed/F<G2cG2@G1G+~Q,hQ_eQj9 2)J*L/vzhKtKeoSNm-VJ/RhK_*LdQsm+LdtM3/V*LhK_JQ
It's quite a monster.
Try it online: Demonstration. The input format is c\n[a,b] and the output format is [x,y].
In the case that no integer solution exists, I'll print nothing, and in the case that no natural integer solution exists, I'll simply print a random integer solution.
Explanation (Rough Overview)
At first I'll find an integer solution to the equation
ax + by = gcd(a,b)by using the Extended Euclidean algorithm.Then I'll modify the solution (my multiplying
aandbwithc/gcd(a,b)) to get an integer solution ofax + by = c. This works, ifc/gcd(a,b)is an integer. Otherwise there doesn't exist a solution.All the other integer solutions have the form
a(x+n*b/d) + b(y-n*a/d) = cwithd = gcd(a,b)for integern. Using the two inequalitiesx+n*b/d >= 0andy-n*a/d >= 0I can determine 6 possible values forn. I'll try all 6 of them and print the solution with the highest lowest coefficient.
Explanation (Detailed)
The first step is to find an integer solution to the equation ax' + by' = gcd(a,b). This can be done by using the extended Euclidean algorithm. You can get an idea on how it works at Wikipedia. The only difference is, that instead of using 3 columns (r_i s_i t_i) I'll use 6 columns (r_i-1 r_i s_i-1 s_i t_i-1 t_i). This way I don't have to keep the last two rows in memory, only the last one.
K%2u?sm,ed-hd*ed/F<G2cG2@G1G+~Q,hQ_eQj9 2) implicit: Q = [a,b] (from input)
j9 2 convert 9 to base 2: [1,0,0,1]
+ Q add to Q => [a,b,1,0,0,1]
this is the initial row
u ) start with G = ^ and update G repeatedly
by the following expression, until
the value of G doesn't change anymore
? @G1 if G[1] != 0:
cG2 split G into parts of 2
m map the parts d to:
, the pair
ed d[1]
-hd*ed/F<G2 d[0]-d[1]*G[0]/G[1]
s unfold
else:
G G (don't change it, stop criterion for u)
%2 take every second element
we get the list [gcd(a,b),x',y']
K store this list in K
~Q,hQ_eQ afterwards change Q to [Q[0],-Q[1]] = [a,-b]
This will be important for the other parts.
Now I want to find a solution to ax + by = c. This is possible only, when c mod gcd(a,b) == 0. If this equation is satisfied, I simply multiplying x',y' with c/gcd(a,b).
I!%vzhK...J*L/vzhKtK implicit: z = c in string format (from input)
%vzhK evaluated(z) mod K[0] (=gcd(a,b))
I! if not ^ than:
/vzhK c/K[0]
*L tK multipy ^ to each element in K[1:] (=[x',y'])
J and store the result in J, this is now [x,y]
We have an integer solution for ax + by = c. Notice, that x, y or both may be negative. So our goal is to transform these to non-negative.
The nice thing about Diophantine equations is, that we can describe all solution using only one initial solution. If (x,y) is a solution, that all other solutions are of the form (x-n*b/gcd(a,b),y+n*a/gcd(a,b)) for n integer.
Therefore we want to find a n, where x-n*b/gcd(a,b) >= 0 and y+n*a/gcd(a,b >= 0. After some transformation we end up with the two inequalities n >= -x*gcd(a,b)/b and n >= y*gcd(a,b)/a. Notice that the inequality symbol might look in the other direction due the division with a potential negative a or b. I don't care that much about it, I simply say that one number of -x*gcd(a,b)/b - 1, -x*gcd(a,b)/b, -x*gcd(a,b)/b + 1 definitly satisfies inequality 1, and one number of y*gcd(a,b)/a - 1, y*gcd(a,b)/a, y*gcd(a,b)/a + 1 satisfies inequality 2. It there is a n, that satisfies both inequalities, one of the 6 numbers also does.
Then I calculate the new solutions (x-n*b/gcd(a,b),y+n*a/gcd(a,b)) for all 6 possible values of n. And I print the solution with the highest lowest value.
eoSNm-VJ/RhK_*LdQsm+LdtM3/V*LhK_JQ
_J reverse J => [y,x]
*LhK multiply each value with K[0] => [y*gcd,x*gcd]
/V Q vectorized division => [y*gcd/a,-x*gcd/b]
m map each d of ^ to:
tM3 [-1,0,1]
+Ld add d to each ^
s unfold
these are the possible values for n
m map each d (actually n) of ^ to:
*LdQ multiply d to Q => [a*n,-b*n]
_ reverse => [-b*n,a*n]
/RhK divide by K[0] => [-b*n/gcd,a*n/gcd]
-VJ vectorized subtraction with J
=> [x+b*n/gcd,y-a*n/gcd]
oSN order the solutions by their sorted order
e print the last one
The sort by their sorted order thing works the following way. I'm using the example 2x + 3y = 11
I sort each of the 6 solutions (this are called keys), and sort the original solutions by their keys:
solutions: [1, 3], [4, 1], [7, -1], [-5, 7], [-2, 5], [1, 3]
keys: [1, 3], [1, 4], [-1, 7], [-5, 7], [-2, 5], [1, 3]
sort by key:
solutions: [-5, 7], [-2, 5], [7, -1], [1, 3], [1, 3], [4, 1]
keys: [-5, 7], [-2, 5], [-1, 7], [1, 3], [1, 3], [1, 4]
This sorts a complete non-negative solution to the end (if there is any).