10
\$\begingroup\$

A person has to complete N units of work; the nature of work is the same.

In order to get the hang of the work, he completes only one unit of work in the first day.

He wishes to celebrate the completion of work, so he decides to complete one unit of work in the last day.

He is only allowed to complete x, x+1 or x-1 units of work in a day, where x is the units of work completed on the previous day.

Your task is to create a program or function that will compute the minimum number of days will he take to complete N units of work.

Sample Input and Ouput:

input -> output (corresponding work_per_day table)
-1    -> 0      []
0     -> 0      []
2     -> 2      [1,1]
3     -> 3      [1,1,1]
5     -> 4      [1,1,2,1] or [1,2,1,1]
9     -> 5      [1,2,3,2,1]
13    -> 7      [1,2,2,2,3,2,1]

Input may be taken through STDIN or as function argument, or in any appropriate way.

Output may be printed or as the result of a function, or in any appropriate way.

This is . Shortest solution wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hint: this integer list could be helpful. \$\endgroup\$ – Leaky Nun Apr 22 '16 at 12:28
  • 1
    \$\begingroup\$ So, is input restricted to positive integers, since Kenny showed that it's possible to achieve a negative work count? Or is the work per day restricted to a minimum of zero? \$\endgroup\$ – mbomb007 Apr 22 '16 at 19:31
  • 1
    \$\begingroup\$ Why did you accept the Pyth answer? My Jelly answer is 3 bytes shorter... \$\endgroup\$ – Dennis Apr 23 '16 at 5:43
  • \$\begingroup\$ Hey,@Dennis I need to understand the approach and @Kenny Lau help me to understand it. \$\endgroup\$ – HarshGiri Apr 23 '16 at 6:55
  • \$\begingroup\$ I am new to CodeGolf so It will take some time to understand all stuffs here fully. \$\endgroup\$ – HarshGiri Apr 23 '16 at 7:02

11 Answers 11

3
\$\begingroup\$

Jelly, 5 bytes

×4’½Ḟ

This uses a closed form of @LeakyNun's approach.

Try it online!

Due to a lucky coincidence, is overloaded as floor/real for real/complex numbers. This is one of the only three overloaded atoms in Jelly.

How it works

×4’½Ḟ  Main link. Argument: n (integer)

×4     Compute 4n.
  ’    Decrement; yield 4n - 1.
   ½   Square root; yield sqrt(4n - 1).
       If n < 2, this produces an imaginary number.
    Ḟ  If sqrt(4n - 1) is real, round it down to the nearest integer.
       If sqrt(4n - 1) is complex, compute its real part (0).
\$\endgroup\$
  • 1
    \$\begingroup\$ One does not simply... \$\endgroup\$ – Leaky Nun Apr 22 '16 at 22:35
  • 1
    \$\begingroup\$ "Lucky coincidence" \$\endgroup\$ – Arcturus Apr 23 '16 at 4:22
4
\$\begingroup\$

Pyth, 8 bytes

tfg/*TT4

How it works:

tfg/*TT4   Q is implicitly assigned to the input.
 f         test for T=1,2,3,... returning the first successful case
   /*TT4   whether T * T / 4
  g     Q  is greater than or equal to the input (second argument implied)
t          and subtract 1 from the first successful case

Try it online!

In pseudo-code:

for(int T=1;;T++)
    if(T*T/4 >= Q)
        return T-1;

bonus, 22 bytes

"should return 7 for -1"

+tfg/*TT4?>Q0Q-2Q1*4g1

Try it online!

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

JavaScript (ES2016), 24 bytes

Shortened version of the ES6 variant below thanks to @Florent and the Exponentiation Operator (currently only in Firefox nightly builds or transpilers).

n=>(n-1)**.5+(n+1)**.5|0

JavaScript (ES6), 30 bytes

n=>(s=Math.sqrt)(n-1)+s(n+1)|0

Based upon this sequence.

f=n=>(s=Math.sqrt)(n-1)+s(n+1)|0

units.oninput = () => output.value = f(+units.value||0);
<label>Units: <input id="units" type="number" value="0" /></label>
<label>Days: <input id="output" type="number" value="0" disabled /></label>

\$\endgroup\$
  • \$\begingroup\$ Even shorter in ES2016 (26 chars): f=n=>(n-1)**.5+(n+1)**.5|0 \$\endgroup\$ – Florent Apr 23 '16 at 16:14
  • \$\begingroup\$ @Florent Wow thanks, wasn't aware of the upcoming exponentiation operator. \$\endgroup\$ – George Reith Apr 25 '16 at 2:44
2
\$\begingroup\$

JavaScript, 32 31 bytes

f=(q,t=1)=>q>t*t/4?f(q,t+1):t-1

Ungolfed code:

function f(q, t = 1) {
  return q > t * t / 4
    ? f(q, t + 1)
    : t - 1
}

It uses the same algorithm as Kenny Lau's anwser but it is implemented as recursive closure to save some bytes.

Usage:

f(-1)  // 0
f(0)   // 0
f(2)   // 2
f(3)   // 3
f(5)   // 4
f(9)   // 5
f(13)  // 7

REPL solution, 23 bytes

for(t=1;t*t++/4<q;);t-2

Prepend q= to run the snippet:

q=-1;for(t=1;t*t++/4<q;);t-2 // 0
q=9;for(t=1;t*t++/4<q;);t-2  // 5
q=13;for(t=1;t*t++/4<q;);t-2 // 7
\$\endgroup\$
  • \$\begingroup\$ It even uses the same variable names as mine :) \$\endgroup\$ – Leaky Nun Apr 22 '16 at 14:49
  • \$\begingroup\$ Can save one byte by turning >= to < :D \$\endgroup\$ – Leaky Nun Apr 22 '16 at 14:50
  • \$\begingroup\$ @KennyLau Thanks! It's been a long time since i've not golf. I'm a little bit rusted x) \$\endgroup\$ – Florent Apr 22 '16 at 14:56
  • \$\begingroup\$ for(t=1;;)if(t*t++/4>=q)return t-1; is only 36 bytes :) \$\endgroup\$ – Leaky Nun Apr 22 '16 at 15:01
  • 1
    \$\begingroup\$ @KennyLau I've added 23 bytes solution :) \$\endgroup\$ – Florent Apr 22 '16 at 15:17
2
\$\begingroup\$

Python, 28 bytes

lambda n:max(4*n-1,0)**.5//1

Outputs a float. The max is there to give 0 for n<=0 while avoiding an error for square root of negative.

\$\endgroup\$
2
\$\begingroup\$

UGL, 30 25 bytes

i$+$+dc^l_u^^$*%/%_c=:_do

Try it online!

Does not work for negative inputs.

How it works:

i$+$+dc^l_u^^$*%/%_c=:_do
i$+$+d                     #n = 4*input-1
      c                    #i=0
       ^l_     %/%_c=:_    #while      > n:
           ^^$*            #      i**2
          u                #                i = i+1
                       do  #print(i)

Previous 30-byte solution:

iuc^l_u^^$*cuuuu/%_u%/%_c=:_do

Online interpreter here.

Does not work for negative inputs.

How it works:

iuc^l_u^^$*cuuuu/%_u%/%_c=:_do
iuc                             #push input; inc; i=0;
   ^l_u             %/%_c=:_    #while        > input:
       ^^$*cuuuu/%_             #      i**2/4
                   u            #                      i = i+1
                            do  #print(i)
\$\endgroup\$
1
\$\begingroup\$

MATL, 11 bytes

E:t*4/G<f0)

Similar algorithm to @KennyLau except that rather than looping indefinitely, I loop from 1...2n to save some bytes.

Try it Online!

Explanation

    % Implicitly grab the input
E   % Double the input
:   % Create an array from 1...2n
t*  % Square each element
4/  % Divide each element by 4
G<  % Test if each element is less than G
f   % Get the indices of the TRUE elements in the array from the previous operation
0)  % Get the last index (the first index where T*T/4 >= n)
    % Implicitly display the result.
\$\endgroup\$
  • \$\begingroup\$ @LuisMendo Thanks for pointing that out. Updated! \$\endgroup\$ – Suever Apr 22 '16 at 20:43
0
\$\begingroup\$

Pyke, 8 bytes

#X4f)ltt

Try it here!

Uses same algorithm as @KennyLau

\$\endgroup\$
0
\$\begingroup\$

Python, 43 bytes

f=lambda n,i=1:i-1if i*i>=n*4 else f(n,i+1)
\$\endgroup\$
  • 1
    \$\begingroup\$ can save a byte by using < instead of >= \$\endgroup\$ – Leaky Nun Apr 22 '16 at 22:30
0
\$\begingroup\$

Java 8, 30 24 bytes

n->(int)Math.sqrt(n*4-1)

Try it online.

No need to check if n is larger than 0, because Java's Math.sqrt returns NaN for negative inputs, which becomes 0 with the cast to int we already use for the positive inputs.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 30 bytes

->n{n<1?0:((4*n-1)**0.5).to_i}

Try it online!

Saving a byte here with .to_i instead of .floor.

Support for non-positive amounts of work comes at a cost of 6 bytes (n<1?0:).

\$\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.