The Early Bird Catches The Worm
February 13, 2018
Today we have another homework problem:
What is the earliest time of day (using a 24-hour clock) that can be written with four given digits? For instance, given the digits 1, 2, 3, and 4, times like 14:32 and 23:14 can be written, but the earliest time is 12:34. Your program should report that no time can be formed with digits 6, 7, 8 and 9.
Your task is to find the earliest time of day that can be written by four digits. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Some Haskell. Roll together running a little FSA recognizer and generating the permutations (in lexicographic order):
split [] = [] split (a:s) = (a,s) : map f (split s) where f (b,s) = (b,a:s) match s = map reverse (f 0 [] s) where -- FSA function f n t s = concatMap (g n) (split s) where -- state transition g 0 (0,s) = f 1 (0:t) s g 0 (1,s) = f 1 (1:t) s g 0 (2,s) = f 2 (2:t) s g 1 (a,s) | a >= 0 && a <= 9 = f 3 (a:t) s g 2 (a,s) | a >= 0 && a <= 3 = f 3 (a:t) s g 3 (a,s) | a >= 0 && a <= 5 = f 4 (a:t) s g 4 (a,s) | a >= 0 && a <= 9 = [(a:t)] g _ _ = [] main = print (match [1,2,3,4]) >> print (match [1,4,5,6]) >> print (match [6,7,8,9]) >> return ()I wanted a more direct computation of just the required answer
(minimum feasible time). Here is an implementation in standard R7RS
Scheme, plus ‘sort’ and ‘take’. It was surprisingly troublesome. As a
slight generalization, it accepts also accepts more than 4 digits in
its input.
(import (scheme base) (scheme write) (only (srfi 1) take) (only (srfi 43) vector-swap!) (only (srfi 95) sort)) (define (earliest-time/digits digits) (let ((dvec (list->vector (take (sort digits <) 4)))) ;; dvec is now optimal, but perhaps not feasible (when (> (vector-ref dvec 2) 5) ;; Smallest potentially feasibility-restoring change from optimal: (vector-swap! dvec 1 2)) ;; Check feasibility; failure means no feasible solution (and (or (<= (vector-ref dvec 0) 1) (and (= (vector-ref dvec 0) 2) (<= (vector-ref dvec 1) 3))) (<= (vector-ref dvec 2) 5) (vector->list dvec)))) (for-each (lambda (lst) (display lst) (display (earliest-time/digits lst)) (newline)) '((1 2 3 4) (6 7 8 9) (1 8 2 6) (8 9 1 3) (8 9 2 3 5 1 3 3)))I notice my solution doesn’t handle inputs with repeated elements well – removing duplicates from the output of split should fix this (and the input must be ordered to get the output in lexicographic order of course).
Here’s a solution in C. It loops over all permutations of the four digits in lexicographic order, returning the first valid time (if found).
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> static inline void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } bool earliest_time(int* input, int* output) { size_t n = 4; memcpy(output, input, sizeof(int) * n); // Bubble sort while (true) { bool done = true; for (size_t i = 1; i < n; ++i) { if (output[i] < output[i-1]) { swap(&output[i], &output[i-1]); done = false; } } if (done) break; } // Algorithm L (Lexicographic permutation generation) // from TAOCP Section 7 while (true) { size_t j, l, k; int hour = (output[0] * 10) + output[1]; int minute = (output[2] * 10) + output[3]; if (hour < 24 && minute < 60) return true; j = n - 2; while (output[j] >= output[j+1]) { if (j == 0) return false; --j; } l = n - 1; while (output[j] >= output[l]) --l; swap(&output[j], &output[l]); k = j + 1; l = n - 1; while (k < l) { swap(&output[k], &output[l]); ++k; --l; } } } int main(int argc, char* argv[]) { char usage[] = "Usage: earliest_time <FOUR_DIGITS>"; if (argc != 2) { fprintf(stderr, "%s\n", usage); return EXIT_FAILURE; } int output[4]; int digits[4]; const char ASCII_0 = 48; if (strlen(argv[1]) != 4) { fprintf(stderr, "%s\n", usage); return EXIT_FAILURE; } for (size_t i = 0; i < 4; ++i) { char char_digit = argv[1][i]; if (char_digit < ASCII_0 || char_digit > ASCII_0 + 9) { fprintf(stderr, "%s\n", usage); return EXIT_FAILURE; } digits[i] = char_digit - ASCII_0; } bool success = earliest_time(digits, output); if (success) { printf("%d%d:%d%d\n", output[0], output[1], output[2], output[3]); } else { printf("N/A\n"); } return EXIT_SUCCESS; }Example Usage:
C# solution. This takes advantage of the fact that the earliest time, if a valid time exists, can be obtained by sorting the digits (ascending), and swapping the 2nd and 3rd digits if the the 3rd digit is > 5. Unless I’ve missed a case…
using System; using System.Collections.Generic; using System.Linq; namespace EarlyBird { class Program { static string Earliest24HourTime(List<int> digits) { if (digits.Count != 4 || digits.Any(x => x > 9)) throw new ArgumentException("Must supply 4 single digit values."); digits.Sort(); if (digits[2] > 5) { int temp = digits[1]; digits[1] = digits[2]; digits[2] = temp; } if (digits[2] > 5 || digits[0] > 2 || (digits[0] == 2 && digits[1] > 3)) { return "None"; } return string.Join("", digits); } static void Main(string[] args) { Console.WriteLine(Earliest24HourTime(new List<int> { 0, 0, 0, 0 })); Console.WriteLine(Earliest24HourTime(new List<int> { 9, 9, 0, 0 })); Console.WriteLine(Earliest24HourTime(new List<int> { 1, 2, 3, 4 })); Console.WriteLine(Earliest24HourTime(new List<int> { 1, 8, 2, 6 })); Console.WriteLine(Earliest24HourTime(new List<int> { 8, 9, 1, 3 })); Console.WriteLine(Earliest24HourTime(new List<int> { 6, 7, 8, 9 })); } } }Example Output:
I see that chaw had already posted the same approach to solving the problem. I need to get better at reading scheme code.
Another Haskell version.
import Control.Applicative ((<|>)) import Data.List (sort) import Data.Maybe (maybe) import Text.Printf (PrintfArg, printf) data Time a = Time a a a a -- The earliest time, if any, that can be made from the given digits. earliest :: Integral a => a -> a -> a -> a -> Maybe (Time a) earliest h0 h1 m0 m1 = maybeTime' $ sort [h0, h1, m0, m1] -- Make time from a list of digits. maybeTime' :: Integral a => [a] -> Maybe (Time a) maybeTime' [h0, h1, m0, m1] = maybeTime h0 h1 m0 m1 <|> maybeTime h0 m0 h1 m1 maybeTime' _ = Nothing -- Make time from four digits. maybeTime :: Integral a => a -> a -> a -> a -> Maybe (Time a) maybeTime h0 h1 m0 m1 | h0 `inRange` (0, 2) && h1 `inRange` (0, 9) && m0 `inRange` (0, 5) && m1 `inRange` (0, 9) = Just $ Time h0 h1 m0 m1 | otherwise = Nothing -- True iff lo ≤ x ≤ hi. inRange :: Ord a => a -> (a, a) -> Bool inRange x (lo, hi) = x >= lo && x <= hi -------------------------------------------------------------------------------- -- Show the time in a nice format. prettyTime :: PrintfArg a => Time a -> String prettyTime (Time h0 h1 m0 m1) = printf "%d%d:%d%d" h0 h1 m0 m1 test :: Int -> Int -> Int -> Int -> IO () test i j k l = printf "%d %d %d %d -> %s\n" i j k l time where time = maybe "no valid time" prettyTime $ earliest i j k l main :: IO () main = do test 3 1 4 2 test 9 7 6 8 test 0 0 0 0 test 4 9 0 1 test 5 3 9 2 test 9 9 0 0