How to Solve it by Computer #1

How to solve it by computer

by R.G. Dromey (1982)

Intro:how-to-solve-it-by-computer-cover

I quite enjoy reading older ‘technical’ books. I think mainly because they have less fluff as the new ones. I saw this one How to Solve it by Computer recommended a few times. It’s an homage to Polya’s How to Solve it which covers mathematical problem solving. I never read Polya’s book more than a couple of pages so I can’t say how similar they are. How to Solve it by Computer covers several of the fundamental algorithms, especially around the time which is 1982. So it’s over 30 years old but nonetheless covers a lot of more modern books. In comparison to The Algorithm Design Manual LINK it’s a lot more ‘user-friendly’ and accessible. The single subchapters build on each other to some degree, everything is explained in detail and very thoroughly. I think it’s great for intermediate learners. If you new to programming it’s overwhelming probably and a bit boring. However, if you have solved some of the problems yourself and you want to go deeper it’s a great book.

I present you some of the solutions to problems in this book which I solved in Clojure. I skipped most problems, mostly because I already solved them in the past or I knew how to solve them in my head. So, I focused on solving more demanding problems. I cover lots of different algorithms from series, prime numbers, pseudo-random numbers to textwrap and permutations.

I enjoyed solving the problems and learned quite a bit. I also feel much more comfortable in Clojure which is splendid. I can recommend this book and think it’s a well-written book. Not a lot of fluff, lots of explanations and a good coverage of basic algorithms.

Enjoy.

 

Problem 2.1.2: Design an algorithm that makes the following exchanges:

a -> b -> c -> a

I’ll write this in pseudo code:

tmp = c
c = b
b = a
a = tmp

More interesting is the case for an arbitrary number of variables. Let’s say we have an array A with length N. We want the value of A[1] in A[2], A[2] in A[3], etc. And the value of A[N] in A[1].

tmp = A[N]
for i = N to 2:
A[I-1] = A[I]
A[1] = tmp

 

Inspirational quote Part 3

h) The program doesn’t generate pictures without out-of-bounds problems

Okay. So what do I do? Pretty simple again. I knew I had multiple parameters which I could adjust. I started off with the textwrap length. At first I set it to 30 or so characters. However, if the starting point was too far to the right it easily got into problems. So I wrote a function which computed the text wrap based on the starting position and image size. Problem solved.

i) The text jumps out-of-bounds at the bottom

Yeah, the text was too long. The next step? Scaling the font size. I wrote a simple function which scales the font size (which is randomized) by a factor which decreases when the text size increases. Now I could generate really long texts without an out-of-bounds jump.

j) The text was really small

And a second fix I started to make the minimum sized font size and the problem was solved.

These were my steps for creating the picture generating functions. There were other problems I had to solve but I solved them before so it was quite easy and a bit boring. If you want to see how I solved the problems check out github.

Inspirational quote Part 2

The next problem was that the input could be varied in length. There’s maybe 80 characters or 200.
e) I want to display my text properly when it’s too long to fit into one line

I thought about the problem and thought about different design decisions. I could either shrink my font size or break my text into lines. I liked the latter better. So I looked up solutions. Gladly, Python provides textwrap which wraps text for you given a maximum length. Problem solved.

It worked so far however, it was rather uninteresting because the text was in the same size and same location. The next step was to write a function which varies the font size (easy) and finds locations which are interesting.
f) I want interesting locations for the text

My first attempt was to use the golden ratio. Still only one location. So I started to do a bit more. I thought about it and thought that it could vary by a certain degree but not too much. I wrote something like

>>> randint(2,4) / 9.0

After I read it, it reminded me of bootstrap’s grid layout. So I basically created a simple grid for the inspirational quotes.

Now a new problem appeared.
g) Text shouldn’t appear outside of the picture

When text was long or my available grid was pretty small the text would leave the bounds. Not ideal. A good thing about the text is that I works from left to right and from up to down, i.e. I only have to check the most far right text and the most far down text against the image dimensions.

Here I made a bit lazy but imho interesting solution. In case the text gets out-of-bounds I just let the function generate a new one. It basically is a function like that:

def generate_picture():
    image = generate()
    if not out_of_bounds():
        return image
    else:
        return generate_picture()

The use of recursion here is pretty neat because it makes the function so simple and in my opinion quite logical. What can happen of course that it runs forever. In my test cases (even pretty long text) it worked pretty fast but that’s a real possibility. However, it was a problem at first.

Part 3 tomorrow

Inspirational quote Part 1

Every time I see the hostility in the Python movement I get drawn nearer to Clojure. It’s crazy but it’s something that can destroy a community.

Nonetheless, I wrote some code in Python. I was looking around for a project to apply some Clojure. I had some idea but none was overwhelming engaging.

Thankfully, last evening a found a post in /r/RequestABot on which someone requested a bot which should create inspirational quote pictures based on comments. It was an elaborate joke but some intriguing problem.

I was engaged and started writing some code. I just wanted my program to generate inspirational quote pictures based on a random string.

I think it may be interesting how I approached the problem. I’ve written some picture generating software – albeit pretty simple – in the past. So I started off looking at Pillow which is a fork of PIL – the Python Image Library.

My first to problems were:
a) How can I load an image into Python?
b) How can I write text with a specific font into the image?

To test that I downloaded a background image and a font from GoogleFonts. Then I started the REPL. This is something I did even more since I started writing some Clojure. The focus on the REPL in Clojure is pretty big so I just adopted it into Python.

Solving a) was pretty simple. I just read the docs for Pillow – more specifically the tutorial and the first code example reads:

To load an image from a file, use the open() function in the Image module:

>>> from PIL import Image
>>> im = Image.open("lena.ppm")

Bingo. So I started on the REPL and typed:

>>> im = Image.open("backgrounds/test.jpg")

It worked. The next step was looking at the second problem. How do I load a font? Again, docs and there was a font module. I simply tried it out and it worked without problems. I don’t go into the details, you can read the code if you like.

Now that these two things worked I wrote down my first code. Basically I copy and pasted my working REPL commands.

I solved problem a) and b) but now new problems appeared:
c) I wanted to get a random background
d) I wanted to get a random font

These problems are very similar. So what I really wanted was:
c+d) I want to get a random file from a directory

Also easy to solve. It worked and I put everything together. Now I had a function which returned a random background and a random font. My composition function was the same and it worked fine.

Part 2 tomorrow