Problem 49 i.e. P3.04 done for Java

shekhargulati · shekhargulati · commit 7bc7ca53823d · 2016-02-26T17:09:47.000+05:30
diff --git a/java8/README.md b/java8/README.md
@@ -742,3 +742,32 @@ Skipping this problem for now.
 ### [P48](https://github.com/shekhargulati/99-problems/blob/master/java8/src/main/java/com/shekhargulati/ninetynine_problems/java8/_03_logic_and_codes/P48.java) **(\*\*)  Truth tables for logical expressions (3).**
 
 Skipping this problem for now.
+
+
+### [P49](https://github.com/shekhargulati/99-problems/blob/master/java8/src/main/java/com/shekhargulati/ninetynine_problems/java8/_03_logic_and_codes/P49.java) **(\*\*)  Gray code.**
+
+An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,
+```
+n = 1: C(1) = ['0','1'].
+n = 2: C(2) = ['00','01','11','10'].
+n = 3: C(3) = ['000','001','011','010','110','111','101','100'].
+```
+```java
+@Test
+public void shouldFindGrayCodeWhenNIs1() throws Exception {
+    List<String> graySequence = P49.gray(1);
+    assertThat(graySequence, contains("0", "1"));
+}
+
+@Test
+public void shouldFindGrayCodeWhenNIs2() throws Exception {
+    List<String> graySequence = P49.gray(2);
+    assertThat(graySequence, contains("00", "01", "11", "10"));
+}
+
+@Test
+public void shouldFindGrayCodeWhenNIs3() throws Exception {
+    List<String> graySequence = P49.gray(3);
+    assertThat(graySequence, contains("000", "001", "011", "010", "110", "111", "101", "100"));
+}
+```
diff --git a/java8/src/main/java/com/shekhargulati/ninetynine_problems/java8/_03_logic_and_codes/P49.java b/java8/src/main/java/com/shekhargulati/ninetynine_problems/java8/_03_logic_and_codes/P49.java
@@ -0,0 +1,29 @@
+package com.shekhargulati.ninetynine_problems.java8._03_logic_and_codes;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.stream.Stream;
+
+import static java.util.stream.Collectors.toList;
+
+/**
+ * (**) Gray code.
+ * An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,
+ * n = 1: C(1) = ['0','1'].
+ * n = 2: C(2) = ['00','01','11','10'].
+ * n = 3: C(3) = ['000','001','011','010','110','111','101','100'].
+ */
+public class P49 {
+
+    public static List<String> gray(int n) {
+        if (n == 1) {
+            return Arrays.asList("0", "1");
+        }
+        List<String> original = gray(n - 1);
+        List<String> reversed = new ArrayList<>(original);
+        Collections.reverse(reversed);
+        return Stream.concat(original.stream().map(s -> "0" + s), reversed.stream().map(s -> "1" + s)).collect(toList());
+    }
+}
diff --git a/java8/src/test/java/com/shekhargulati/ninetynine_problems/java8/_03_logic_and_codes/P49Test.java b/java8/src/test/java/com/shekhargulati/ninetynine_problems/java8/_03_logic_and_codes/P49Test.java
@@ -0,0 +1,30 @@
+package com.shekhargulati.ninetynine_problems.java8._03_logic_and_codes;
+
+import org.junit.Test;
+
+import java.util.List;
+
+import static org.hamcrest.collection.IsIterableContainingInOrder.contains;
+import static org.junit.Assert.assertThat;
+
+public class P49Test {
+
+    @Test
+    public void shouldFindGrayCodeWhenNIs1() throws Exception {
+        List<String> graySequence = P49.gray(1);
+        assertThat(graySequence, contains("0", "1"));
+    }
+
+    @Test
+    public void shouldFindGrayCodeWhenNIs2() throws Exception {
+        List<String> graySequence = P49.gray(2);
+        assertThat(graySequence, contains("00", "01", "11", "10"));
+    }
+
+    @Test
+    public void shouldFindGrayCodeWhenNIs3() throws Exception {
+        List<String> graySequence = P49.gray(3);
+        assertThat(graySequence, contains("000", "001", "011", "010", "110", "111", "101", "100"));
+    }
+
+}
