1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
use strict;
use warnings;
# Question 2: You are given $n steps to climb
# Write a script to find out the distinct ways to climb to the top.
# You are allowed to climb either 1 or 2 steps at a time.
# I know there is a better way to implement this. I remember hearing about this (or a similar question)
# during a programming interview--albeit it was about counting the ways to climb $n stairs, and not
# generating them. I believe the solution involved a recurrence relation, so I think there is a nice
# way to determine the methods of climbing $n in terms of some lower $ns.
# But first, I need some data on what f($n) is. Following some advice I was given: let the computer do the
# work for you. This function will recursively generate all methods of climbing stairs and terminate after
# we have climbed at least $n. It only will contribute to the final count if exactly $n stairs were climbed
# Variables for checking effiency
my $calls = 0;
# The idea: we implement a recursive prefix search.
# At any point we have to options to take -> 1 or 2 steps
# We just take any and all paths (for n levels) adding valid paths as we go
#sub brute {
# my ($n, $cur) = @_;
# $calls++;
# #print "n = $n and cur = $cur\n";
# return 1 if $n == $cur;
# return 0 if $cur > $n;
# return brute($n, $cur + 1) + brute($n, $cur + 2);
#}
# Example output:
# f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8, f(6) = 13, f(7) = 21, f(8) = 34, f(9) = 55, f(10) = 89
# ^ we can refactor this to be more like fib! Furthermore, fib would take less operations.
# NOTE: BASE CASES ARE SLIGHTLY OFF, climb(n) = fib(n+1)
# I could have implemented fib with altered base cases, but it felt weird, so climb is a separate function
sub fib {
my $n = shift;
$calls++;
return $n if $n < 2;
return fib($n - 1) + fib($n - 2);
}
# ^ we can optimize further by memoizing!
# The table of memoized values. I've added $fib[0] so there is no offset due to 0 indexing
my @fib = (0, 1);
sub fib_memo {
my $n = shift;
#$calls++;
if ($n > $#fib){
# oddity of perl, this works!
# normally, we would have to store new calculated value in a temporary
# variable because the other fib calls fill the table up to $n, thus
# allowing us to store the $nth fib value.
# However, perl doesn't seem to care (at least on my machine)
# as long as the value is initalized. You can have gaps between initialized values!
# Nonethless, we fill up the table by the end anyway
$fib[$n] = fib_memo($n - 1) + fib_memo($n - 2);
}
return $fib[$n];
}
sub climb {
my $n = shift;
return fib_memo($n + 1);
}
# Now we have a new problem (2b if you will) -> how do we get the order of the steps?
# The example answer listed all the sequences of steps you could take. I have a really
# nice way of calculating how many sequences you can take, but this does not calculate them
# Theoretically, we can apply a similar method. We can store/calc the sequences for $fib[$n - 1] and
# $fib[$n - 2] and then generate a new sequence that has a 1 and 2 step added (and shuffled) throughtour
# the other sequences respectively
# this func stores the order of the steps
#sub brute_path {
# my ($n, $cur, @order) = @_;
# $calls++;
# #return @order if $n == $cur;
# if($cur == $n){
# print "$_ + " foreach @order[0..$#order-1];
# print "$order[$#order]\n";
# return 1;
# }elsif($cur > $n){
# return 0;
# }
# #return () if $cur > $n;
# $order[@order] = 1;
# my $lbranch = brute_path($n, $cur + 1, @order);
# $order[$#order] = 2;
# return $lbranch + brute_path($n, $cur + 2, @order);
#}
# Test about how and when array warnings are generated
# It will onlt throw warnings when trying to access uninitialized elements
# You can assign to $test[10] without initialized 0..9 and will get no
# errors or warnings as long as you only access elt 10
#my @test = (1, 2, 3);
#$test[10] = 9;
#print "@test\n";
#print "$test[3]\n";
#print "$test[10]\n";
# helper function
#sub push_to_copy{
# my $elt, @arr = @_;
#
#}
# Okay so now I have to work on outputing the path like in the sample
# Based on the counting solution, I know f(n) = f(n-1) + f(n-2)
# So we just need to take the last step
# Add a 1 to end of f(n-1) paths
# Add a 2 to end of f(n-2) paths
# Going to try to memoize this
# Pushes a value on each array stored within the reference based in
sub push2each{
my ($val, @arefs) = @_;
my @arrs;
foreach (@arefs){
# Make a copy by creating a new array based on the value of the reference
my @cp = @{$_};
push @cp, $val;
# push a reference!
push @arrs, \@cp;
}
return @arrs;
}
# Contains the paths for climb n-1 stairs
# Used for memoizing
my @paths = (
[[1]],
[[1,1], [2]]
);
# Memoized climb subroutine
# NOTE: This takes a ton of memory
# TODO: Look into alternate ways to represent the sequence of steps
# e.g., store the indices where the number of steps change?
sub climb_paths{
my $n = shift;
--$n; #index is offset! n = 1 path stored at index 0
if($n > $#paths){
my @new_paths = push2each(1, @{climb_paths($n-1)});
push @new_paths, push2each(2, @{climb_paths($n-2)});
$paths[$n] = \@new_paths;
}
return $paths[$n];
}
# Print's all of the arrays stored in a refence passed in
sub print_paths{
my $pref = shift;
foreach my $aref (@{$pref}){
print "\t[@{$aref}]\n";
}
}
# Calculate and print the paths to climb n stairs
# Do this up to $n = 5 because the output becomes too long
# and the method chews up a lot of memory
my $count = 0;
for (1 .. 5){
my $ref = climb_paths $_;
$count = @{$ref};
print "n = $_ => $count ways:\n";
print_paths $ref;
}
# Switch to the method that counts the number of ways (without determine
# the sequence of steps to compute faster and with less memory)
print "Switching to count only method, omitting the sequences...\n";
for (6 .. 100){
$count = climb $_;
print "n = $_ => $count ways\n" # with $calls funcalls\n";
#$calls = 0;
}
|
