Generating time from numbers

Question

I have numbers as x,y,z, and w. I am trying to create max possible time in 24 hours format. Example:

My approach is to sort the all numbers. Then for hours check the number less than equal 2, then for next digit in hour, check number less then equal to 4, and so on for minutes also. (0-60 minutes)

Is any other efficient approach than bruteforce solution?

Answer 1

Simple approach would be to create all possible combinations of all the number from four digits. Then sort and pick out all the values less than 2359 (Max time allowed). After this you start with the max number and just validate if it is a correct time if not check the next biggest number.

Answer 2

Basically what you can do is instead of all permutations you create conditions for each value in the array. For example if we have a 2 we know the hour should be 2 for our ten spot but our ones spot for the hour can only be 3 at that point. If we have a 1 then we know our one spot for the hour can be 9. We know our minute ten spot is 5 and our max minute one spot is 9. createTime shows these conditions. The findMaxSpecific returns -1 if it isn't able to find a valid number in the given array. That way we know the time is invalid if we ever get an array returned by createTime with -1's in it. See example output.

public static int[] createTime(int[] numbers)
{
    int[] time = new int[4];
    time[0] = findMaxSpecific(numbers, 2);
    time[1] = time[0] == 2 ? findMaxSpecific(numbers, 3) : findMaxSpecific(numbers, 9);
    time[2] = findMaxSpecific(numbers, 5);
    time[3] = findMaxSpecific(numbers, 9);

    return time;
}

public static int findMaxSpecific(int[] arr, int valToFind)
{
    if(arr.length != 4)
        return -1;

    int numToFind = -1; 
    int indexToRemove = -1;


    for(int i = 0; i < arr.length; i++)
    {
        if(arr[i] <= valToFind)
        {
            if(arr[i] > numToFind)
            {
                numToFind = arr[i];
                indexToRemove = i;
            }
        }
    }

    if(indexToRemove == -1)
        return -1;

    arr[indexToRemove] = -1;

    return numToFind;
}

At the end of all this is if any value comes back as -1 we know we have an invalid time we were given

Example

        int[] time = new int[4];
        int[] numbers = {1,2,3,4};
        time = createTime(numbers);
        System.out.println(time[0] + "" + time[1] + ":" + time[2] + "" + time[3]);
        int[] numbers2 = {0,9,7,1};
        time = new int[4];
        time = createTime(numbers2);
        System.out.println(time[0] + "" + time[1] + ":" + time[2] + "" + time[3]);

        int[] numbers3 = {9,9,9,9};
        time = new int[4];
        time = createTime(numbers3);
        System.out.println(time[0] + "" + time[1] + ":" + time[2] + "" + time[3]);

Output is

23:41
19:07
-19:-19 //invalid numbers

Answer 3

For input 1 2 9 9, the only possibility is 19:29, but what you describe picks the two first and gets 21:99, an invalid time.

Unless this is indeed a bottleneck and not a programming exercise, the most straightforward solution is to try all possible permutations of the digits, for each one, check whether it constitutes a valid time, and take the lexicographically maximal valid string.

The point is, there are fast solutions and there are correct solutions. Here, the fast solution is tricky, so if program running time is not critical, do consider the possibility to pick the slower but more obvious solution. This will perhaps give you, as a programmer, more time to tackle the other problems where running time does matter.

Sadly, Java does not seem to provide a builtin nextPermutation method, but Stackoverflow sure does.

Answer 4

input = (1,2,3,4)
ans = None
for hour in range(0, 24):
    for minute in range(0,60):
        if possible(hour, minute, input):
            ans = "%s:%s" % (hour, minute)

here your possible function should count the digits in hour, minute and input and make sure they equate.

Answer 5

I would have a method you can give a predicate which extract the highest value which matches the predicate.

e.g.

public static int highest(List<Integer> values, Predicate<Integer> test) {
    Integer max = values.stream()
                        .filter(test)
                        .max(Comparator.natrualOrder())
                        .orElseThrow(() -> new InvalidStateException());
    values.remove(max);
    return max;
}

int digit1 = highest(list, i -> i < 3);
int digit3 = highest(list, i -> i < 6);
int digit2 = highest(list, i -> digit1 < 2 || i < 4);
int digit4 = highest(list, i -> true);

Answer 6

Interesting problem. Seems a little bit more complex than it appears. Here is a python script for the problem.

def getmin(num):   # check if two digits are valid for minutes
    min = -1
    sum = num[0] * 10 + num[1]
    if sum < 60:
        min = sum
    sum = num[1] * 10 + num[0]
    if sum < 60 and min < sum:
        min = sum
    return min

def maxtime(num):
    hour = -1
    min = -1
    h1 = 0
    h2 = 0
    for i in range(4):
        for j in range(4):  # these two loops are to get maxi hour, if possible
             if i != j:
                 sum = num[i] * 10 + num[j]
                 if hour < sum and sum < 24:
                     c = num[:]     # get a copy of input digits
                     if i > j:      # delete numbers used in hour
                         del c[i]
                         del c[j]
                     else:
                         del c[j]
                         del c[i]
                     if getmin(c) > -1: 
                         h1 = i
                         h2 = j
                         hour = sum
    if hour > -1:
        if h2 > h1:      # delete numbers used in hour
            del num[h2]
            del num[h1]
        else:
            del num[h1]
            del num[h2]

        min = getmin(num)

        if min > -1:
            print(str(hour) + ':' + str(min))

    if hour < 0 or min < 0:
        print("no solution")

maxtime([4, 8, 1, 9])
maxtime([7, 3, 4, 2])
maxtime([9, 2, 2, 5])
maxtime([9, 2, 7, 3])

#19:48
#23:47
#22:59
#no solution