Number Generation Time

Question

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

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

Is there any other effective approach than bruteforce solution?

Answer 1

A simple approach would be to create all possible combinations of the entire four-digit number. Then sort and select all values ​​less than 2359 (Maximum time allowed). After that, you start with the maximum number and simply check if this time is correct if you do not check the next largest number.

Answer 2

Basically, what you can do is not all the permutations that you create for each value in the array. For example, if we have 2, we know that the hour should be 2 for our ten places, but our spots for the hour can only be 3 at that moment. If we have 1, then we know that our one place for an hour can be 9. We know that our ten minute spot is 5 and our maximum minute point is 9. createTime shows these conditions. The findMaxSpecific function returns -1 if it cannot find a valid number in the given array. So we know that time is invalid if we ever get the array returned by createTime with -1 in it. See sample 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, if any value is returned as -1, we know that we have an invalid time given to us

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

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

Answer 3

To enter 1 2 9 9 only option is 19:29 , but what you describe selects the first two and gets 21:99 , an invalid time.

If this is really a bottleneck, and not a programming exercise, the easiest solution is to try all possible permutations of numbers, for each of them, check whether it is a real time, and take the lexicographically maximum permissible string.

The fact is that there are quick solutions and there are the right decisions. Here, a quick solution is difficult, therefore, if the program’s runtime is not critical, consider choosing a slower, but more obvious solution. This may give you, as a programmer, more time to solve other problems in which running time matters.

Unfortunately, Java doesn't seem to provide the built-in nextPermutation method, but Stackoverflow is sure it 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 numbers in hours, minutes and input and make sure that they are equal.

Answer 5

I will have a method that you can give a predicate that retrieves the highest value that matches the predicate.

eg.

 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

An interesting problem. Seems a little more complicated than it sounds. Below is an example python script.

 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