Project Euler 117

I enjoy solving Project Euler problems in my downtime. Problem 117 is one that I’ve looked at multiple times, but never came up with a good solution. The premise is easy enough, but, as with most Euler problems, the scale of the problem presents issues.

Using a combination of grey square tiles and oblong tiles chosen from: red tiles (measuring two units), green tiles (measuring three units), and blue tiles (measuring four units), it is possible to tile a row measuring five units in length in exactly fifteen different ways.

How many ways can a row measuring fifty units in length be tiled?

For the context of my solution, I am representing the tiles as an array or list of integers that each represent the length of a tile. For example, (1, 3, 1) would be a black, green, and black tile taking up a total of 5 spaces.

Brute Force sometimes works on these problems, but more often than not, they take far too long to complete. I don’t feel like I’ve “solved” one of these problems if the solution takes more than a second or two. My first naive attempt to solve this problem was to attack it recursively and build all the combinations of tiles. After letting it run for a few minutes, I gave up and assumed there must be a better way.

While building each tile combination was prohibitively time consuming, I found that I could still use recursion to get the base combinations for the tiles. There are only about 1000 of those, so the trick will be permuting them to get the full count. Well, as it turns out, this led to a few more problems.

Using the permutations tool provided in itertools proved to be too slow as well. First of all, it was finding too many solutions. For example:
>>> for i in list(itertools.permutations([1, 1, 2, 2])): print i
(1, 1, 2, 2)
(1, 1, 2, 2)
(1, 2, 1, 2)
(1, 2, 2, 1)
(1, 2, 1, 2)
(1, 2, 2, 1)
(1, 1, 2, 2)
(1, 1, 2, 2)
(1, 2, 1, 2)
(1, 2, 2, 1)
(1, 2, 1, 2)
(1, 2, 2, 1)
(2, 1, 1, 2)
(2, 1, 2, 1)
(2, 1, 1, 2)
(2, 1, 2, 1)
(2, 2, 1, 1)
(2, 2, 1, 1)
(2, 1, 1, 2)
(2, 1, 2, 1)
(2, 1, 1, 2)
(2, 1, 2, 1)
(2, 2, 1, 1)
(2, 2, 1, 1)

When in reality many of those are equivalent in the terms of the problem conditions. What we want is a set which looks more like this:
>>> for i in set(itertools.permutations([1, 1, 2, 2])): print i
(1, 1, 2, 2)
(2, 1, 2, 1)
(2, 1, 1, 2)
(1, 2, 2, 1)
(1, 2, 1, 2)
(2, 2, 1, 1)

That works, but the program still has to calculate all the permutations that we are throwing out which is time consuming; at the most, a set will have 50 tiles which is 50! permutations. That’s  30414093201713378043612608166064768844377641568960512000000000000 permutations, which is really just an insane amount! So that won’t do.

Well, we don’t need to know the permutations, just the amount of permutations! Let’s see if we can find a formula for that. The general formula that I found which researching permutations looks like this:

where n is the number of terms, and r is the number of terms you are choosing from your source pool. In this case, we are going to always use all the tiles in our base combination that we want to permute, so the number of permutations is just the factorial of the number of tiles. Hmm. That doesn’t really help since it doesn’t filter out any duplicates.

Perhaps if I researched a bit more, I could have found the proper formula for this situation. Rather than read more about permutations, I decided to take one of my base combinations and do some experiments to see if I could derive a formula for this situation. I took the last combination from my list and computed the number of unique permutations in order to see what my goal should be. (This operation took over 10 minutes)
>>> print len(set(itertools.permutations([3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4])))

I played around with factorials and found that for my 13 terms there would be 13!, or 6227020800, possible permutations. Since I knew I wanted the formula to result in 78, I divided the number of permutations by 78 and got 79833600. In theory, this number would be the denominator of my not-yet-existent formula. I tried grouping my 3s and 4s together; there are 2 and 11 respectively. I checked what 11! is and it turned out to be 39916800 which is exactly half of my target value for the denominator. And 2! (for the number of 3s) is 2. That seems pretty promising!

My hypothesis was that multiplying the factorials of the number of similar terms together and then dividing them into the number of possible permutations would yield my desired result. I tested it out on another combination and it worked out correctly, so I modified my program to perform this operation on each combination. I ran it and checked the answer, and it was correct!

And it only took .083 seconds! I’m pretty happy with the results. I’m sure a mathematician might have a more clever, direct way of solving this problem, however I think that since this solution is accurate and quick I can be proud of it. You can see the complete code on my github.


Emacs Notes

Emacs is a very feature-laden editor. As such, it can be hard to remember all of the various features that are very useful, but perhaps, not frequently used. I thought I would create a list of some features I have learned and did not want to forget.

Show a list of all currently opened buffers

C-x C-b

When there are dozens of buffers open, it can be difficult to switch to the correct one. This command will list them all, and allow you to go directly to the buffer you wish to edit.

Display current function name

M-x which-function-mode

This will add the name of the function that the cursor is currently in to the status bar at the bottom of the page. I have found this pretty useful when exploring unknown code, or long documents with hundreds of functions. I don’t enable this all the time though because I have found it can sow the responsiveness in larger documents.

Show invisible characters

M-x whitespace-mode

Sometimes its nice to see if a document is using spaces or tabs. Enabling white-space mode makes it clear the type of indentation being used, as well as making other whitespace sins apparent. This is particularly useful when you work on a file that’s been passed around multiple editors and is not consistently indented.

Along with this, you can easily remove whitespace present on the end of the lines by selection a region and using the following command:

M-x delete-trailing-whitespace

Easy alignment

M-x align-regexp

This is actually a command I do use frequently. I like to have things lined up as I feel that it improves legibility. This command, when run on selected text, will align the text to the matching user input. For example, I can use this to align multiple lines on an equal sign.

Selection, Etc.

C-x space

Mark. This begins a selection by marking where you cursor is and highlight to where you move your cursor thereafter


Copy. This will copy the marked region


Cut. This will cut the marked region


Yank. This will paste the kill buffer contents at the location of the cursor

Rectangular Commands

C-x r k

Rectangular cut/kill. Make a selection across multiple lines, then run this command. It will kill the rectangular region of text that was selected

C-x r y

Rectangular yank/paste. This command will paste the rectangular area of text killed by the command above.

C-x r t

Make a selection across multiple lines, then run this command. As you type, it will insert the text on each line you selected in the column that you began/ended with. If you start and end in different columns, it will replace the text in those columns on each line.

Navigational Hot Keys

Moving within the buffer can be tedious without some hotkeys to speed things up.


Go to end of document


Go to beginning of document

M-g M-g

This brings up the ‘goto line’ prompt for quickly going to a specific line

M-g tab

Similarly, this brings up the ‘move to column’ prompt


Page down


Page up


Center cursor/cursor position in window


Search for term. Use the combination repeatedly to find the next instance of the search term


Search in reverse. As with the previous command, repeatedly using the combination will take you to previous instances of the search term.

Formatting Hotkeys


Make word capitalized from cursor position to end of word


Make word lowercase from cursor position to end of word


Make word uppercase from cursor position to end of word

Window Navigation

C-x 1

Return to single view

C-x 2

Split pane horizontally

C-x 3

Split pane vertically

C-x o

Move cursor to other pane/view

C-x left

Switch buffer to preceding buffer

C-x right

Switch buffer to next buffer

File Handling

C-x C-f

Find a file to open/edit


Also of note, when opening a file, you can use the above syntax to open a file on a remote machine.

C-x k

Kill buffer (close file)

C-x C-q

If a file is write protected, but you want to edit the buffer anyway…

Keyboard Macros

Keyboard macros allow you to create a set of commands that you can repeat in order to speed up repetitive tasks.


This will begin your macro recording. Every keystroke and command until you do will be recorded until you stop recording


This will stop the macro recording. Once you have stopped recording, every time you press F4 it will repeat your whole macro.

mg; The Emacs Like Editor

Sometimes you don’t want to install an 80 MB text editor on your machine. Sometimes you want something lightweight, but just don’t want to use ‘vim’. For those times, you have ‘mg’ (micro gnu). It’s a very small binary (200k on my current install) that gives a similar experience to Emacs. It has the familiar interface, keybindings and most of the essential features. Obviously the exotic commands are missing, but the fundamentals are there. I’d much rather be stuck using this than vim, vi, or nano.

Closing thoughts

While not a comprehensive list, these are some of the commands I wish I had known when starting out with Emacs. There are so many, and while I like Emacs a lot, my main gripe with it is the lack of discoverability with commands. As a last tip, the following command will show you all of the available key shortcuts:

C-h b

Happy editing!


Jenkins 503 Error on CentOS 7

My Jenkins install was whining at me to upgrade to the newest release (2.57) for security reasons. I finally relented, and updated the jenkins.war file only to be greeted with this wonderful error:

Problem accessing /. Reason:
    Service Unavailable

Not terribly informative. My first Google perusal revealed that it was probably an error with Jetty, and so I checked jetty configurations. No luck there there though.

I looked at the Jenkins log (/var/log/jenkins/jenkins.log), and found this:

WARNING: Failed to delete the temporary Winstone file /tmp/winstone/jenkins.war
May 01, 2017 12:29:43 PM org.eclipse.jetty.util.log.JavaUtilLog info
INFO: Logging initialized @923ms
May 01, 2017 12:29:43 PM winstone.Logger logInternal
INFO: Beginning extraction from war file
May 01, 2017 12:29:43 PM org.eclipse.jetty.util.log.JavaUtilLog warn
WARNING: Empty contextPath
May 01, 2017 12:29:43 PM org.eclipse.jetty.util.log.JavaUtilLog info
INFO: jetty-9.2.z-SNAPSHOT
May 01, 2017 12:29:44 PM org.eclipse.jetty.util.log.JavaUtilLog info
INFO: NO JSP Support for /, did not find org.eclipse.jetty.jsp.JettyJspServlet
May 01, 2017 12:29:44 PM org.eclipse.jetty.util.log.JavaUtilLog warn
WARNING: Failed startup of context w.@18d4479b{/,file:/var/cache/jenkins/war/,STARTING}{/var/cache/jenkins/war}

Looks like I am having trouble writing/removing files. So, I check permissions and users, but nothing looks out of the ordinary there.

I also use my Google-fu to see if I can get any clue on the last warning there. The only similar issues I can find are related to missing font-packs. That doesn’t make too much sense, but I try it any way. No avail.

Finally, I tried upgrading my Java install to 1.8 from 1.7. I looked through the Jenkins release notes, and I didn’t see anything overtly saying that Java 8 is the new requirement, but I did see some notes about Java 9 being supported, and Java 7 being the minimum for slaves.

I followed the instructions here to install Java 8, and what do you know? Success! So there you go. If you upgrade your Jenkins and see this error, try upgrading to Java 8!


© 2007-2015 Michael Caldwell