L-99 - Lists

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

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

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

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

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

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

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.