24
\$\begingroup\$

In this challenge, you need to simulate a frog jumping back and forth on lily pads. The pond is infinitely big, has a line of an infinite number of lily pads, and the frog can jump across as many lily pads as he likes.

This frog likes to jump back and forth: after jumping forward, he always jumps backwards, and vice versa.

You are passed a list of integers, which represents his jumps. You need to output the result of his jumps.

For example, say you are passed [2,3,6,8,2]:

Our frog starts by jumping 2 lily pads forward:

_2

Then 3 lily pads back:

3__2

Then 6 lily pads forward:

3__2__6

8 back:

8_3__2__6

Then finally, 2 lily pads forward (notice how the 2 overwrites the 3):

8_2__2__6

To be more explicit: Your input is an an array of numbers S, you need to output S[K] at the position S[K] - S[K-1] + S[K-2] - S[K-3]....

  • If multiple numbers are to be printed at a certain location, print only the one with the highest index.
  • You are to use _ if a particular location is empty
  • If a number has multiple digits, it does not take up multiple locations. (In other words, a location can consist of multiple characters)
  • You can assume that your list is non-empty, and that all integers are greater than 0.

Test cases:

5                   ____5
2,2                 2_2
4,3,2,1             3124
5,3,2,1             _3125
2,3,6,8,2           8_2__2__6
10,3,12,4,1,12,16   ___12__3__10____41__1216
100,4,7,2,2         _______________________________________________________________________________________________4___1002_2

This is a , so answer it in as few characters as possible!

\$\endgroup\$
  • 13
    \$\begingroup\$ I wonder who watched Numberphile? \$\endgroup\$ – Okx Feb 23 '17 at 19:13
  • 3
    \$\begingroup\$ So there's gonna be a challenge for every Numberphile video then... \$\endgroup\$ – Fatalize Feb 23 '17 at 19:13
  • 5
    \$\begingroup\$ Related :-P \$\endgroup\$ – Luis Mendo Feb 23 '17 at 19:14
  • 5
    \$\begingroup\$ @Fatalize I see nothing wrong with that. \$\endgroup\$ – orlp Feb 23 '17 at 19:22
  • 1
    \$\begingroup\$ Also related ;-) \$\endgroup\$ – Arnauld Feb 23 '17 at 19:25

10 Answers 10

9
\$\begingroup\$

MATL, 35 34 bytes

Thanks to @Emigna for saving 1 byte!

32Oittn:oEq*Yst1hX<-Q(Vh' 0'95ZtXz

Try it online! Or verify all test cases.

How it works

Golf your code, not your explanations!

The following uses input [2,3,6,8,2] as an example. To see intermediate results in the actual code, you may want to insert a % (comment symbol) to stop the program at that point and see the stack contents. For example, this shows the stack after statement Ys (cumulative sum).

32       % Push 32 (ASCII for space)
O        % Push 0
i        % Input array
         % STACK: 32, 0, [2,3,6,8,2]
t        % Duplicate
         % STACK: 32, 0, [2,3,6,8,2], [2,3,6,8,2]
tn:      % Push [1 2 ... n] where n is length of input array
         % STACK: 32, 0, [2,3,6,8,2], [2,3,6,8,2], [1,2,3,4,5]
o        % Modulo 2
         % STACK: 32, 0, [2,3,6,8,2], [2,3,6,8,2], [1,0,1,0,1]
Eq       % Multiply by 2, subtract 1
         % STACK: 32, 0, [2,3,6,8,2], [2,3,6,8,2], [1,-1,1,-1,1]
*        % Multiply elementwise
         % STACK: 32, 0, [2,3,6,8,2], [2,-3,6,-8,2]
Ys       % Cumulative sum
         % STACK: 32, 0, [2,3,6,8,2], [2,-1,5,-3,1]
         % The top-most array is the positions where the entries of the second-top
         % array will be written. But postions cannot be less than 1; if that's
         % the case we need to correct so that the minimum is 1. If this happens,
         % it means that the frog has gone further left than where he started
t        % Duplicate
1hX<     % Append 1 and compute minimum. So if the original minimum is less than 1
         % this gives that minimum, and if it is more than 1 it gives 1
         % STACK: 32, 0, [2,3,6,8,2], [2,-1,5,-3,1], -3
-        % Subtract
         % STACK: 32, 0, [2,3,6,8,2], [5 2 8 0 2]
Q        % Add 1
         % STACK: 32, 0, [2,3,6,8,2], [6 3 9 1 3]
(        % Assign values (top array) to specified positions (second-top) into array
         % which contains a single 0 (third-top). Newer values overwrite earlier
         % values at the same position
         % STACK: 32, [8 0 2 0 0 2 0 0 6]
V        % Convert to string. This produces spaces between the numbers
         % STACK: 32, '8 0 2 0 0 2 0 0 6'
h        % Concatenate with initial 32 (space). This converts to char
         % STACK: ' 8 0 2 0 0 2 0 0 6'
         % Thanks to this initial space, all zeros that need to be replaced by '_'
         % are preceded by spaces. (In this example that initial space would not
         % be needed, but in other cases it will.) Other zeros, which are part of
         % a number like '10', must not be replaced
' 0'     % Push this string: source for string replacement
         % STACK: ' 8 0 2 0 0 2 0 0 6', ' 0 '
95       % Push 95 (ASCII for '_'): target for string replacement
         % STACK: ' 8 0 2 0 0 2 0 0 6', ' 0 ', 95
Zt       % String replacement
         % STACK: ' 8_2__2__6'
Xz       % Remove spaces. Implicit display
         % STACK: '8_2__2__6'
\$\endgroup\$
  • \$\begingroup\$ I think you could save two bytes by replacing '0' instead of ' 0 ', because Xz removes the spaces after \$\endgroup\$ – B. Mehta Feb 23 '17 at 21:26
  • 1
    \$\begingroup\$ @B.Mehta Thanks. I initially did that, but unfortunately it doesn't work, because then the '0' in '10' gets replaced too. That's why I add an initial 32 too \$\endgroup\$ – Luis Mendo Feb 23 '17 at 21:29
  • \$\begingroup\$ Ah of course, my mistake \$\endgroup\$ – B. Mehta Feb 23 '17 at 21:32
  • \$\begingroup\$ @B.Mehta No, it wasn't clear at all from my explanation. I'll clarify that later \$\endgroup\$ – Luis Mendo Feb 23 '17 at 21:48
  • 1
    \$\begingroup\$ The mod 2 array is inverted in the explanation. And also, wouldn't ' 0' work just as well? \$\endgroup\$ – Emigna Feb 23 '17 at 22:58
4
\$\begingroup\$

PHP, 100 101 99 104 bytes

for($p=-1;$d=$argv[++$k];+$i<$p?:$i=$p,$x>$p?:$x=$p)$r[$p+=$k&1?$d:-$d]=$d;for(;$i<=$x;)echo$r[$i++]?:_;

takes input from command line arguments; run with -nr.

breakdown

for($p=-1;          // init position
    $d=$argv[++$k]; // loop $d through command line arguments
    +$i<$p?:$i=$p,          // 3. $i=minimum index
    $x>$p?:$x=$p            // 4. $x=maximum index
)
    $r[
        $p+=$k&1?$d:-$d     // 1. jump: up for odd indexes, down else
    ]=$d;                   // 2. set result at that position to $d
for(;$i<=$x;)           // loop $i to $x inclusive
    echo$r[$i++]?:_;        // print result at that index, underscore if empty
\$\endgroup\$
  • \$\begingroup\$ How does this handle the example input 2,3,6,8,2, where the 8 jumps "backwards" past the "beginning" of the lily pads? \$\endgroup\$ – AdmBorkBork Feb 23 '17 at 20:04
  • \$\begingroup\$ @AdmBorkBork PHP supports negative array indexes. \$\endgroup\$ – Titus Feb 23 '17 at 20:22
  • \$\begingroup\$ Ah, did not know that. Thanks! \$\endgroup\$ – AdmBorkBork Feb 23 '17 at 20:40
4
\$\begingroup\$

JavaScript (ES6), 99 107 bytes

Edit: Because the OP clarified that the only limit should be the available memory, this was updated to allocate exactly the required space instead of relying on a hardcoded maximum range.

f=(a,x='',p=M=0)=>a.map(n=>x[(p-=(i=-i)*n)<m?m=p:p>M?M=p:p]=n,i=m=1)&&x?x.join``:f(a,Array(M-m).fill`_`,-m)

How it works

This function works in two passes:

  • During the first pass:

    • The 'frog pointer' p is initialized to 0.
    • The x variable is set to an empty string, so that all attempts to modify it are simply ignored.
    • We compute m and M which are respectively the minimum and maximum values reached by p.
    • At the end of this pass: we do a recursive call to f().
  • During the second pass:

    • p is initialized to -m.
    • x is set to an array of size M-m, filled with _ characters.
    • We insert the numbers at the correct positions in x.
    • At the end of this pass: we return a joined version of x, which is the final result.

Test cases

f=(a,x='',p=M=0)=>a.map(n=>x[(p-=(i=-i)*n)<m?m=p:p>M?M=p:p]=n,i=m=1)&&x?x.join``:f(a,Array(M-m).fill`_`,-m)

console.log(f([5]));                  // ____5
console.log(f([4,3,2,1]));            // 3124
console.log(f([5,3,2,1]));            // _3125
console.log(f([2,3,6,8,2]));          // 8_2__2__6
console.log(f([10,3,12,4,1,12,16]));  // ___12__3__10____41__1216
console.log(f([100,4,7,2,2]));        // _..._4___1002_2

\$\endgroup\$
  • \$\begingroup\$ This fails for cases where the frog jumps below index -998 or above 1002. Example: [1100] results in the number printed at position 1002 instead of position 1100. \$\endgroup\$ – nderscore Feb 23 '17 at 20:33
  • 1
    \$\begingroup\$ @nderscore This is fixed, at the cost of 8 bytes. \$\endgroup\$ – Arnauld Feb 24 '17 at 0:34
  • \$\begingroup\$ awesome! nice method also :) \$\endgroup\$ – nderscore Feb 24 '17 at 1:13
4
\$\begingroup\$

R, 100 97 96 bytes

function(x){p=cumsum(x*c(1,-1))[seq(x^0)]
p=p+max(1-p,0)
v=rep('_',max(p));v[p]=x
cat(v,sep='')}

Try it online!

Line 1 finds all positions where to jump. First, all jumps in x are multiplied by 1 or −1 and then transformed to final positions using cumulative summation. The vector c(-1,1) is recycled if necessary, however, when x is of length 1, x is recycled instead. Therefore only seq(x^0) (equivalent to seq_along(x)) sums are considered. (A warning is generated when the length of x is not a multiple of 2 but it does not affect the result)

Line 2 increases the jumping positions so that all are at least 1.

Lines 3 and 4 create the output and print it.

−1 byte from Giuseppe

\$\endgroup\$
  • \$\begingroup\$ neat trick with seq(x^0)! \$\endgroup\$ – Giuseppe Mar 4 '18 at 16:31
  • \$\begingroup\$ -p+1 can be 1-p for one byte less. \$\endgroup\$ – Giuseppe Mar 4 '18 at 16:36
  • \$\begingroup\$ @Giuseppe Ah, definitely, thanks! \$\endgroup\$ – Robert Hacken Mar 4 '18 at 18:59
3
\$\begingroup\$

Javascript (ES6), 109 bytes

f=x=>x.map((y,i)=>o[j=(j-=i%2?y:-y)<0?o.unshift(...Array(-j))&0:j]=y,o=[],j=-1)&&[...o].map(y=>y||'_').join``
<!-- snippet demo: -->
<input list=l oninput=console.log(f(this.value.split(/,/)))>
<datalist id=l><option value=5><option value="4,3,2,1"><option value="5,3,2,1"><option value="2,3,6,8,2"><option value="10,3,12,4,1,12,16"><option value="100,4,7,2,2"></datalist>

Commented:

f=x=>x.map((y,i)=>o[j=(j-=i%2?y:-y)<0?o.unshift(...Array(-j))&0:j]=y,o=[],j=-1)&&[...o].map(y=>y||'_').join``
                /* initialize output array [] and index j at -1: */  o=[],j=-1
     x.map((y,i)=> /* iterate over all items in input x (y=item, i=index) */  )
                      (j-=i%2?y:-y) /* update j +/-y based on if index i is odd */
                                   <0? /* if resulting j index is less than zero */
                                      o.unshift(...Array(-j)) /* prepend -j extra slots to the output array */
                                                             &0 /* and give result 0 */
                                                               :j /* else give result j */
                    j= /* assign result to j */
                  o[ /* assign y to output array at index j */   ]=y
   /* short-circuit && then spread output array to fill any missing entries */ &&[...o]
                                                      /* fill falsey slots with '_' */ .map(y=>y||'_')
                                                                         /* join with empty spaces */ .join``
\$\endgroup\$
3
\$\begingroup\$

Perl 6, 68 67 bytes

{(my @a)[[[\+] |(1,-1)xx*Z*$_].&{$_ X-min 1,|$_}]=$_;[~] @a X//"_"}

Try it online!

How it works

First it determines the cumulative jump locations:

[[\+] |(1,-1)xx*Z*$_]
                  $_  # Input array.          e.g.  2, 3, 6, 8, 2
      |(1,-1)xx*      # Infinite sequence:          1,-1, 1,-1, 1...
                Z*    # Zip-multiplied.       e.g.  2,-3, 6,-8, 2
 [\+]                 # Cumulative addition.  e.g.  2,-1, 5,-3,-1

Then it turns them into 0-based array indices by subtracting the minimum number (but at most 1) from all the numbers:

.&{$_ X-min 1,|$_}    #                       e.g.  5, 2, 8, 0, 2

Then it creates an array with the input numbers assigned to those indices:

(my @a)[   ]=$_;      #                       e.g.  8, Nil, 2, Nil, Nil, 2 Nil, Nil, 6

Finally it concatenates the array to a string, with the underscore in place of undefined elements:

[~] @a X//"_"         #                       e.g.  8_2__2__6
\$\endgroup\$
3
\$\begingroup\$

Jelly,  28  24 bytes

-2 (and further allowing another -2) thanks to FrownyFrog (use the [post-challenge] functionality of the prefix application quick, Ƥ)

ṚƤḅ-µCṀ»0+µṬ€×"³Ṛo/o”_;⁷

Try it online! Full program, for a test suite using the same functionality, click here.

How?

ṚƤḅ-µCṀ»0+µṬ€×"³Ṛo/o”_;⁷ - Main link: list a       e.g. [ 5, 3, 2, 1]
 Ƥ                       - prefix application of:
Ṛ                        -  reverse                e.g. [[5],[3,5],[2,3,5],[1,2,3,5]]
   -                     - literal minus one
  ḅ                      - from base (vectorises)  e.g. [ 5, 2, 4, 3]=
    µ                    - start a new monadic chain - call that list c
                         - [code to shift so minimum is 1 or current minimum]
     C                   - complement (vectorises) e.g. [-4,-1,-3,-2]
      Ṁ                  - maximum                 e.g.     -1
       »0                - maximum of that & zero  e.g.      0
         +               - add to c (vectorises)   e.g. [ 5, 2, 4, 3]
          µ              - start a new monadic chain - call that list d
           Ṭ€            - untruth €ach            e.g. [[0,0,0,0,1],[0,1],[0,0,0,1],[0,0,1]]
               ³         - the program input (a)
             ×"          - zip with multiplication e.g. [[0,0,0,0,5],[0,3],[0,0,0,2],[0,0,1]]
                Ṛ        - reverse                      [[0,0,1],[0,0,0,2],[0,3],[0,0,0,0,5]]
                 o/      - reduce with or          e.g. [0,3,1,2,5]
                    ”_   - '_'
                   o     - or (replace 0 with '_') e.g. ['_',3,1,2,5]
                      ;⁷ - concatenate a newline   e.g. ['_',3,1,2,5, '\n']
                         - implicit print

Notes:

The final concatenation of a newline, ;⁷ is for cases when no _ appear in the output, in which case the implicit print would display a representation of the list, e.g. [3, 1, 2, 4], rather than something like the example, _3125. For no trailing newline one could replace ;⁷ with ;““ to append a list of character lists, [[''],['']] (no close required as it's the last character of a program).

The untruth function, Ṭ, gives a list with 1s at the indexes in it's input, for a single natural number, n that is n-1 0s followed by a 1 allowing the input numbers to be placed at their correct distance from the left by multiplication. The reversal, , is required to have later frog-visits overwrite rather than earlier ones when the reduction with or, o/, is performed.

\$\endgroup\$
  • \$\begingroup\$ 1,-ṁ×µ+\UƤ_@/€ ? \$\endgroup\$ – FrownyFrog Mar 3 '18 at 12:12
  • \$\begingroup\$ Ƥ was not a feature at the point this was written, but yes that will work. Better is UƤḅ€- (since conversion from base -1 is like multiplying by ...,1,-1,1,-1,1,-1,1 and then summing). \$\endgroup\$ – Jonathan Allan Mar 3 '18 at 13:40
  • \$\begingroup\$ ...or even UƤḅ- since vectorises :) (I also went with plain reverse, , since we don't need the complexity of upend, U) \$\endgroup\$ – Jonathan Allan Mar 3 '18 at 13:55
1
\$\begingroup\$

APL (Dyalog Unicode), 45 30 bytesSBCS

{∊⍕¨⍵@i⍴∘'_'⌈/1+i←(⊢-1⌊⌊/)-\⍵}

Try it online!

-\⍵ scan the argument with alternating - and +

(⊢ - 1 ⌊ ⌊/) from that () subtract 1 or the minimum (⌊/), whichever is smaller ()

i← assign to i

⌈/ 1+ increment and take the maximum

⍴∘'_' produce that many underscores

⍵@i put the numbers from the argument () at positions i

∊⍕¨ format each and flatten

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

Ruby, 85 bytes

->a{i=1;j=c=0;a.map{|x|[c-=x*i=-i,x]}.to_h.sort.map{|x,y|[?_*[x+~j,0*j=x].max,y]}*''}

Try it online!

Records the positions after each jump, converts the resulting array to hash to remove duplicates (preserving the last value at each duplicated position), and then glues the values with the required amount of underscores.

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

Python 2, 113 110 bytes

J=input()
i=sum(J)
l=['_']*2*i
v=i,
d=1
for j in J:i+=d*j;d=-d;l[i]=`j`;v+=i,
print''.join(l[min(v):max(v)+1])

Try it online!

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