Saturday, May 20, 2017

Optimized WireWorld Algorithm

As usual, this entry was written because it is an uncommon subject that I just happen to be working on.

I've been slowly working on a virtual reality world and decided that it would be nice to add some technology to the simulation. I decided that a custom version of the WireWorld cellular automaton in 3 dimensions would be perfect since it is Turing complete, can run relatively fast, and would be rather simple to integrate with any other in-game technologies.

It had to be customized because it had to be fast (to prevent simulator sickness in VR), but there is very little interest in this automaton and all the code I've seen uses the traditional implementation. This is why I came up with this version (which someone probably has done and I just didn't know about it).

In this blog post, I will be describing an optimized version of the algorithm for WireWorld. In theory this version is a little slower than the classical 2 array version of WireWorld on small simulations, but should slowly become faster than the traditional implementation as the simulation gets bigger.

The rules of the automaton state that when a cell is an electron head, it will degrade into an electron tail. When the cell is an electron tail, it will degrade into a conductor. When the cell is a conductor, it can turn into an electron head only if one or two of its immediate neighbors are electron heads.

The way this is usually implemented is with an array where each element holds the state of the cell. A value of 0 is nothing, 1 is an electron head, 2 is an electron tail, and 3 is a conductor. The simulation goes through and writes the updated states to a second array in order to retain the new states without altering the current frame. Then the second array is copied back onto the first and is displayed and the process starts all over again. This works fine, but requires you to iterate through each array element and it if it has live neighbors and degrade its state until it becomes a conductor. Going through each element for every single frame is generally an O(n^2) time complexity, but is better on a small scale because it would use less memory and less time in general.

The way I will write about here will only go through the cells that actually have a state that isn't 0. Instead of holding the states in an array, the cells are held in a list of data structures that contain the x & y coordinates, the state, the addresses of the immediate neighbors, and a count of the live neighbors. The simulation goes through each cell a first time and if the cell is an electron head, then it will go through the list of neighbors and update the live neighbor count if the neighbor is a conductor. Then each cell will be iterated through a second time to degrade the state and then change its state based on if it had the 1 or 2 neighbors or not. This way all the empty "cells" that would have been in an array are skipped over since they are not in the list.

Of course, each cell in the second implementation takes more time and memory to execute on a small scale, but on a large scale there would be much more empty space that could be skipped and at a certain point the second implementation should be able to run faster than the first implementation. The time complexity for the second implementation should be something like O(n). In practice, this is only better in large scales because even though O(n) is less than O(n^2), it uses more memory and computing power per cell, but doesn't rise in power and memory as fast as O(n^2) would.

Enough of this theory stuff, lets get some actual pseudo code.

define cell data type
    x position
    y position
    state
    dynamic list 'neighbors'
    live neighbor count
 
initialize dynamic list 'wires'
set erase mode to false
 
define find function, input x and y coordinates
    loop through each element in 'wires', return index if coordinates match
    return -1 if no cell found at those coordinates
 
define get neighbors function, input cell
    loop through each coordinate around the cell's position
        if cells exist at those coordinates, add reference to cell's neighbor list

define add cell function, input x and y coordinates
    add new blank cell to wires list
    run get neighbors function on this new cell
    iterate through the neighbor list and add this cell to those neighbor's neighbor list

define delete cell function, input cell
    loop through each cell in cell's neighbor list
        remove the reference to this cell from the neighbor's neighbor list
    remove reference to this cell from the wires list

infinite loop
    clear screen
    if enter is pressed, toggle erase mode
    get mouse position and mouse buttons
    draw mouse cursor onto screen 
 
    if mouse click
        get index of cell at mouse coordinates with find function
        if left click and not erase mode and no cell existing at mouse coords
            call add cell function with mouse coordinates
        if left click and erase mode and cell existing at mouse coords
            call delete cell function with cell from index in wires list
        if right click and cell existing at mouse coordinates
            set cell at index to have stage of 1 (electron head)

    loop through cells in wires list
        if cell state is electron head
            loop through neighbors that are conductors
                increment live neighbor count of that neighbor cell
 
    loop through cells in wires list
        if cell is not 3 (conductor)
            increment cell state
        if cell's live neighbor count is 1 or 2
            change state to 2 (electron head )
        clear cell's live neighbor count to 0
        set color equal to black for 0 (void), blue for 1 (electron head), red for 2 (electron tail), yellow for 3 (conductor)
        draw cell on screen with coordinates and color

The Python source for this looks like this:
(Left click adds a conductor, right click activates it, pressing enter turns on delete mode)

#!/usr/bin/env python
import pygame
from pygame.locals import *
pygame.display.init()
pygame.font.init()
screen = pygame.display.set_mode((640,480))
pygame.display.set_caption("")
font = pygame.font.Font(None,20)
clock = pygame.time.Clock()
           # 0   1   2      3          4
wires = [] #[xp, yp, state, neighbors, live]
# 0 black void, 1 blue electron head, 2 red electron tail, 3 yellow wire
erase = False

def findWire(xp,yp):
 for w in xrange(len(wires)):
  if wires[w][0]==xp and wires[w][1]==yp: return w
 return -1
def updateNeighbors(ww):
 for x in xrange(-1,2):
  for y in xrange(-1,2):
   wp = findWire(ww[0]+x,ww[1]+y)
   if (x,y) != (0,0) and wp != -1:
    ww[3].append(wires[wp])
def insertWire(wx,wy):
 wires.append([wx,wy,3,[],0])
 updateNeighbors(wires[-1])
 for ww in wires[-1][3]:
  ww[3].append(wires[-1])
def deleteWire(ww):
 for w in ww[3]: #remove references from neighbors
  for wg in xrange(len(w[3])):
   if ww[0]==w[3][wg][0] and ww[1]==w[3][wg][1]:
    w[3].pop(wg)
    break
 wires.pop(findWire(ww[0], ww[1])) #remove reference from wires

while True:
 for event in pygame.event.get():
  if event.type == QUIT: exit()
  elif event.type == KEYDOWN:
   if event.key == K_RETURN: erase = not erase
   elif event.key == K_ESCAPE: exit()
 screen.fill((0,0,0))
 
 mx,my = pygame.mouse.get_pos()
 b = pygame.mouse.get_pressed()
 if erase: c = (100,0,0)
 else: c = (50,50,50)
 pygame.draw.rect(screen,c,(mx/5*5,my/5*5,5,5))
 mx /= 5
 my /= 5
 w = findWire(mx,my)
 if b[0]:
  if erase and w != -1: deleteWire(wires[w])
  elif not erase and w == -1: insertWire(mx,my)
 elif b[2] and w != -1:
  wires[w][2] = 1

 for w in wires:
  if w[2] == 1: #inc neighbor counters
   for v in w[3]:
    if v[2] == 3: v[4] += 1

 for w in wires:
  if w[2] != 3: w[2] += 1
  if w[4] == 1 or w[4] == 2: w[2] = 1
  w[4] = 0
  c = [(0,0,0),(0,0,255),(255,0,0),(255,255,0)][w[2]]
  #c = [(0,0,0),(0,255,255),(0,100,0),(40,40,40)][w[2]]
  pygame.draw.rect(screen,c,(w[0]*5,w[1]*5,5,5))
 
 clock.tick()
 screen.blit(font.render("%.2f"%clock.get_fps(),-1,(255,255,255)),(0,0))
 
 pygame.display.flip()

And as always, if you have some suggestions or ways to optimize this algorithm further, please let me know and I'll be more than happy to update this post with the new information.

Saturday, March 11, 2017

Generating Every Combination of a List

So today at work I had to modify a program to generate relative links to points in a database based on a customer's specifications.
The chosen implementation required that I come up with every possible combination for a list containing unique elements to be only used if absolutely necessary.
If the elements had to be used, then the specification called for using the minimum amount at the lowest level of our tree data structure as possible.

No problem, I was sure that generating all the combinations (not permutations) for a list in lexicographical order wouldn't be so hard.

I couldn't have been more wrong.

In popular languages, like Python, there's always some library that can help out with a task like this. Unfortunately, I didn't have the luxury of using a library because the language used at my work is called Axon and it only has whatever "libraries" we make for it.

Therefore, I had to make my own functions to handle this, but there were limitations.
  • The functions had to work without while loops because Axon doesn't support while loops.
  • I should avoid recursion as much as possible because it is particularly difficult in Axon, and the program would be running on embedded devices with low resources.
  • The combinations should be autmatically sorted using the lexicographic order that they came in from the input list.
  • No combinations could be repeated in a different order, e.g. [a,b] <=> [b,a]
  • It had to be fast because it would be part of a tool and users can't stand waiting.

Now, I won't show the code I wrote for work, because it's a little proprietary and seeing it in Axon would mean nothing to most people.

Instead I will show it in Python, this is the language that the algorithm was originally prototyped in. (My boss walked in on me prototyping the algorithm and he was like "You've been staring at the same line for 20 mintues already", which it true. I even worked on this through lunch.)

1  def combos(i,j,l): #i is input list, j is r in nCr, l is n in nCr
2   if j == 1:
3    return [[x] for x in xrange(l)] #[[0],[1],[2],...]
4   if j == l:
5    return [[x for x in xrange(l)]] #[[0,1,2,3,...]]
6   #remove lists that have too big starting number
7   i = [x for x in i if x[0] <= l-j]
8   t = []
9   for x in i:
10   if x[-1]+1 < l: #further remove lists that are too big
11    for y in xrange(x[-1]+1,l):
12     t.append(x+[y])
13  return t #returns list of index lists
14 
15 def genCombination(arr): # 2**n - 1 total combinations
16  o = []
17  s = len(arr)
18  g = []
19  #generate list combinations from lists of index lists
20  for x in xrange(1, s+1):
21    o = combos(o,x,s)
22   for y in o:
23    g.append([arr[z] for z in y])
24  return g
25 
26 #pretty print the combinations
27 for x in genCombination(['a','b','c','d']):
28  print x

Here is the output

['a']
['b']
['c']
['d']
['a', 'b']
['a', 'c']
['a', 'd']
['b', 'c']
['b', 'd']
['c', 'd']
['a', 'b', 'c']
['a', 'b', 'd']
['a', 'c', 'd']
['b', 'c', 'd']
['a', 'b', 'c', 'd']


I can't totally explain why it works, even though I made it, but I can explain a few of the design decisions.

The functions are designed to take the previous answer and use that to calculate the next answer, so no jumping to random combinations. It has to be sequential, which for my purposes was adequate.

Line 2 and 4 are just if statements that return a list of lists.
This is because if you want the combination of nCr where r = 1, then it will look like [0],[1],[2],[3],[4],...,[n-1].
If you want the combination of nCr where r = n, then it will look like [0,1,2,3,...,n-1].
This is mainly for speed, no point in calculating it if you know what it's supposed to be.

Then there's a line that removes rows from the previous input that can't be used.
This is because in cases like the rows of the output with only 2 elements, you can't add to the [d] row because there is nothing after d to add.

Then there is a nest of 2 for loops.
I'm not really sure what happens here. I'm not even sure how I figured this out, but this is where the magic happens.
It also contains an if statement to further filter out rows that can't work. (It originally didn't have an if statement there, but that gave me problems in Axon so I added it there to make it easier to port it to other languages.)

The combos() function that I just described doesn't actually make the list of combinations from the input list, instead it makes the list of combinations of indexes for the input list.

The genCombination() function is the one that starts the list for the previous input scheme, gets the combination for a different value of r in nCr, and maps the input list to the lists of indexes.

Then it returns the lists of the combinations of the inputs with the specifications listed above.

The listed output is exactly what you would get if you used ['a','b','c','d'] as your input list.

I hope this is helpful to someone.
It would have helped me quite a bit if I could find something like this when I had to incorporate this feature into the program I had to modify. Instead I wasted about a whole work day making this and porting it to Axon and debugging it.

Sunday, September 11, 2016

Super Simple Interpreter

I was wondering how to write a simple interpreter in assembly for a 6510 processor (#c64) and I dawned upon probably the simplest interpreter ever (aside from a brainfuck interpreter).

Here is the basic pseudo code of the program:
define array of lines
define dictionary of variables
define left variable
define right variable
define counter and set to 1

loop
    write '> '
    get line
    append line to array of lines if line not empty
    break loop if line is 'run'
end loop

loop for each line
    split line by spaces

    if first element is 'print' or 'write' then
        if second element is single quote do
            get second to last element
            join with spaces
            write string excluding first and last character
        end
        else do
            find second element from dictionary of variables
            get value associated with element
            turn value to string
            write value string
        end
        if first element is 'print' do
            write '\n'
        end
    end

    else if second element is '=' do
        if third element is number do
            set left to number
        end
        else do
            get variable name
            find value from variable dictionary
            set left to value
        end
        if line is > 3 elements do
            if fifth element is number do
                set right to number
            end
            else do
                get variable name
                find value from variable dictionary
                set right to value
            end
            if fourth element is '+' do
                left = left + right
            end
            if fourth element is '-' do
                left = left - right
            end
            if fourth element is '*' do
                left = left * right
            end
            if fourth element is '/' do
                left = left / right
            end
        end
        set dictionary position of first element to value of left
    end

    else do
        write 'Error on line ' + counter
        break loop
    end

    counter = counter + 1
end loop

The syntax of this interpreted language is this:
Each operation is its own line.
The mathematical operations are limited to +, -, *, /
All numbers are integers and operations return integers.
Strings are only allowed in print/write statements.
Strings are enveloped in single quotes.
Variable names must be single letters.
All individual parts of a line must be separated by 1 space.
Write writes to screen without newline.
Print is like write but with a newline.
No direct string concatenation, use write statements for that.

Example program:
a = 5
write 'A is: '
print a
b = a + 5
b = b / 7
write 'B is: '
print b

Example output:
A is: 5
B is: 1

To test its simple nature, I wrote the original version of the interpreter in Python 2.7 and was able to make it in 26 lines of code. Here is the source:
import sys
varis = {}
lines = []
write = sys.stdout.write
while 1: #get input
    inp = raw_input("> ")
    if inp == "run": break
    lines.append(inp)
for y in range(len(lines)): #parse program
    x = lines[y].split()
    if x[0] == "print" or x[0] == "write":
        if x[1][0] == "'": write(" ".join(x[1:])[1:-1])
        else: write(str(varis[x[1]]))
        if x[0] == "print": write("\n")
    elif len(x) > 2 and x[1] == "=":
        if ord(x[2][0]) > 96 and ord(x[2][0]) < 123: left = varis[x[2]]
        else: left = int(x[2])
        if len(x) > 3:
            if ord(x[4][0]) > 96 and ord(x[4][0]) < 123: right = varis[x[4]]
            else: right = int(x[4])
            if x[3] == "+": left += right
            elif x[3] == "-": left -= right
            elif x[3] == "*": left *= right
            elif x[3] == "/": left /= right
        varis[x[0]] = left
    else: print "Error: line "+str(y+1)

I then wrote a modified version of it in Axon (the main programming language I use at work) and I was able to make it in 31 lines of code. Here is the source:
(x) => do
  vars: {}
  x = x.replace("\n",";").split(";")
  t: []
  cou: 1
  left: ""
  right: ""
  x.each y=> do
    t = y.split(" ")
    if(t[0] == "print") do
      if(t[1][0..0] == "'") echo(t[1..-1].concat(" ")[1..-2])
      else echo(vars.trap(t[1]))
    end
    else if(t[1] == "=") do
      if(t[2][0] > 47 and t[2][0] < 58) left = parseInt(t[2])
      else left = vars.trap(t[2])
      if(t.size > 3) do
        if(t[4][0] > 47 and t[4][0] < 58) right = parseInt(t[4])
        else right = vars.trap(t[4])
        if(t[3] == "+") left = left + right
        else if(t[3] == "-") left = left - right
        else if(t[3] == "*") left = left * right
        else if(t[3] == "/") left = floor(left / right)
      end
      vars = vars.set(t[0], left)
    end
    else echo("Error: line "+cou)
    cou = cou + 1
  end
end

The differences in each of the implementations is that the Python one is more like a command line in which you type in your lines and then type in "run" when you want to execute the program, and it supports both "write" and "print". The Axon implementation only has "print" and is a function that takes in the whole program as a string parameter, so I made that to also work with semicolons between the statements.

Friday, April 8, 2016

Easily Install Oracle's Java On Ubuntu Linux

Hello world, today I have a quick "life hack" type thing for Ubuntu people.

Where I work, I am kind of the Linux guy, installing our software for clients who wish to run it on Ubuntu machines.
The problem is that our software runs on Java, and some of the people either don't know how to install Java or have it installed in a weird way.

I was asked what was the easiest way to install Java, and here you go:

sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer
(agree to the two prompts)
(wait for download to finish)
java -version


The first 2 commands installs the webupd8team Java repository and updates apt-get so you can install from there.
The next command actually installs it, with a license agreement and a download.
The last command just confirms that you have Java installed.

Sunday, March 20, 2016

Making C64 Program Tap Files

Before I go ahead and tell you guys how to make a tap file that is loadable in a C64 emulator, I'm going to give you the link to the source of all my info: http://c64tapes.org/dokuwiki/doku.php?id=loaders:rom_loader and http://c64tapes.org/dokuwiki/doku.php?id=analyzing_loaders

This is where I learned how to make tap files (although it took me two weeks to find that page).

Enough chat, here is the structure of a C64 tap file.
There are 3 different kinds of pulses:
-    a long pulse lasting about 672 µS represented as ASCII char 86 or hex 56
-    a medium pulse lasting about 512 µS represented as ASCII char 66 or hex 42
-    a short pulse lasting about 352 µS represented as ASCII char 48 or hex 30
Physically, these pulses are square wave pulses running at 50% duty with a period of the specified µS.
I will refer to long as L, medium as M, and small as S. Data encoded using a combination of these pulses will be referred to as LMS format.

Now these pulses alone don't make up binary data (as I learned the hard way).
Bits are represented as a pair of pulses, a 0 bit being SM, a 1 bit being MS, a start bit being LM, and a data end bit being a LS.
A LMS byte is represented as a certain sequence of pulses which looks like this:
LM     xx    xx    xx    xx    xx    xx    xx    xx    nn
start  bit0  bit1  bit2  bit3  bit4  bit5  bit6  bit7  check

There is a start bit in front of every byte, but each byte doesn't have its own end bit. The check bit at the end is calculated with the bitwise formula:
1 xor bit0 xor bit1 xor bit2 xor bit3 xor bit4 xor bit5 xor bit6 xor bit7
Or more conveniently, if the byte has an even number of 1's, the check bit is 1, if the byte has an odd number of 1's, the check bit is 0.

Now that single bytes are covered, it's time to learn how whole data is encoded in a tap file.

Every C64 tap file starts off with 20 bytes of information, kind of like meta data. All information should be coded in hex, as this is raw data.
Bytes 0 to 11 are C64-TAPE-RAW, byte 12 is the number 1, bytes 13 to 15 are just 0, and bytes 16 to 19 is the length of the actual tap data in least significant byte first (LSBF) format. The tap data length is usually added last, since we don't know how long our tap data is yet.

The rest of the bytes are the data.
We start with 27136 small (S) pulses, this is the leader block used to calibrate the datasette speed.
Then we start the header with 9 sync bytes, from 137 down to 129 (LMS).
Then we write the header file type, in this case just the number 1 (LMS).
Next is the starting address for the data, two bytes in LSBF format (LMS).
Next is the ending address for the data plus 1, also two bytes in LSBF format (LMS).
Then the bytes in PETSCII code for the file name, no more than 16 bytes (LMS).
Then 16-lengthOfFileName bytes of the number 32 for title padding (LMS).
Then write the number 32 for 171 times, this is the header body, not sure what it's for (LMS).
Then a checksum byte for the header, this is all the bytes from the header file type (byte1) to the end of the header body (last byte) (LMS), use this bitwise formula to calculate:
0 xor byte1 xor byte2 xor ... xor last byte
Then a data end bit of LS to end the header.
Then we write a small pulse 79 times as an interblock gap.

Now we write the header again, but with some changes.
Write the 9 sync bytes, but this time from 9 to 1 (LMS).
Then write the exact same header data from the header file type to the data end bit (LMS).
Next write 78 small pulses as the header end trailer.
Then write 5376 small pulses as the interrecord gap.

Now we can start writing our actual program data.
Before we do that, you'll need to know how to make program data (useful link: https://www.c64-wiki.com/index.php/BASIC_token) or get it from RAM. (Or use my tapwriter.py program on GitHub)
Start the program with 9 sync bytes, from 137 down to 129 (LMS).
Next write the bytes of your program exactly how it would appear in ram from the starting address to the ending address (LMS).
Then write your checksum byte, calculated just like on the header blocks, only from after the sync bytes all the way to before this checksum byte (LMS).
Then write your data end bit of LS to end the header.
Then write a small pulse 79 times as the interblock gap.

Now we write the program data again, just like with the header.
Write the 9 sync bytes, but from 9 to 1 (LMS).
Copy the program block from after the sync bytes all the way to the data end bit.
Then write a small pulse 78 times for the data end trailer.

That's all there is to it, just remember to update the tap data length in bytes 16 to 19, this is only the length from byte 20 to the end.

This isn't the most efficient way to store data, since it takes about 10 seconds just to get to the header after the leader block, but it works and it's pretty cool to have a program load off a tap file that you made (forged with your own hands in the heart of a dying star).

If you understand how to create a tap file, and can actually get it to work (took me 3 days), then it wouldn't be hard to reverse the protocol to read the data off of the cassette or even directly from the C64, just as I will be doing for my C64 Arduino Internet project.

GitHub program files:
https://github.com/koppanyh/C64Net/blob/master/tapwriter.py

Wednesday, October 21, 2015

Pebble Time Watch - Shutting Down a Server

Here's my story: I have this server computer that I turn on every morning. It runs some basic server stuff, syncs my FitBit to the internet and charges my phone. I turn it off before I leave to school or work in the morning because it cannot be accessed from outside my LAN network and would otherwise waste energy with no one there to use it.

Here's my problem: To turn it off, I normally have to SSH into the server and run the command "sudo poweroff". This normally takes longer than I would like, especially if I happen to be running late.

Here's my solution: Make an app for my Pebble Time smart watch that could turn my server off easily.

My Implementation: I decided the best way to do this was to take advantage of the PHP part of the web server, running Apache 2 on an Ubuntu Server 14.04 box. I could make a web page that runs the Linux shutdown command and replies something through HTML. Then I could make an app for the Pebble Time smart watch that calls the page and displays the status.
The PHP code looks like this:
Poweroff ---
<?php
  echo(exec("sudo poweroff"));
?>

It is just a small PHP script called poweroff.php that runs the poweroff command and returns "Poweroff ---" plus whatever might be appended from the poweroff command. Running it is as simple as just calling "http://IPofServer/poweroff.php".
It's important that the Apache 2 web server is given admin permissions, otherwise it cannot run the "sudo poweroff" command. To give it admin permissions, run this command in terminal: sudo visudo and write this line to the end of the file: www-data ALL=NOPASSWD: ALL then press Ctrl+x, press y, press enter and you should be good. Type sudo service apache2 restart to restart the Apache 2 server and apply the changes, or just reboot the whole server.
The watch app itself was written using the Pebble.js method, this way I didn't have to waste a lot of time making it in C, but I might port it later. The code is very simple:
var UI = require("ui");
var ajax = require("ajax");


var card = new UI.Card({ //init the card
  title: "Shutdown",
  subtitle: "USERV2",
  body: "LOADING..."
});
 
card.show(); //show the card
 
ajax( //send the shutdown request
  {url: "http://IPofServer/poweroff.php"},
  function(data){ //success function
    card.body("STATUS: "+data);
  },
  function(error){ //error function
    card.body("ERROR - Cannot Reach Server: "+error);
  }
);


How it works: The app just initializes a card screen and all the parameters are hard coded, but I'm planning on changing that in a possible future update. The app then sends an AJAX request to my server (where it says IPofServer, change to an actual IP) and calls the shutdown page. The shutdown page return some text, in my case "Poweroff ---", and proceeds to send the shutdown command to the system. The watch receives the output of the server and replaces the "LOADING..." (on the image) with "STATUS: Poweroff ---". If it cannot reach the server or something goes wrong, then the watch says "LOADING..." for a while and then returns "ERROR - Cannot Reach Server: " with any errors appended to it. Once you see "Poweroff ---" then you know the server is shutting down and you can press the back button on your Pebble and proceed with whatever you were doing previously.

Screenshot of emulator with shutdown app.

Friday, October 16, 2015

Sale on GearBest.com!!!

Hey guys, there's a sale happening on GearBest.com right now: http://www.gearbest.com/promotion-electrical-amp-tools-special-233.html

In case you happen to miss it, just remember that GearBest.com always has cool stuff at rock bottom prices! And keep an eye out for any possible sales, they are somewhat frequent.