Archive for the ‘Uncategorized’ Category

Project Euler 117

Thursday, February 4th, 2021

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])))
78

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.

 

Wile E. Coyote

Thursday, December 31st, 2020

Wile E. Coyote was a large part of my childhood. His cartoons were my favorite of all the Looney Tunes. I love his determination at catching the Road-Runner. I love his inexhaustible budget for all things ACME. I love the complexity of his Rube Goldberg-like plans. I love the absurdity of his failures.

One of my favorite episodes is “Beep, Beep” from 1958. In this one, Coyote employs blueprints to aid in his preparations against Road-Runner. I think of the blueprints as quintessential coyote-ness, however after a careful rewatch of all the shorts I have access to, he only uses blueprints in this episode and “Operation Rabbit.”

At any rate, the blueprints from this episode make me smile, and I thought printing the blueprints out would be a nice thing for a shop wall or for other family member who also have a fondness for the determined coyote.

I screen-grabbed some shots off of a Laser Disc compilation of Road Runner shorts and redrew them using Affinity Designer. I tried to be true to the source material so that the images would be clearly recognizable. I took some liberties by straightening some lines, using a font instead of hand written letters, etc., and I am pleased with the results.

Screen capture from Laser Disc

In this first scene, Wile E. Coyote plans to drop an anvil onto an unsuspecting Road-Runner from a tight-wire strung across a gorge.

Screen capture from Laser Disc

In this second scene, a box is rigged to explode when the water glass is lifted. One of the things I love about the box is that even though it is introduced near the beginning of the episode, the payoff comes at the end after the viewer has probably assumed the gag was over and not going to be revisited.

While, I don’t want him to hurt the Road-Runner, I do feel a sense of pity for him and all the pain he has to endure for the audience’s enjoyment.

 

LCARS Clock

Friday, January 25th, 2019

LCARS, the Library Computer Access and Retrieval System, is the fictional operating system used in the 24th century on Star Trek the Next Generation, Voyager, and Deep Space Nine. LCARS was designed to be a futuristic looking computer interface, while being very cheap and easy to create for the sets. In the show’s production, the effect was made by taking plexiglass sheets, applying vinyl shapes to the glass, then back-lighting it. It was a great effect and really sold the futurism that was felt when looking into the world of the Enterprise D. The entire design of the Enterprise D is very special to me, and seeing it gives me that nostalgic sense of coming home.

I recently found a small 3 inch display for the Raspberry Pi. It was only about 20 dollars, and I thought that was really nifty, and bought it without really having an idea what to do with it. After I got it, It seemed so neat that I thought it would be so cool to display something on it with an LCARS style interface. I like clocks, so why not start there?

After looking for something ready-made and not finding anything I really liked, I decided to make my own. On my list of things to do was to try using SVGs to make a website. This seemed like a perfect opportunity to do just that.

SVG (Scalable Vector Graphics) is a format that describes graphics by lines, curves, and points. I’ve used SVG a lot in design projects but not much in online applications. I started out by creating a basic design on Affinity Designer to the scale of my little screen.

Once the design was prototyped, I saved the file as an SVG and created an HTML wrapper around it, and began getting it set up. I started writing the Javascript that would actually display the time. That was pretty easy as it turns out. I was so pleased by the results, I decided to expand upon it, and add weather to the display.

To add weather, I had to do a few things. The first was get the location of the user. I wanted to avoid having to input anything and wanted the geolocation to be automatic. This is pretty easy using the built in command on most browsers.

navigator.geolocation.getCurrentPosition()

This will pop up one of those confirmation dialogs that the website wants to use the user’s current location. In the event that the user selects no, I wanted a fall-back solution as well. This is done using a free service from geoiplookup.io. They have an API that requires no key that returns JSON data.

Between the two of those options, I now have the approximate latitude and longitude of the user, and can query a weather website about the weather. I am using open weather map for that. They require registration to use the API, but it is free and caps out at 10,000 queries a month. That’s about 13 times an hour. For now I decided that 1 update an hour would be enough.

Their API returns JSON data that is easily parsed to get the weather and other things. Things are looking good.

Now I decide that I have these elements just sitting there, surely I could do something more interesting with them. What’s really cool about SVG is that the elements are just like HTML elements, and that makes it really easy to use with Javascript. I decided to make buttons on the side to do more than just label things. Clicking the time button cycles format (blinking separators, 24 hour, etc) and clicking the date button cycles date formats (US, ISO, Star Date, etc). Lastly, I decide to add a diagram of the Enterprise that replaces the weather data when “Diag” is pressed. I happened to have a vector drawing of the Enterprise that I made a few years ago that I could repurpose.

It looked spectacular. I was very happy. But like all projects, it’s fun to keep fiddling. The next step was to make the diagram less static. This time, instead of using Javascript to affect the image, I decided I would try SVG animations. These were completely new to me.

I wanted the nacelles to have the the flowing blue texture that we often saw in the TV show. I made a mask, and a gradient map in Affinity Design and then created an SVG animation where the gradient would pass behind the mask and move 30 pixels, then reset and repeat. It looked so great!

  <rect x="1" y="20" width="150" height="46" style="fill:url(#_Linear2);">
<animateMotion
path="M35,0 5,0"
begin="0s" dur="1s" repeatCount="indefinite"
/>
</rect>

Next, I decided to add points of interest to the diagram. I created all the points by hand and then used SVG animations to make them appear and disappear sequentially. This is done by having the animations kick off when they see the previous animation being completed. Once I overcame a few pitfalls, it came together great and was really easy.

Lastly, I wanted to move the diagram out of the main HTML. The SVG data was really cumbersome, and I wanted to have it be isolated for clarity. This was done by moving it to it’s own document, and giving it the proper SVG tags. In the HTML, I created an image tag that links to the SVG file, and then wrapped it in a g tag with a transform command so I can place it correctly within the main graphic.

    <g id="diag_data" transform="matrix(1,0,0,1,75,180)" style="display:none;">
      <image x="0" y="0" width="380" height="150" xlink:href="diagram.svg" />
    </g>

There is only one minor problem now… I’ve defined a custom font in the main HTML, and the embedded SVG can’t use it. Additionally, defining a custom font in the embedded SVG file does work when looking as the file directly, as soon as it is embedded using and image, img, or object tag, the fon’t definitions break. I believe this is a security thing, but I’m not really sure. The only way I could find to solve this problem was to embed the font as data in the SVG file.

I used a service I found at font-converter.net that gave me the encoded data, and then I put it into the SVG file. It worked like a charm. It’s not super pretty, but it worked.

<style type="text/css">
<![CDATA[
@font-face {
font-family: 'lcars';
src: url(data:application/x-font-woff;charset=utf-8;base64,d09GRgABAAAAAF2IABEAAAAAkoQAAQAvAAAAAAAAAAAAAAAAAAAAAAAAAABGRlRNAAABgAAAABoAAAAcGo5L0kdERUYAAAGcAAAAHwA... continues ad infinitum...) format('woff');
}
]]>
 

The result is about a day’s worth of tinkering, and I’m very pleased with the result. I am also really excited about how easy working with SVGs was with Javscript, and want to find another project that gives me an excuse to tinker some more.

Update

I had some trouble configuring the touch screen on my Pi. It seems like there was some information missing. The first thing is that the brand of touchscreen I purchased was Kuman, specifically the 3.5 inch HDMI screen. They have multiple models; some that use HDMI, others that use GPIOs. The original drivers I found for it were outdated and not meant for the current Raspbian OS. The newest drivers are available here on their GitHub page.

The second mistake I made was trying to install with the incorrect install script. I was using the “LCD35-show” script which is actually intended for the screen that does not use HDMI. That resulted in a black screen and no touch input. The correct installer for my screen is the “MPI3508-show”. After executing the script and rebooting, the screen worked correctly.