Python A* path search algorithm with wall destruction

I recently stumbled across Google’s challenge, and it’s quite an interesting set of problems! I got through the first couple levels without much difficultly, but level 3 is kicking my butt. I finally solved this maze problem after a day, so I’m posting it here to explain my thought process and because I’m pretty proud that I learned how to A* in the 5 hours or so I spent on the question.

Anyhow, the original challenge is twofold. First, given a maze represented by a grid of cells, find the shortest path you can take to get from the beginning to the end of the maze. Secondly, solve the maze again with the additional ability to now destroy one wall in your path. Though I’m sure there are many approaches one could take to solve this, I went with modified A*.

(No cheating on the challenge if you’re currently taking it! I really enjoyed the learning process I went though while taking the challenge, so don’t rob yourself of that opportunity! °˖✧◝(⁰▿⁰)◜✧˖°)
[Read more…]

Algorithm for solving Knights Tour with Python(revisited)

The original Algorithm For Knights Tour was a pretty popular post, so I decided to revisit it thanks to an interesting email I got. This implementation has a couple changes:

  • You can define a ruleset for locations the knight must be at any given move
  • You can define whether the path needs to be closed or not (Knight returns to starting position)
  • There’s a visualizer now! (You’ll need to have pygame installed for it to work though)
  • No more ugly exiting using sys.exit(), we catch custom exceptions this time around

Here’s what the visualizer looks like:
(pink because pink is the best color obvs)

The tour code is mainly the same as the original post, but with the added custom exception class and booleans. Lines 137-146 deal with obeying to a custom tour ruleset 
[Read more…]

The Holographic Universe

I’m currently reading “The Holographic Universe” by Michael Talbot. I expected quite a bit more science than is actually present in the book,  but it’s an interesting read nonetheless. (Though the book definitely explains science through a super new-age lens.) Only a quarter of the way through so far, but chapter three bought something up that blew my mind.

First, holograms 101:

The reason we can see stuff is because light bounces off of everything. Traditional images taken by cameras record incident light intensities as the photons hit the elements in a CCD or whatever sensor the camera is using. A hologram also records the phase of this light as well, meaning that playback of the recorded image retains all of the information during the recording phase.

Recording a holographic image. [Source: Wikipedia]

To record an image, a coherent light beam (aka laser) is sent through a beam splitter so we have two identical beams of light. One beam is reflected off the object to be recorded while the other beam serves as the reference of the recording laser. The two beams (object & laser) form interference patterns when they intersect, and this is recorded on the photographic plate.

Reconstructing the image. [Source: Wikipedia]

When the image is to be read/reconstructed, the original recording beam (or laser of same wavelength) is shone through the plate. Interference allows the original beam to be recovered, restoring the recording of the object to the identical state it was in when the image was recorded. Because we literally recorded the light bouncing off the image, the holographic result is actually identical.

In this way, a mirror recorded as a hologram will also reflect light. And a holographic recording of a magnifying glass will actually magnify objects behind it. The recording plate can also be cut into as many pieces as desired, while the full original image can still be restored albeit being a little more blurry because of the cutting. SO COOL. TOO COOL.

[Read more…]

Sync iTunes playlists to Spotify

iTunes is dumb and has a super restrictive API. Spotify is awesome, and has an API for all my things, like my PS4 and Amazon Echo. But I like the iTunes UI, and it plays better with my local library than Spotify. As a result, I subscribe to both services, but it’s such a pain managing playlists between the two.

I present to you, the super not janky at all sync script/setup that I wrote up in a 3 hour burst of inspiration last night. The main flow of the idea is this:

  1. CRON job runs AppleScript periodically
  2. Applescript queries iTunes for playlist information and saves each playlist and its songs to a .txt file
  3. Python script compares .txt files to Spotify playlists – information retreived via API calls
  4. Python script updates Spotify playlists with differences found between the two services

AppleScript is a very interesting programming language, where the code is incredibly human readable at the cost of ease of use when coding. Here’s what I wrote for extracting playlist information out of iTunes:

This extracts playlist information and saves each playlist as a .txt file to a specified directory. The Python component does most of the legwork in terms of finding which tracks needed to be added to Spotify. You’ll need to create a new application at the Spotify Developers page to get a client_id and client_secret_key.
[Read more…]

Teaching cars to drive with genetic algorithms

“What the heck Sophie?!” You say, “Why are you writing a debrief for a project you did 3 years ago???”

Hahaha, please bear with me dear reader. If I don’t, I’ll forget about the cool thing I did as a freshman in college still stumblin’ through Python. And how cool and easy genetic algorithms are. 😀

Anyhow, carrying on….

For our software design final project, we wrote a simulation program that would allow you to draw a track, then generate cars that would eventually learn how to drive around said track. It was a pretty fun project, and we got a pretty cool result.

Here’s our website!
Here’s the code!

Demo video:

What’s happening is that the cars are starting with random parameters for their wheels relative to its distance from the wall. As the the cars progress through the generations, these parameters are selected using our parameters, such that the car that make it around the track is the only one that survives.

[Read more…]

Summary of modern bone trauma analysis

*Edit 10/21/16: Fixed broken link to pdf, sorry. :C

tl;dr contents:

  • Material Properties of Bone
    • Classifying bone trauma by time of occurrence
  • Types of bone trauma
    • Ballistic
    • Blunt force
    • Sharp force
    • Thermal

I’m not gonna include a lot of pictures because this is a topic that not everyone will want to see images of. You can google stuff if you want to see examples, or read my final paper where everything is cited.

Material Properties of Bone

Bone is divided into two kinds of osseous material. Cortical bone is about 80% of the mass of the exoskeleton, and forms a hollow cylinder in which the cancellous bone resides. The main purpose of cortical is for structure, while cancellous bone is spongy interior that is responsible for nutrient storage and transport. 

A cross-section of a human femur, look at how cancellous bone is a lot less dense than the cortical bone.

A cross-section of a human femur, look at how cancellous bone is a lot less dense than the cortical bone.

Injuries to bone are classified based on when the injury occurs.

Ante-mortem trauma: Refers to trauma on the skeleton that occurs prior to the death of the individual. In-vivo bone exhibits healing, and edges of a fracture will be fairly smooth. As healing rates differ depending on the characteristics of the individual, the same injury may look different from case to case.

Peri-mortem trauma: Refers to trauma occurring around death. Fracture patterns observed in peri-mortem trauma can be similar to those seen in ante-mortem trauma, but have sharper edges since no healing will have occurred (in most cases). Patterns will show evidence of some terminal event, i.e fast collision with an object, but fracture edges will show characteristics of plastic deformation as the external fibers of the bone tissue begin to show micro-tears.

Post-mortem damage: Refers to damage occurring after death. Bone becomes brittle once it has dried out, and exhibits ceramic-like material properties. Fractures will be jagged and exhibit no healing, and may also be irregular. I.E: Fractures lack a common correlation to an event that caused the damage, such as those resulting from post-mortem bone shrinkage.

Types of Bone Trauma

Ballistic trauma on bone is usually the result of a bullet or an explosive, though this categorization may be applied to any fast traveling object that has collided with bone. Features that indicate possible ballistic trauma include the presence of a projectile that can be associated with bone, fracture patterns corresponding to a high velocity impact, or fragmentary foreign material found within the bone or the environment.

[Read more…]

Infinity and Zeno’s Paradoxes

Infinity is a well explored concept across many disciplines. As of yet, I’ve managed to only interact with infinity behind the safety net of definite integrals and unbounded limits. So I thought I’d take a deeper look at infinity though the lens of Zeno’s paradoxes. But first, a short discussion about English.

When I was 6, “red” was the color of my favorite rain jacket. That was it.

When I was 14, “red” was no longer simply a color, it was an emotion, an object, a physical force. I could smell the redness of a cherry orchard and hear the redness of a laugh.

In fact, if I were imaginative enough, I could make the word “red” mean anything I wanted. “You are a poet!” my teacher cried, “Bend your words, twist them, pepper them with your thoughts; present to the world a feast of poetry.” English was quite a willing and malleable medium, which was great, but this foray into non-literal completely defeated the sure-ness of words that I had believed in as a kid. With poetry, even the most innocuous sentence like “today was sunny” could have ten different meanings.

Now, I’ve held on to the belief in the certainty of mathematics since my days of Algebra I. Unlike poetry, the result of a definite integral doesn’t change with the whims of the one grading the problem. Math was unmoved by emotion, and (to borrow the words of Bertrand Russell) I felt that it was the turtle that could hold all other turtles.

However, take a hard look at this concept called “infinity”. Infinity is to mathematics what poetry is to English—it takes the previously solid math of algebra into the fuzziness of philosophy. Though I knew nothing of its intricacies, I often invoked the threat of infinity upon my childhood friends when I “triple times infinity dared” them to do something dumb. Infinity was a big deal, since we didn’t know anything of what it was other than the fact that it was really, really big. But what is the actual value of infinity? How can a mere concept of “really, really, big” become something we can realistically use?

[Read more…]

Algorithm for knight’s tour in Python

I’ve written an updated version of this code here. Please take a look! It adds a visualizer, ability to solve for closed tours and step requirements, and has a better exiting strategy. 🙂

In Discrete class, we’ve been talking about planar graphs and stuff like Hamilton traversals. One of our in-class exercises involved the knight’s tour, and whether we could find a rule that would allow us to decided if a knight’s tour was possible given a chessboard of a certain dimension. I have a hard time understanding graphs, but the “Knight’s Tour” sounded really cool so I looked it up on Wikipedia. The problem is actually a pretty interesting one, so I decided to try my hand at implementing an algorithm for solving it in Python.

From Wikipedia:
A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.

The .gif below is an example of what knight’s tour would look like on an 8×8 board.
Gif of knight's tour

In writing my own implementation, I heavily referenced this site and this site. I’ll do a walkthrough of my code below.

[Read more…]

Equations of motion for a planar simple double pendulum

To provide some background information for my N-link pendulum project, I’ve broken the methodology for solving the equations of motion (EOM) for a simple double pendulum into a separate post. I’ll explain to the best of my abilities!

The pendulum that we are solving for is composed of two masses, m1 and m2, suspended from each other by strings of length l1 and l2. Their positions relative to 0 is represented by theta1 and theta2. The entire pendulum is supported by point 0, which is a frictionless, massless point. The whole thing is a pain to create digitally, so I drew the setup below:


This will be a pretty long post, so scroll to the bottom for the cool graphs!

[Read more…]

N-link compound pendulum simulation

For our Mechanical Dynamics final project, a friend and I decided to generalize the equations for compound pendulums to write a simulation program that could generate animations for n-link compound pendulums with user specified lengths, masses, angular displacement and velocities. We originally wanted to write a full blown physics engine, but quickly realized that two weeks was not enough time to do something of that scale, haha.

First things first, a demonstration! The following is an simulation of a 5 link compound pendulum:

Read our final report for a more formal/comprehensive explanation of the process!
Download the code!

[Read more…]