aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJames Smith <js5@sanger.ac.uk>2023-05-09 06:39:23 +0100
committerGitHub <noreply@github.com>2023-05-09 06:39:23 +0100
commitff37fe408cc094e08dfca21054962a0e993adf79 (patch)
tree27a391f8e22b4a4b1d11b090612b65297d8a0aeb
parent111a80fe927d2d0596fa6a4ea2aed024f37103c4 (diff)
downloadperlweeklychallenge-club-ff37fe408cc094e08dfca21054962a0e993adf79.tar.gz
perlweeklychallenge-club-ff37fe408cc094e08dfca21054962a0e993adf79.tar.bz2
perlweeklychallenge-club-ff37fe408cc094e08dfca21054962a0e993adf79.zip
Update README.md
-rw-r--r--challenge-216/james-smith/README.md27
1 files changed, 25 insertions, 2 deletions
diff --git a/challenge-216/james-smith/README.md b/challenge-216/james-smith/README.md
index 1518a7f6e6..4935e8816d 100644
--- a/challenge-216/james-smith/README.md
+++ b/challenge-216/james-smith/README.md
@@ -48,8 +48,29 @@ Firstly we get a list of the lower-cased letters in the number plate. Then for e
Interestingly this task uses the trick - copy hash and delete elements - within it's core.
-We note:
- * We are looking for fewest stickers - well this suggests a solution based on a queue as we want to do a depth based search.
+We note we:
+ * are looking for fewest stickers so:
+ * this suggests a depth first solution;
+ * once we have found a solution it is by definition the best one;
+ * queue solutions work well in these cases;
+ * use a count based solution
+ * we count every letter in the target word;
+ * check that all of these are available on the sticker:
+ * if not we return a "0" value
+ * initialise the queue with an element:
+ * where we have not used any stickers;
+ * the last sticker we have "chosen" is the first one;
+ * the counts are the inital counts we calculated above
+ * for every element of the queue:
+ * we loop through the stickers;
+ * for each sticker we loop through the letters;
+ * and if we need that letter we make a note we have removed a letter and reduce the count of that letter by one (if the count goes to zero we remove it);
+ * if the counts array is empty we return the size
+ * if we have removed a letter we push the new values back on to the queue;
+ * **Note** when looping through the stickers we start with the last one we used and loop to the end. This avoids duplicates and greatly reduces the search space.
+ * we loop till the queue is empty - actually we don't because we will exit the loop with the count array check above before we exhaust the queue.
+
+Here is the code that the describes....
```perl
sub word_stickers {
@@ -69,6 +90,8 @@ sub word_stickers {
}
```
+And to know what bit does what - here it is with comments:
+
```perl
sub word_stickers {
my( %f, %s, $n, $l, $x );