Lua 444 Chars
Works for the example on the wiki page
3
2 1942
4 3402
5 4414
But somehow does not work for the examples here on this page. If anyone can find the error?
Non-golfed version:
-- Reconstruct shamir secret
-- convention, poly = {[0]=a0,a1,...,an}
i=io.read
f=math.fmod
w=1928049029
k=i():match"%d+"
x={} -- Will contain X values
y={} -- Will contain Y values
p={} -- will contain lagrange polynomials
-- Read data
for j=0,k-1 do
x[j],y[j]=i():match("(%d+) (%d+)")
print(j,x[j],y[j])
end
-- Multiplication and scaling function
function mul(p,q,s)
-- multiply polies
r={} -- poly to be returned
for k=0,#p do
for l=0,#q do
r[l+k]=r[l+k] or 0 -- if the coeff for degree l+k of x doesn't exist, put 0
p[k]=p[k] or 0 -- if p hasn't got a coeff for x^k
q[l]=q[l] or 0 -- idem for q
r[l+k]=(r[l+k]+s*p[k]*q[l]%w -- calculate increment for coeff for x^(l+k)
end
end
-- Debugging
io.write"Multiplied "
printPoly(p)
io.write"With "
printPoly(q)
io.write("And scaling factor ",tostring(s),"\n")
io.write"Yielding "
printPoly(r)
return r
end
function printPoly(p) -- "Pretty" printing of the polynomial
for k=#p,1,-1 do
io.write(tostring(p[k] or 0),"x^",tostring(k),"+")
end
io.write(p[0])
io.write"\n"
end
function egcd(a,b)
if a == 0 then
return b, 0, 1
else
local g, y, x = egcd(b % a, a)
return g, x - math.floor(b / a) * y, y
end
end
function inv(a,m)
a=a>=0 and a or a+m
local g,x,y = egcd(a,m)
if g== 1 then
return x%m
else
print(a,"has no inverse mod",m)
end
end
-- generate lagrange polynomials
for j=0,#x do
print("j=",j,"*********")
for m=0,k-1 do
if m~=j then -- if m==j, continue
p[j]=p[j]or{[0]=1} -- if this poly doesn't exist, take 1
p[j]=mul( p[j], {[0]=-x[m],1},inv(x[j]-x[m],w))-- multiply with (x-x_m)/(x_j-x_m)
io.write"---------------------------------\n"
end
end
end
r=0 -- Result for x^0
for k=0,#p do
print("l_"..k)
printPoly(p[k]) -- print l_k
r=r+f(y[k]*p[k][0],w) -- add coeff for x^0 to result
end
print("Secret was",f(r,w)) -- display result
Golfed (not using finite field), 444 chars:
i=io.read f=math.fmod w=1928049029 k=i():match"%d+"x={}y={}p={}for j=0,k-1 do x[j],y[j]=i():match("(%d+) (%d+)")end
function mul(p,q,s)r={}for k=0,#p do for l=0,#q do r[l+k]=r[l+k]or 0 p[k]=p[k]or 0 q[l]=q[l]or 0 r[l+k]=f(r[l+k]+s*p[k]*q[l],w)end end return r end
for j=0,#x do for m=0,k-1 do if m~=j then p[j]=p[j]or{[0]=1}p[j]=mul(p[j],{[0]=-x[m],1},1/(x[j]-x[m]))end end end r=0 for k=0,#p do r=r+f(y[k]*p[k][0],w)end
print(f(r,w))
Nice! I never expected to see a bash answer to this problem. +1 – Juan – 2011-03-05T18:58:54.300
@Juan, I started doing it in Perl, and got fed up with having to force it to do integer division rather than float. And I know bash better anyway, so it involves less beating of head against wall. – Peter Taylor – 2011-03-05T20:35:00.570