Merge pull request #8771 from jeanluc2020/jeanluc-236

Add solution 236

6 files changed, 250 insertions, 0 deletions

diff --git a/challenge-236/jeanluc2020/blog-1.txt b/challenge-236/jeanluc2020/blog-1.txt
new file mode 100644
index 0000000000..48e603fcda
--- /dev/null
+++ b/challenge-236/jeanluc2020/blog-1.txt
@@ -0,0 +1 @@
+http://gott-gehabt.de/800_wer_wir_sind/thomas/Homepage/Computer/perl/theweeklychallenge-236-1.html
diff --git a/challenge-236/jeanluc2020/blog-2.txt b/challenge-236/jeanluc2020/blog-2.txt
new file mode 100644
index 0000000000..ef2868c9dd
--- /dev/null
+++ b/challenge-236/jeanluc2020/blog-2.txt
@@ -0,0 +1 @@
+http://gott-gehabt.de/800_wer_wir_sind/thomas/Homepage/Computer/perl/theweeklychallenge-236-2.html
diff --git a/challenge-236/jeanluc2020/perl/ch-1.pl b/challenge-236/jeanluc2020/perl/ch-1.pl
new file mode 100755
index 0000000000..f8d94b2f87
--- /dev/null
+++ b/challenge-236/jeanluc2020/perl/ch-1.pl
@@ -0,0 +1,81 @@
+#!/usr/bin/perl
+# https://theweeklychallenge.org/blog/perl-weekly-challenge-236/#TASK1
+#
+# Task 1: Exact Change
+# ====================
+#
+#
+#
+# You are asked to sell juice each costs $5. You are given an array of bills.
+# You can only sell ONE juice to each customer but make sure you return exact
+# change back. You only have $5, $10 and $20 notes. You do not have any change
+# in hand at first.
+#
+# Write a script to find out if it is possible to sell to each customers with
+# correct change.
+#
+## Example 1
+##
+## Input: @bills = (5, 5, 5, 10, 20)
+## Output: true
+##
+## From the first 3 customers, we collect three $5 bills in order.
+## From the fourth customer, we collect a $10 bill and give back a $5.
+## From the fifth customer, we give a $10 bill and a $5 bill.
+## Since all customers got correct change, we output true.
+#
+## Example 2
+##
+## Input: @bills = (5, 5, 10, 10, 20)
+## Output: false
+##
+## From the first two customers in order, we collect two $5 bills.
+## For the next two customers in order, we collect a $10 bill and give back a $5 bill.
+## For the last customer, we can not give the change of $15 back because we only have two $10 bills.
+## Since not every customer received the correct change, the answer is false.
+#
+## Example 3
+##
+## Input: @bills = (5, 5, 5, 20)
+## Output: true
+#
+############################################################
+##
+## discussion
+##
+############################################################
+#
+# Each bill we get goes into our change hash. If we receive
+# a bill > 5, we calculate the return value, then we try to
+# pay it starting with a 10 bill if available. If in the end we
+# still have something left to return, but no more fitting bills,
+# we return false. Otherwise, we return true.
+#
+use strict;
+use warnings;
+use Data::Dumper;
+
+exact_change(5, 5, 5, 10, 20);
+exact_change(5, 5, 10, 10, 20);
+exact_change(5, 5, 5, 20);
+
+sub exact_change {
+   my @bills = @_;
+   my $change = {};
+   print "Input: (" . join(", ", @bills) . ")\n";
+   foreach my $bill (@bills) {
+      $change->{$bill}++;
+      my $to_return = $bill - 5;
+      foreach my $return_bill (10, 5) {
+         while ($to_return >= $return_bill && $change->{$return_bill} ) {
+            $to_return -= $return_bill;
+            $change->{$return_bill}--;
+         }
+      }
+      if($to_return > 0) {
+         print "Output: false\n";
+         return;
+      }
+   }
+   print "Output: true\n";
+}
diff --git a/challenge-236/jeanluc2020/perl/ch-2.pl b/challenge-236/jeanluc2020/perl/ch-2.pl
new file mode 100755
index 0000000000..f867968567
--- /dev/null
+++ b/challenge-236/jeanluc2020/perl/ch-2.pl
@@ -0,0 +1,98 @@
+#!/usr/bin/perl
+# https://theweeklychallenge.org/blog/perl-weekly-challenge-236/#TASK2
+#
+# Task 2: Array Loops
+# ===================
+#
+# You are given an array of unique integers.
+#
+# Write a script to determine how many loops are in the given array.
+#
+### To determine a loop: Start at an index and take the number at array[index]
+### and then proceed to that index and continue this until you end up at the
+### starting index.
+#
+## Example 1
+##
+## Input: @ints = (4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10)
+## Output: 3
+##
+## To determine the 1st loop, start at index 0, the number at that index is 4,
+## proceed to index 4, the number at that index is 15, proceed to index 15 and
+## so on until you're back at index 0.
+##
+## Loops are as below:
+## [4 15 1 6 13 5 0]
+## [3 8 7 18 9 16 12 17 2]
+## [14 11 19 10]
+#
+## Example 2
+##
+## Input: @ints = (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19)
+## Output: 6
+##
+## Loops are as below:
+## [0]
+## [1]
+## [13 9 14 17 18 15 5 8 2]
+## [7 11 4 6 10 16 3]
+## [12]
+## [19]
+#
+## Example 3
+##
+## Input: @ints = (9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17)
+## Output: 1
+##
+## Loop is as below:
+## [9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0]
+#
+############################################################
+##
+## discussion
+##
+############################################################
+#
+# We start at index 0 and walk all the way up to the last index.
+# Then we just calculate the loop starting at that index in the
+# array. If by any chance we see an index that is already part
+# of a loop, we can return.
+#
+use strict;
+use warnings;
+
+array_loops(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10);
+array_loops(0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19);
+array_loops(9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17);
+
+my $seen_index = {};
+
+sub array_loops {
+   my @ints = @_;
+   my @loops = ();
+   $seen_index = ();
+   print "Input: (" . join(", ", @ints) . ")\n";
+   foreach my $index (0..$#ints) {
+      next if $seen_index->{$index};
+      my $loop = get_loop($index, @ints);
+      push @loops, $loop if $loop;
+   }
+   print "Output: " . scalar(@loops) . "\n";
+   foreach my $loop (@loops) {
+      print "[" . join(", ", @$loop) . "]\n";
+   }
+}
+
+sub get_loop {
+   my $index = shift;
+   my @ints = @_;
+   my $loop = [];
+   $index = $ints[$index];
+   while(! $seen_index->{$index}) {
+      $seen_index->{$index} = 1;
+      push @$loop, $index;
+      $index = $ints[$index];
+   }
+   return $loop;
+}
+
diff --git a/challenge-236/jeanluc2020/python/ch-1.py b/challenge-236/jeanluc2020/python/ch-1.py
new file mode 100755
index 0000000000..b15c5c8847
--- /dev/null
+++ b/challenge-236/jeanluc2020/python/ch-1.py
@@ -0,0 +1,35 @@
+#!/usr/bin/python3
+#
+# This is just me learning a bit of python.
+# Look at the perl solution for a discussion of the details.
+
+def exact_change(*args):
+    change = {}
+    print("Input: ", end="")
+    first = 1
+    for i in args:
+        if first:
+            print("(", end="")
+            first = 0
+        else:
+            print(", ", end="")
+        print(i, end="")
+    print(")")
+
+    for bill in args:
+        change[bill] = change.get(bill, 0) + 1
+        to_return = bill - 5
+        for return_bill in [10, 5]:
+            change[return_bill] = change.get(return_bill, 0)
+            while to_return >= return_bill and change[return_bill] >= 1:
+                to_return -= return_bill
+                change[return_bill] -= 1
+        if to_return > 0:
+            print("Output: false")
+            return
+    print("Output: true")
+
+
+exact_change(5, 5, 5, 10, 20);
+exact_change(5, 5, 10, 10, 20);
+exact_change(5, 5, 5, 20);
diff --git a/challenge-236/jeanluc2020/python/ch-2.py b/challenge-236/jeanluc2020/python/ch-2.py
new file mode 100755
index 0000000000..922e4ae219
--- /dev/null
+++ b/challenge-236/jeanluc2020/python/ch-2.py
@@ -0,0 +1,34 @@
+#!/usr/bin/python3
+#
+# This is just me learning a bit of python.
+# Look at the perl solution for a discussion of the details.
+
+seen_index = {}
+
+def get_loop(index, ints):
+    loop = []
+    index = ints[index]
+    while not index in seen_index:
+        seen_index[index] = 1
+        loop.append(index)
+        index = ints[index]
+    return loop
+
+def array_loops(*ints):
+    loops = []
+    seen_index.clear()
+    for index in range(len(ints)):
+        if index in seen_index:
+            next
+        loop = get_loop(index, ints)
+        if len(loop) > 0:
+            loops.append(loop)
+    print("Output: ", len(loops))
+    for loop in loops:
+        print("[", end="")
+        print(*loop, sep=", ", end="")
+        print("]")
+
+array_loops(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10)
+array_loops(0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19)
+array_loops(9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17)