Generowanie czasu z numerów

Question

Mam numery jako x, y, z i w. Próbuję stworzyć maksymalny możliwy czas w formacie 24-godzinnym. Przykład:

Moje podejście polega na posortowaniu wszystkich liczb. Następnie przez kilka godzin sprawdź liczbę mniejszą niż równą 2, następnie dla następnej cyfry w godzinie, sprawdź liczbę mniejszą niż równą 4, itd. Również dla minut. (0-60 minut)

Czy inne skuteczne rozwiązanie niż rozwiązanie bruteforce?

Answer 1

Chciałbym mieć metodę, którą można podać predykatu, który wyodrębnia najwyższą wartość, która pasuje do predykatu.

np.

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 2

Dla wejścia 1 2 9 9, jedyną możliwością jest 19:29, ale to, co można opisać wybiera dwa pierwsze i dostaje 21:99, nieprawidłowy czas.

Jeśli nie jest to rzeczywiście wąskie gardło, a nie ćwiczenie programistyczne, najprostszym rozwiązaniem jest wypróbowanie wszystkich możliwych permutacji cyfr, dla każdego z nich sprawdzenie, czy jest to poprawny czas, i pobranie maksymalnego poprawnego leksyku.

Chodzi o to, że istnieją szybkie rozwiązania i istnieją poprawne rozwiązania. W tym przypadku szybkie rozwiązanie jest trudne, więc jeśli czas działania programu nie jest krytyczny, należy rozważyć możliwość wyboru wolniejszego, ale bardziej oczywistego rozwiązania. Zapewne będzie to, jako programista, więcej czasu na rozwiązanie innych problemów, w których liczy się czas działania.

Niestety, Java wydaje się nie zapewniać wbudowanej następnej metody, ale Stackoverflow sure does.

Answer 3

Proste podejście polegałoby na stworzeniu wszystkich możliwych kombinacji wszystkich cyfr z czterech cyfr. Następnie posortuj i wybierz wszystkie wartości mniejsze niż 2359 (Maksymalny dozwolony czas). Następnie zacznij od maksymalnej liczby i po prostu sprawdź, czy jest to właściwy czas, jeśli nie sprawdź następnego największego numeru.

Answer 4

Zasadniczo można zamiast wszystkich permutacji stworzyć warunki dla każdej wartości w tablicy. Na przykład, jeśli mamy 2, wiemy, że godzina powinna wynosić 2 dla naszej dziesiątki, ale nasze jedyne miejsce na godzinę może wynosić tylko 3 w tym punkcie. Jeśli mamy 1, to znamy nasze jedno miejsce, bo godzina może wynosić 9. Wiemy, że nasza minuta to 10, a nasza maksymalna minuta to 9. Czas utworzenia pokazuje te warunki. FindMaxSpecific zwraca -1, jeśli nie jest w stanie znaleźć poprawnej liczby w podanej macierzy. W ten sposób wiemy, że czas jest nieważny, jeśli kiedykolwiek otrzymamy tablicę zwróconą przez createTime z -1. Zobacz przykładowy wynik.

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; 
} 

Na końcu tego wszystkiego jest, jeśli jakakolwiek wartość wraca jako -1 wiemy, że mamy nieprawidłowy czas dostaliśmy

Przykład

 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]); 

Wyjście jest

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

Answer 5

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) 

tutaj twój possible funkcja powinna policzyć cyfry w godzinach, minutach i na wejściu i upewnić się, że się zrównają.

Answer 6

Interesujący problem. Wydaje się nieco bardziej skomplikowany, niż się wydaje. Oto skrypt Pythona dla problemu.

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