TWC 119: Task #1, Swap Nibbles & Task #2, Sequence without 1-on-1
Hello everyone, I'm back after a year's absence, good to see everything is going as strong as ever. I have some extra time this weekend, so thought I'd try my hand at an answer again.
But, oh golly, looking back over my earlier posts on earlier problems was just painful--too many details! Going forward I'll just broad-brush things (and I mean it this time). If anyone has a question about details, then ask about them in the comments.
The swap nibbles problem is equivalent to a "swap hex-chars problem" and since we have the bigint module then any hex string can be represented by an integer. When a little investigation brought up that every bigint object has an as_hex() method, I found the restriction to positive integers less than 255 too restrictive: I decided to do them all! (Well, not quite all, since there are an infinite number of integers, but you know what I mean.)
There is one more thing: Swapping. I was excited to use a swapping technique that I learned about when I asked for one on perlmonks a decade ago. (There are other good ones in that thread too, but this is a one-liner.)
The meat of the script is in the
$ ./ch-1.pl --test ok 1 - First example: 101 -> 86 ok 2 - Second example: 18 -> 33 ok 3 - Composition is identity. ok 4 - Bytes of twin nybbles are unchanged. ok 5 - Handles a special 770 digit number. 1..5
The second task reminded me of my favorite perl book, Higher Order Perl (HOP) and its exposition on Breadth-First Search (BFS) (start around page 213). The task given this week is closely related to the problem solved in that section of HOP for finding palindromes of strings composed of the letters A, B, C.
The main function is
seq123() and the helper function to select from the terms is
$ ./ch-2.pl --test ok 1 - First Example: 5 -> 13 ok 2 - Second Example: 10 -> 32 ok 3 - Third Example: 60 -> 2223 ok 4 - First 15 in problem description is correct. 1..4
The only thing left to address is my guilt.
- Proof of ascending numerical sort not provided. The terms come out in ascending numerical sort as an effect of construction of the BFS, but that's all the justification I'm going to give here.
- The approach taken is for the result as a one-off. It doesn't matter if you run fresh from the command line as a user, but the approach is inefficient for the testing functionality because the same (potentially large) BFS list of numbers is being recreated again and again. So yes, I'm nagged by the thought that I should have used memoization in testing the code.
I guess I'll just have to give my permission to treat this as fun and not work ;-)