Hef Does Homework

L-99 - Lists

2008-08-13T18:13:00.000-07:00

L-99: Ninety-Nine Lisp Problems--or as I like to call it, I got 99 problems but a LISP ain't one--is a problem set designed to test prowess in Lisp (or Scheme, in my case), as well as algorithmic thinking. The problems are divided into subsets, each subset having a particular focus: lists, arithmetic, graphs, etc.

The first subset, comprised of problems 1 through 28, is the list-focused subset. The problems start easy; but, difficulty increases from there. Things get interesting around Problems 26 and 27, which deal with combinatoric set generation. I found Problem 27, in particular, to be challenging; and, it required a fair bit of thought to reach my current solution. The last two problems, Problems 28A and 28B, deal with sorting. I also found Problem 28B to be challenging; but, it was easier than Problem 27 to wrap my mind around. Perhaps the difference there is due simply to algorithm familiarity--which is good, when learning new things is the end game. Solutions.

EoPL - Ch 1 - Exs 19-26

2008-07-27T17:45:00.000-07:00

Exercises 19 through 26 in Chapter 1 of Essentials of Programming Languages begin delving into parsing concepts. In particular, they explore the concepts of free and bound variables in lambda expressions.

In the book, Figure 1.1 provides an implementation of the definition of occurring free and occuring bound (given by Definition 1.3.3). All the exercises are based on this definition; and, Exercises 22 through 26 focus on extending it.

Ex. 19
Define a function free-vars that takes a list structure representing a lambda calculus expression (as referenced by Definition 1.3.3), and returns a set of all variables that occur free within the expression. Similarly, define a function bound-vars that returns a set of all variables that occur bound in a given expression. Solution.

Ex. 20
Give an example of a lambda calculus expression in which the same variable occurs free, but also has a value independent of its free occurence. Solution.

Ex. 21
Give an example of a lambda calculus expression in which the same variable occurs both free and bound. Solution: The solution for Exercise 20 also suffices for this exercise. In fact, I do not see much difference between the problems.

Ex. 22
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to allow lambda abstractions and applications with any number of parameters. Solution.

Ex. 23
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include if expressions. Solution.

Ex. 24
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include let and let* expressions. Solution.

Ex. 25
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include expressions of the form (quote [datum]). Solution.

Ex. 26
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include set! assignment expressions. Solution.

The inclusion of set! expressions in Exercise 26 is somewhat ambiguous: if a variable that was not in scope (i.e. free) is set!-ed does it become a bound variable? The actual Scheme interpreter only allows in-scope (i.e. bound) variables to be set!-ed, therefore set! never makes a bound variable from a free one. With that in mind, I chose to make my solution disregard appearance as the first operand in a set! statement as criteria for a bound variable.

TopCoder - SRM 145 - Div 2

2008-07-16T17:43:00.000-07:00

The following problems are from Single Round Match No. 145, Division 2 of TopCoder's Algorithm Competition. (Full problem specifications are copyright TopCoder; and, can be found in the TopCoder problem archives.)

250 Point Problem
Write a method count that, given a matrix and a set of fill values, returns the number of elements in the matrix that make up the fill value set.
Solution.
Unit Tests For Sample Data.

I found the original problem statement for this problem to be very ambiguous. The actual context of the problem is image dithering; the given matrix represents a colored display, and the set of fill values represents dithering colors. The solution objective is to count the number of pixels in the display that are part of a dithered color. The ambiguity is in how to treat a single pixel that is colored with one of the dithering colors, but is surrounded by pixels which are not colored by dithering colors. The sample data for the problems hints that such a pixel should be counted, while my (very basic) understanding of image dithering suggests such a pixel should not be counted. In the end, I designed my algorithm to do the latter.

500 Point Problem
Write a method getPercentages that, given a time quantity in HH:MM:SS format, returns the number of times a whole percentage would be encountered if a timer were to count up and, each second, compute the ratio of elapsed time to total time. This count of whole percentages should exclude 0% and 100%.
Solution.
Unit Tests For Sample Data.

From a different perspective, this problem is actually asking how many pieces (minus one) a quantity can be divided into, with the stipulations that each piece must represent a whole percentage of the quantity, and that each piece must consist of a whole number of units. Because of the first stipulation, the maximum number of pieces we are interested in is 100. Thus, a simple, brute force solution which tests the two stipulations on 100 pieces, 99 pieces, 98 pieces, etc, works well.

1100 Point Problem
Write a method motorUse which simulates a motorized vending machine and, when given list of purchases, returns the number of seconds the motor is active.
Solution.
Unit Tests For Sample Data.

This problem was different, in the algorithmic sense, than other TopCoder problems I've seen. The difficulty in it came mostly from having to adhere to the many details in the problem specification. Consequently, the problem seemed more a software engineering puzzle; but, it was still a fun change of pace.

Sloganizer & Flipper

2008-07-13T20:33:00.000-07:00

Sloganizer and Flipper are two Google Gadgets I created for fun. They are both very simple; but they served as a nice introduction to the Google Gadget API.

Sloganizer takes a word or phrase and injects it into a random marketing slogan, to (hopefully) hilarious effect.

Flipper takes a word or phrase and "flips" it horizontally and vertically, via visually approximate unicode characters.

EoPL - Ch 1 - Ex 18

2008-07-09T17:48:00.000-07:00

Exercise 18 in Chapter 1 of Essentials of Programming Languages is our last Scheme introductory programming exercise. It broaches the topic of function composition.

Ex. 18, Pt. 1
Define a function compose : (f1 : 'b -> 'c) * (f2 : a' -> b') -> 'c that returns the composition of the functions f1 and f2, such that ((compose f g) x) is equivalent to (f (g x)). Solution.

Ex. 18, Pt. 2
Define a function car&cdr : (s : 'a) * (slist : ['a]) * (errvalue: 'b) -> [_] that returns an expression which, when evaluated, produces a function in turn. This expression should be comprised of car, cdr, and compose (see Pt. 1) applications only. The function generated by this expression, when given a list similar to slist, should return the element in the given list that is at the same position as the first occurrence of s in slist. If slist does not contain an instance of s, car&cdr should return errvalue instead of an expression. Solution.

Ex. 18, Pt. 3
Define a function car&cdr2 : (s : 'a) * (slist : ['a]) * (errvalue: 'b) -> [_] that returns an expression which, when evaluated, produces a function in turn. This expression should be comprised of car and cdr applications, and lambda expressions only. The function generated by this expression, when given a list similar to slist, should return the element in the given list that is at the same position as the first occurrence of s in slist. If slist does not contain an instance of s, car&cdr2 should return errvalue instead of an expression. Solution.

TopCoder - SRM 144 - Div 2 - 1100 Pt

2008-07-06T21:34:00.000-07:00

From Single Round Match No. 144 of TopCoder's Algorithm Competition:
Write a method estimateTimeOut that, given an edge-weighted tree, returns the minimum cost to visit all nodes. [Plus some backstory about a power outage, underground transformers, and a catacombic sewer.]
(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 1100-point problem. It reminds me of certain ACM-ICPC problems: mix two parts strong underlying data structure and algorithm with one part playful, semi-verbose problem description.

The solution to the problem is to realize that each edge in the tree will need to be traversed twice (once to go to a node, and once to come back from it) in order to visit all nodes, except for the edges on the path to the last visited node. Therefore, the minimum cost can be calculated by finding the most expensive node to reach (from the tree's root), and subtracting the cost reaching that node from twice the sum of all edge weights.

BNN v1

2008-07-02T18:34:00.000-07:00

Bitmapping Neural Network (version 1) is a simple neural network that I prototyped after reading an introduction to artificial neural networks (ANNs). The idea behind the project is to explore ANN fundamentals by creating a neural network which exrapolates patterns from bitmaps.

Version 1 (Source) is comprised of two main classes, NeuralNet and Neuron, and one utility class, BitmapUtil. In this initial version, the neural network's capabilities are limited to downscaling (resizing) a perfect square 0/1 bitmap. As an additional restriction, all input bitmaps must be an integral constant ratio larger than the expected output (i.e. all input bitmaps must be the same size).

To test BNN v1, I ran 4 teach cases, followed by 5 use cases on the same NeuralNet instance. Each case had an expected output length of 10 (i.e. a 10x10 output bitmap), and an input length-ratio of 2 (i.e. a 20x20 input bitmap). The results of the test were interesting because the code knows nothing of resizing algorithms; and, yet, it was still able to accurately resize a bitmap with multiple patterns (use 4) and nested patterns (use 5). The teach cases were interesting precisely because they were uninteresting--four very simple patterns allowed accurate behavior for more complex input.

Of all the teach cases, however, none taught non-zero data to the neurons which correpsonded to the outer-most bits of the output bitmap. Thus in any use case involving non-zero input data for those neurons the output bitmap will be incorrect. This omission exposes the obvious limitation of neural networks: they are only as smart as their teaching mechanism (in this case, handcrafted sample data). Future work for the project will probably involve addressing this limitation, among other things.

EoPL - Ch 1 - Ex 17

2008-06-29T20:06:00.000-07:00

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

2008-06-25T16:55:00.000-07:00

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 bit_enc[i] = bit_orig[i-1] + bit_orig[i] + bit_orig[i+1], returns a string[] containing the two possible original binary strings. These two possible originals are yielded by assuming either bit_orig[0] == 0 or bit_orig[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 bit_enc[i] = bit_orig[i-1] + bit_orig[i] + bit_orig[i+1] to yield bit_orig[j] = bit_enc[j-1] - bit_orig[j-1] - bit_orig[j-2]. Then once we generate our original, we only have to verify that bit_enc[i_last] == bit_orig[i_last-1] + bit_orig[i_last] (and that the original contains only binary digits).

ShiftSrt

2008-06-22T20:15:00.000-07:00

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:

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

Source (Python).
Source (Perl).

EoPL - Ch 1 - Ex 16

2008-06-18T16:23:00.000-07:00

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

2008-06-15T18:52:00.000-07:00

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.

Glass Half Full. Cork, Bottle, Coin. Globe Traversal.

2008-06-11T17:49:00.000-07:00

Glass Half Full (source: [wu:riddles]):
You are in an empty room and you have a transparent glass of water. The glass is a right cylinder, and it looks like it's half full, but you're not sure. How can you accurately figure out whether the glass is half full, more than half full, or less than half full? You have no rulers or writing utensils.

Solution:
Spread your thumb and index finger on one hand to measure the distance between the top of the glass and the water line. Lock your thumb and index finger in that position. Next, move your hand down such that whichever finger was at the top of the glass is now positioned at the water line. Now, if your other finger is exactly at the the bottom of the glass, the glass is half full. If that other finger is below the bottom of the glass, the glass is less than half full. Otherwise (if that other finger is between the water line and the bottom of the glass), the glass is more than half full.

This problem is a good example of simple solutions being overlooked. The first two solutions I came up with--rapidly placing the glass upside-down on the floor; or, raising one edge of the glass (tipping the glass) by a length equal the base's diameter--were both more complex and less accurate.

Cork, Bottle, Coin ([wu:riddles]):
If you were to put a coin into an empty bottle and then insert a cork in the bottle's opening, how could you remove the coin without taking out the cork or breaking the bottle?

Solution:
Push the cork all the way inside the bottle. Then, remove the coin.

Another simple solution that can be overlooked. My guess as to why is that people are accustomed to undoing things by way of the opposite of what they did in the first place (e.g., if the door was opened via a pull, it should be closed via a push). The lesson here is to question your approach--or more broadly, your assumptions.

Globe Traversal (source: [wu:riddles]):
How many places are there on the earth that one could walk one mile south, then one mile west, then one mile north and end up in the same spot? To be precise, let's assume the earth is a solid smooth sphere, so oceans and mountains and other such things do not exist. You can start at any point on the sphere. Also, the rotation of the earth has nothing to do with the solution; you can assume you're walking on a static sphere if that makes the problem less complicated to you.

Solution:
Infinitely many. To see this, temporarily disregard the south and north legs of the journey, as they will eventually cancel each other out. Now, the only way to travel west for some distance and end up in the same place we started is if we circle the globe. Thus we pick a cross-section of the earth perpendicular to its axis, say near the South Pole, which produces a circle having a circumference of one mile. Note that this circle is comprised (at least theoretically) of infinitely many points; and, that walking around the edge of this circle for one mile will always take us back to our original position. Now we factor the south and north legs of the journey back in by simply shifting our infinitely many starting points one mile north.

This is another solution that involves an atypical "undo action." Specifically, typical reasoning suggests that for each unit traveled in one direction, one must travel one unit in the opposite direction in order to return to where to he started.

EoPL - Ch 1 - Ex 15

2008-06-08T19:07:00.000-07:00

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

2008-06-04T20:26:00.000-07:00

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.