The Early Bird Catches The Worm
February 13, 2018
Our solution generates all possible permutations of the four given digits, discards those that are not valid times, and keeps the minimum of those that remain, returning #f if there are no valid times:
(define (time? n)
(and (< (quotient n 100) 24)
(< (modulo n 100) 60)))
(define (earliest xs)
(try (car
(sort <
(filter time?
(map undigits
(permutations xs)))))
#f))
Here are the two examples from the assignment:
> (earliest '(1 2 3 4)) 1234 > (earliest '(6 7 8 9)) #f
This was easy because we reused much from earlier exercises: permutations computes the permutations of a list, undigits converts a list of digits to a number, and try turns an exception (the car of an empty list) to a default value.
You can run the program at https://ideone.com/mmrZAD.
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