Hello.
A month ago I saw
this on reddit claiming that all "real" programmers should be able to solve these 5 problems in less than an hour total. I, and many of the commenters thought that was bullshit because 4 can be tricky and 5 is kinda tough (funnily enough, the blogger got number 4 wrong the first time). Regardless, I left it bookmarked a long time and finally decided to try them all anyway and so I'm posting my solutions!
Problem 1:
"Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion."
Very straight forward...
My solution:
#!/usr/bin/perl -w
use strict;
my @givenList = (1,2,3,4,5,6,7,8,9,0);
sub forList{
my $runningTotal = 0;
for(my $i = 0;$i<scalar(@givenList);++$i){
$runningTotal += $givenList[$i];
}
return $runningTotal;
}
sub whileList{
my $i = 0;
my $runningTotal = 0;
while($i<scalar(@givenList)){
$runningTotal += $givenList[$i];
++$i;
}
return $runningTotal;
}
sub recursiveList{
my @thisList = @_;
if(scalar(@thisList) == 1){
return $thisList[0];
}else{
return pop(@thisList)+recursiveList(@thisList);
}
}
print forList."\n";
print whileList."\n";
print recursiveList(@givenList)."\n";
Problem 2:
"Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3]."
Also very straight forward...
My solution:
#!/usr/bin/perl -w
use strict;
my(@listOne, @listTwo, @listThree, $i);
@listOne = ('a','b','c');
@listTwo = (1,2,3);
@listThree = ();
#I assume they are equal size. Otherwise this'd need:
#Some conditionals to avoid null pointers.
#The conditional in the for loop to be (;$i<scalar(@listOne) and $i<scalar(@listTwo)
for($i = 0;$i<scalar(@listOne);++$i){
push(@listThree, $listOne[$i]);
push(@listThree, $listTwo[$i]);
}
print join(", ", @listThree);
Problem 3:
"Write a function that computes the list of the first 100 Fibonacci numbers."
If you don't know, the Fibonacci sequence is a sequence of numbers where each number is the sum of the previous two and the first two numbers are 0 1. So it goes 0 1 1 2 3 5 8 13 21...
My solution:
#!/usr/bin/perl -w
use strict;
my($one, $two, $i, $temp);
$one = 0;
$two = 1;
print "$one\n$two\n";
for($i = 0;$i<100;++$i){
$temp = $two;
$two = $one + $two;
$one = $temp;
print "$two\n";
}
Problem 4:
"Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021."
So this one is the first one that's a bit tricky and requires you to think of a way to solve it rather than just implementing what it told you. My way was to bruteforce each combination of the numbers as a string, then typecast it to an integer and compare it to the previous largest number. My program only works for lists of 4 numbers which is kind of stupid. There's probably a good recursive way to do this or something, and I should probably redo it to be honest, but whatever.
My solution:
#!/usr/bin/perl -w
use strict;
my(@nums, @nums2, @nums3, @nums4, $largest, $current, $i, $j, $k, $l);
@nums = (50, 2, 1, 9);
$largest = 0;
for($i = 0;$i<scalar(@nums);++$i){
@nums2 = ();
for($j = 0;$j<scalar(@nums);++$j){ #construct @nums2
if($j == $i){
next;
}else{
push(@nums2, $nums[$j]);
}
}
for($j = 0;$j<scalar(@nums2);++$j){
@nums3 = ();
for($k = 0;$k<scalar(@nums2);++$k){ #construct @nums3
if($k == $j){
next;
}else{
push(@nums3, $nums2[$k]);
}
}
for($k = 0;$k<scalar(@nums3);++$k){
@nums4 = ();
for($l = 0;$l<scalar(@nums3);++$l){ #construct @nums4
if($l == $k){
next;
}else{
push(@nums4, $nums3[$l]);
}
}
for($l = 0;$l<scalar(@nums4);++$l){
$current = $nums[$i].$nums2[$j].$nums3[$k].$nums4[$l]; #concatenated numbers typecasted to a number
if( $current > $largest ){
$largest = $current;
}
}
}
}
}
print $largest;
Problem 5:
"Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100."
This one is actually a bit harder. My solution was to first create an array of every unique concatenation of the numbers 1-9 (1 2 3 4 5 6 7 8 9, 1 2 3 4 5 6 7 89, 1 2 3 4 5 6 78 9, etc...) by counting upward in binary from 00000000 to 11111111 where each number represents a spot between two numbers and 1s are concatenations and 0s are a space. After that I looped through each entry and did basically the same thing again but where 1s were + and 0s were - and then I'd check each one to see if it equaled 100.
My solution:
#!/usr/bin/perl -w
use strict;
my($runningTotal, $ones, $goodString);
my @concats = &allCombinations; #All different concatenations of 1-9
my @binaryList; #The binary array representing + and -
my @thisConcat; #Array containing all the different numbers in the current concatenation
my @finalCombos; #Array containing all configurations that add to 100
for(my $i = 0; $i<scalar(@concats); ++$i){ #for each unique concatenation of 0-9.
$ones = "";
@binaryList = ();
@thisConcat = split(' ', $concats[$i]);
for(my $e = 0; $e<scalar(@thisConcat)-1; ++$e){ #Fill @binaryList with 0s
push(@binaryList, 0);
$ones .= 1;
}
while(join('', @binaryList)<$ones){ #Try all combinations of + and - between concatenations.
for(my $e = scalar(@binaryList)-1; $e>=0; --$e){ #count upwards in binary
if($binaryList[$e] == 0){
$binaryList[$e] = 1; #1 means +
last;
}elsif($binaryList[$e] == 1){
$binaryList[$e] = 0; #0 means -
}
}
$runningTotal = $thisConcat[0];
for(my $e = 1; $e<=scalar(@binaryList); ++$e){ #edit $runningTotal.
if($binaryList[$e-1] == 1){
$runningTotal += $thisConcat[$e];
}else{
$runningTotal -= $thisConcat[$e];
}
}
if($runningTotal == 100){
$goodString = "";
for(my $e = 0; $e<scalar(@binaryList); ++$e){
$goodString .= $thisConcat[$e];
if($binaryList[$e] == 1){
$goodString .= "+";
}else{
$goodString .= "-";
}
}
$goodString .= $thisConcat[scalar(@thisConcat)-1];
push(@finalCombos, $goodString);
}
}
}
for(my $i = 0; $i<scalar(@finalCombos); ++$i){
print $finalCombos[$i]."\n";
}
sub allCombinations{
my($check, $one1, $two1, $thisString);
my @numbers = (1,2,3,4,5,6,7,8,9);
my @concats = (); #list of lists that are unique combinations of the above numbers.
my @binaryList = (0,0,0,0,0,0,0,0); #a number for each space between entries in @numbers. 1 means concat.
while(join('', @binaryList)<11111110){ #count upwards in binary
for(my $i = 7; $i>=0; --$i){
if($binaryList[$i] == 0){
$binaryList[$i] = 1;
last;
}elsif($binaryList[$i] == 1){
$binaryList[$i] = 0;
}
}
$thisString = $numbers[0];
my $i = 0;
for(my $i = 0; $i<scalar(@binaryList); ++$i){
if($binaryList[$i] == 0){
$thisString .= " ";
}
$thisString .= $numbers[$i+1];
}
push(@concats, $thisString);
}
return @concats;
}
So there ya go! Tell me what you think of my implementations/algorithms and what your first thought was for each one if it was different than mine!
Show Posts
