TWC 119: Task #1, Swap Nibbles & Task #2, Sequence without 1-on-1

TWC Task #1, Swap Nibbles

jaredor submission for Task #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 nybble_swap() function.

$ ./ --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.

TWC Task #2, Sequence without 1-on-1

jaredor submission for Task #2

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 get_nth().

$ ./ --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.

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 ;-)

1 Comment

Leave a comment

About Jared Martin

user-pic I blog about Perl.