16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If there are multiple solutions, does it matter which solution we print?. E.g. for your last test case (5 13.0), this is also a valid solution: 81 1 1 1 1 \$\endgroup\$ – Jakube Nov 26 '14 at 11:11
  • \$\begingroup\$ And are zeros allowed in the solution? \$\endgroup\$ – Jakube Nov 26 '14 at 11:20
  • 1
    \$\begingroup\$ Is the input always space-separated? \$\endgroup\$ – Sp3000 Nov 26 '14 at 16:43
  • \$\begingroup\$ And is entering input via function call allowed? \$\endgroup\$ – Jakube Nov 26 '14 at 16:46
  • \$\begingroup\$ Also, what about duplicate solutions? For the first example, is our code allowed to print all six permutations of 6 7 8 for the second bonus? \$\endgroup\$ – Martin Ender Nov 26 '14 at 16:49

10 Answers 10

9
\$\begingroup\$

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 + x2 > 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' - i0.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'2 > i.

Rearranging we get x'2 + 1.897x' + 0.948 < i < 0.1 + x'2, 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.

\$\endgroup\$
  • \$\begingroup\$ You can avoid abs with x*x<1e-12. \$\endgroup\$ – xnor Nov 26 '14 at 18:45
  • 1
    \$\begingroup\$ I think this while loop works to replace the for: while.1+x*x>i:S(x-i**.5,n+[i]);i+=1, having initialized i=1 in the function parameters. The idea is to avoid needing to convert to ints. The .1 is to handle float inaccuracies; I think it's safe against infinite loops. \$\endgroup\$ – xnor Nov 26 '14 at 19:06
  • \$\begingroup\$ @xnor I've implemented the first tip for now. I'm still checking the correctness of the second one, but if it's good then that's a lot of bytes saved! (Also I actually expected you to post a solution :P) \$\endgroup\$ – Sp3000 Nov 27 '14 at 4:59
  • 1
    \$\begingroup\$ And with N now a function argument, it's shorter to recurse down with N-1 and check when N==0 rather than len(n)==N. \$\endgroup\$ – xnor Nov 29 '14 at 10:48
  • \$\begingroup\$ @Sp3000 I'm convinced now that the .1 is safe; I can chat you an argument if you'd like. \$\endgroup\$ – xnor Dec 2 '14 at 7:15
6
\$\begingroup\$

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).

\$\endgroup\$
  • 3
    \$\begingroup\$ It also prints "Yes" when it succeeds! Oh Prolog. \$\endgroup\$ – Sp3000 Nov 26 '14 at 16:20
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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}}
\$\endgroup\$
  • \$\begingroup\$ How does this print No? Also, the output isn't space separated. Also, can't you use Tr@ instead of Plus@@? And you might be able to save some characters by changing Select to Cases, the function at the end to a pattern, and making f an unnamed pure function. \$\endgroup\$ – Martin Ender Nov 28 '14 at 12:37
2
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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)))
\$\endgroup\$
  • \$\begingroup\$ Your program has the wrong output format (commas instead of spaces). Also, you can shave off 2 bytes by removing the braces around n,x. \$\endgroup\$ – Zgarb Nov 26 '14 at 15:51
  • \$\begingroup\$ I seem to be getting SyntaxErrors when I try the eval line... \$\endgroup\$ – Sp3000 Nov 26 '14 at 15:56
  • \$\begingroup\$ @Sp3000: try enter 3,7.923668178593959. You need the ',' \$\endgroup\$ – Jakube Nov 26 '14 at 16:35
  • \$\begingroup\$ 4 little improvements: from itertools import* saves 1, removing the space z**.5for saves 1, and removing the [] in sum(z**.5for z in c) saves 2 and removing the () in if(...) saves 1. \$\endgroup\$ – Jakube Nov 26 '14 at 16:40
  • \$\begingroup\$ Would a change to Python 2 and using n,x=input() be more compact? \$\endgroup\$ – Octavia Togami Nov 26 '14 at 23:22
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.