EoPL - Ch 1 - Ex 17

Exercise 17 in Chapter 1 of Essentials of Programming Languages furthers the aims of Exercise 15 and Exercise 16. The subparts of Exercise 17 are more algorithmic in nature than the previous exercises, however. Namely, they touch upon sorting and binary tree traversal.

Ex. 17, Pt. 1
Define a function path : (n : int) * (bst : BinarySearchTree) -> [left|right] that returns a list, where each element is either left or right, that describes the path to the node in bst which contains n. If that node is the root node, return an empty list. Solution.

Ex. 17, Pt. 2
Define a function sort : (lon : [int]) -> [int] that returns a list like lon but with all elements sorted in increasing order. Solution.

Ex. 17, Pt. 3
Define a function sort : (predicate : int * int -> bool) * (lon : [int]) -> [int] that returns a list like lon but with all elements sorted according to the comparison predicate. Solution.

TopCoder - SRM 144 - Div 2 - 550 Pt

From Single Round Match No. 144 of TopCoder's Algorithm Competition:
Write a method decode that, given a string which represents an encoded binary string, where the encoding method dictates bitenc[i] = bitorig[i-1] + bitorig[i] + bitorig[i+1], returns a string[] containing the two possible original binary strings. These two possible originals are yielded by assuming either bitorig[0] == 0 or bitorig[0] == 1. If the encoded string cannot be produced via an assumption, return "NONE" in place of a binary string.
(Full problem specification is copyright TopCoder; and, can be found in the TopCoder problem archives.)

Solution.
Unit Tests For Sample Data.

This problem was used as the Division 2 550-point problem and as the Division 1 300-point problem. The solution here is to rearrange bitenc[i] = bitorig[i-1] + bitorig[i] + bitorig[i+1] to yield bitorig[j] = bitenc[j-1] - bitorig[j-1] - bitorig[j-2]. Then once we generate our original, we only have to verify that bitenc[ilast] == bitorig[ilast-1] + bitorig[ilast] (and that the original contains only binary digits).

ShiftSrt

ShiftSrt is a script I wrote to time shift video file subtitles stored in .srt format (see SubRip for .srt fomat examples).

My motivation for the script came when I downloaded a video with accompanying .srt subtitle file; and, I found the subtitles were out of sync with the video. Specifically, all of the subtitles were timed to display two and half seconds before the actual dialog occurred.

I first wrote the script in Python to brush up on my (limited) Python knowledge. I then ported it to Perl (same reasons).

Using the script is easy. Simply provide the following command line arguments (in order) when executing:

1. path to the .srt file
2. amount of time to shift by in milliseconds

Source (Python).
Source (Perl).

EoPL - Ch 1 - Ex 16

Exercise 16 in Chapter 1 of Essentials of Programming Languages builds on the progress of Exercise 15. It further explores programming with lists by delving into deeply-nested list structures (pun intended). Note that the up function in Part 1 plays counterpart to the down function from Exercise 15, Part 9.

Ex. 16, Pt. 1
Define a function up : (lst : [_]) -> [_] that returns a list like lst but with each list-element (element of type list) replaced by the elements that that list-element contains. Solution.

Ex. 16, Pt. 2
Define a function swapper : (s1 : 'a) * (s2 : 'a) * (lst : [_]) -> [_] that returns a list like lst but with all instances of s1 replaced by s2, and all instances of s2 replaced by s1. Solution.

Ex. 16, Pt. 3
Define a function count-occurrences : (s : 'a) * (slist : [_]) -> int that returns the number of times s occurs in slist, including occurrences nested arbitrarily deep in list-elements of slist. Solution.

Ex. 16, Pt. 4
Define a function flatten : (slist : [_]) -> [_] that returns a list of all non-list-elements in slist (including non-list-elements nested arbitrarily deep within list-elements) in depth-first-traversal order. Solution.

Ex. 16, Pt. 5
Define a function merge : (lon1 : [int]) * (lon2 : [int]) -> [int] that returns a list, in ascending order, of the elements in lon1 and in lon2, where lon1 and lon2 are each already sorted in ascending order themselves. Solution.

TopCoder - SRM 144 - Div 2 - 200 Pt

From Single Round Match No. 144 of TopCoder's Algorithm Competition:
Write a method whatTime which takes an int representing the number of seconds since midnight on some day, and returns a string formatted as H:M:S.
(Full problem specification is copyright TopCoder; and, can be found in the TopCoder problem archives.)

Solution.
Unit Tests For Sample Data.

This problem was used as the Division 2 200-point problem. Being a 200-point problem, it's very straightforward; and, there are no real "gotchas" involved in the solution.

EoPL - Ch 1 - Ex 15

Exercise 15 in Chapter 1 of Essentials of Programming Languages attempts to familiarize the reader with programming in the Scheme. It's split into ten parts that together provide a gentle introduction to working with lists, and to a lesser extent vectors, in a functional programming language.

Ex. 15, Pt. 1
Define a function duple : (n : int) * (x : 'a) -> ['a] that returns a list containing n copies of x. Solution.

Ex. 15, Pt. 2
Define a function invert : (lst : [('a,'b)]) -> [('b,'a)] that returns a list like lst but with each pair element of reversed. Solution.

Ex. 15, Pt. 3
Define a function filter-in : (pred : 'a -> bool) * (lst : ['a]) -> ['a] that returns a list of the elements in lst for which pred succeeds. Solution.

Ex. 15, Pt. 4
Define a function every? : (pred : 'a -> bool) * (lst : ['a]) -> bool that returns false if pred fails for any element of lst, or otherwise returns true. Solution.

Ex. 15, Pt. 5
Define a function exists? : (pred : 'a -> bool) * (lst : ['a]) -> bool that returns true if pred succeeds for any element of lst, or otherwise returns false. Solution.

Ex. 15, Pt. 6
Define a function vector-index : (pred : 'a -> bool) * (v : #['a]) -> int|FALSE that returns the zero-based index of the first element in v for which pred succeeds, or returns false if no such element exists. Solution.

Ex. 15, Pt. 7
Define a function list-set : (lst : ['a]) * (n : int) * (x : 'a) -> ['a] that returns a list similar to lst, except that the n-th (using zero-based indexing) element is replaced with x. Solution.

Ex. 15, Pt. 8
Define a function product : (los1 : ['a]) * (los2 : ['b]) -> [('a, 'b)] that returns a list of pairs (in any order) that represents the Cartesian product of los1 and los2. Solution.

Ex. 15, Pt. 9
Define a function down : (lst : [_]) -> [[_]] that returns a list like lst but with each element wrapped in its own (single-element) list. Solution.

Ex. 15, Pt. 10
Define a function vector-append-list : (v : #['a]) * (lst : ['a]) -> #['a] that returns a new vector with the elements of v followed by the elements of lst. Do not use any built-in vector-to-list, list-to-vector, or append functions. Solution.

Introduction

My name is Hef; and, I like to solve problems. This blog is an amalgam of various academic exercises, riddles, and puzzles. Whenever I solve a problem I think is interesting, I post it here with my solution and any commentary I may have.

This blog's overarching purpose is to record a history of problems I've solved; to motivate me to solve ever more problems; and to yield insights towards continuously improving my problem solving abilities.