From ea0c3961141f01290485e5a947875e20ec5ebe1d Mon Sep 17 00:00:00 2001
From: Mark Thom <markjordanthom@gmail.com>
Date: Thu, 19 Mar 2020 20:42:11 -0600
Subject: [PATCH] add least_time example

---
 src/prolog/examples/least_time.pl | 64 +++++++++++++++++++++++++++++++
 1 file changed, 64 insertions(+)
 create mode 100644 src/prolog/examples/least_time.pl

diff --git a/src/prolog/examples/least_time.pl b/src/prolog/examples/least_time.pl
new file mode 100644
index 00000000..d6bd92b9
--- /dev/null
+++ b/src/prolog/examples/least_time.pl
@@ -0,0 +1,64 @@
+/*  least_time.pl
+ *
+ *  By Mark Thom, 2020
+ *
+ *  find_min_time/2 solves a problem sometimes posed in the first round
+ *  of Google interviews: given a time of day in 24 H format, what is the
+ *  lexographically least permutation of the time that is itself a
+ *  valid time in 24 H format?
+ *
+ *  Full generality is achieved using the reif library.
+ */
+
+:- module(least_time, [find_min_time/2,
+		       write_time_nl/1]).
+
+
+:- use_module(library(dcgs)).
+:- use_module(library(format)).
+:- use_module(library(reif)).
+
+
+permutation([], []).
+permutation([X|Xs], Ys) :-
+    permutation(Xs, Yss),
+    select(X, Ys, Yss).
+
+
+valid_time([H1,H2,M1,M2], T) :-
+    memberd_t(H1, [0,1,2], TH1),
+    memberd_t(H2, [0,1,2,3,4,5,6,7,8,9], TH2),
+    memberd_t(M1, [0,1,2,3,4,5], TM1),
+    memberd_t(M2, [0,1,2,3,4,5,6,7,8,9], TM2),
+    (  maplist(=(true), [TH1, TH2, TM1, TM2]) ->       
+       (  H1 =:= 2 ->
+	  (  H2 =< 3 ->
+	     T = true
+	  ;  T = false
+	  )
+       ;  T = true
+       )
+    ;  T = false
+    ).
+
+
+permuted_times(Time, PermutedTimes) :-
+    setof(P, permutation(Time, P), PermutedTimes0),
+    tfilter(valid_time, PermutedTimes0, PermutedTimes).
+
+
+find_min_time(Time, Min) :-
+    valid_time(Time, true),
+    permuted_times(Time, PermutedTimes),
+    find_min_time_(PermutedTimes, Time, Min).
+
+find_min_time_([], Min, Min).
+find_min_time_([Time|Times], MinSoFar, Min) :-
+    (  Time @< MinSoFar ->
+       find_min_time_(Times, Time, Min)
+    ;  find_min_time_(Times, MinSoFar, Min)
+    ).
+
+
+write_time_nl(Time) :-
+    format("\"~w~w:~w~w\"~n", Time).
-- 
2.54.0