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

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.