News -- /dev/random

Collatz Conjecture in Haskell

Overview

The Collatz Conjecture is based on sequences from the following formulas:

n/2 for even n
3*n + 1 for odd n

These seequences go back down to one, no matter what starting number is chosen. The interesting part is that noone has been able to formally prove this. So I started writing some simple code to play around with it, and practice my Haskell coding.

Collatz Sequence Code

Code to generate sequences and find the lengths of the sequences:

test :: Int -> Int
test x | even x     = x `div` 2
       | otherwise  = 3*x + 1

collatz :: Int -> [Int]
collatz 1 = [1]
collatz x = x : collatz (test x)

numCollatz = map (length . collatz) [1..]

Output Code

Generates a table that gnuplot can handle.

format x y = show x ++ "t" ++ show y
table x = unlines (zipWith format [1..] (take x numCollatz))

main = writeFile "collatz.dat" (table 100000)

Images

1000, 10000, and 100000 numbers respectively

Video

Click the image below for a video of the behavior as we go to higher numbers (Pretty obvious from the above pictures :p).

Code

collatz.hs --Haskell code described above
collatz.gnu -- The gnuplot code to generate a graph

Comments(0) 2010-02-28 23:24:35

Continuous Inking System (Epson R300)

Overview

Continuous Inking Systems (CIS) allow you to use bulk ink in a printer, instead of ink cartridges. Basically it involves hooking tubes between bottles of ink and the dampers(The things that distribute ink). Also putting in a custom chipset to basically ignore ink levels and such. Some people are insane and do it themselves using the old cartridges, syringes, and normal tubing. I opted to get a kit from inkrepublic.

This is more or less a review/issues I encountered than a detailed write-up

Pictures

Front of device:

Printed picture of the above image (There was some glare):

Back of device (Rerouted waste ink tube):

Pros

The major pro is that it is MUCH cheaper. A standard ink cartridge costs ~$20 for 5ml of ink. Bulk ink is $12 for 100ml, which is over 300% cheaper ( If I did my math right :)
Inkrepublic was fast to ship, and delivery went quick
Setup was more or less painless, slightly messy though :)
Print quality is excellent so far

Cons/Issues

One of the caps was broken on arrival. They said a replacement was shipped, but it never arrived. Thankfully there is a spare cap (Of ambiguous color) with the kit, so it wasn't a huge deal.
Kinda pricey at $150, might not be worth it if you don't plan to do alot of printing
Epson sucks, and tries to make you take in the printer to be serviced at the drop of the hat. Part of this scheme is the waste ink disposal, you more or less have to pull out the tube, route it into a container, and do a factory reset.
Even after fixing the waste ink, it still comes on every time the printer is turned off and then back on. The easy fix is to leave it on all the time :p
Leaving it on seems to cause it to get out of alignment. This is simply corrected by doing a quick print before doing a real one. This may seem wasteful, but the startup of the printer uses a ton of ink to do this same thing anyway.

Conclusion

Works good, although feels like a hack even with the kit. I didn't see a laser printer for cheap that did color (I can get B&W ones for under $50), and I *hopefully* will be having to print out a ton of stuff soon, so this was the only viable option I could come up with that wasn't really expensive. It will pay for itself after about 25ml of use, which I'm sure I'll reach.

Comments(0) 2010-01-29 23:55:39

Streamed web images without flickering

Overview

Putting a stream of images on the web, like from a camera, can be painful. Constantly refreshing the page with a meta tag causes flickering, DOM modification requires busting the cache, and without the cache you again get flickering on the image.

Code

<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript">

   function upd(count)
   {
      $("#capImg").html(
         '<img width=384px height=288px src="foo.jpg?' + 
         count + '">');
      count ++;
      $("#capImgHidden").html(
         '<img width=1px height=1px src="foo.jpg?' + 
          count + '">');
      setTimeout("upd(" + count + ");",500);
   }
   setTimeout("upd(0);",500);
</script>
<html>
<head>
<title>Image Stream</title>
</head>
<body>

<div id="capImg">
<img src="foo.jpg">
</div>
<BR>
<div id="capImgHidden" style:display="none">
<img width=1 height=1 src="foo.jpg?0">

</div>

</body>
</html>

Explanation

jQuery is used to modify the html on in the javascript. This is done every 500 milliseconds using setTimeout.
Each call of the upd function has count incremented by one each time. This is then used as part of the image location (foo.jpg?0, foo.jpg?1, foo.jpg?2), making the browser think each one is a separate location and thus bypassing the cache. We are passing in the number as a GET parameter, which is discarded at the server side since foo.jpg is just a normal image and does not take parameters.
Since we've busted the cache, the browser downloads a fresh copy of the image each time. The time it takes to do that causes flickering. The trick is to load the image with the same name in a hidden area, which is just a 1x1 image (capImgHidden). For example:
1. Display foo.jpg?0, hide foo.jpg?1
2. Display foo.jpg?1, hide foo.jpg?2
3. Display foo.jpg?2, hide foo.jpg?3
4. ...
In this way we always have cached the next image to display.

Conclusion

Works well, and isn't that complicated to implement. Really fast rates (Under 100ms on my machine) will still cause flickering even with caching. Also the data source can produce it's own issues, such as slow writing of files resulting in corrupted images being retrieved.

Comments(0) 2010-01-27 03:15:37

Self Modifying 2D Turing Automata

Overview

2D turing machines with 4 possible symbols per space were made. Their state tables were stored in the 'tape' that was used to run the programs, thus allowing self modification. Several of these machines were laid out in the same grid representing the 'tape', and allowed to travel anywhere, modifying themselves or others.

Algorithm

The algorithm is simple. A machine is represented by a 16x16 state table. The columns correspond to the symbols, which also have a direction(More on that later):

α(0) -- Displayed as Red, moves Up
β(1) -- Displayed as Green, moves Down
γ(2) -- Displayed as Blue, moves Left
δ(3) -- Displayed as White, moves Right

There are 16 states. Since there are 4 symbols we can use 2 spaces in the table (m,n) to represent all states with 4*m + n.
Also since there are 4 symbols we can use each one to represent which direction to move on the 'tape'. We end up with each row in the table as:

State

(α) Direction

(α) New Symbol

(α) New State(m)

(α) New State(n)

(β) Direction

...

(δ) New State(m)

(δ) New State(n)

A lookup based on the current state and symbol underneath is then easily performed. For the actual implementation the state tables and the grid were seeded with random numbers.

Pictures

Start state for one of the runs (They all look similar starting out, since it's random):

A few end state pictures:

Videos

Click images below for timelapsed video:

Code

turingAutomata.pde -- You can set the number of individuals (Must be square) and the grid display size up top, but don't have to.

Conclusion

These turned out pretty interesting. They always seem to end up in a steady state of repeated behaviour, usually 'trains' moving around the screen. I've seen a few interesting things happen, such as piston motions, , and really close timing ( moving horizontal chains with small breaks, having diaganol chains going through multiple at once).

Also weird is that it almost always (Roughly 90% of the time) tends towards 2 colors at the end. Also, there is always a dominant color, which makes some sense...I guess. I have alot of other stuff I want to try with them, but I first needed to make sure the basic design worked out.

Comments(0) 2009-12-20 05:05:24

Competing Conway Life Automata

Overview

I took the Processing example implementation of Conway's game of life and hacked it to try to evolve patterns that will take the most space possible. Click the picture below to see a time lapsed video of it running:

General Algorithm

Take 4 sets of patterns each in a 50x50 space on the board
Run them for 5000 cycles and rank them by how many spaces they occupy
Carry over the first and second most successful patterns
Take the most successful pattern and introduce 5 random mutations (Turn off a cell that's on, or vice versa) to create a new pattern
Take half of the most successful with half the second most successful to create a new pattern
Repeat with these four patterns

Download

geneticConway.pde -- The Processing code to run the program

Conclusion

It reaches a good solution quickly, and then doesn't get much better after about half an hour of running it. They develop interesting, psuedo-intelligent, patterns such as 'shooting' multiple gliders and forming large clouds of activity that are very resilient to another color being introduced.

Comments(0) 2009-12-14 18:17:37

X11 Timelapse Desktop Video

Overview

Not really a 'project', but somewhat useful. Allows you to create a time lapsed video of a screen in X. The only dependencies are ffmpeg and import.

Example Video

Reddit new submission time lapse (I decided against /b/ ;). Click image to see video:

Code

timeLapse.sh -- The script to capture video. Start the script and it will prompt you to click on the window to capture from. Will spit out a file called timeLapse.mpg. It unfortunately requires the window to remain visible during capture. Usage:
```
./timeLapse.sh DELAY_IN_SECONDS NUMBER_OF_CAPTURES [MUSIC]
```
Example:
```
./timeLapse.sh 5 1000
```
would take 1000 captures, one every 5 seconds. Example:
```
./timeLapse.sh 60 1440 test.mp3
```
would take capture a frame every minute for a day, and put the audio of test.mp3 with the end video.

Conclusion

Simple yet handy, not much else to say :p I was originally going to put it as a tutorial and not a project. It's really trivial, and the simple technique can be used to do other types of video creation.

Comments(0) 2009-12-10 16:58:21

/dev/random

an exercise in futility

Collatz Conjecture in Haskell

Overview

Collatz Sequence Code

Output Code

Images

Video

Code

Continuous Inking System (Epson R300)

Overview

Pictures

Pros

Cons/Issues

Conclusion

Streamed web images without flickering

Overview

Code

Explanation

Conclusion

Self Modifying 2D Turing Automata

Overview

Algorithm

Pictures

Videos

Code

Conclusion

Competing Conway Life Automata

Overview

General Algorithm

Download

Conclusion

X11 Timelapse Desktop Video

Overview

Example Video

Code

Conclusion

Recent Activity

Recent Comments

Search