Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Reverse runs of odd numbers in a given list of 2 to 215 non-negative integers.
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
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
Old version: 75 bytes
print doesn't need parens. Also, you only use a once, so there's no need for a variable.
\$\endgroup\$
{∊⌽¨⍵⊂⍨e⍲¯1↓0,e←2|⍵}
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
h%p|(l,r)<-span(odd.(h*))p=l++h:r
foldr(%)[]
Thanks to @xnor for recognizing a fold and saving two bytes.
(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(%)[]:
\$\endgroup\$
foldr after all! Thank you.
\$\endgroup\$
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.
Ḃ¬ðœpUżx@F
Try it online! or verify all test cases.
Ḃ¬ðœ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.
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 :)
k.i=0 on the last line. It's just a variable.
\$\endgroup\$
k and k.i related?
\$\endgroup\$
Jul 3, 2016 at 6:05
k.i is a persistent variable between calls of k. See it as a makeshift global without having to use the global keyword.
\$\endgroup\$
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))
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();}
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
TiodgvYsG8XQ!"@gto?P
Input is a column array, using ; as separator.
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.
k=mod(l,2)
K=l.length
a=[K...1]
L=a[k[a]=1]
g(q)=∑_{n=1}^{[1...q.length]}q[n]
A=g(join(1,sign(L-L[2...]-1)))
f(l)=l[\{k>0:\sort(L,A.\max+1-A)[g(k)],k\}+[1...K](1-k)]
Hooooly crap, this was pretty challenging to do in Desmos given its limited list functionalities, but after lots of puzzling and scratched ideas, I finally managed to pull together something that actually works.
g(M,j)=j-max([1...j]0^{mod(M,2)})
f(L)=L[[i+g(L[n...1],n+1-i)-g(L,i)fori=[1...n]]]
n=L.length
*-1 byte thanks to @AidenChow (remove space after for)
g(M,j) gives the difference between j and the greatest index less than (or equal to) j of an even entry in M. For example, g([0,2,4,1,3,5,7,6,8],6) = 3 because the 6th element in the list is 5, and the last even entry before it is 4, which is 3 elements earlier.
f(L) is the solution to the challenge. It's of the form L[[h(i)for i=[1...n]]], which is a list indexing: h(i) gives the index of the value in L that should be at index i in the result list.
The main difficulty lies in h(i), defined as h(i) = i+g(L[n...1],n+1-i)-g(L,i). Note that g(M,j) = 0 whenever M[j] is even, so h(i)=i if L[i] is even (this corresponds to even entries not moving) since L[n...1][n+1-i]=L[i]=even
If L[i] is odd then we have a more complicated story: g(L,i) gives the distance to the element before the start of the odd run, and g(L[n...1],n+1-i) gives the distance to the element after the end of the odd run. Then g(L[n...1],n+1-i)-g(L,i) says how much closer the element is to the end of the run than the start of the run. For example, for L=[0,2,4,1,3,5,7,6,8] and i=6, this difference is -1, so L[6] has to move 1 element to the left, to where the 3 is currently.
In general regarding the difference g(L[n...1],n+1-i)-g(L,i):
{...} around mod(M,2) btw. Also I'm pretty sure you don't need a space between for and i.
\$\endgroup\$
Jun 15, 2022 at 21:28
#(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
[:;]<@(A.~2-@|{.);.1~1,2|2-/\]
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
ṁ↔ġ¤&%2
ṁ↔ġ¤&%2 Implicit input, a list of integers.
ġ Group by equality predicate:
¤ %2 Arguments modulo 2
& are both truthy.
ṁ Map and concatenate
↔ reversing.
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.
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).
\$\endgroup\$
Feb 27, 2018 at 8:12
Edit 4 bytes saved thx @Neil
a=>[...a,[]].map(x=>x&1?o=[x,...o]:r=r.concat(o,x,o=[]),r=o=[])&&r
: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.
\$\endgroup\$
->l{l.chunk(&:odd?).flat_map{|i,j|i ?j.reverse: j}}
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}}
->l{l.chunk{_1%2}.flat_map{_1>0?_2.reverse: _2}}
Unsupported by TIO :(
JYVQ=+J*%hN2+YN=Y*%N2+NY;+JY
Direct translation of my python answer (when has translating from python to pyth become a good idea?)
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
Çⁿ╜"}☻≥º╚(
Tied Jelly! So sad that packing only saved one byte.
Unpacked version with 11 bytes:
{|e_^*}/Frm
{|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.
[:;]<@(|.^:{.);.1~1,2|2-/\]
A minor improvement over miles' J answer.
[:;]<@(|.^:{.);.1~1,2|2-/\] NB. Input: an integer vector V
1,2|2-/\] NB. Pairwise difference modulo 2 and prepend 1
NB. giving starting positions for same-parity runs
] ;.1~ NB. Cut V at ones of ^ as the starting point and
(|.^:{.) NB. reverse each chunk (head of the chunk) times
NB. (effectively, reverse odd chunks only)
<@ NB. and enclose it
[:; NB. Finally, flatten the result
a=>a.map((c,k)=>o.splice(n=c&1?+n:k+1,0,c),o=n=[])&&o
a=>a.map((c,k)=>o.splice(n=c&1?n:k+1,0,c),o=[],n=0)&&o
v=scan();ifelse(o<-v%%2,v[rep(2*cumsum(r<-rle(o)$l)-r+1,r)-seq(v)],v)
Ungolfed, commented version:
o=v%%2 # get the odd numbers in the list
r=rle(o)$l # find the run lengths of odd/even numbers
# reverse the indices of all the runs:
e=cumsum(r) # the indices of the ends of each run
ie=rep(e,r) # for each index in v, the index of the end of its run
is=rep(e-r+1,r) # for each index in v, the index of the start of its run
irev=is+(ie-seq(v)) # reverses all runs
# the above 4 steps can be combined as:
irev=rep(2*cumsum(r)-r+1,r)-seq(v)
# so: use the reversed indices for odd numbers, and leave the even numbers unchanged
ifelse(o,v[irev],v)
grouping.extras, 62 bytes[ [ odd? ] group-by [ last2 swap [ reverse ] when ] map-flat ]
.γÈN>*}í˜
Try it online or verify all test cases.
Explanation:
.γ } # Adjacent group the (implicit) input-list by:
È # Check if the value is even (1 if even; 0 if odd)
N>* # Multiply it by the 1-based index
# (adjacent odd values will be grouped together, and every even
# value is in its own separated group)
í # After the adjacent group-by: reverse each inner list
˜ # Flatten the list of lists
# (after which the result is output implicitly)
λ&›₂¥*;ḊRf
Port of 05AB1E.
Another 10-byter that I produced independently: ⁽₂Ḋƛh∷ßṘ;f
