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

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 * 10) + output;
int minute = (output * 10) + output;
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;
int digits;
const char ASCII_0 = 48;
if (strlen(argv) != 4) {
fprintf(stderr, "%s\n", usage);
return EXIT_FAILURE;
}
for (size_t i = 0; i < 4; ++i) {
char char_digit = argv[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, output, output, output);
} 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 > 5)
{
int temp = digits; digits = digits; digits = temp;
}

if (digits > 5 || digits > 2 || (digits == 2 && digits > 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

```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
```