20
\$\begingroup\$

Challenge:

Input:

A sorted list of positive integers.

Output:

The amount of integers which are still at the exact same index, after rotating the digits in each integer its index amount of times towards the left and sorting the modified list again.

Example:

Input: [8,49,73,102,259,762,2782,3383,9217,37846,89487,7471788]
Output (0-based indexing): 6
Output (1-based indexing): 5

Why?

0-based indexing:

After rotating each: [8,94,73,102,592,276,8227,3338,9217,63784,89487,7887471]
Sorted again:        [8,73,94,102,276,592,3338,8227,9217,63784,89487,7887471]

Input indices:        0  1  2   3   4   5    6    7    8     9    10      11
Original input-list: [8,49,73,102,259,762,2782,3383,9217,37846,89487,7471788]
Modified list:       [8,73,94,102,276,592,3338,8227,9217,63784,89487,7887471]
Modified indices:     0  2  1   3   5   4    7    6    8     9    10      11
Equal indices:        ^         ^                      ^     ^     ^       ^

So the output is: 6

1-based indexing:

After rotating each: [8,49,37,021,925,762,2278,3383,2179,37846,94878,8874717]
Sorted again:        [8,(0)21,37,49,762,925,2179,2278,3383,37846,94878,8874717]

Input indices:        1  2  3   4   5   6    7    8    9    10    11      12
Original input-list: [8,49,73,102,259,762,2782,3383,9217,37846,89487,7471788]
Modified list:       [8,21,37,49,762,925,2179,2278,3383,37846,94878,8874717]
Modified indices:     1  4  3  2   6   5    9    7    8    10    11      12
Equal indices:        ^     ^                               ^     ^       ^

So the output is: 5

Challenge rules:

  • The input-list is guaranteed to only contain positive integers.
  • The input-list is guaranteed to be sorted from lowest to highest.
  • The input-list is guaranteed to contain at least two items.
  • As you can see above, both 0-based and 1-based indexing is allowed. Please state in your answer which of the two you've used, since outputs can differ accordingly!
  • Leading 0s after rotating are ignored, which can be seen with the 1-based example above, where the integer 102 becomes 021 after rotating, and is then treated as 21.
  • Integers are guaranteed unique in the input-list, and are guaranteed to remain unique after the rotations are completed.
  • Note that we only look at the positions of the rotated integers in correlation with the positions of the input, not with the values of the input-list. To clarify what I mean by this: with the input-list [1234,3412] and 1-based indexing, the list becomes [2341,1234] after rotating each integer it's index amount of times, and then when sorted becomes [1234,2341]. Although both the original input-list and the rotated list contains the integer 1234 at the leading position, they aren't the same! The rotated 1234 was 3412 before. The 1-indexed output for this input-list is therefore 0, since the two integers have swapped their positions.
  • Input is flexible. Can be a list/stream/array of integers/strings/digit-arrays, etc. Please state what you've used if you don't take the inputs as integers.

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Test cases:

Input: [8, 49, 73, 102, 259, 762, 2782, 3383, 9217, 37846, 89487, 7471788]
0-based output: 6
1-based output: 5

Input: [1234, 3412]
0-based output: 2
1-based output: 0

Input: [2349, 2820, 17499, 21244, 29842, 31857, 46645, 56675, 61643, 61787]
0-based output: 3
1-based output: 0

Input: [4976, 11087, 18732, 22643, 52735]
0-based output: 2
1-based output: 3

Input: [4414, 5866, 7175, 8929, 14048, 16228, 16809, 19166, 24408, 25220, 29333, 44274, 47275, 47518, 53355]
0-based output: 4
1-based output: 4

Input: [11205, 16820, 63494]
0-based output: 1
1-based output: 3

Feel free to generate more random test cases with (or draw inspiration from) this ungolfed 05AB1E program, where the input is the size of the random list (NOTE: the output of this generator might not comply with the rule "Integers are guaranteed unique in the input-list, and are guaranteed to remain unique after the rotations are completed", so keep that in mind when using it.)

\$\endgroup\$
  • \$\begingroup\$ May we assume that the input has at least 2 elements? \$\endgroup\$ – Robin Ryder May 28 at 21:02
  • 2
    \$\begingroup\$ @RobinRyder Hmm, my first thought would be no, but since I don't have any test cases with single items and it won't add much to the challenge, why not. I'll add a rule that the input-list is guaranteed to contain at least 2 items. \$\endgroup\$ – Kevin Cruijssen May 28 at 21:07
  • \$\begingroup\$ May we accept input as a list of strings? \$\endgroup\$ – Embodiment of Ignorance May 29 at 3:29
  • 1
    \$\begingroup\$ @Shaggy I've notified the answers I thought would benefit from it. If you see any that could benefit from it as well, feel free to notify them as well. \$\endgroup\$ – Kevin Cruijssen May 29 at 6:24
  • 1
    \$\begingroup\$ From the example it seems the output should be "The amount of integers which are still at the exact same index, after rotating the digits in each integer its index amount of times towards the left, and sorting the array again"? \$\endgroup\$ – qwr May 31 at 13:53

22 Answers 22

11
\$\begingroup\$

R, 114 107 bytes

-5 bytes thanks to Giuseppe.

Outgolfed by digEmAll.

function(l){for(j in seq(l))l[j]=rep(l[j]%/%(e=10^(b=nchar(l[j]):1-1))%%10,j+1)[j+0:b]%*%e
sum(sort(l)==l)}

Try it online!

0-indexed.

Ungolfed version:

function(l) {
  n = length(l)                         # size of input
  for (j in 1:n) {  
    b = nchar(l[j]) -1                  # number of digits in l[j] -1
    e = 10 ^ (b:0) 
    d = l[j] %/% e %% 10                # convert to vector of digits
    l[j] = rep(d, j + 1)[j + 0:b] %*% e # rotate digits and convert back to an integer
  }
  sum(sort(l) == l)                     # number of integers which are in the same position
}

To rotate the b digits of an integer by j positions, the code repeats the digits many times, then takes the digits in positions j+1 to j+b. For instance, to rotate 102 4 times, keep the values marked with an x (positions 5 to 7):

102102102102
    xxx

so the result is 021.

\$\endgroup\$
  • \$\begingroup\$ 111 bytes \$\endgroup\$ – Giuseppe May 28 at 16:40
  • \$\begingroup\$ @Giuseppe Thanks! I need to remember seq(a=...). I expect there is some Map magic to perform, but my attempts left the byte count unchanged at best. \$\endgroup\$ – Robin Ryder May 28 at 19:23
  • \$\begingroup\$ Map might be a bit too expensive since the function boilerplate is at least 9 bytes, but if you switch to 0-indexing, we can do 109 bytes \$\endgroup\$ – Giuseppe May 28 at 19:26
  • 1
    \$\begingroup\$ Good find! Down to 107 by realizing that seq(a=l) can be seq(l) as long as the input has at least 2 elements (I asked whether this is OK). \$\endgroup\$ – Robin Ryder May 28 at 21:02
  • 1
    \$\begingroup\$ Let's change the approach :D \$\endgroup\$ – digEmAll May 29 at 12:03
6
\$\begingroup\$

05AB1E, 9 bytes

ΣN._ï}-_O

Try it online!

Uses 0-based indexing.

Explanation:

Σ    }       # sort the input by
 N._         # each number rotated its index to the left
    ï        # then cast to int (otherwise the sort is alphabetic)
      -      # subtract the input from the result
       _O    # then count the 0s
\$\endgroup\$
6
\$\begingroup\$

Japt -x, 10 9 bytes

0-based

í¶UñÈséYn

Try it

í¶UñÈséYn     :Implicit input of integer array U
í             :Interleave with
  Uñ          :U sorted by
    È         :Passing each integer at 0-based index Y through the following function
     s        :  Convert to string
      é       :  Rotate right by
       Yn     :    Y negated
 ¶            :Reduce each pair by testing for equality
              :Implicit output of sum of resulting array
\$\endgroup\$
4
\$\begingroup\$

Jelly, 9 bytes

Dṙ"JḌỤ=JS

Try it online!

Monadic link that takes a list of integers and returns an integer indicating the number of integers that remain in place after performing the rotation using 1-indexing.

Explanation

D         | Convert to decimal digits
 ṙ"J      | Rotate left by index
    Ḍ     | Convert back to integer
     Ụ    | Index in sorted list
      =J  | Check if equal to index in original list
        S | Sum
\$\endgroup\$
4
\$\begingroup\$

Python 2, 104 100 97 93 bytes

b=[int((s*-~i)[i:i+len(s)])for i,s in enumerate(input())]
print map(cmp,b,sorted(b)).count(0)

Try it online!

0-based indexing.

First rotates each number, and then compares the result with result, but sorted.


Saved:

  • -3 bytes, thanks to Erik the Outgolfer
  • -4 bytes, thanks to Kevin Cruijssen (and his rule-change)
\$\endgroup\$
  • \$\begingroup\$ -3 as a full program. \$\endgroup\$ – Erik the Outgolfer May 28 at 16:04
  • \$\begingroup\$ @eriktheoutgolfer thanks, I was too busy trying to make a lambda, that I forgot about input() :) \$\endgroup\$ – TFeld May 28 at 17:57
  • \$\begingroup\$ That's why I first try to make a full program... :D Seriously, if you first try to make a full program, you will then clearly see if it's worth converting to a lambda or not. Don't start with a def right away (they're pretty useless in Python 2, contrary to Python 3). \$\endgroup\$ – Erik the Outgolfer May 28 at 18:00
  • \$\begingroup\$ I've allowed the input-list as strings now, so you can drop 4 bytes by removing the grave accents surrounding the s. \$\endgroup\$ – Kevin Cruijssen May 29 at 6:19
4
\$\begingroup\$

R, 90 88 85 bytes

function(x)sum(rank(as.double(substr(strrep(x,L<-sum(x|1)),y<-1:L,y+nchar(x)-1)))==y)

Try it online!

  • 0-indexed rotation
  • rotation strategy inspired by @RobinRyder's answer
  • -5 bytes thanks to @Giuseppe

Unrolled code with explanation :

function(x){
    L=sum(x|1)                         # store the length of x

    R=strrep(x,L)                      # repeat each string of vector x L times

    S=substring(R,1:L,1:L+nchar(x)-1)) # for each string of R, extract a substring of the same 
                                       # length of the original number starting from index 1 
                                       # for the 1st element, index 2 for the 2nd and so on
                                       # (this basically rotates the strings )

    Y=as.double(S)                     # convert the strings to numbers

    sum(rank(Y)==1:L)                  # return the number of times the ranks of Y
                                       # match with their original positions
}
\$\endgroup\$
3
\$\begingroup\$

J, 28 26 bytes

-2 bytes thanks to Jonah

1#.i.@#=[:/:#\".@|.&>":&.>

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice. Looks like you can lose the "0 (Try it online!) but other than that I didn't see a way to golf further. \$\endgroup\$ – Jonah May 28 at 22:58
  • \$\begingroup\$ @Jonah Thank you! I don't know why I didn't try without it. \$\endgroup\$ – Galen Ivanov May 29 at 3:46
2
\$\begingroup\$

Stax, 11 10 bytes

ìát'óJ♣á◄·

Run and debug it

This program uses 0-based indexing and takes input as an array of strings. I saved a byte by taking opportunity of the new input clarificatinos.

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

Perl 5 -pa, 80 bytes

map$d{$_.substr$_,0,$b%y///c,''}=$b++,@F;$\+=$d{$_}==$r++for sort{$a-$b}keys%d}{

Try it online!

Takes input as space separated numbers on STDIN; gives 1-based result.

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

Pyth, 15 bytes

sqVSJ.ev.<`bkQJ

Try it online! Uses 0-based indexing.

sqVSJ.ev.<`bkQJ   Implicit: Q=eval(input())
     .e      Q    Map elements of Q, as b and with index k, using:
          `b        Convert b to string
        .<  k       Rotate the above left k places
       v            Convert back to integer
    J             Store the above as J
   S              Sort the above
 qV           J   Vectorised equality check with the unsorted list
s                 Sum, implicit output
\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman I've now allowed a list of strings as input, so it's valid now. \$\endgroup\$ – Kevin Cruijssen May 29 at 6:21
  • \$\begingroup\$ @FryAmTheEggman You're probably right, I'd not considered lexographic sorting vs integer sorting when omitting the s - the original version of the code had a v for the same effect. I'll edit it back in \$\endgroup\$ – Sok May 29 at 7:08
  • \$\begingroup\$ Ah, well as Kevin points out now you could drop the backtick and take the input as a list of strings to save a byte. \$\endgroup\$ – FryAmTheEggman May 29 at 14:53
2
\$\begingroup\$

APL+WIN, 23, 21 19 bytes

2 bytes saved by inputting the integers as a nested vector of characters

+/i=⍋⍎¨(i←⍳⍴v)⌽¨v←⎕

1 indexed.

v←⎕ prompt for input. 

(i←⍳⍴v)⌽¨ rotate each set of characters by input indices.

⍋⍎¨ convert characters to integers and get sorted indices.

+/i= sum where original and sorted indices are the same.

Try it online! Courtesy of Dyalog Classic

\$\endgroup\$
  • \$\begingroup\$ Not sure if it would save any bytes, but I allowed the input as a list of strings or list of digit-lists now. \$\endgroup\$ – Kevin Cruijssen May 29 at 6:22
  • \$\begingroup\$ @KevinCruijssen Thanks for pointing that out. Inputting a nested vector of strings saves 2 bytes \$\endgroup\$ – Graham May 29 at 8:43
2
\$\begingroup\$

JavaScript (Node.js), 107 99 95 bytes

-8 bytes Thanks @Shaggy for accepting array of strings instead. Further golfed 4 bytes from this. Will not trigger memory error this time.

a=>[...b=a.map(F=(x,i)=>i--?F(x.slice(1)+x[c=0],i):x)].sort((p,q)=>q-p).map(x=>c+=x==b.pop())|c

Try it online!

JavaScript (Node.js), 111 107 bytes

-4 bytes Thanks @Arnauld!

a=>[...b=a.map((x,i)=>"".padEnd(x+i,x+=c='').substr(i,x.length))].sort((p,q)=>q-p).map(x=>c-=x==b.pop())|-c

Try it online!

JavaScript (Node.js), 113 111 bytes

a=>[...b=a.map((x,i)=>"".padEnd(x+i,x).substr(i,`${x}`.length))].sort((p,q)=>p-q).map((x,i)=>x-b[i]||c++,c=0)|c

Try it online!

0-indexed. May trigger memory error for very large entries.

\$\endgroup\$
  • 2
    \$\begingroup\$ 99 bytes, taking input as an array of integer strings. \$\endgroup\$ – Shaggy May 28 at 22:43
  • \$\begingroup\$ @Shaggy Thanks, and it's now 95 bytes ;) \$\endgroup\$ – Shieru Asakoto May 29 at 9:00
2
\$\begingroup\$

Perl 6, 50 bytes

{sum ^$_ Z==sort {+[~] rotate .[$^i].comb,$i},^$_}

Try it online!

0-based indexing. Also exposed a Rakudo bug.

Explanation

{                                                }  # Anonymous block
            sort                              ^$_   # Sort indices 0..n
                 {                          },  # by
                              .[$^i]            # element at index i
                                    .comb       # split into chars
                       rotate            ,$i    # rotated i times
                   [~]  # joined
                  +     # converted to number
     ^$_ Z==  # Pairwise equal to original indices 0..n
 sum   # Sum of equal indices
\$\endgroup\$
2
\$\begingroup\$

PHP, 159 141 134 130 bytes

function($a){foreach($a as$x){for($j=$i;$j--;$x=substr($x,1).$x[0]);$b[$x]=$i++;}ksort($b);foreach($b as$z)$y+=++$j==$z;return$y;}

Try it online!

Zero-based indexing.

Ungolfed:

function( $a ) { 
    // iterate through digits
    foreach( $a as $x ) {
        // rotate the digits the number of times based on their index
        for( $j = $i; $j--; ) {
            // move first digit to last digit
            $x = substr( $x, 1 ) . $x[0];
        }
        // the new number is used as key for sort, value is the original index
        $b[ $x ] = $i++;
    }
    // sort by the new numbers
    ksort( $b );
    // iterate sorted array
    foreach( $b as $z ) {
        // if new index matches original index, increment count ($y)
        if ( ++$j == $z ) {
            $y++;
        }
    }
    return $y;
}
  • -4 bytes taking input as array of strings, thx to @KevinCruijssen for pointing that out.
\$\endgroup\$
  • \$\begingroup\$ I don't know PHP too well, but I allow a list of strings instead of integers now, so I think you can remove the .=''? \$\endgroup\$ – Kevin Cruijssen May 29 at 6:20
  • \$\begingroup\$ @KevinCruijssen you are correct. Taking as an array of strings will remove that from being necessary. I'll update accordingly. \$\endgroup\$ – gwaugh May 29 at 13:21
2
\$\begingroup\$

K (Kona), 25 21bytes

-4 bytes thanks to ngn!

{+/t=<.:'(t:!#x)!'$x}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ {.:y!x}'[$x;t:!#x] -> .:'(t:!#x)!'$x \$\endgroup\$ – ngn Jun 4 at 11:57
  • \$\begingroup\$ @ngn Thank you, it's much better now! \$\endgroup\$ – Galen Ivanov Jun 4 at 14:24
2
\$\begingroup\$

T-SQL query, 99 bytes

Sql has no rotating method, so I had to implement my own syntax, since this is a query, it had to be done without looping.

0-based indexing.

Using a table variable as input.

SELECT-sum(1/~(z*3))FROM(SELECT~i+rank()over(order by
substring(n+n,i%len(n)+1,len(n))*1)z FROM @)c

Try it online

\$\endgroup\$
1
\$\begingroup\$

Icon, 141 bytes

procedure f(l)
n:=0
b:=[]
t:=l[k:=1to*l]&m:=k%*t&t:=t[m+1:0]||t[1:m+1]&put(b,[+t,l[k]])&\x
l[i:=1to*l]=sortf(b,1)[i,2]&n+:=1&\x 
return n
end

Try it online!

1-based indexing

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 104 bytes

sub f{my$i;grep/\d+$/&&$i++==$&,sort{$a<=>$b}map{my$n=shift;map$n=~s/(.)(.+)/$2$1/,1..$_;"$n.$_"}0..$#_}

Try it online!

0-based indexing in Perl. Ungolfed and commented:

sub f {
  my $i;                            #index counter
  grep /\d+$/ && $i++==$&,          #keep/return elems where $i matches original index stored as decimals
  sort { $a<=>$b }                  #sort rotated elems numerically (<=> is the numerical comparison op
  map {                             #loop through input
    my $n = shift;                  #shift(@_) got elem from input array @_
    map $n=~s/(.)(.+)/$2$1/, 1..$_; #rotate left times current index 
    "$n.$_"                         #use rotated number with original index number as decimals (to dont affect sort)
  }
  0..$#_
}
\$\endgroup\$
1
\$\begingroup\$

Ruby -ap, 77 bytes

1-indexed. Was temp deleted earlier because I missed part of the spec.

-p reads a line of STDIN, and outputs $_ at the end. -a splits that read line by spaces and saves it as $F.

i=0
$_=$F.zip($F.sort_by{|s|s.chars.rotate(i+=1).join.to_i}).count{|a,b|a==b}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ you can save 2 bytes by replacing [...].join.to_i with eval [...]*'' \$\endgroup\$ – Doorknob May 29 at 13:48
  • 1
    \$\begingroup\$ @Doorknob unfortunately not... there are edge cases where if a number is rotated to have a leading zero, eval will interpret it as a base-8 number, which could mess up our counts... \$\endgroup\$ – Value Ink May 29 at 20:34
1
\$\begingroup\$

Wolfram Language (Mathematica), 65 bytes

o=Ordering
g=Count[o@MapIndexed[FromDigits@*RotateLeft,#]-o@#,0]&

Try it online!

1-based. We take the input as a list of digit lists, which works because Mathematica orders lists by length, then lexicographically, i.e. just like the original numbers.

\$\endgroup\$
1
\$\begingroup\$

Bash, 204 201 bytes

The only interesting thing here (possibly) is the use of eval. The algorithm is also clunky in that it creates a sorted list then reads it in order to determine changed index/indices.

1-based solution. My thanks to @RobinRyder for the helpful rotation algorithm.

for((i=1;i<$#+1;i++));do eval s=\${$i};for((j=0;j<i;j++));do eval s=${s}\${$i};done;eval n=\${s:$i:\${#$i}};echo $n $i;done|sort -nk1,1|{ i=1;c=0;while read d j;do((i==j))&&((c++));((i++));done;echo $c; }

Try it online!

Revised code following Kevin's comments; Try it online!

\$\endgroup\$
  • \$\begingroup\$ I don't know Bash too well, but I think you can remove the last space between ;}. Also, you can change your first loop to for((i=0;++i<=$#;));. \$\endgroup\$ – Kevin Cruijssen May 29 at 13:21
  • \$\begingroup\$ @KevinCruijssen -- usually I have found Bash and friends needs that space to parse the command line. On this occasion you are correct it may be removed. Nice idea to re-base and pre-increment. 202 bytes. \$\endgroup\$ – PJF May 29 at 13:29
1
\$\begingroup\$

Scala, 200 160 bytes

def f(a:Seq[String])=
  a.zipWithIndex
   .map(x=>{val r=x._2%x._1.size;x._1.drop(r)+x._1.take(r)->x._2})
   .sortBy(_._1.toInt)
   .zipWithIndex
   .filter(x=>x._1._2==x._2)
   .size

Try it online!

0-indexed. 160 chars after removing indentation and newlines. This prints 6:

println( f(Seq("8","49","73","102","259","762","2782","3383","9217","37846","89487","7471788")) )
\$\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.