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.

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: