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.

Advertisements

Pages: 1 2

7 Responses to “The Early Bird Catches The Worm”

  1. matthew said

    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 ()
    
    $ ./times.hs 
    [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1]]
    [[1,4,5,6],[1,5,4,6],[1,6,4,5],[1,6,5,4]]
    []
    
  2. chaw said

    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)))
    
    (1 2 3 4) (1 2 3 4)
    (6 7 8 9) #f
    (1 8 2 6) (1 6 2 8)
    (8 9 1 3) (1 8 3 9)
    (8 9 2 3 5 1 3 3) (1 2 3 3)
    

  3. matthew said

    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).

  4. Daniel said

    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:

    $ earliest_time 1234
    
    12:34
    
    $ earliest_time 6789
    
    N/A
    
    $ earliest_time 0178
    
    07:18
    
  5. nobody said

    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:

    0000
    0909
    1234
    1628
    1839
    None
    
  6. nobody said

    I see that chaw had already posted the same approach to solving the problem. I need to get better at reading scheme code.

  7. Globules said

    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
    
    $ ./earlybird 
    3 1 4 2 -> 12:34
    9 7 6 8 -> no valid time
    0 0 0 0 -> 00:00
    4 9 0 1 -> 01:49
    5 3 9 2 -> 23:59
    9 9 0 0 -> 09:09
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: