Shifty sort

Computer Science Level 5

Ayumu the chimp is given the task of sorting a group of integers $a_{0},a_{1},a_{2},a_{3}..$ into a non-decreasing order. Unfortunately Ayumu can only perform one operation,a single shift. That is,he can only move the last element of a sequence to the beginning. $a_{0},a_{1},a_{2} \ldots a_{n} \rightarrow a_{n},a_{0},a_{1} \ldots a_{n-1}$ Let $F(a)$ be the minimum number of times Ayumu has to do the single shift so that the sequence $a$ is sorted. If $a$ cannot be sorted with the shift operation then $F(a)$ is equal to $-1$ .

This text file contains 100 lines and in each line there is a sequence $a$ . Find the sum of $F(a)$ for all the sequences in the text file.

Explicit examples

For the sequence $a=[2,1]$ , $F(a)=1$ .
If $a=[1]$ , $F(a)=0$
If $a=[1,3,2]$ , $F(a)=-1$
If $a=[1,2]$ , $F(a)=0$

The answer is 14575.

7 solutions

Haroun Meghaichi
Aug 4, 2014

This is not optimized at all, I just wrote what I first had in mind since there is only a 100 lines.

l=[];
from ast import literal_eval as jr;
with open('the file', 'r') as fh:
    for line in fh:
        l.append(jr(line));
def sq(x): # indicates whether the list is sorted.
    return sorted(x)==x;     
def shift(x): #the shift function.
    t=x; r=t[-1];
    del(t[-1]);
    return [r]+t;
def f(x): #the function f that is described in the problem.
    t=x;k=0;
    while k<len(t) and not(sq(t)):
        k=k+1;
        t=shift(t);
    if k==len(t):
        return -1;
    else :
        return k;
counting=0; 
for i in range(0,len(l)): #the calculation of the sum.
    counting+=f(l[i]);
print(counting);

You Kad
Jan 4, 2017

from urllib.request import urlopen
from collections import deque
import ast

Sum = 0

with urlopen('http://pastebin.com/raw/VPfpDRVW') as f:
    for line in f:
        L = deque(ast.literal_eval(line.strip().decode("utf-8")))
        n = len(L)
        counter = 0
        while any(L[i]>L[i+1] for i in range(n-1)) and counter < n:
            L.rotate()
            counter+=1
        if counter == n:
            counter = -1
        Sum += counter

print(Sum)

David Holcer
Apr 4, 2015

def chimp(l):
    current=0
    while current<=len(l)+1:
        if (all(l[i] <= l[i+1] for i in xrange(len(l)-1))):
            return current
            break
        elif (current>len(l)):
            return -1
            break
        else:
            l=l[-1:] + l[:-1]
            current+=1
summ=0
filee=open('data.txt',"r")
for i in xrange(100):
    l=[]
    line=filee.readline().split(',')
    for i in line:
        l.append(int(i))
    summ+=chimp(l)
print summ

basic outline with file in location and file stripped of '[' and ']'

Brian Riccardi
Sep 30, 2014

This solution works fine in O(N) where N is the number of integers: for each sequence, I count the times when the i-est integer is strictly less than his predecessor (with the variable " numb ") and I save the lenght of the righmost non-decreasing subsequence (with the variable " j ").

If numb is equal to zero then the sequence is already ordered;
If numb is equal to one then we have to move j integers to order the list;
If numb is bigger than one then there isn't any possible way to order the sequence.

The only bug in this program is the case when numb is equal to one but the rightmost integer of the sequence is bigger than the leftmost integer of the sequence: but it's easy to debug (we have just to introduce a variable to store the leftmost integer of the sequence and then the condition to re-order our list of integer is ( numb == one AND leftmost >= rightmost ) )

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
        freopen("input.txt","r",stdin);

        int prec, n, numb, j, ans=0;
        char x;

        for( int i=0; i<100; i++ ){
                j=numb=0; prec=-1;
                cin >> x;
                do{
                        cin >> n >> x;
                        if( n<prec ){
                                j=0;
                                numb++;
                        }
                        j++;
                        prec=n;
                }while(  x!=']' );

                if( numb==1 ) ans+=j;
                if( numb>1 ) ans--;
        }

        cout << ans << endl;

        return 0;
}

Kenny Lau
Sep 7, 2014

java code:

import java.io.*;
public class brilliant201409071744{
    public static void main(String[] args){
        int sum = 0;
        BufferedReader file = null;
        try{file = new BufferedReader(new FileReader("brilliant201409071744.txt"));}catch(Exception ex){}
        String line;
        try{while(!(line=file.readLine()).equals("")){
            String[] split = line.split(" ");
            int[] numbers = new int[split.length+1];
            for(int i=0;i<split.length;i++) numbers[i] = Integer.parseInt(split[i]);
            numbers[split.length] = numbers[0];
            int f = -2;
            for(int i=0;i<split.length;i++){
                if(numbers[i]>numbers[i+1]){
                    if(f==-2) f = split.length-i-1;
                    else f = -1;
                }
            }
            if(f==-2) f=0;
            sum += f;
        }}catch(Exception ex){}
        System.out.println(sum);
    }
}

output:

14575
Press any key to continue . . .

Note: I have modified the text file to remove all the punctuation marks.

Luciano Riosa
Aug 5, 2014

Pseudocode:

For every set

If the set a is ordered then F(a)=Switch Counter. Stop.
if the set is not orderered:

2.2. the first element<the last one:

F(a) = -1. Stop.

2.3. the first element>=the last one

switch

increase Switch Counter.

goto 1.

Of course with "switch" I meant that the content of the sequence deprived of the last element be shifted to the right by one place, leaving space for putting it on the first position.

Luciano Riosa - 6 years, 10 months ago

Brian Cloutier
Aug 3, 2014

A rather inefficient way of going about things, but luckily computers are fast and the data set was small. The valid lines are rotated arrays of increasing numbers. Find the smallest element then rotate them back, and add the amount you had to rotate by to your accumulator. If 'rotated != sorted(rotated)' we know the original array wasn't an array of increasing numbers, so we subtract one from our accumulator.

import ast

def rotate(array, pivot):
    # the new array starts at the pivot
    return array[pivot:] + array[:pivot]

accum = 0
for line in open('lists').readlines():
    # the data set conveniently uses python syntax
    line = ast.literal_eval(line)

    smallest = line.index(min(line))
    rotated = rotate(line, smallest)

    if rotated != sorted(line):
        accum -= 1
        continue
    if smallest == 0:
        continue
    accum += len(line) - smallest

print accum

This solution isn't actually 100% correct. Consider the input:

[1, 1, 2, 2, 3, 4, 5, 1]

The list is totally valid (it takes 1 shift to sort it), but your code would deem $F(x) = -1$ in that case because it would rotate on the first $1$ , not the one at the end. However, there are in fact no lists in the input file with this property, so the solution works anyway.

My solution is basically the same as yours, except I checked for the wrap-around case. Both solutions are $O(N\:log(N))$ , where $N$ is the length of the list, and minimum bound is $O(N)$ , so I don't know about calling this inefficient. $O(N)$ is probably possible too, though.

Daniel Ploch - 6 years, 10 months ago

A very good point, I am ashamed.

Brian Cloutier - 6 years, 10 months ago

Shifty sort

The answer is 14575.

7 solutions

0 pending reports