From 0dd39878210616911d720178b091a2e8a5810d26 Mon Sep 17 00:00:00 2001
From: William Carroll <wpcarro@gmail.com>
Date: Fri, 21 Feb 2020 11:30:01 +0000
Subject: Solve InterviewCake's inflight-entertainment problem

Write a predicate that tests whether two films in a list of films can exactly
fill the duration of a flight.
---
 .../deepmind/part_two/inflight-entertainment.ts    | 85 ++++++++++++++++++++++
 scratch/deepmind/part_two/todo.org                 |  2 +-
 2 files changed, 86 insertions(+), 1 deletion(-)
 create mode 100644 scratch/deepmind/part_two/inflight-entertainment.ts

(limited to 'scratch/deepmind')

diff --git a/scratch/deepmind/part_two/inflight-entertainment.ts b/scratch/deepmind/part_two/inflight-entertainment.ts
new file mode 100644
index 000000000000..d6da1db3d313
--- /dev/null
+++ b/scratch/deepmind/part_two/inflight-entertainment.ts
@@ -0,0 +1,85 @@
+function canTwoMoviesFillFlightBonus(
+  xs: Array<number>,
+  duration: number
+): boolean {
+  // Returns true if two movies exist that can fill the flight duration +/- 20
+  // minutes.
+  const seeking = {};
+
+  for (let x of xs) {
+    for (let i = 0; i < 40; i += 1) {
+      if (seeking[x + i + 1]) {
+        return true;
+      }
+    }
+    for (let i = 1; i <= 20; i += 1) {
+      seeking[duration - x - i] = true;
+      seeking[duration - x + i] = true;
+    }
+  }
+
+  return false;
+}
+
+function canTwoMoviesFillFlight(xs: Array<number>, duration: number): boolean {
+  const seeking = {};
+
+  for (let x of xs) {
+    if (seeking[x]) {
+      return true;
+    } else {
+      seeking[duration - x] = true;
+    }
+  }
+
+  return false;
+}
+
+// Tests
+let desc = "short flight";
+let actual = canTwoMoviesFillFlight([2, 4], 1);
+let expected = false;
+assertEquals(actual, expected, desc);
+
+desc = "long flight";
+actual = canTwoMoviesFillFlight([2, 4], 6);
+expected = true;
+assertEquals(actual, expected, desc);
+
+desc = "one movie half flight length";
+actual = canTwoMoviesFillFlight([3, 8], 6);
+expected = false;
+assertEquals(actual, expected, desc);
+
+desc = "two movies half flight length";
+actual = canTwoMoviesFillFlight([3, 8, 3], 6);
+expected = true;
+assertEquals(actual, expected, desc);
+
+desc = "lots of possible pairs";
+actual = canTwoMoviesFillFlight([1, 2, 3, 4, 5, 6], 7);
+expected = true;
+assertEquals(actual, expected, desc);
+
+desc = "not using first movie";
+actual = canTwoMoviesFillFlight([4, 3, 2], 5);
+expected = true;
+assertEquals(actual, expected, desc);
+
+desc = "only one movie";
+actual = canTwoMoviesFillFlight([6], 6);
+expected = false;
+assertEquals(actual, expected, desc);
+
+desc = "no movies";
+actual = canTwoMoviesFillFlight([], 2);
+expected = false;
+assertEquals(actual, expected, desc);
+
+function assertEquals(a, b, desc) {
+  if (a === b) {
+    console.log(`${desc} ... PASS`);
+  } else {
+    console.log(`${desc} ... FAIL: ${a} != ${b}`);
+  }
+}
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
index e734c23abdb8..a51ee9c59017 100644
--- a/scratch/deepmind/part_two/todo.org
+++ b/scratch/deepmind/part_two/todo.org
@@ -5,7 +5,7 @@
 ** DONE Merge Sorted Arrays
 ** DONE Cafe Order Checker
 * Hashing and hash tables
-** TODO Inflight Entertainment
+** DONE Inflight Entertainment
 ** TODO Permutation Palindrome
 ** TODO Word Cloud Data
 ** TODO Top Scores
-- 
cgit 1.4.1