[QUIZ] B & E (#72)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
by Stephen Waits
Like many homeowners, I have a residential monitored alarm system installed in
my house. It consists of a few keypads and several remote sensors.
My alarm has three modes of operation:
1. Off - completely disarmed
2. Away - everything (perimeter and interior) armed
3. Stay - perimeter armed
The keypad consists of 12 buttons, which includes the digits '0' through '9',
plus '*' and '#'. The '*' and '#' are only used for special programming.
The digits '1', '2', and '3' are also labeled "Off", "Away", and "Stay". This
corresponds to the three system modes mentioned above.
The security code is 4 digits long. To set or change the system's mode, you
simply enter your 4 digit security code, followed by the digit ('1', '2', or
'3') which corresponds to the mode you want to set.
For example, if the security code was 1234:
12341 - sets system to "Off"
12342 - sets system to "Away"
12343 - sets system to "Stay"
What if you make a mistake when you're entering your code? Yes, this is where
an interesting observation comes into play. To answer the question... if you
make a mistake you just start over. In other words, the keypad seems to only
care that the last 5 keypresses match a valid code+command sequence.
For example, if you entered the first two digits of your code incorrectly, you
could just simply start over with the correct code, without any kind of reset:
8912341
++ => first 2 keypresses erroneous, oops!
+++++ => last 5 keypresses == valid code+command sequence
The thought occurs to me, and I'm sure to the reader, that perhaps this can be
exploited. For example, if you entered the sequence 1234123, you are actually
testing 3 different codes:
1234123 => what you entered
12341 => 1234 + 1/off
.23412 => 2341 + 2/away
..34123 => 3412 + 3/stay
Problems:
1. What is the shortest sequence of digits you can come up with that tests every
code in this alarm system? The worst case is 5*10**4, or 50000 keypresses.
2. What if the security code was 5 digits instead of 4? Worst case here is
6*10**5, or 600000 keypresses.
3. What if the "stop digits" changed from [1, 2, 3], to just [1]? For instance,
maybe the system is armed (mode 2 or 3) and only actually beeps when switching
to mode 1. (See Assumptions below)
4. Can you also minimize the number of duplicate code tests?
Assumptions:
* We assume the keypad will actually let you go on entering digits for this
long. I haven't tested it, but it seems silly that it might actually allow
this. However, as a long time comp.risks reader, almost nothing surprises me.
* We assume that the keypad will always signify a valid code+command sequence,
regardless of mode. In reality, if you set to Away when it's already in Away,
it might not emit it's "success" signal.
#!/usr/bin/env ruby -w
#
# Stephen Waits <st...@waits.net>
#
class AlarmKeypad
# init a keypad, with length of security code, and the code's
# stop digits
def initialize(code_length = 4, stop_digits = [1,2,3])
# remember the length of the security code
@code_length = code_length
# and which digits cause a code to be checked
@stop_digits = stop_digits
# and reset our data structures to 0
clear
end
# reset keypad to initial state
def clear
# an array of each code and how many times it's been entered
@codes = Array.new(10**@code_length,0)
# last N+1 keypad button presses
@key_history = []
# total number of keypad button presses
@key_presses = 0
end
# press a single digit
def press(digit)
# add digit to key history
@key_history.shift while @key_history.size > @code_length
@key_history << digit
@key_presses += 1
# see if we just tested a code
if @stop_digits.include?(@key_history.last) and
@key_history.length > @code_length
@codes[@key_history[0,@code_length].join.to_i] += 1
end
end
# find out if every code had been tested
def fully_tested?
not @codes.include?(0)
end
# find out if an individual code has been tested
# NOTE: an actual keypad obviously doesn't offer this functionality;
# but, it's useful and convenient (and might save duplication)
def tested?(code)
@codes[code] > 0
end
# output a summary
def summarize
tested = @codes.select { |c| c > 0 }.size
tested_multiple = @codes.select { |c| c > 1 }.size
puts "Search space exhausted." if fully_tested?
puts "Tested #{tested} of #{@codes.size} codes " +
"in #{@key_presses} keystrokes."
puts "#{tested_multiple} codes were tested more than once."
end
end
if $0 == __FILE__
# a random button presser, 3 digit codes
a = AlarmKeypad.new(3)
a.press( rand(10) ) until a.fully_tested?
a.summarize
# sequential code entry, 4 digit codes
a = AlarmKeypad.new(4)
("0000".."9999").each do |c|
next if a.tested?(c.to_i)
c.split(//).each { |d| a.press(d.to_i) }
a.press(rand(3)+1)
end
a.summarize
# sequential code entry, 5 digit codes, only [1] as a stop digit
a = AlarmKeypad.new(5,[1])
("00000".."99999").each do |c|
next if a.tested?(c.to_i)
c.split(//).each { |d| a.press(d.to_i) }
a.press(1)
end
a.summarize
end
James Edward Gray II
> by Stephen Waits
Just by a neat little quirk of serendipity this quiz was launched on
the quiz creator's birthday. Happy birthday Stephen!
James Edward Gray II
Stephen Waits
On Mar 24, 2006, at 6:57 AM, James Edward Gray II wrote:
> Happy birthday Stephen!
Thanks! I'm looking forward to those solutions...
--Steve
Timothy Bennett
Happy birthday Steve.
In case you're curious, my solution is... not doing so well. I
thought I'd built up a decent model by working with code lengths I
could fit in my head (e.g. 1 or 2 digits), but it actually does much
worse than the naive solution for 4 and 5 digit codes (it does better
for 1-3 digit codes). So, back to the drawing board for me.
Tim
semm...@gmail.com
(10**4)*3 different combinations which totals 30,000. But that takes
30,000*5 key presses which is 150,000 key presses. So if the code was 5
digits, it is 1,500,000 key presses to test them all by brute force.
Anyway, here is my first solution. It is unrefined, but I haven't
really had time to work on it much.
<code>
# Shane Emmons
#
# Quiz 72 B&E
#
# This code is very ugly and inefficient, but I wanted to get
# something out there to look at. Sorry I didn't have more
# time to work on this quiz.
all_possible = ""
10.times do |key1| 10.times do |key2| 10.times do |key3|
10.times do |key4| 3.times do |key5|
current_code = Array.new
current_code << key1 << key2 << key3 << key4 << key5 + 1
next if all_possible.include?( current_code.to_s )
left, left_over = Array.new( current_code ), Array.new
right, right_over = Array.new( current_code ), Array.new
while true do
left_over << left.shift
right_over << right.pop
if left.length == 0
all_possible += current_code.to_s
break
elsif all_possible =~ /^#{left.to_s}/
all_possible = left_over.to_s + all_possible
break
elsif all_possible =~ /#{right.to_s}$/
all_possible += right_over.to_s
break
end
end
end end
end end end
print "string: ", all_possible, "\n"
print "string length: ", all_possible.length, "\n"
</code>
Shane
Ross Bamford
seriously tried to clean it up, either) and slow.
There are actually two solutions in here, one that's fast and 'good
enough' for the smaller digit counts, and one that's *very* slow but
gives shorter results with less retesting of codes.
Neither of these are all that much better than simply running through
and checking each code against AlarmKeypad#tested? but then that's to be
expected I guess, perhaps this is why real alarms don't tend to
duplicate that functionality :P
I ran benchmarked tests to get an idea of how it did. The tests are
doing simple sequential tests (seq), sequential using tested? (seq/chk),
the simple/quick(er) way (simple) and the slow, better way (best). Check
out the 'best' time for 4 digit codes - there has to be room for
improvement there :/
### 2 digits, [1,2,3] stops ###
user system total real
seq. 0.010000 0.000000 0.010000 ( 0.005530)
Search space exhausted.
Tested 100 of 100 codes in 300 keystrokes.
39 codes were tested more than once.
seq/chk 0.010000 0.000000 0.010000 ( 0.008893)
Search space exhausted.
Tested 100 of 100 codes in 234 keystrokes.
11 codes were tested more than once.
simple 0.000000 0.000000 0.000000 ( 0.006074)
Search space exhausted.
Tested 100 of 100 codes in 243 keystrokes.
15 codes were tested more than once.
best 0.050000 0.000000 0.050000 ( 0.054995)
Search space exhausted.
Tested 100 of 100 codes in 223 keystrokes.
2 codes were tested more than once.
### 3 digits, [1,2,3] stops ###
user system total real
seq. 0.070000 0.000000 0.070000 ( 0.064838)
Search space exhausted.
Tested 1000 of 1000 codes in 4000 keystrokes.
513 codes were tested more than once.
seq/chk 0.060000 0.000000 0.060000 ( 0.062613)
Search space exhausted.
Tested 1000 of 1000 codes in 2944 keystrokes.
224 codes were tested more than once.
simple 0.090000 0.000000 0.090000 ( 0.086938)
Search space exhausted.
Tested 1000 of 1000 codes in 2960 keystrokes.
223 codes were tested more than once.
best 6.430000 0.050000 6.480000 ( 6.741495)
Search space exhausted.
Tested 1000 of 1000 codes in 2623 keystrokes.
50 codes were tested more than once.
### 4 digits, [1,2,3] stops ###
user system total real
seq. 0.820000 0.020000 0.840000 ( 0.871923)
Search space exhausted.
Tested 10000 of 10000 codes in 50000 keystrokes.
6108 codes were tested more than once.
seq/chk 0.690000 0.010000 0.700000 ( 0.704795)
Search space exhausted.
Tested 10000 of 10000 codes in 33395 keystrokes.
2569 codes were tested more than once.
simple 1.830000 0.030000 1.860000 ( 1.869937)
Search space exhausted.
Tested 10000 of 10000 codes in 33555 keystrokes.
2620 codes were tested more than once.
best 781.350000 5.520000 786.870000 (796.666829)
Search space exhausted.
Tested 10000 of 10000 codes in 28614 keystrokes.
435 codes were tested more than once.
### 5 digits, [1,2,3] stops ###
user system total real
seq. 11.010000 0.140000 11.150000 ( 11.248501)
Search space exhausted.
Tested 100000 of 100000 codes in 600000 keystrokes.
69494 codes were tested more than once.
seq/chk 7.450000 0.060000 7.510000 ( 7.563379)
Search space exhausted.
Tested 100000 of 100000 codes in 371028 keystrokes.
30902 codes were tested more than once.
simple 136.960000 6.250000 143.210000 (145.916674)
Search space exhausted.
Tested 100000 of 100000 codes in 371394 keystrokes.
31105 codes were tested more than once.
best (not tested)
Stephen Waits
> I think that there are more key presses then you think. There are
> (10**4)*3 different combinations which totals 30,000. But that takes
> 30,000*5 key presses which is 150,000 key presses. So if the code was 5
> digits, it is 1,500,000 key presses to test them all by brute force.
> Anyway, here is my first solution. It is unrefined, but I haven't
> really had time to work on it much.
Hi Shane,
I'm not sure I follow you..
With 4 digit codes, there are 10,000 unique codes, or 10**4. Each code
takes a maximum of 5 keypresses to test, therefore 5*10**4 == 50k
keypresses.
Regardless, thanks for your solution!
--Steve
Stephen Waits
> Hmm, this is a tricky one :)
Indeed.. thanks for the solutions Ross!
--Steve
semm...@gmail.com
codes can have any of the three unique modifier keys attached to it so
10,000 * 3 = 30,000 unique combinations you must press. And, since
there are 5 keys in the 4 key code + 1 modifier key, it is 30,000 * 5 =
150,000. At first I didn't realize this until I wrote the loop to
generate all of the unique code/modifier key combinations. The one key
to this I believe, is that you have to treat the modifier key (1,2,3)
as part of the code not a seperate entity. Here is some code to prove
the solution.
<code>
output, num_codes = '', 0
10.times do |x1| 10.times do |x2| 10.times do |x3|
10.times do |x4| 3.times do |x5|
output += x1.to_s + x2.to_s + x3.to_s + x4.to_s + x5.to_s
num_codes += 1
end end
end end end
print "number codes: ", num_codes.to_s, "\n"
print "output length: ", output.length, "\n"
</code>
Matthew Moss
key you hit, the system would confirm the code. So while 150,000 is
right if you need to test every combo with every modifier, 50,000 is
what the problem was looking for (i.e., every combo with _any_
modifier).
Stephen Waits
On Mar 28, 2006, at 6:53 AM, Matthew Moss wrote:
> I think part of the problem was that it didn't matter which modifier
> key you hit, the system would confirm the code. So while 150,000 is
> right if you need to test every combo with every modifier, 50,000 is
> what the problem was looking for (i.e., every combo with _any_
> modifier).
That's right. Sorry for the confusion.
--Steve
semm...@gmail.com
better.
<code>
all_possible = ""
10.times do |key1| 10.times do |key2|
10.times do |key3| 10.times do |key4|
current_code = Array.new
current_code << key1 << key2 << key3 << key4
next if all_possible =~ /#{current_code.to_s}(1|2|3)/
left, left_over = Array.new( current_code ), Array.new
right, right_over = Array.new( current_code ), Array.new
while true do
left_over << left.shift
right_over.insert( 0, right.pop )
if left.length == 0
if key1 == 0
all_possible += current_code.to_s + "1"
elsif key1 == 1
all_possible += current_code.to_s + "2"
else
all_possible += current_code.to_s + "3"
end
break
elsif all_possible =~ /^#{left.to_s}(1|2|3)/
all_possible = left_over.to_s + all_possible
break
elsif all_possible =~ /#{right.to_s}$/
if key1 == 0
all_possible += right_over.to_s + "1"
elsif key1 == 1
all_possible += right_over.to_s + "2"
else
all_possible += right_over.to_s + "3"
end
break
end
end
end end
end end
Ross Bamford
> Hmm, this is a tricky one :) This solution is pretty ugly (I've not
> seriously tried to clean it up, either) and slow.
Probably a bit late on (sorry) but this is a cleaned up version that
does much the same and is marginally quicker.
--
Ross Bamford - ro...@roscopeco.REMOVE.co.uk
Stephen Waits
On Mar 29, 2006, at 3:44 AM, Ross Bamford wrote:
> Probably a bit late on (sorry) but this is a cleaned up version that
> does much the same and is marginally quicker.
Thanks Ross!
Timothy Bennett
me a while to come up with an algorithm that would actually produce
fewer keystrokes than the naive just write-out-every-code-so-long-as-
it-isn't-already-tested solution in every case. After trying a few
(I believe 3 is the number) poor solutions, I was getting frustrated,
so I figured I'd just try to work through it backwards. This worked
out rather well, I think (it beats the naive solution by over 70,000
strokes on the 5-digit, 3-stop case). It was pretty fun, too: I
actually had a reason to use lambda and shift (which I've never used
before), as well as inject (which I've only used once before).
Of course, it takes a while to run (the 5 digit, 3 stop code case
took nearly 40 minutes on a dual 2.7GHz PowerMac G5), so I'm
providing the output as well as the code.
So, here're my results:
user system total real
One stop digit:
2 digits 0.010000 0.000000 0.010000 ( 0.006755)
Search space exhausted.
Tested 100 of 100 codes in 271 keystrokes.
0 codes were tested more than once.
============================================================
3 digits 0.110000 0.000000 0.110000 ( 0.132552)
Search space exhausted.
Tested 1000 of 1000 codes in 3439 keystrokes.
0 codes were tested more than once.
============================================================
4 digits 9.580000 0.260000 9.840000 ( 11.005426)
Search space exhausted.
Tested 10000 of 10000 codes in 40951 keystrokes.
0 codes were tested more than once.
============================================================
5 digits 1208.900000 23.850000 1232.750000 (1439.590285)
Search space exhausted.
Tested 100000 of 100000 codes in 468682 keystrokes.
46 codes were tested more than once.
============================================================
Three stop digits:
2 digits 0.010000 0.000000 0.010000 ( 0.005834)
Search space exhausted.
Tested 100 of 100 codes in 219 keystrokes.
0 codes were tested more than once.
============================================================
3 digits 0.170000 0.000000 0.170000 ( 0.196276)
Search space exhausted.
Tested 1000 of 1000 codes in 2545 keystrokes.
4 codes were tested more than once.
============================================================
4 digits 16.580000 0.300000 16.880000 ( 19.149404)
Search space exhausted.
Tested 10000 of 10000 codes in 28105 keystrokes.
96 codes were tested more than once.
============================================================
5 digits 1910.240000 27.430000 1937.670000 (2240.603938)
Search space exhausted.
Tested 100000 of 100000 codes in 299559 keystrokes.
1517 codes were tested more than once.
============================================================
My code is attached, along with alarm_keypad.rb (which contains the
AlarmKeypad class).
Tim
Timothy Bennett
perspective. Anyone that's interested, please comment on this, I'm
curious what others' thoughts are.
It strikes me that there should be a mathematical way to determine
the minimum number of presses necessary to cover all key codes. This
would of course be based on the code length (n), and the number of
stop codes (m). I also believe that attaining the minimum number of
strokes requires that there be no duplicated codes, but that having
that nice "0 codes were tested more than once" message doesn't
guarantee that you have the best solution.
For examples, I'm going to talk about the easiest case to think
about: n = m = 1. That is, each code is just 1 digit in length, and
there is only one stop code (we'll choose 1, but it really doesn't
matter). Now, the general formula for the worst case (the brute
force just-enter-every-code method, without the tested? check), is (n
+ 1) * 10 ** n. In this example, the worst case is 20:
01112131415161718191
It is easy to see that the best case here is 19: 0112131415161718191
Now let's switch the example to n = 1, m = 3, where the stop codes
are 1, 2, and 3. This is now the best case:
01231415161718191 (length 17)
A little bit more experimentation should be enough to convince anyone
that the length of the best solution will be 20 - m when n = 1, and m
is in the range [1,9]. The formula breaks if m = 10, so I'm just
going to throw that out to keep the model simple right now. The 20
in this case is the length of the worst case scenario, so I believe
that this can be generalized to
worst-case-length - amount-of-overlap
The worst-case-length is of course (n + 1) * 10 ** n; I don't think
that needs further study. The part that I haven't been able to
generalize is the "amount of overlap." For n = 1, we're good, but
that's not very interesting, and the formula breaks when n = 2.
Take this case: n = 2, m = 1. I worked out a solution by hand, and I
don't believe it's possible to go below 271 keystrokes.
I haven't been able to figure out a general formula that works for n
= 1 and for that n = 2, m = 1 data point. I think it may be based on
the number of occurrences of the stop codes in the code set (let's
call this number k), but I'm not sure. To be clear on what I mean,
for the n = 2 case, the digit 1 appears 20 times in the 00..99
range. This is the same for 2 and 3, so if m = 3, stop codes appear
60 times in the code set.
In general, k = m * n * (10 ** (n - 1))
But I can't find a way to work k in, and I've only got those data
points to work with.
There are a couple of other potential data points, but I don't know
if they're valid. For example, my solution found the n = 2, m = 3
case solution with 219 strokes and no overlap. However, I don't know
for sure, yet, whether 219 is the correct minimum for that case. I
think it probably is, but I don't know.
To explain why I'm not sure, take this example for n = 1, m = 1:
000000112131415161718191
Running that through the keypad will produce no duplicate tests, but
it's obviously not a minimal solution. So, I can't trust that the
program's solution is the true minimum, even if no codes were tested
more than once.
Anyway, some other possible data points that my program generated
(but have not been verified) are:
n = 3, m = 1 => 3,439
n = 4, m = 1 => 40,951
For all other cases, my solution didn't manage to avoid duplicate
testing.
So, that's an outline of what I've figured out so far. If anyone has
ideas about how one might predict the length of the ideal solution,
speak up :)
Tim
Ross Bamford
> Hi, I wanted to discuss this problem from a more mathematical
> perspective. Anyone that's interested, please comment on this, I'm
> curious what others' thoughts are.
>
(I'm not a mathematician (by any stretch of the word) so I may be
utterly wrong in all of this).
I think this problem is basically the shortest common superstring
problem:
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE209.HTM
Which is basically how my solution (and I think yours too) approached
it. The upshot is that it's easy to find a common superstring, and even
a reasonably short common superstring, but very difficult to find the
_shortest_ or determine how long it would be (it's NP complete I
think).
That said, while working on it my limited mathematical knowledge kept
taunting me that there was a much easier way given that we were dealing
with numbers only, but I couldn't find it and gave up after a bit - I'd
love to see something like that done.
Timothy Bennett
>
> I think this problem is basically the shortest common superstring
> problem:
>
> http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE209.HTM
>
> Which is basically how my solution (and I think yours too) approached
> it. The upshot is that it's easy to find a common superstring, and
> even
> a reasonably short common superstring, but very difficult to find the
> _shortest_ or determine how long it would be (it's NP complete I
> think).
I definitely need to study more math and algorithms. Yes, this does
seem to be a variation on the shortest common superstring, and the
sources I'm finding say that it is NP-complete. Unfortunately, the
existence of the stop digits seems to complicate matters somewhat.
The most thorough discussion I've found online (so far, haven't
looked very long yet) is a PDF discussing, of all things, the Pokemon
trading card game: http://home.earthlink.net/~mstamp1/papers/poke.pdf
Nothing I've found so far discusses how one might predict the length
of the shortest common superstring, though. I feel, that for our
rather narrow problem domain, that it should be possible. Especially
since the substrings in the more traditional superstring problems are
random to some degree, while we know what all of our strings are.
Hm, I'll have to think on this more.
Tim
Ruby Quiz
tighter solution and it's not as big a difference as you might think. Here's
some output from running Ross's solution:
### 4 digits, [1,2,3] stops ###
user system total real
seq. 1.000000 0.020000 1.020000 ( 1.021674)
Search space exhausted.
Tested 10000 of 10000 codes in 50000 keystrokes.
6146 codes were tested more than once.
seq/chk 0.790000 0.000000 0.790000 ( 0.804365)
Search space exhausted.
Tested 10000 of 10000 codes in 33395 keystrokes.
2557 codes were tested more than once.
simple 2.840000 0.040000 2.880000 ( 2.930310)
Search space exhausted.
Tested 10000 of 10000 codes in 33830 keystrokes.
2721 codes were tested more than once.
best 665.050000 5.390000 670.440000 (678.840230)
Search space exhausted.
Tested 10000 of 10000 codes in 28687 keystrokes.
464 codes were tested more than once.
Compare that with the trivial tests in the quiz code:
Search space exhausted.
Tested 10000 of 10000 codes in 33635 keystrokes.
2664 codes were tested more than once.
At "best", Ross managed to trim 4,948 keystrokes and there was a hefty time
penalty to pay for getting that far.
Let's work through the code that amounts to the "best" search. First we need to
examine a helper class it makes use of:
# This was originally a delegator, but that was *slow*
class PoolStr < String
def initialize(obj, parent = nil)
super(obj)
@parent = parent
end
def suffixes(maxlen = nil)
@suffixes ||= get_suffixes(maxlen).map do |s|
PoolStr.new(s,self)
end
end
def prefixes(maxlen = nil)
@prefixes ||= get_suffixes(maxlen,reverse).map do |s|
PoolStr.new(s.reverse,self)
end
end
private
def get_suffixes(maxlen = nil, str = self)
start = maxlen ? str.length-maxlen : 1
(start..(str.length-1)).map do |i|
suf = str[i..-1]
suf
end
end
end
There's nothing too tricky hiding in here. Basically we have a String, that can
give us an Array of suffixes or prefixes as needed. Those are both found with
some simple index work in get_suffixes(). To handle prefixes, the String is
reversed before it goes in, and the suffixes are reversed as they come out to
transform them into prefixes. Note that both of these are cached the first time
they are figured, to speed up future calls. (I'm not sure what @parent is for
here. It doesn't seem to be used.)
Next we need to look at one more short helper, which turns out to be the heart
of the "seq." search from the results:
# Make our codes. Using random stop digits gives a more
# compressible string (less stop digits = longer string).
def mkpool(digits, stops)
(("0"*digits)..("9"*digits)).inject([]) do |ary,e|
ary << PoolStr.new("#{e}#{stops[rand(stops.length)] if stops}", nil)
end
end
Again, nothing tricky here. Assuming a parameter of 4 for digits, this builds
an Array of the codes from "0000" to "9999", with a random stop digit at the end
of each one.
Now we are ready for the main method of the "best" search:
# A more involved way, a simplified greedy heuristic
# that takes _forever_ but gives (slightly) better results.
def best_code(digits, stops = [1,2,3])
out = ""
pool = mkpool(digits, stops)
best = []
bestcode = nil
# Keep going until it's empty - if ever we can't find a match
# we'll just take one at random.
until pool.empty?
unless bestcode
# first iteration, just grab a start and carry on
bestscore = 0
bestcode = pool[rand(pool.length)]
else
# Get the array of arrays of best matches for the previous code.
# This array matches suffixes to best-fit prefixes for
# the previously-added code to find the most mergeable code
# (i.e. the one that shares most of it's prefix with the end
# of the output string).
#
# This contains at a given index all the codes that share that
# many letters of pre/suffix with 'need'. Eh? Well, it's like this:
#
# best for "1234" => [ nil, ["4321", "4048"], ["3412"], ["2348"]]
#
# Then, (one of) the highest scoring code(s) is taken from
# the top of the last nested array, best[best.length-1].
#
# We do it this way, rather than reversing the array, because
# we need to know what the actual score was, to merge the
# strings. Running on each iteration helps a bit
# with performance, since as time goes on the number of
# elements decreases.
best.clear
pool.each do |nxt|
next if nxt == bestcode
if r = (bestcode.suffixes & nxt.prefixes).first
(best[r.length] ||= []) << nxt
end
end
bestcode = (best[bestscore = best.length - 1] || EMPTYARRAY).first
# No best code? Nothing with matching pre/suff, so let's just grab
# a code at random instead to keep things moving.
unless bestcode
bestscore = 0
bestcode = pool[rand(pool.length)]
end
end
# Remove from the pool. Bit slow...
pool[pool.index(bestcode),1] = nil
# Chop off matched prefix from this code and append it
merged = bestcode[bestscore..-1]
out << merged
end
out
end
Here's the beast, but the comments are good and they will get us through it.
First you can see that the method makes a pool of all the codes, using the
mkpool() method we just examined. Now anytime this method doesn't have a
bestcode, like right at the beginning here, it just pulls one at random from the
pool. (You can see the code for this in the first unless clause and at the end
of the big else clause.)
The real work is done right after that big comment. The pool is walked
comparing prefixes of possible codes with the suffixes of the bestcode (our last
find). The matching groups are placed in an Array where the index is their
score or how many digits they share. The code then just chooses a match with
the highest score so it shares the most possible digits. (The EMPTYARRAY
constant used here is defined elsewhere in the code as `EMPTYARRAY = []`.)
From there the code merges the suffix of the selected code (we already have the
matching prefix from the last code), and adds it to the digits to enter. It
then loops until the pool is exhausted.
The actual solution is just one line from that:
best_code(n).split(//).each { |c| a.press c.to_i }
You saw the results of that at the beginning of this summary. You would have to
examine usage for this code carefully though, to determine if shaving around
5,000 keystrokes is worth the unfortunately large speed penalty. It's all about
tradeoffs.
A huge thank you to the quiz creator for a challenging little problem and the
two brave souls who were equal to the task.
Tomorrow's quiz is still up in the air! We're trying to sneak in a research
project we can all help with, if we can get it ready in time...
Ross Bamford
> This quiz turned out to be surprisingly tough. Ross Bamford seemed to get the
> tighter solution and it's not as big a difference as you might think.
Thanks both James and Stephen for a good quiz, this one really got me
thinking :) I knew my solution was slow, and at least I can now prove it
- check out Timothy Bennett's solution (which I think just missed the
summary, unfortunately) - it kicks my solution's ass on performance and
comes up with similar (even slightly shorter) codes. Good work, Tim!
James Edward Gray II
> check out Timothy Bennett's solution (which I think just missed the
> summary, unfortunately)
Yes, I was done with the summary when this came in. :( It is very
nice though.
James Edward Gray II
Stephen Waits
On Mar 31, 2006, at 5:54 AM, James Edward Gray II wrote:
> It is very nice though.
Indeed, as were all of the solutions. Thanks everyone for
participating!
--Steve