30 Day Challenge

My friend Chris and I are doing a 30-day daily programming challenge, inspired by Sabrina's 30-day drawing challenge (which you can find here).

We will program a solution to a randomly selected algorithm problem each day. We can choose our programming language of choice from a list, although we can only use each language a certain number of times. This forces us to step outside of our comfort zones and use, e.g. INTERCAL or Q#, instead of using Python for every challenge.

Read the 'official' rules and constraints here

Solutions

We are starting the challenge as of June 15, 2018. As we complete each challenge, I will post my solution code here.

Day 1: Huffman Coding Method

The task for the day is to implement the Huffman Coding Method. That is, given a text string, we are to construct the Huffman Tree describing the appropriate codeword for that string.

I haven't practiced with Haskell in a while, and this program (although painfully small) is a bit larger and messier than I am used to in Haskell. I thought it would be fun to do a naturally iterative algorithm functionally and recursively. Here goes:

CODE

Day 2: Bresenham Line Algorithm

Oh boy! This took me much longer than expected (I used Java today, but unfortunately that didn't help as much as I had hoped). I learned this algorithm for the first time (exciting!), and had a lot of trouble handling the various cases (xf < x0, yf < y0, and handling steep slopes).

But with grit and the wikipedia page, I prevailed! Here's the Joe:

CODE

Day 3: Insertion Sort

Not much to say today. We were going to do the Finite Difference Method, but we both spent too much time with our fathers for Fathers' Day. This is insertion sort: no tricks, no shenanigans. I used PHP because I was tired.

CODE

Catchup Day

I've been over-exerting myself lately, and I need to get some rest. I am partway through an implementation of BFS, and I will finish it tomorrow morning. Sorry about that.

Day 4: Breadth-First Search

In order to do BFS, I had to implement a graph object and do some hefty I/O (at least, heftier than I would like to do in Haskell). I decided to make my life easier by choosing Python, which is object-oriented (making graph management easier), and which does most of my I/O automagically.

I had the misfortune of following the June 20, 2018 version of this article on BFS, which includes the most convoluted and general expression of the BFS algorithm. Many of my problems resulted in a misunderstanding caused by that nasty code in the Pseudocode section.

I'm pretty sick of BFS. Anyway, here is the code.

CODE

Day 5: Specific Instance of a Scheduling Problem

This problem was my idea, so it is my responsibility to elaborate.

I'm pulling the problem from Levesque's Thinking As Computation, page 117, problem 7. Here it is:

"Consider a course timetable for a Fine Arts sutdent at a mythical university. The student wants to take a course in art, music, film, and dance, and each of these has three hours of classes a week. To accommodate a variety of timing constraints, some courses offer two sections at different times.

  • There are two possible sections for art. One is offered MWF10, and the other, MWF11.
  • There is a single section of dance: Friday 1-4
  • Music can be taken either Monday at 11, Wednesday at 3, and Friday at 3, or Monday at 2, Wednesday at 2, and Friday at 11.
  • There are two sections of film: one on Monday at 11, Wednesday at 11, and Friday at noon, and one on Monday at noon, Wednesday at noon, and Wednesday at 3.

In addition, the student wants a free hour for lunch each day at noon or at 1. Write a Prolog program that generates a timetable for the student."

EDIT: Neither of us were motivated to program in Prolog; the language is not useful, practical, nor is it programmer-friendly. Most importantly, Prolog is not even fun (which is our redeeming quality for, e.g., Q# and INTERCAL). We both already know Prolog, so it's not even an educational experience. TLDR: We weren't really feeling it.

Instead, we are going to reassign a random problem for the day! In order to maintain our days, we are going to do the Polish Notation Arithmetic problem twice (we decided on it because we want to see a stack implemented in very different language environments). We are also going to allow one more use of Java, to balance things out.

Day 5 Redux: Image Filtering

We hit random, and got image filtering!