Undo the square roots

Question

Your job is to convert decimals back into the sum of the square roots of integers. The result has to have an accuracy of at least 6 significant decimal digits.

Input:

A number indicating the number of square roots and a decimal indicating the number to approximate.

Example input:

2 3.414213562373095

Output: Integers separated by spaces that, when square rooted and added, are approximately the original decimal accurate to at least 6 significant decimal digits.

Zeros are not allowed in the solution.

If there are multiple solutions, you only have to print one.

Example output (in any order):

4 2

This works because Math.sqrt(4) + Math.sqrt(2) == 3.414213562373095.

This is code golf. Shortest code (with optional bonus) wins!

There is always going to be a solution but -10 if your program prints "No" when there is no solution with integers. In addition, -10 if your program prints all solutions (separated by newlines or semicolons or whatever) instead of just one.

Test cases:

3 7.923668178593959 --> 6 7 8
2 2.8284271247461903 --> 2 2
5 5.0 --> 1 1 1 1 1
5 13.0 --> 4 4 9 9 9 --> 81 1 1 1 1 --> 36 9 4 1 1 etc. [print any, but print all for the "all solutions bonus"]

And yes, your program has to finish in finite time using finite memory on any reasonable machine. It can't just work "in theory," you have to be able to actually test it.

Answer 1

Python 3, 90 - 10 = 80

def S(N,x,n=[],i=1):
 if x*x<1e-12>N==0:print(*n)
 while.1+x*x>i:S(N-1,x-i**.5,n+[i]);i+=1

(Mega thanks to @xnor for tips, especially the restructuring of the for loop into a while)

A simple recursive attempt. It starts off with the target number and continuously subtracts square roots until it hits 0 or lower. The function S can be called like S(2,3.414213562373095) (the second argument is assumed to be positive).

The program doesn't just print out all solutions, it prints out all permutations of solutions (a little extraneous, I know). Here's the output for the last case: Pastebin.

A slight tweak gives a 98 - 10 = 88 solution which doesn't print permutations, making it more efficient:

def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x<1e-12>N==0:print(*n)
 while.1+x*x>i:S(N-1,x-i**.5,n+[i]);i+=1

And just for fun, this 99 - 10 = 89 one is about as efficient as it gets (unlike the others, it doesn't blow the stack on S(1,1000):

def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x<1e-12>N:print(*n)
 while(.1+x*x>i)*N:S(N-1,x-i**.5,n+[i]);i+=1

Note that, although we have a mutable default argument, this never causes a problem if we rerun the function since n+[i] creates a new list.

---

Proof of correctness

In order to end up in an infinite loop, we must hit some point where x < 0 and 0.1 + x² > 1. This is satisfied by x < -0.948....

But note that we start from positive x and x is always decreasing, so in order to hit x < -0.948... we must have had x' - i^0.5 < -0.948... for some x' > -0.948... before x and positive integer i. For the while loop to run, we must also have had 0.1 + x'² > i.

Rearranging we get x'² + 1.897x' + 0.948 < i < 0.1 + x'², the outer parts implying that x' < -0.447. But if -0.948 < x' < -0.447, then no positive integer i can fit the gap in the above inequality.

Hence we'll never end up in an infinite loop.

Answer 2

ECLiPSe Prolog - 118 (138-20)

I used the following implementation of Prolog: http://eclipseclp.org/

:-lib(util).
t(0,S,[]):-!,S<0.00001,S> -0.00001.
t(N,S,[X|Y]):-A is integer(ceiling(S*S)),between(1,A,X),M is N-1,T is S-sqrt(X),t(M,T,Y).

This is a very naive, exponential approach. Listing all possible solutions takes time to cover all combinations (edit: the range of visited integers now decreases at each step, which removes a lot of useless combinations).

Here follows a transcript of a test session. By default, the environment will try to find all possible solutions (-10) and prints "No" when it fails to do so (-10).

As Sp3000 properly noted in the comment, it also prints "Yes" when it succeeds. That surely means I can remove 10 more points ;-)

[eclipse 19]: t(1,0.5,R).

No (0.00s cpu)
[eclipse 20]: t(2,3.414213562373095,R).

R = [2, 4]
Yes (0.00s cpu, solution 1, maybe more) ? ;

R = [4, 2]
Yes (0.00s cpu, solution 2, maybe more) ? ;

No (0.01s cpu)
[eclipse 21]: t(3,7.923668178593959,R).

R = [6, 7, 8]
Yes (0.02s cpu, solution 1, maybe more) ? ;

R = [6, 8, 7]
Yes (0.02s cpu, solution 2, maybe more) ? ;

R = [7, 6, 8]
Yes (0.02s cpu, solution 3, maybe more) ? 
[eclipse 22]: t(5,5.0,R).

R = [1, 1, 1, 1, 1]
Yes (0.00s cpu, solution 1, maybe more) ? ;
^C

interruption: type a, b, c, e, or h for help : ? abort
Aborting execution ...
Abort
[eclipse 23]: t(5,13.0,R).

R = [1, 1, 1, 1, 81]
Yes (0.00s cpu, solution 1, maybe more) ? ;

R = [1, 1, 1, 4, 64]
Yes (0.00s cpu, solution 2, maybe more) ? ;

R = [1, 1, 1, 9, 49]
Yes (0.00s cpu, solution 3, maybe more) ?
[eclipse 24]:

---

(Edit) Regarding performance, it is quite good, at least compared to other ones (see for example this comment from FryAmTheEggman). First, if you want to print all results, add the following predicate:

    p(N,S):-t(N,S,L),write(L),fail.
    p(_,_).

See http://pastebin.com/ugjfEHpw for the (5,13.0) case, which completes in 0.24 seconds and find 495 solutions (but maybe I am missing some solutions, I don't know).

Answer 3

Erlang, 305-10 302-10

f(M,D)->E=round(D*D),t(p(E,M,1),{M,E,D}).
p(_,0,A)->A;p(E,N,A)->p(E,N-1,A*E).
t(-1,_)->"No";t(I,{N,E,D}=T)->L=q(I,N,E,[]),V=lists:sum([math:sqrt(M)||M<-L])-D,if V*V<0.1e-9->lists:flatten([integer_to_list(J)++" "||J<-L]);true->t(I-1,T)end.
q(I,1,_,A)->[I+1|A];q(I,N,E,A)->q(I div E,N-1,E,[I rem E+1|A]).

This function returns string "No" or a string with values separated by spaces. It (inefficiently) processes every possible values encoding them into a large integer, and starting with higher values. 0 are not allowed in the solution, and encoded 0 represents all ones. Error is squared.

Example:

f(1,0.5).               % returns "No"
f(2,3.414213562373095). % returns "4 2 "
f(3,7.923668178593959). % returns "8 7 6 "
f(5,5.0).               % returns "1 1 1 1 1 "
f(5,13.0).              % returns "81 1 1 1 1 "

Please be patient with f(5,13.0) as function search space is 13^10. It can be made faster with 2 additional bytes.

Answer 4

Python 3 2: 173 159 - 10 = 149

Explanation: Each solution is of the form x_1 x_2 ... x_n with 1 <= x_1 <= x^2 where x is the target sum. Therefore we can encode each solution as an integer in base x^2. The while loop iterates over all (x^2)^n possibilities. Then I convert the integer back and test the sum. Pretty straight forward.

i=input;n=int(i());x=float(i());m=int(x*x);a=m**n
while a:
 s=[a/m**b%m+1for b in range(n)];a-=1
 if abs(x-sum(b**.5for b in s))<1e-5:print' '.join(map(str,s))

It finds all solutions, but the last test case takes way too long.

Answer 5

JavaScript (ES6) 162 (172 - 10) 173

Edit A little shorter, a little slower.

As a function with 2 parameters, output to javascript console. This prints all solutions with no repetitions (solutions tuples are generated already sorted).
I cared more about timing than about char count, so that it's easily tested in a browser console within the standard javascript time limit.

(Feb 2016 update) Current time for last test case: about 1 150 secs. Memory requirements: negligible.

F=(k,t,z=t- --k,r=[])=>{
  for(r[k]=z=z*z|0;r[k];)
  { 
    for(;k;)r[--k]=z;
    for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
    w*w<1e-12&&console.log(r.join(' '));
    for(--r[k];r[k]<1;)z=--r[++k];
  }
}

ES 5 Version Any browser

function F(k,t)
{
  var z=t- --k,r=[];  
  for(r[k]=z=z*z|0;r[k];)
  {
    for(;k;)r[--k]=z;
    for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
    w*w<1e-12&&console.log(r.join(' '));
    for(--r[k];r[k]<1;)z=--r[++k];
  }
}

Test Snippet it should run on any recent browser

F=(k,t)=>
{
   z=t- --k,r=[];
   for(r[k]=z=z*z|0;r[k];)
   { 
      for(;k;)r[--k]=z;
      for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
      w*w<1e-12&&console.log(r.join(' '));
      for(--r[k];r[k]<1;)z=--r[++k];
   }
}

console.log=x=>O.textContent+=x+'\n'

t=~new Date
console.log('\n2, 3.414213562373095')
F(2, 3.414213562373095)
console.log('\n5, 5')
F(5, 5)
console.log('\n3, 7.923668178593959')
F(3, 7.923668178593959)
console.log('\n5, 13')
F(5, 13)

t-=~new Date
O.textContent = 'Total time (ms) '+t+ '\n'+O.textContent

<pre id=O></pre>

(Edit) Below are the result on my PC when I posted this answer 15 months ago. I tried today and it is 100 times faster on the same PC, just with a 64 bit alpha version of Firefox (and Chrome lags well behind)! - current time with Firefox 40 Alpha 64 bit: ~2 sec, Chrome 48: ~29 sec

Output (on my PC - last number is runtime in milliseconds)

2 4
1 1 1 1 1
6 7 8
1 1 1 1 81
1 1 1 4 64
1 1 1 9 49
1 1 4 4 49
1 1 1 16 36
1 1 4 9 36
1 4 4 4 36
1 1 1 25 25
1 1 4 16 25
1 1 9 9 25
1 4 4 9 25
4 4 4 4 25
1 1 9 16 16
1 4 4 16 16
1 4 9 9 16
4 4 4 9 16
1 9 9 9 9
4 4 9 9 9
281889

Answer 6

Pyth 55 54 47-20 = 27

DgGHKf<^-Hsm^d.5T2^10_12^r1hh*HHGR?jbmjdkKK"No

Try it online.

Shamelessly borrows from xnor's comment ;)

This will run out of memory on any sane computer even for a value like 5,5.0. Defines a function, g, that can be called like g 3 7.923668178593959.

This python 3 program uses essentially the same algorithm (just doesn't do the "No" printing at the end, which could be done by assigning a variable to all the results, then writing print(K if K else "No")), but uses a generator, so it doesn't get a memory error (it will still take extremely long, but I've made it print as it finds the values):

This gave the exact same results that @Sp3000 got. Also, this took several days to finish (I didn't time it, but around 72 hours).

from itertools import*
def g(G,H):
    for x in product(range(1,int(H*H+2)),repeat=G):
        if (H-sum(map(lambda n:n**.5,x)))**2<1e-12:print(*x)

Answer 7

Mathematica - 76 - 20 = 56

f[n_,x_]:=Select[Union[Sort/@Range[x^2]~Tuples~{n}],Abs[Plus@@√#-x]<10^-12&]

Examples

f[2, 3.414213562373095]
> {{2, 4}}
f[3, 7.923668178593959]
> {{6, 7, 8}}
f[3, 12]
> {{1, 1, 100}, {1, 4, 81}, {1, 9, 64}, {1, 16, 49}, {1, 25, 36}, {4, 4, 64}, {4, 9, 49}, {4, 16, 36}, {4, 25, 25}, {9, 9, 36}, {9, 16, 25}, {16, 16, 16}}

Answer 8

Haskell, 87 80 - 10 = 70

This is a recursive algorithm similar to the Python 3 program of @Sp3000. It consists of an infix function # that returns a list of all permutations of all solutions.

0#n=[[]|n^2<0.1^12]
m#n=[k:v|k<-[1..round$n^2],v<-(m-1)#(n-fromInteger k**0.5)]

With a score of 102 99 92 - 10 = 82 we can print each solution only once, sorted:

0#n=[[]|n^2<0.1^12]
m#n=[k:v|k<-[1..round$n^2],v<-(m-1)#(n-fromInteger k**0.5),m<2||[k]<=v]

Answer 9

Python 3 - 157 174 169 - 10 = 159

Edit1: Changed the output format to space-separated integers instead of comma-separated. Thanks for the tip of removing the braces around (n,x).

Edit2: Thanks for the golfing tips! I can trim off another 9 chars if I just use an == test instead of testing for approximate equality to within 1e-6, but that would invalidate approximate solutions, if any such exist.

Uses itertools to generate all possible integer combinations, hopefully efficiently :)

I haven't found a way to add printing "No" efficiently, it always seems to take more than 10 extra characters.

from itertools import*
n,x=eval(input())
for c in combinations_with_replacement(range(1,int(x*x)),n):
 if abs(sum(z**.5for z in c)-x)<1e-6:print(' '.join(map(str,c)))

Answer 10

Scala (397 bytes - 10)

import java.util.Scanner
object Z extends App{type S=Map[Int,Int]
def a(m:S,i:Int)=m updated(i,1+m.getOrElse(i,0))
def f(n:Int,x:Double):Set[S]={if(n==0){if(x.abs<1e-6)Set(Map())else Set()}
else((1 to(x*x+1).toInt)flatMap{(i:Int)=>f(n-1,x-Math.sqrt(i))map{(m:S)=>a(m,i)}}).toSet}
val s=new Scanner(System.in)
f(s.nextInt,s.nextDouble)foreach{(m:S)=>m foreach{case(k,v)=>print(s"$k "*v)};println}}

If there are no permutations, then this program prints nothing.