10
\$\begingroup\$

Write a function (such as placeAt) that takes an array of non-negative integers and an index that is a non-negative integer. It should place a 1 at the given index, possibly shifting other entries by one spot to vacate that spot, with 0's standing for empty spots.

  • If the entry at the desired index is 0, fill it with a 1.
  • Otherwise, look for the nearest 0 to the left of the index. Shift entries one spot left into that 0 to make room, then fill the index with a 1.
  • If there's no 0 to the left, do the same going right.
  • If neither is possible (i.e. if there is no 0), return the array unchanged.

The items are 0-indexed. Function name can be anything you want.

Examples:

(Letters stand for any positive integer values.)

[a, b, 0, c, d, 0] placeAt 2    // output [a, b, 1, c, d, 0]    place 2 is 0, just fill
[a, b, 0, c, d, 0] placeAt 3    // output [a, b, c, 1, d, 0]    place 3 is filled, shift items left
[a, b, 0, c, d, 0] placeAt 0    // output [1, a, b, c, d, 0]    place 0 is filled, can't shift left, shift items right
[a, b, 0, c, d, 0] placeAt 1    // output [a, 1, b, c, d, 0]    place 1 is filled, can't shift left, shift items right
[0, a, b, 0, c, d, 0] placeAt 2 // output [a, b, 1, 0, c, d, 0] place 2 is filled, shift items left
[0, a, b, 0, c, d, 0] placeAt 4 // output [0, a, b, c, 1, d, 0] place 4 is filled, shift items left (notice you keep shifting up until a 0)
[0, 2, 0, 2] placeAt 3          // output [0, 2, 2, 1]          place 3 is filled, shift items left

This is a code golf challenge. The shortest entry at the end of 9 days wins.

\$\endgroup\$
  • 4
    \$\begingroup\$ How do you know whether to shift left or right when both are possible? Also, what if there is no 0? \$\endgroup\$ – xnor Aug 14 '15 at 19:08
  • \$\begingroup\$ For [0, 2, 0, 2] placeAt 3, is it legal to output [2, 0, 2, 1]? Is the code required to actually be a function called placeAt? Note that some languages don't exactly have functions. "Throw an exception" might also not apply to some languages; I'd suggest allowing an output indicating an error. \$\endgroup\$ – xnor Aug 14 '15 at 19:21
  • \$\begingroup\$ Can the array have negative values? \$\endgroup\$ – Kade Aug 14 '15 at 22:05
  • \$\begingroup\$ I'm 99% sure I understand the OP's intentions with the rules of this challenge, so I've reorganized the post (it's in the queue right now) and I will attempt to answer questions. eguneys, you can correct any of my answers if need be. \$\endgroup\$ – ETHproductions Aug 15 '15 at 1:06
  • \$\begingroup\$ @xnor Shifting left always takes preference over shifting right. If there is no 0, just return the original array. Also, [2, 0, 2, 1] is not a legal output, as you should always shift as few elements as possible, and you can name the function whatever you want. \$\endgroup\$ – ETHproductions Aug 15 '15 at 1:07

10 Answers 10

4
\$\begingroup\$

JavaScript (ES6), 85

Test running the snippet on any EcmaScript 6 compliant browser (notably not Chrome not MSIE. I tested on Firefox, Safari 9 could go)

(I found this without looking at any of the other answers, now I see it's very similar to rink's. Yet quite shorter. Probably I won't get many upvotes for this one)

F=(a,p,q=~a.lastIndexOf(0,p)||~a.indexOf(0))=>(q&&(a.splice(~q,1),a.splice(p,0,1)),a)

// Ungolfed
U=(a,p)=>{
  q = a.lastIndexOf(0, p)
  if (q < 0) q = a.indexOf(0)
  if (q >= 0) {
    a.splice(q, 1)
    a.splice(p, 0, 1)
  }
  return a
}  

// TEST
out=x=>O.innerHTML+=x+'\n';

[ [['a', 'b', 0, 'c', 'd', 0], 2, ['a', 'b', 1, 'c', 'd', 0]] // place 2 is 0, just fill
, [['a', 'b', 0, 'c', 'd', 0], 3, ['a', 'b', 'c', 1, 'd', 0]] // place 3 is filled, shift items left
, [['a', 'b', 0, 'c', 'd', 0], 0, [1, 'a', 'b', 'c', 'd', 0]] // place 0 is filled, can't shift left, shift items right
, [['a', 'b', 0, 'c', 'd', 0], 1, ['a', 1, 'b', 'c', 'd', 0]] // place 1 is filled, can't shift left, shift items right
, [[0, 'a', 'b', 0, 'c', 'd', 0], 2, ['a', 'b', 1, 0, 'c', 'd', 0]] // place 2 is filled, shift items left
, [[0, 'a', 'b', 0, 'c', 'd', 0], 4, [0, 'a', 'b', 'c', 1, 'd', 0]] // place 4 is filled, shift items left (notice you keep shifting up until a 0)
, [['a', 'b', 'c', 'd'], 2, ['a', 'b', 'c', 'd']] // impossible
, [[0, 2, 0, 2], 3, [0, 2, 2, 1]]] // place 3 is filled, shift items left
.forEach(t=>{
  i=t[0]+''
  r=F(t[0],t[1])+''
  k=t[2]+''
  out('Test ' + (r==k?'OK':'Fail') +'\nInput: '+i+' '+t[1]+'\nResult:'+r+'\nCheck: '+k+'\n')
})
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ +1 because I just learned about the comma operator, and for beating me \$\endgroup\$ – rink.attendant.6 Aug 17 '15 at 6:54
  • \$\begingroup\$ @rink.attendant.6 but your use of && to join the splice is better than my comma \$\endgroup\$ – edc65 Aug 17 '15 at 9:44
3
\$\begingroup\$

Julia, 122 bytes

Just a naïve implementation of the spec to get things started.

f(x,i)=(i+=1;x[i]==0?(x[i]=1):i>2&&x[i-1]==0?(x[i-1]=x[i];x[i]=1):i<length(x)-1&&x[i+1]==0?(x[i+1]=x[i];x[i]=1):error();x)

Ungolfed:

function placeAt(x::Array, i::Int)
    # Make i 1-indexed
    i += 1

    # Shift and modify the array as necessary
    if x[i] == 0
        x[i] = 1
    elseif i > 2 && x[i-1] == 0
        x[i-1], x[i] = x[i], 1
    elseif i < length(x)-1 && x[i+1] == 0
        x[i+1], x[i] = x[i], 1
    else
        error()
    end

    # Return the modified array
    x
end
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 98 bytes

Pretty much the same approach as my CoffeeScript answer but I'm short-circuiting to the extreme in order to save a return statement:

f=(a,x)=>(~($=a.lastIndexOf(0,x))||~(_=a.indexOf(0,x)))&&a.splice(~$?$:_,1)&&a.splice(x,0,1)&&a||a

Explanation

To easier explain, I have rearranged my code a bit:

// Declare function f with two arguments: array and position
f = (a, x) => {
    // Take the part of the array from beginning to x and find the last 0
    $ = a.lastIndexOf(0, x)

    // Find the first 0 after position x
    _ = a.indexOf(0, x);

    // indexOf returns -1 if they aren't found
    // ~1 == 0 so I am checking if either $ or _ is truthy (zeros were found)
    if (~$ || ~_)
       // If zeros were found in the left, use that.
       // Otherwise use the found zero in the right.
       // Delete it from the array
       // Array.prototype.splice will return an array which evaluates to truthy
       // and continues execution with the &&
       // Insert value 1 at position x, deleting 0 elements
       // The last value is returned
       return a.splice(~$ ? $ : _, 1) && a.splice(x, 0, 1) && a
    else
       // No zeros were found so just return the original
       // In the golfed code the if would have evaluated to false to cut into the || part
       return a
}

Here's some information on JS short-circuit evaluation.

Demo

At the moment this demo only works in Firefox and Edge due to use of ES6:

f=(a,x)=>(~($=a.lastIndexOf(0,x))||~(_=a.indexOf(0,x)))&&a.splice(~$?$:_,1)&&a.splice(x,0,1)&&a||a

// Snippet stuff
console.log = x => O.innerHTML += x + '\n';

console.log(f(['a', 'b', 0, 'c', 'd', 0], 2))
console.log(f(['a', 'b', 0, 'c', 'd', 0], 3))
console.log(f(['a', 'b', 0, 'c', 'd', 0], 0))
console.log(f([0, 'a', 'b', 0, 'c', 'd', 0], 2))
console.log(f([0, 'a', 'b', 0, 'c', 'd', 0], 4))
console.log(f(['a', 'b', 0, 'c', 'd', 0], 2))
console.log(f(['a', 'b', 0, 'c', 'd', 0], 1))
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ How does this work can you explain please. \$\endgroup\$ – eguneys Aug 15 '15 at 3:39
  • \$\begingroup\$ @eguneys Explanation added \$\endgroup\$ – rink.attendant.6 Aug 15 '15 at 3:53
  • \$\begingroup\$ it doesn't work for f(['a', 'b', 0, 'c', 'd', 0], 2) \$\endgroup\$ – eguneys Aug 15 '15 at 3:59
  • \$\begingroup\$ @eguneys Fixed. I forgot that CoffeeScript automatically adds one when using their shorthand slice [a..b]. \$\endgroup\$ – rink.attendant.6 Aug 15 '15 at 4:02
  • \$\begingroup\$ doesn't work for f(['a', 'b', 0, 'c', 'd', 0], 1) \$\endgroup\$ – eguneys Aug 15 '15 at 11:30
1
\$\begingroup\$

Ruby, 208 bytes

def f(a,i)
  x=a.take(i).rindex(0);y=a[i+1..-1].index(0)
  if a[i]==0
    a[i]=1
  elsif !x.nil?
    a.delete_at(x);a.insert(i,1)
  elsif !y.nil?
    a.delete_at(y+i+1);a.insert(i,1)
  end
  a
end
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Some simple golfing tips for Ruby: you don't need any indentation, so you can get rid of all the spaces. Then you also don't need the semicolons, because a single newline is the same number of bytes. Method calls at the end of a statement don't need parentheses, so you can do, e.g. .rindex 0, saving one byte each time. You can also save some bytes by using a proc instead of a method, which doesn't even have to be named: ->a,i{...}. The if/elsif/elsif can probably be shortened with a nested ternary operator ...?...:...?...:.... \$\endgroup\$ – Martin Ender Aug 16 '15 at 15:39
  • \$\begingroup\$ Thanks a lot for the kind advice. I'll look into it and see what I can do. \$\endgroup\$ – handrake Aug 16 '15 at 22:54
1
\$\begingroup\$

Haskell, 119 bytes

e=elem 0
r=reverse
f=(g.).splitAt
g(a,y@(x:b))|e(x:a)=r(h(x:r a)1)++b|e y=a++h y 1|1<2=a++y 
h(0:r)n=n:r
h(a:r)n=n:h r a

Usage example:

*Main> mapM_ (print.uncurry f) [ 
                (2,[2,3,0,4,5,0]),
                (3,[2,3,0,4,5,0]),
                (0,[2,3,0,4,5,0]),
                (1,[2,3,0,4,5,0]),
                (2,[0,2,3,0,4,5,0]),
                (4,[0,2,3,0,4,5,0]),
                (3,[0,2,0,2]),
                (2,[2,3,4,5])  ]
[2,3,1,4,5,0]
[2,3,4,1,5,0]
[1,2,3,4,5,0]
[2,1,3,4,5,0]
[2,3,1,0,4,5,0]
[0,2,3,4,1,5,0]
[0,2,2,1]
[2,3,4,5]

How it works: Split the input list at the given position into left part a, the element at the position itself x and right part b. If there's a 0 in a++x, make room up to first 0 in the reverse of a++x. If there's a 0 in x++b, make room there. If there's no 0 at all, combine all parts unchanged to get the original list again.

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

CoffeeScript, 96 bytes

f=(a,_)->a.splice((if~($=a.lastIndexOf 0,_)then $ else a.indexOf 0),1);a.splice(_,0,1)if 0in a;a
\$\endgroup\$
0
\$\begingroup\$

Python 2, 102 bytes

def f(a,i):
 x=(a[i-1::-1]+a[i:]+[0]).index(0)
 if x<len(a):del a[(x,i-x-1)[x<i]];a[i:i]=[1]
 return a

Calculates the index of the zero to be removed by concatenating the list reversed up to the insertion index with the part after the index in normal order, then finding the index of the first zero. A zero is added to the end to avoid ValueError exceptions when no zero is found. Then just delete, insert and return.

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

R, 87 bytes

f=function(a,i)if(0%in%a)append(a[-abs(min((b=which(a==0))*(1-(b<=i+1)*2)))],1,i)else a

Explanation

function(a,i)
if(0%in%a)                      # as long as a 0 exists
    append(                     # append 1 after i
        a[
          -abs(                 # remove absolute of min index
            min(                # minimum of adjusted index
              (b=which(a==0))*  # index of all 0's
              (1-(b<=i+1)*2)    # multiple -1 if <= i
              )
            )
        ]
        ,1
        ,i
    )
else                            # otherwise return untouched
    a

Tests

> f(c(2, 3, 0, 4, 5, 0) , 2)   
[1] 2 3 1 4 5 0
> f(c(2, 3, 0, 4, 5, 0) , 3)   
[1] 2 3 4 1 5 0
> f(c(2, 3, 0, 4, 5, 0) , 0)   
[1] 1 2 3 4 5 0
> f(c(2, 3, 0, 4, 5, 0) , 1)   
[1] 2 1 3 4 5 0
> f(c(0, 2, 3, 0, 4, 5, 0) , 2)
[1] 2 3 1 0 4 5 0
> f(c(0, 2, 3, 0, 4, 5, 0) , 4)
[1] 0 2 3 4 1 5 0
> f(c(0, 2, 0, 2) , 3)         
[1] 0 2 2 1
> 
\$\endgroup\$
0
\$\begingroup\$

C#, 265 bytes

Golfed (265 Characters)

static void placeAt(String[]Q,int P){int I;if(Q[P]=="0"){Q[P]="1";}else{I=Array.IndexOf(Q,"0");if(I>=0){if(I<P){for(int i=I;i<=P;i++){Q[i]=(i==P)?"1":Q[i+1];}}else if(I>P){for(int i=I;i>=P;i--){Q[i]=(i==P)?"1":Q[i-1];}}}}foreach(String s in Q)Console.Write(s+" ");}

With white spaces and indentations

static void placeAt(String[] Q, int P)
    {
        int I;

        if(Q[P] == "0")
        {
            Q[P] = "1";
        }
        else
        {
            I = Array.IndexOf(Q, "0");
            if (I >= 0)
            {
                if (I < P)
                {
                    for (int i = I; i <= P; i++)
                    {
                        Q[i] = (i == P) ? "1" : Q[i + 1];
                    }
                }
                else if (I > P)
                {
                    for (int i = I; i >= P; i--)
                    {
                        Q[i] = (i == P) ? "1" : Q[i - 1];
                    }
                }
            }
        }

        foreach (String s in Q)
            Console.Write(s + " ");
    }

Whole Program

using System;

class FillZero
{
    static void placeAt(String[] Q, int P)
    {
        int I;

        if(Q[P] == "0")
        {
            Q[P] = "1";
        }
        else
        {
            I = Array.IndexOf(Q, "0");
            if (I >= 0)
            {
                if (I < P)
                {
                    for (int i = I; i <= P; i++)
                    {
                        Q[i] = (i == P) ? "1" : Q[i + 1];
                    }
                }
                else if (I > P)
                {
                    for (int i = I; i >= P; i--)
                    {
                        Q[i] = (i == P) ? "1" : Q[i - 1];
                    }
                }
            }
        }

        foreach (String s in Q)
            Console.Write(s + " ");
    }

    static void Main()
    {
        String[] X = {"a", "b", "0", "c", "d", "0"};
        placeAt(X , 1);

    }

}

Test Cases enter image description here

\$\endgroup\$
  • 1
    \$\begingroup\$ this doesn't work for ([0, 'a', 'b', 0, 'c', 'd'], 2) \$\endgroup\$ – eguneys Aug 15 '15 at 4:02
  • 1
    \$\begingroup\$ You can save some chars by removing all unnecessary whitespace, for example String[] Q, int P to String[]Q,int P. \$\endgroup\$ – ProgramFOX Aug 15 '15 at 12:26
  • \$\begingroup\$ Hi @eguneys, thanks for pointing that out. I have modified the logic and thus works for all of your test cases. I have also updated the test cases image. The placing is done correctly, however the shifting results are different. \$\endgroup\$ – Merin Nakarmi Aug 17 '15 at 19:10
  • \$\begingroup\$ Hi @ProgramFOX, thanks for your valuable comment. I saved some 10 characters. \$\endgroup\$ – Merin Nakarmi Aug 17 '15 at 19:10
0
\$\begingroup\$

C, 154 bytes

p(a,l,i,c)int*a;{for(c=i;c+1;c--){if(!a[c]){for(;c<i;c++)a[c]=a[c+1];return a[i]=1;}}for(c=i;c<l;c++){if(!a[c]){for(;c>i;c--)a[c]=a[c-1];return a[i]=1;}}}

Passes the given test cases, a is the pointer to the array, l is the length of the array (I hope this doesn't break the brief), i is the index for the insert and c is used internally. Could possibly be improved by combining the left and right search for loops.

Example

int main(int argc, char * argv[]) {
    int a[] = {0, 2, 0, 2};
    p(a, 4, 3);
}

Ungolfed

Straight forward, and not really any tricks beyond K&R style declaration.

p(a,l,i,c) int *a; {
    /* Search left from i (also handles a[i] == 0) */
    for (c=i;c+1;c--) {
            if (!a[c]) {
                    /* Shift items left until i */ 
                    for (;c<i;c++) a[c]=a[c+1];
                    return a[i]=1;
            }
    }
    /* Search right from i */
    for (c=i;c<l;c++) {
            if(!a[c]) {
                    /* Shift items right until i */
                    for(;c>i;c--) a[c]=a[c-1]; 
                    return a[i]=1;
            }
    }
}
\$\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.