Grains approaches (exercism#2234)

bobahop · web-flow · commit 1bbd99e4600f · 2023-01-20T14:23:14.000+01:00
* Create config.json

* Create introduction.md

* Create snippet.txt

* Create content.md

* Create snippet.txt

* Create content.md
diff --git a/exercises/practice/grains/.approaches/bit-shifting/content.md b/exercises/practice/grains/.approaches/bit-shifting/content.md
@@ -0,0 +1,57 @@
+# Bit-shifting
+
+```java
+import java.math.BigInteger;
+
+class Grains {
+
+    BigInteger grainsOnSquare(final int square) {
+        if (square < 1 || square > 64) {
+            throw new IllegalArgumentException("square must be between 1 and 64");
+        }
+        return BigInteger.ONE.shiftLeft(square - 1);
+    }
+
+    BigInteger grainsOnBoard() {
+        return BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE);
+    }
+}
+```
+
+To calculate the grains on a square you can set a bit in the correct position of a [`BigInteger`][biginteger] value.
+
+To understand how this works, consider just two squares that are represented in binary bits as `00`.
+
+You use the [`BigInteger.shiftLeft()`][shiftleft] method to set `1` (i.e. [`BigInteger.ONE`][one]) at the position needed to make the correct decimal value.
+- To set the one grain on Square One you shift `1` for `0` positions to the left.
+So, if `square` is `1` for square One, you subtract `square` by `1` to get `0`, which will not move it any positions to the left.
+The result is binary `01`, which is decimal `1`.
+- To set the two grains on Square Two you shift `1` for `1` position to the left.
+So, if `square` is `2` for square Two, you subtract `square` by `1` to get `1`, which will move it `1` position to the left.
+The result is binary `10`, which is decimal `2`.
+
+| Square  | Shift Left By | Binary Value | Decimal Value |
+| ------- | ------------- | ------------ | ------------- |
+|       1 |             0 |         0001 |             1 |
+|       2 |             1 |         0010 |             2 |
+|       3 |             2 |         0100 |             4 |
+|       4 |             3 |         1000 |             8 |
+
+For `grainsOnBoard` we want all of the 64 bits set to `1` to get the sum of grains on all sixty-four squares.
+The easy way to do this is to set the 65th bit to `1` and then subtract `1`.
+To go back to our two-square example, if we can grow to three squares, then we can shift `BigInteger.ONE` two positions to the left for binary `100`,
+which is decimal `4`.
+By subtracting `1` we get `3`, which is the total amount of grains on the two squares.
+
+| Square  | Binary Value | Decimal Value |
+| ------- | ------------ | ------------- |
+|       3 |         0100 |             4 |
+
+| Square  | Sum Binary Value | Sum Decimal Value |
+| ------- | ---------------- | ----------------- |
+|       1 |             0001 |                 1 |
+|       2 |             0011 |                 3 |
+
+[biginteger]: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html
+[shiftleft]: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#shiftLeft(int)
+[one]: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#ONE
diff --git a/exercises/practice/grains/.approaches/bit-shifting/snippet.txt b/exercises/practice/grains/.approaches/bit-shifting/snippet.txt
@@ -0,0 +1,6 @@
+BigInteger grainsOnSquare(final int square) {
+    if (square < 1 || square > 64) {
+        throw new IllegalArgumentException("square must be between 1 and 64");
+    }
+    return BigInteger.ONE.shiftLeft(square - 1);
+}
diff --git a/exercises/practice/grains/.approaches/config.json b/exercises/practice/grains/.approaches/config.json
@@ -0,0 +1,21 @@
+{
+  "introduction": {
+    "authors": ["bobahop"]
+  },
+  "approaches": [
+    {
+      "uuid": "92f88a04-31e2-4ae9-8f05-55b290490ad0",
+      "slug": "pow",
+      "title": "Pow",
+      "blurb": "Use BigInteger.pow to raise 2 by a specified power.",
+      "authors": ["bobahop"]
+    },
+    {
+      "uuid": "00186454-8013-4f5e-9177-cdab3ef98a31",
+      "slug": "bit-shifting",
+      "title": "Bit-shifting",
+      "blurb": "Use bit-shifting to raise 2 by a specified power.",
+      "authors": ["bobahop"]
+    }
+  ]
+}
diff --git a/exercises/practice/grains/.approaches/introduction.md b/exercises/practice/grains/.approaches/introduction.md
@@ -0,0 +1,74 @@
+# Introduction
+
+There are various idiomatic approaches to solve Grains.
+You can use `BigInteger.pow()` to calculate the number on grains on a square.
+Or you can use bit-shifting.
+
+## General guidance
+
+The key to solving Grains is to focus on each square having double the amount of grains as the square before it.
+This means that the amount of grains grows exponentially.
+The first square has one grain, which is `2` to the power of `0`.
+The second square has two grains, which is `2` to the power of `1`.
+The third square has four grains, which is `2` to the power of `2`.
+You can see that the exponent, or power, that `2` is raised by is always one less than the square number.
+
+| Square | Power | Value                   |
+| ------ | ----- | ----------------------- |
+| 1      | 0     | 2 to the power of 0 = 1 |
+| 2      | 1     | 2 to the power of 1 = 2 |
+| 3      | 2     | 2 to the power of 2 = 4 |
+| 4      | 3     | 2 to the power of 4 = 8 |
+
+## Approach: `BigInteger.pow()`
+
+```java
+import java.math.BigInteger;
+
+class Grains {
+
+    BigInteger grainsOnSquare(final int square) {
+        if ((square <= 0) || (square >= 65)) {
+            throw new IllegalArgumentException("square must be between 1 and 64");
+        }
+        return BigInteger.valueOf(2).pow(square - 1);
+    }
+
+    BigInteger grainsOnBoard() {
+        return BigInteger.valueOf(2).pow(64).subtract(BigInteger.ONE);
+    }
+}
+```
+
+For more information, check the [`BigInteger.pow()` approach][approach-pow].
+
+## Approach: Bit-shifting
+
+```java
+import java.math.BigInteger;
+
+class Grains {
+
+    BigInteger grainsOnSquare(final int square) {
+        if (square < 1 || square > 64) {
+            throw new IllegalArgumentException("square must be between 1 and 64");
+        }
+        return BigInteger.ONE.shiftLeft(square - 1);
+    }
+
+    BigInteger grainsOnBoard() {
+        return BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE);
+    }
+}
+```
+
+For more information, check the [Bit-shifting approach][approach-bit-shifting].
+
+## Which approach to use?
+
+Since benchmarking with the [Java Microbenchmark Harness][jmh] is currently outside the scope of this document,
+the choice between `pow` and bit-shifting can be made by perceived readability.
+
+[approach-pow]: https://exercism.org/tracks/java/exercises/grains/approaches/pow
+[approach-bit-shifting]: https://exercism.org/tracks/java/exercises/grains/approaches/bit-shifting
+[jmh]: https://github.com/openjdk/jmh
diff --git a/exercises/practice/grains/.approaches/pow/content.md b/exercises/practice/grains/.approaches/pow/content.md
@@ -0,0 +1,41 @@
+# `BigInteger.pow()`
+
+```java
+import java.math.BigInteger;
+
+class Grains {
+
+    BigInteger grainsOnSquare(final int square) {
+        if ((square <= 0) || (square >= 65)) {
+            throw new IllegalArgumentException("square must be between 1 and 64");
+        }
+        return BigInteger.valueOf(2).pow(square - 1);
+    }
+
+    BigInteger grainsOnBoard() {
+        return BigInteger.valueOf(2).pow(64).subtract(BigInteger.ONE);
+    }
+}
+```
+
+Other languages may have an exponential operator such as `**` or `^` to raise a number by a specified power.
+Java does not have an exponential operator, but can use the [`BigInteger.pow()`][pow] method.
+
+The `pow` method is nicely suited to the problem, since we start with one grain and keep doubling the number of grains on each successive square.
+`1` grain is `BigIntger.valueOf(2).pow(0)`, `2` grains is `BigIntger.valueOf(2).pow(1)`, `4` grains is `BigIntger.valueOf(2).pow(2)`, and so on.
+So, to get the right exponent, we subtract `1` from the `square` number.
+The [`valueOf`][valueof] method is used to get `2` as a `BigInteger`.
+
+For `grainsOnBoard`, the easiest way to get the total grains on all 64 squares is to get the value for an imaginary 65th square,
+and then subtract 1 from it.
+To understand how that works, consider a board that has only two squares.
+If we could grow the board to three squares, then we could get the number of grains on the imaginary third square, which would be 4.
+You could then [subtract][subtract] 4 by 1 (i.e. [`BigInteger.ONE`][one]) to get 3, which is the number of grains on the first square (1) and the second square (2).
+Remembering that the exponent must be one less than the square you want,
+you can call `BigIntger.valueOf(2).pow(64)` to get the number of grains on the imaginary 65th square.
+Subtracting that value by 1 gives the values on all 64 squares.
+
+[pow]: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#pow(int)
+[valueof]: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#valueOf(long)
+[subtract]: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#subtract(java.math.BigInteger)
+[one]: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#ONE
diff --git a/exercises/practice/grains/.approaches/pow/snippet.txt b/exercises/practice/grains/.approaches/pow/snippet.txt
@@ -0,0 +1,6 @@
+BigInteger grainsOnSquare(final int square) {
+    if ((square <= 0) || (square >= 65)) {
+        throw new IllegalArgumentException("square must be between 1 and 64");
+    }
+    return BigInteger.valueOf(2).pow(square - 1);
+}
