Merge pull request #1171 from dcw803/master

imported my solutions to challenge 044

3 files changed, 149 insertions, 29 deletions

diff --git a/challenge-044/duncan-c-white/README b/challenge-044/duncan-c-white/README
index 2424e913c2..884fd73e48 100644
--- a/challenge-044/duncan-c-white/README
+++ b/challenge-044/duncan-c-white/README
@@ -1,35 +1,19 @@
-Task 1: "Octal Number System
+Task 1: "Only 100, please.
 
-Write a script to print decimal number 0 to 50 in Octal Number System.
+You are given a string "123456789". Write a script that would insert "+"
+or "-" in between digits so that when you evaluate, the result should
+be 100."
 
-For example:
-Decimal 0 = Octal 0
-Decimal 1 = Octal 1
-Decimal 2 = Octal 2
-Decimal 3 = Octal 3
-Decimal 4 = Octal 4
-Decimal 5 = Octal 5
-Decimal 6 = Octal 6
-Decimal 7 = Octal 7
-Decimal 8 = Octal 10
+My notes: hmm.. looks like it might be combinatorial.  Is there a clever way?
+It's almost like a version of Countdown's number game (without * and /).
 
-and so on.
-"
-
-My notes: Trivial.
-
-Task #2: "Balanced Brackets
-
-Write a script to generate a string with random number of ( and ) brackets. Then make the script validate the string if it has balanced brackets.
+Task #2: "Make it $200
 
-For example:
-() - OK
-(()) - OK
-)( - NOT OK
-())() - NOT OK
+You have only $1 left at the start of the week. You have been given an
+opportunity to make it $200. The rule is simple with every move you can
+either double what you have or add another $1. Write a script to help
+you get $200 with the smallest number of moves.
 "
 
-My notes: sounds quite easy. Generate is like coin tossing, validator could
-either count how many nested brackets we're in, or we could use regex search
-and replace to repeatedly delete () pairs of adjacent characters, valid if
-we end up with the empty string.
+My notes: doubling sounds like the way to go..  exhaustive breadth first
+search "try both options at every move" seems obvious but combinatorial growth
diff --git a/challenge-044/duncan-c-white/perl/ch-1.pl b/challenge-044/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..0d83bccdbf
--- /dev/null
+++ b/challenge-044/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,57 @@
+#!/usr/bin/perl
+#
+# Task 1: "Only 100, please.
+#
+# You are given a string "123456789". Write a script that would insert "+"
+# or "-" in between digits so that when you evaluate, the result should
+# be 100."
+# "
+# 
+# My notes: hmm.. looks like it might be combinatorial.  Is there a clever way?
+# It's almost like a version of Countdown's number game (without * and /).
+# 
+
+use feature 'say';
+use strict;
+use warnings;
+use Function::Parameters;
+
+die "Usage: ch-1.pl [GOAL]\n" if @ARGV>1;
+
+my $goal = shift // 100;
+
+my $str = "123456789";
+
+my @ch = ('', '+', '-' );
+
+my $ip = 1;		# insertion point in string
+
+mutate( $str, 1, 8, $goal );
+
+#
+# mutate( $str, $ip, $nleft, $goal );
+#	Given a string $str, an insertion point $ip (1..length($str)-1)
+#	and a number of recursions left ($nfleft), mutate the string in
+#	all possible ways, inserting each sequence in @ch into $str at $ip,
+#	then recursing.  Search for cases where eval(mutatedstr)==$goal,
+#	printing them out.
+#
+fun mutate( $str, $ip, $nleft, $goal )
+{
+	foreach my $a (@ch)
+	{
+		my $s2 = $str;
+		substr( $s2, $ip, 0, $a );
+		#say "str:$str, a:$a, ip:$ip, nleft:$nleft, s2:$s2";
+		my $ip2 = $ip+1+length($a);
+		if( $nleft>1 )
+		{
+			mutate( $s2, $ip2, $nleft-1, $goal );
+		}
+		if( $nleft==1 )
+		{
+			my $n = eval $s2;
+			say "FOUND $s2" if $n==$goal;
+		}
+	}
+}
diff --git a/challenge-044/duncan-c-white/perl/ch-2.pl b/challenge-044/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..32d4340370
--- /dev/null
+++ b/challenge-044/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,79 @@
+#!/usr/bin/perl
+#
+# Task #2: "Make it $200
+# 
+# You have only $1 left at the start of the week. You have been given an
+# opportunity to make it $200. The rule is simple with every move you can
+# either double what you have or add another $1. Write a script to help
+# you get $200 with the smallest number of moves.
+# "
+# 
+# My notes: doubling sounds like the way to go..  exhaustive breadth first
+# search "try both options at every move" seems obvious but combinatorial
+# growth could be a problem again. Is there a clever way?
+# 
+
+use feature 'say';
+use strict;
+use warnings;
+use Function::Parameters;
+use Data::Dumper;
+
+
+die "Usage: ch-2.pl [GOAL]\n" if @ARGV>1;
+
+my $goal = shift // 200;
+my $seq = search( 1, $goal );
+say "$goal can be achieved by shortest sequence $seq";
+
+my $curr = 1;
+say "start with $curr, goal: $goal";
+foreach my $op (split(//,$seq))
+{
+	if( $op eq "i" )
+	{
+		$curr++;
+		say "increment curr to $curr";
+	} else
+	{
+		$curr *= 2;
+		say "double curr to $curr";
+	}
+}
+say "result: $curr, goal: $goal";
+
+
+#
+# my $shortseq = search( $initial, $goal );
+#	Given that you have $initial dollars, and you want $goal dollars,
+#	perform a breadth-first search to find the $goal in the smallest
+#	number of increment or doubling steps.  Return the shortest sequence
+#	or 'i' (increment) or 'd' (double) steps that result in $goal dollars.
+#
+#	Do this using a todo list of ( $dollars, $sequence ) pairs.
+#
+fun search( $initial, $goal )
+{
+	my $seq = "";
+	my @todo = ( [$initial, ""] );
+	for(;;)
+	{
+		# Build a new list of todo pairs, twice as long as the old one.
+		# stopping if we hit $goal
+		my @newtodo;
+		foreach my $pair (@todo)
+		{
+			my( $currvalue, $currseq ) = @$pair;
+	return $currseq if $currvalue == $goal;
+
+			# try doubling $currvalue
+			push @newtodo, [ 2 * $currvalue, $currseq."d" ];
+
+			# try incrementing $currvalue
+			push @newtodo, [ $currvalue + 1, $currseq."i" ];
+		}
+		@todo = @newtodo;
+	}
+}
+
+