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

Some Haskell. Roll together running a little FSA recognizer and generating the permutations (in lexicographic order):

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.

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

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…

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.