Reverse odd runs

17

Inspiration.

Task

Reverse runs of odd numbers in a given list of 2 to 215 non-negative integers.

Examples

0 1 → 0 1
1 3 → 3 1
1 2 3 → 1 2 3
1 3 2 → 3 1 2
10 7 9 6 8 9 → 10 9 7 6 8 9
23 12 32 23 25 27 → 23 12 32 27 25 23
123 123 345 0 1 9 → 345 123 123 0 9 1

Adám

Posted 2016-07-03T04:32:06.103

Reputation: 37 779

4>

  • I only understood the challenge after looking at the examples. I think runs of odd integers would be clearer than sequences. 2. I don't think setting an explicit upper limit is a good thing. If a language has only 8-bit integers, participating will be a lot harder.
  • < – Dennis – 2016-07-03T04:59:25.190

    Also, I'm not sure what further numeric computation refers to. Does it mean that I cannot return an immutable tuple or simply print the numbers? – Dennis – 2016-07-03T05:10:07.407

    @Dennis Updated as you suggested. It is to prevent input/output as string. Any suggestion for better wording? – Adám – 2016-07-03T05:14:59.790

    4Why do you want to prevent string output? – Dennis – 2016-07-03T05:16:02.060

    @Dennis Good point taken. – Adám – 2016-07-03T05:17:07.863

    Related. Maybe dupe? – xnor – 2016-07-03T07:01:13.557

    @xnor This one requires much more processing to find the parts that should be reversed. – Adám – 2016-07-03T07:07:45.387

    2Yes, looking at the other challenge, most of the answers rely on splitting on zeroes, whereas here you'd have to split on a condition, which most languages don't have a built-in for. – xnor – 2016-07-03T07:14:22.440

    @LuisMendo Yes. – Adám – 2016-07-03T13:34:54.727

    Answers

    8

    Python 2, 75 68 63 bytes

    5 bytes thanks to Dennis.

    And I have outgolfed Dennis.

    Credits to Byeonggon Lee for the core of the algorithm.

    o=t=[]
    for i in input():o+=~i%2*(t+[i]);t=i%2*([i]+t)
    print o+t
    

    Ideone it!

    Old version: 75 bytes

    Leaky Nun

    Posted 2016-07-03T04:32:06.103

    Reputation: 45 011

    Tied, really. Also, I'm counting 81, not 75. I'm guessing you counted it with tabs, but the SE editor filled in spaces. – James – 2016-07-03T06:02:20.637

    @DrGreenEggsandIronMan Your guess is correct. Tabs for readability. Either count the source or count the ideone one. – Leaky Nun – 2016-07-03T06:05:11.837

    1print doesn't need parens. Also, you only use a once, so there's no need for a variable. – Dennis – 2016-07-03T06:20:58.647

    5

    Python 2, 79 75 73 bytes

    def f(x):
     i=j=0
     for n in x+[0]:
        if~n%2:x[i:j]=x[i:j][::-1];i=j+1
        j+=1
    

    This is a function that modifies its argument in place. Second indentation level is a tabulator.

    Test it on Ideone.

    Dennis

    Posted 2016-07-03T04:32:06.103

    Reputation: 196 637

    Where's the meta for this? – Leaky Nun – 2016-07-03T06:02:35.387

    http://meta.codegolf.stackexchange.com/a/4942/12012 – Dennis – 2016-07-03T06:03:20.563

    5

    APL, 21 20 bytes

    {∊⌽¨⍵⊂⍨e⍲¯1↓0,e←2|⍵}
    

    Try it || All test cases

    Explanation:

                      2|⍵ Select all the odd numbers
                    e←    Save that to e
                  0,      Append a 0
               ¯1↓        Delete the last element
             e⍲           NAND it with the original list of odd numbers
         ⍵⊂⍨             Partition the list: (even)(even)(odd odd odd)(even)
      ⌽¨                 Reverse each partition
     ∊                    Flatten the list
    

    Edit: Saved a ~ thanks to De Morgan's laws

    Woofmao

    Posted 2016-07-03T04:32:06.103

    Reputation: 211

    1Hello, and welcome to PPCG! This is a good post. – NoOneIsHere – 2016-07-03T19:43:59.647

    5

    Haskell, 46 44 bytes

    h%p|(l,r)<-span(odd.(h*))p=l++h:r
    foldr(%)[]
    

    Thanks to @xnor for recognizing a fold and saving two bytes.

    Lynn

    Posted 2016-07-03T04:32:06.103

    Reputation: 55 648

    Nice method, especially the (h*)! You can save a byte on the base case by writing f x=x second to match the empty list, though it looks like a foldr is yet shorter: h%p|(l,r)<-span(odd.(h*))p=l++h:r;foldr(%)[]: – xnor – 2016-07-05T00:32:21.040

    I knew it was just a foldr after all! Thank you. – Lynn – 2016-07-05T07:02:31.487

    4

    Jelly, 10 bytes

    Ḃ¬ðœpUżx@F
    

    Try it online! or verify all test cases.

    How it works

    Ḃ¬ðœpUżx@F  Main link. Argument: A (array)
    
    Ḃ           Bit; return the parity bit of each integer in A.
     ¬          Logical NOT; turn even integers into 1's, odds into 0's.
      ð         Begin a new, dyadic link.
                Left argument: B (array of Booleans). Right argument: A
       œp       Partition; split A at 1's in B.
         U      Upend; reverse each resulting chunk of odd numbers.
           x@   Repeat (swapped); keep only numbers in A that correspond to a 1 in B.
          ż     Zipwith; interleave the reversed runs of odd integers (result to the
                left) and the flat array of even integers (result to the right).
             F  Flatten the resulting array of pairs.
    

    Dennis

    Posted 2016-07-03T04:32:06.103

    Reputation: 196 637

    4

    Python3, 96 bytes

    Saved a lot of bytes thanks to Leaky Nun!

    o=l=[]
    for c in input().split():
     if int(c)%2:l=[c]+l
     else:o+=l+[c];l=[]
    print(" ".join(o+l))
    

    Byeonggon Lee

    Posted 2016-07-03T04:32:06.103

    Reputation: 419

    4

    Python 2, 78 75 bytes

    def r(l):
     def k(n):o=~n%2<<99;k.i+=o*2-1;return k.i-o
     k.i=0;l.sort(key=k)
    

    Super hacky :)

    orlp

    Posted 2016-07-03T04:32:06.103

    Reputation: 37 067

    what is k.i ? – Leaky Nun – 2016-07-03T06:04:26.553

    @LeakyNun k.i=0 on the last line. It's just a variable. – orlp – 2016-07-03T06:04:57.823

    I don't get it. Are k and k.i related? – Leaky Nun – 2016-07-03T06:05:50.323

    @LeakyNun No. k.i is a persistent variable between calls of k. See it as a makeshift global without having to use the global keyword. – orlp – 2016-07-03T06:06:25.033

    3

    C, 107 bytes

    i;b[65536];f(){for(;i;)printf("%d ",b[--i]);}main(n){for(;~scanf("%d",&n);)n%2||f(),b[i++]=n,n%2||f();f();}
    

    orlp

    Posted 2016-07-03T04:32:06.103

    Reputation: 37 067

    3

    MATL, 20 bytes

    TiodgvYsG8XQ!"@gto?P
    

    Input is a column array, using ; as separator.

    Try it online!

    Explanation

    Consider as an example the input array [1;2;3;5;7;4;6;7;9]. The first part of the code, Tiodgv, converts this array into [1;1;1;0;0;1;0;1;0], where 1 indicates a change of parity. (Specifically, the code obtains the parity of each entry of the input array, computes consecutive differences, converts nonzero values to 1, and prepends a 1.)

    Then Ys computes the cumulative sum, giving [1;2;3;3;3;4;4;5;5]. Each of these numbers will be used as a label, based on which the elements of the input will be grouped. This is done by G8XQ!, which splits the input array into a cell array containing the groups. In this case it gives {[1] [2] [3;5;7] [4;6] [7;9]}.

    The rest of the code iterates (") on the cell array. Each constituent numeric array is pushed with @g. to makes a copy and computes its parity. If (?) the result is truthy, i.e. the array contents are odd, the array is flipped (P).

    The stack is implicitly displayed at the end. Each numeric vertical array is displayed, giving a list of numbers separated by newlines.

    Luis Mendo

    Posted 2016-07-03T04:32:06.103

    Reputation: 87 464

    2

    J, 33 31 30 bytes

    [:;]<@(A.~2-@|{.);.1~1,2|2-/\]
    

    Usage

       f =: [:;]<@(A.~2-@|{.);.1~1,2|2-/\]
       f 0 1
    0 1
       f 1 3
    3 1
       f 1 2 3
    1 2 3
       f 1 3 2
    3 1 2
       f 10 7 9 6 8 9
    10 9 7 6 8 9
       f 23 12 32 23 25 27
    23 12 32 27 25 23
       f 123 123 345 0 1 9
    345 123 123 0 9 1
    

    miles

    Posted 2016-07-03T04:32:06.103

    Reputation: 15 654

    2

    C#, 179 178 177 bytes

    s=>{var o=new List<int>();var l=new Stack<int>();foreach(var n in s.Split(' ').Select(int.Parse)){if(n%2>0)l.Push(n);else{o.AddRange(l);o.Add(n);l.Clear();}}return o.Concat(l);}
    

    I use a C# lambda. You can try it on .NETFiddle.

    The code less minify:

    s => {
        var o=new List<int>();var l=new Stack<int>();
        foreach (var n in s.Split(' ').Select(int.Parse)) {
            if (n%2>0)
                l.Push(n);
            else {
                o.AddRange(l);
                o.Add(n);
                l.Clear();
            }
        }
        return o.Concat(l);
    };
    

    Kudos to Byeonggon Lee for the original algorithm.

    aloisdg moving to codidact.com

    Posted 2016-07-03T04:32:06.103

    Reputation: 1 767

    1You can drop the space at the foreach(var and change if(n%2==1) to if(n%2>0) to save 2 bytes (or actually 1, because your current answer is 179 bytes instead of 178). – Kevin Cruijssen – 2018-02-27T08:12:06.797

    @KevinCruijssen It was changed in the less minify section but not in the minify one. Also thank you for the foreach space! – aloisdg moving to codidact.com – 2018-02-27T12:54:24.970

    2

    Pyth, 14 bytes

    s_McQshMBx0%R2
    
               %R2Q   Take all elements of the input list modulo 2
             x0       Get the indices of all 0s
          hMB         Make a list of these indices and a list of these indices plus 1
         s            Concatenate them
       cQ             Chop the input list at all those positions
     _M               Reverse all resulting sublists
    s                 Concatenate them
    

    Test cases

    Anders Kaseorg

    Posted 2016-07-03T04:32:06.103

    Reputation: 29 242

    1

    Stax, 15 10 bytesCP437

    Çⁿ╜"}☻≥º╚(
    

    Try it online!

    Tied Jelly! So sad that packing only saved one byte.

    Unpacked version with 11 bytes:

    {|e_^*}/Frm
    

    Explanation

    {|e_^*} is a block that maps all even numbers n to n+1, and all odd numbers n to 0.

    {|e_^*}/Frm
    {     }/       Group array by same value from block
     |e            1 if the element is even, 0 if odd.
       _^          Get another copy of the current element and increment by 1
         *         Multiply them
            F      For each group execute the rest of the program
             r     Reverse the group
              m    Print elements from the group, one element per line.
    

    Weijun Zhou

    Posted 2016-07-03T04:32:06.103

    Reputation: 3 396

    1

    Husk, 7 bytes

    ṁ↔ġ¤&%2
    

    Try it online!

    Explanation

    ṁ↔ġ¤&%2  Implicit input, a list of integers.
      ġ      Group by equality predicate:
       ¤ %2   Arguments modulo 2
        &     are both truthy.
    ṁ        Map and concatenate
     ↔       reversing.
    

    Zgarb

    Posted 2016-07-03T04:32:06.103

    Reputation: 39 083

    1

    Pyth, 29 28 bytes

    JYVQ=+J*%hN2+YN=Y*%N2+NY;+JY
    

    Test suite.

    Direct translation of my python answer (when has translating from python to pyth become a good idea?)

    Leaky Nun

    Posted 2016-07-03T04:32:06.103

    Reputation: 45 011

    1

    JavaScript (ES6) 70 66

    Edit 4 bytes saved thx @Neil

    a=>[...a,[]].map(x=>x&1?o=[x,...o]:r=r.concat(o,x,o=[]),r=o=[])&&r
    

    edc65

    Posted 2016-07-03T04:32:06.103

    Reputation: 31 086

    :r=r.concat(o,x,o=[]), saves you a couple of bytes. I think you can then go on to save another two like this: a=>[...a,[]].map(x=>x&1?o=[x,...o]:r=r.concat(o,x,o=[]),r=o=[])&&r. – Neil – 2016-07-03T11:26:59.380

    What is the meaning of ...o? – aloisdg moving to codidact.com – 2016-07-03T16:20:56.297

    1

    @aloisdg http://codegolf.stackexchange.com/a/37723/21348

    – edc65 – 2016-07-03T18:13:25.713

    @Neil the empty array used as the added element is a master stroke – edc65 – 2016-07-04T09:18:57.010

    1

    TSQL 118 bytes

    DECLARE @ TABLE(i int identity, v int)
    INSERT @ values(123),(123),(345),(0),(1),(9)
    
    SELECT v FROM(SELECT sum((v+1)%2)over(order by i)x,*FROM @)z
    ORDER BY x,IIF(v%2=1,max(i)over(partition by x),i),i desc
    

    Fiddle

    t-clausen.dk

    Posted 2016-07-03T04:32:06.103

    Reputation: 2 874

    1

    Clojure, 86 bytes

    #(flatten(reduce(fn[a b](if(odd? b)(conj(pop a)(conj[b](last a)))(conj a b[])))[[]]%))
    

    Here is the ungolfed version

    #(flatten ; removes all empty vectors and flattens odd sequences
        (reduce 
            (fn[a b]
                (if(odd? b) ; if we encounter odd number in the seq
                    (conj(pop a)(conj[b](last a))) ; return all elements but last and the element we encountered plus the last element of current result
                    (conj a b[])) ; else just add the even number and the empty vector
                )
            [[]] ; starting vector, we need to have vector inside of vector if the sequence starts with odd number
            %    ; anonymous function arg
        )   
    )
    

    Basically it goes through the input sequence and if it encounters even number it adds the number and the empty vector otherwise if it's an odd number it replaces the last element with this number plus what was in the last element.

    For example for this seq 2 4 6 1 3 7 2 it goes like this:

    • []<=2
    • [2 []]<=4
    • [2 [] 4 []]<=6
    • [2 [] 4 [] 6 []]<=1
    • [2 [] 4 [] 6 [1 []]]<=3
    • [2 [] 4 [] 6 [3 [1 []]]]<=7
    • [2 [] 4 [] 6 [7 [3 [1 []]]]]<=2
    • [2 [] 4 [] 6 [7 [3 [1 []]]] 2 []]

    And then flattening this vector gives the correct output. You can see it online here: https://ideone.com/d2LLEC

    cliffroot

    Posted 2016-07-03T04:32:06.103

    Reputation: 1 080

    0

    Ruby, 51 bytes

    ->l{l.chunk(&:odd?).flat_map{|i,j|i ?j.reverse: j}}
    

    Try it online!

    Some slight variations:

    ->l{l.chunk(&:odd?).flat_map{|i,j|i&&j.reverse||j}}
    ->l{l.chunk(&:odd?).flat_map{|i,j|!i ?j:j.reverse}}
    ->l{l.chunk(&:even?).flat_map{|i,j|i ?j:j.reverse}}
    

    Asone Tuhid

    Posted 2016-07-03T04:32:06.103

    Reputation: 1 944

    0

    Perl 5 with -p, 42 bytes

    map{$_%2?$\=$_.$\:print$\.$_,$\=""}$_,<>}{
    

    Try it online!

    Dom Hastings

    Posted 2016-07-03T04:32:06.103

    Reputation: 16 415