Problem of the Day -- Sort Times

Sort Times

Woohoo it's Monday!!! We've got some interesting problems coming up this week so let's get started.

The owner of a 24 hour gym has coming to us asking for some help. The owner needs to list the gym's class schedule in a sorted order. The classes start at noon (12) and go to 3 in the morning. Given an array of integers 0-23 inclusive, sort them so that you start at 12 and go to 11, wrapping from 23 to 0.

Sample input:

[2,1,12,3,16,19,23]

Sample output:

[12,16,19,23,1,2,3]

For a bonus convert the times to a pretty string representation such as 16 = 4pm

Permalink: http://problemotd.com/problem/sort-times/

Comments:

Kevin - 10 years, 9 months ago

Here's a potential solution. Very hacky for the formatter. :-)

def sorter(times):
    am = [t for t in times if t<12]
    pm = list(set(times) - set(am))
    return sorted(pm) + sorted(am)

def formatter(times):
    formatted = []
    for t in times:
        suf = 'pm' if t > 11 else 'am'
        time = t % 12 if t % 12 != 0 else 12
        formatted.append(str(time) + suf)
    return formatted

formatter(sorter([0,2,1,12,3,16,19,23]))

reply permalink

Anonymous - 10 years, 9 months ago

J solution, bonus is for later.

sorttimes=: [: (|.~ i.&12) /:~

sorttimes 2 1 12 3 16 19 23  NB. => 12 16 19 23 1 2 3

reply permalink

Anonymous - 10 years, 9 months ago

Python solution:

def sort_times(times):
    return sorted(times, key=lambda x: x if x >= 12 else x+24)

def prettify_time(time):
    return str(time)+'am' if time < 12 else str(time-12)+'pm'

print(list(map(prettify_time, sort_times([2,1,12,3,16,19,23]))))

reply permalink

Tobias Frilling - 10 years, 9 months ago
```
(sort-by #(mod (+ 23 %) 27) [2 1 12 3 16 19 23])
```
reply permalink

Hueho - 10 years, 9 months ago

def sort(arr)
  arr.partition {|n| n >= 12 && n <= 23 }.map(&:sort).flatten
end

def pretty(time)
  hour = if time == 0 || time == 12 then 12 else time % 12 end
  suffix = if time / 2 > 1 then 'pm' else 'am' end
  "#{hour}#{suffix}"
end

def problemotd(arr)
  sort(arr).map { |t| pretty t }
end

reply permalink

Pearce Keesling - 10 years, 9 months ago
Wrote this in C, kind of cheated by using the standard library's sort function. I don't feel too bad though because the sort itself is trivial and irrelevant :). At first I ignored the formatting because I dislike dealing with strings, but I'm I glad I went back and fixed it because I learned some good stuff.

''' #include <stdio.h> #include <stdlib.h> #include <string.h>

int compare(const void* a, const void* b) { return ((int)a-(int)b); }

int main(int argc,char* argv[]) { int times[15]; char* token; char str[strlen(argv[1])+1]; strcpy(str,argv[1]); char* p = str; p++; p[strlen(p)-1] = 0; token = strtok(p,","); int count =0; while(token!=NULL) { times[count] = atoi(token); if(times[count] < 12)times[count] += 24; count++; token= strtok(NULL,","); } qsort(times,count,sizeof(int),compare); char out[400]; out[0] = '\0'; for(int* i = times;i<times+ count;i++) { int delta = 0; if(*i>24)delta=24; char buff[7]; sprintf(buff,"%d%s,",*i-delta,(delta!=0?"am":"pm")); strcat(out,buff); } out[strlen(out)-1]=0; printf("[%s]\n",out);
```
return 0;
```
} '''

keep up the great work :)

reply permalink

Pearce Keesling - 10 years, 9 months ago

Seriously need some accounts so I can edit my posts :P (or atleast some preview).

code in proper format:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b)
{
    return (*(int*)a-*(int*)b);
}

int main(int argc,char* argv[])
{
    int times[15];
    char* token;
    char str[strlen(argv[1])+1];
    strcpy(str,argv[1]);
    char* p = str;
    p++;
    p[strlen(p)-1] = 0;
    token = strtok(p,",");
    int count =0;
    while(token!=NULL)
    {
        times[count] = atoi(token);
        if(times[count] < 12)times[count] += 24;
        count++;
        token= strtok(NULL,",");
    }
    qsort(times,count,sizeof(int),compare);
    char out[400];
    out[0] = '\0';
    for(int* i = times;i<times+ count;i++)
    {
        int delta = 0;
        if(*i>24)delta=24;
        char buff[7];
        sprintf(buff,"%d%s,",*i-delta,(delta!=0?"am":"pm"));
        strcat(out,buff);
    }
    out[strlen(out)-1]=0;
    printf("[%s]\n",out);

    return 0;
}

reply permalink

vick - 10 years, 9 months ago

Java solution ``` public class SortTimes {

private static int[] sortTimes(int[] times) {
    int SHIFT = 24;
    return IntStream.of(times).map(a -> a <= 3 ? SHIFT + a : a).sorted().map(
            a -> a >= SHIFT ? a - SHIFT : a).toArray();
}

private static List<String> formatTimes(int[] times) {
    return IntStream.of(times).mapToObj(a -> a <= 12 ? a + " am" : a - 12 + " pm").collect(Collectors.toList());
}

public static void main(String[] args) {
    System.out.println(formatTimes(sortTimes(new int[]{2, 1, 12, 3, 16, 19, 23})));
}

} ```

reply permalink

asandwich - 10 years, 9 months ago

Lamdas make stuff so clean! Did it without them.

public class Main {
    public static void main(String[] args)
    {
        int[] arr = {2,1,12,3,16,19,23};
        ArrayList<Integer> less = new ArrayList<Integer>();
        ArrayList<Integer> more = new ArrayList<Integer>();

        for(int i : arr)
            if (i < 4) less.add(i);
            else more.add(i);
        Collections.sort(less);
        Collections.sort(more);
        System.out.print("[");
        for(int i : more)
            System.out.print(i + ",");
        for(int i = 0; i < less.size()-1; i++)
            System.out.print(less.get(i) + ",");
        System.out.println(less.get(less.size() -1) + "]");
    }
}

reply permalink

Greg - 10 years, 9 months ago
In Scala (I just started learning it) ''' var times = Array(2,1,12,3,16,19,23) val low = for(i <- times if i < 12) yield i val high = for(i <- times if i >= 12) yield i times = high.sorted ++ low.sorted for(i <- times) println(i) '''

reply permalink
Greg - 10 years, 9 months ago
trying again with format scala var times = Array(2,1,12,3,16,19,23) val low = for(i <- times if i < 12) yield i val high = for(i <- times if i >= 12) yield i times = high.sorted ++ low.sorted for(i <- times) println(i)

reply permalink
Greg - 10 years, 9 months ago
Sigh.... scala var times = Array(2,1,12,3,16,19,23) val low = for(i <- times if i < 12) yield i val high = for(i <- times if i >= 12) yield i times = high.sorted ++ low.sorted for(i <- times) println(i)

reply permalink

gsathya - 10 years, 9 months ago

All of the answers here use sorting, which is not needed. There's an upper bound on the max value in the array, so you just need constant space and count sort to solve this problem.

This runs in O(n), whereas all the other sorting based solutions need O(nlogn).


ip = [2,1,12,3,16,19,23]
array = [0]*24
ans = []

for i in ip:
    array[i]+=1

for id, i in enumerate(array[12:]):
    if i == 0:
        continue

    for t in range(i):
        ans.append(id+12)

for id, i in enumerate(array[:12]):
    if i == 0:
        continue

    for t in range(i):
        ans.append(id)

print ans

reply permalink

Anonymous - 10 years, 7 months ago
Nice solution! But interesting to note that this is also technically a type of sort: http://en.wikipedia.org/wiki/Bucket_sort

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Sort Times

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri