Updates from February, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • .e 6:59 am on February 15, 2016 Permalink
    Tags: , puzzle games, tis-100   

    TIS-100, ranty review 

    I just ‘finished’ the puzzle game TIS-100, meaning I wrote a code that solves the final task of the game and saw all of the plot (other than the hidden puzzle. I’m not ready to tackle that mentally), so please listen to me rant why this is probably my favorite puzzle game of the 2010s, if not of all time.

    First of all: what is it? It’s a game that tells you that you inherited a weird old time-y computer from your missing uncle and are trying to run some debuggers on it to figure out what it is. It comes with an ancient looking manual and very little else. If it sounds like a mystery game, it’s cause it is.

    (Throughout this post, feel free to click to embiggen the images)

    Blank TIS-100 screen

    Blank TIS-100 screen

    The game is really about designing algorithms in the mathematical sense: converting inputs into outputs. To do so you’re given a pretty simple assembly language architecture with one feature, and one huge caveat. The feature is that you have access to multiple chips that all run in parallel and can talk to each other. The caveat is that each only has a single register that can do storage, math, and logic, and a second register that can only be used as long term storage.

    Got it? Ok, so let’s go over a solution to a puzzle, or more precisely my thought process of solving one. Spoiler warning obviously, if you want to solve each one yourself, don’t read this.

    The TIS-100 in later levels includes a ‘graphics’ module that allows you to display pixel data that is being sent to the output. The format is a string of integers formed as

    ( Starting X coordinate, Starting Y coordinate, <series of integers representing colors to draw 1 square of>, -1 )

    In this task we are given a length of a line, then a color to use for it. We have to figure out how to wrap at the edge of the screen if the line is longer than the screen width. Here’s what the tasks look like, along with my initial solution:

    Parts of the screen

    Parts of the screen

    So how does a guy who loves nothing more than clean logical order and Object Orientation handle this? Simple, by creating treating each node as a make-shift object. Let me walk you through the code above.

    First, we got to keep track of where we are on the screen:

    screen2

    The column and row trackers

    The upper circled node iterates from 0 to 30 (screen width), then sends that data to the right. It also sends either 0 or -1 down to the node that keeps track of rows. The row tracking node (circled below) returns it’s stored value, and whenever it receives a -1 it increments the stored value. So now we got a steady generator that spits out

    (0,0), (0,1), (0,2) ... (29,0), (30,0), (0,1), (1,1) ...

    etc etc.

    Now we have to keep track of what color we’re on. We got a third node for that:

    screen3

    The color tracker

    This one stores the length of a color and the value of the color, then by swapping those in and out of the long term register it decrements the length and constructs a little quad packet like (0, 0, 2, -1). That particular packet would draw a grey square in top left for instance. The node then passes this packet down into the chain of helper passing nodes and off they go to the output off the bottom row.

    I make this sound trivial, but in reality it took the better part of an hour to come up with this solution, and then a better part of a second hour debugging a bunch of silly deadlocks and memory corruption mistakes (having two nodes get out of sync and wait for input from each other so that they hang indefinitely, forgetting to swap memory contents before displaying, stuff like that).

    So what kind of performance do we get on that? Well, this:

    speed1

    Initial score

    Not great compared to the average other user. So now we get to the second part of TIS-100. Optimizing to compete with the ‘others’ of the internet. So how can we optimize this?

    Well, first thing that jumps out at me is that the bottom right node seems to be sending stuff pointlessly far. Look:

    A regular Marco Polo this guy

    A regular Marco Polo this guy

    It really doesn’t have to go that far. What if instead of going all the way around, it just goes right? Now the top right packet constructor will only do 3 of the numbers, and the node below him will just plug in the row number from the left as we go. That should skim off a cycle or two, no? And skim them off the innermost loops too. Always good.

    More to the point, this route

    More to the point, this route

    So now we’re just going straight right, though we needed to add a tiny bit of logic to the right to build the packet. 3 cycles less per each loop. Nice.

    We can do better though, can’t we. I mean, what if we reärrange the nodes so that instead of the top right node acting as a packet constructor the packet gets constructed “as needed” and only in the last moment. A Just-In-Time packet, if you forgive the borderline archaic term. It would require moving the two “storage” nodes to below the input and then setting up an assembly line to the right of them. And oh look, the output is already set up exactly in the perfect spot for it. Hm. It’s like the designers knew this.

    It's so beautiful

    It’s so beautiful

    So at time A the packet is (?, ?, Color, ?).

    At B we get (X, ?, Color, ?)

    And only at C do we get (X, Y, Color, -1)

    Now, how much of an improvement do we get?

    A whole freaking lot it turns out

    Quite a bit, it turns out

    Down from 7684 to 4898, so 36%. Not too shabby considering all we did was move some nodes around. Now, if we really wanted to make this mother fly, we would use that feature that lets us create longer packets. I mean, why send

    (0,0,1,-1), (1,0,1,-1), (2,0,1,-1), (3,0,1,-1), ...

    When we can send

    (0,0,1,1,1,1 ... 1,1,-1)

    I mean, it can’t be that difficult can it?

    And before you know it, you’ve sunk another few hours into TIS.

     

     
  • .e 5:59 pm on October 31, 2015 Permalink
    Tags:   

    Quick perl tip: 

    Quick perl tip, don’t confuse

    if( $a >= 3 ) {

    and

    if( $a => 3 ) {

    the first one is “Greater than or equal to”. The second is “set it equal to 1 or 0 depending on whether it’s greater than”. You don’t want that. If you do want that, you shouldn’t want that.

    Yes that just cost me like 10 minutes.

     
  • .e 5:32 pm on October 25, 2015 Permalink
    Tags: , monte carlo, ,   

    Dragon Slayer review 

    UPDATE ON BOTTOM

    A kickstarter micro from Joe (thank you Joe), and another fun travel game.

    IMG_3120

    Dragon Slayer at Tea-n-more

    Roll dice to kill dragons. Blue is easy to kill, green is hard to kill, red is hard to kill. Very push your luck with one minor complication of “challenging” where you can force someone to fight 1 more dragon. I think this is one of those games that I’ve never won against anyone, cause for a mathematician I am surprisingly bad at anything push-your-luck.

    No fear though. I am also a problem solver. I wrote a perl script to try every possible strategy of this game to find the ultimate path: http://www.codesend.com/view/27b4c6737ffb0f258d21f0870ef40f39/ (note, that page apparently stripped the slash from \n turning them into n, putting the slashes back in is left as an ‘exercise to the reader’)

    Ran the above a million times as it plays the game against itself, and dumped out the results split first into 3 bravery strategies, then per line as to what dragons to fight first and when to stop: G is green, B is blue, R is red:

    BRAVE HUNTERS (NEVER STOP):
    G: 3.55582724284349
    GB: 4.83913016118448
    GR: 5.93901419466194
    GBR: 5.88304461564739
    GRB: 6.12547757531082
    B: 1.9422564628113
    BR: 5.43162020514388
    BG: 4.73947086902975
    BGR: 5.8079270759356
    BRG: 5.91094849827848
    R: 4.72113197709436
    RB: 5.62512548057186
    RG: 6.04521196103285
    RGB: 6.19196504822949
    RBG: 6.08984259117755
    
    SORTA COWARDLY HUNTERS (STOP AFTER LOSING 2 DICE):
    G: 3.55736209937724
    GB: 4.83183743505442
    GR: 6.01160921057368
    GBR: 6.29789774295348
    GRB: 6.53803741345588
    B: 1.94158197242587
    BR: 5.36629909166177
    BG: 4.64798593695629
    BGR: 6.12940520044637
    BRG: 6.2615042177132
    R: 4.71602131055088
    RB: 5.71132962958519
    RG: 6.22440274061364
    RGB: 6.74595327517729
    RBG: 6.64300027598123
    
    VERY COWARDLY INDEED HUNTERS (STOP AFTER LOSING 1 DIE):
    G: 3.55764476897338
    GB: 4.48069396594449
    GR: 5.52641870440066
    GBR: 5.59525061049419
    GRB: 5.86873999405275
    B: 1.94178904084078
    BR: 4.67586588050834
    BG: 4.05631865243732
    BGR: 5.16761932796078
    BRG: 5.34570040879832
    R: 4.71543010930324
    RB: 5.43283062052642
    RG: 5.88802350064729
    RGB: 6.23849672751084
    RBG: 6.13399333787887
    

    So the optimal strategy is “Fight Red, then Green, then Blue, stop if you’re ever down to 1 die”. Ready to play this again now 😛

    UPDATE:

    Someone pointed out that this forgets that it’s possible to start over after killing 3 dragons. Went ahead and wrote a mini script to solve 4+ dragons and dropped it on gist here.

    Chart for the 4+ goes:

    RGBB:2		8.95587161894434
    RGBG:2		8.1855250370825
    RGBB:1		7.83691944708024
    RGBR:2		7.2969944065635
    RGBG:1		6.79607331108854
    RGBGB:1		5.9229677180421
    RGBR:1		5.82409754092746
    RGBBG:1		5.67912411832824
    RGBRB:1		5.56045424181697
    RGBRG:1		5.39682940693488
    RGBBR:1		5.20002033243532
    RGBGR:1		5.10485791835152
    RGBRBG:1	4.27486930828093
    RGBBGR:1	4.1413477013505
    RGBBRG:1	4.07694637988488
    RGBGBR:1	4.00618498734889
    RGBRGB:1	3.99050347932869
    RGBBR:2		3.86899117368152
    RGBGRB:1	3.86877828054299
    RGBBG:2		3.81470911086718
    RGBGR:2		3.58723111077088
    RGBGB:2		3.43148089674771
    RGBRG:2		3.26223520818115
    RGBRB:2		3.07526703651569
    RGBRGBB:1	2.81118143459916
    RGBBGRB:1	2.75342465753425
    RGBGBRB:1	2.73006774361647
    RGBRBGB:1	2.67808219178082
    RGBGRBG:1	2.66980146290491
    RGBRBGG:1	2.61403040810883
    RGBRGBG:1	2.52007347152978
    RGBBRGB:1	2.49118188997104
    RGBBRGG:1	2.47904524007771
    RGBGRBB:1	2.46516500785752
    RGBGBRG:1	2.3903355704698
    RGBGBRR:1	2.3730625334046
    RGBGRBR:1	2.30893433799785
    RGBBGRG:1	2.28329361927456
    RGBRBGR:1	2.27629513343799
    RGBRGBR:1	2.24063009234112
    RGBGBR:2	2.2267829656234
    RGBBGRR:1	2.18224789915966
    RGBBGR:2	2.17974814559255
    RGBBRGR:1	1.96322336398053
    RGBBRG:2	1.89581278579754
    RGBRBG:2	1.87088653119942
    RGBRGB:2	1.74605504587156
    RGBGRB:2	1.67498388730319
    RGBGRBG:2	0.8984375
    RGBRBGR:2	0.89143865842895
    RGBBRGG:2	0.86304158185519
    
     
  • .e 1:34 am on June 22, 2015 Permalink
    Tags: , genetic programming, hiv, , , python   

    Requiem 32 is a series of virus genotypes, starting with a simple repeated ‘c’ which then in 31 iterations becomes the HIV genotype. Each of these iterations is then analyzed using a process based on biological DNA parsing which change the music created into a different piece, slowly more and more different from the original, until the original state is completely unrecognizable. I hope the piece gives helps create emotional understanding of the idea of a virus and how something that is so simple can have such an incredible impact, hopefully bridging the very real mental chasm between the biology of infection, and it’s effect on the infected.

    For best experience, please make your browser window as large as possible and use headphones. To interact with the piece click the circles at the top. The RNA sequence clicked on and matching sheet music will be loaded and the piano performance encoded by that RNA string will start. 1 represents a starting state, and encodes the 4 E chords with a repeated E note 4 times. Each of the other states adds a tiny bit more complexity to the virus, creating progressively more and more changes to the music piece.

    A visual guide for the RNA parsing is provided at left. The darker color is the header for a particular function, while the lighter color is the actual data processed by it. Each of the biological parsers, each represented by one color, begins at the top of the genotype, reads until it finds its starting trigger, and then starts reading while getting ready to apply a modification. Upon hitting the terminator (always “cc”), it applies the change to the music. It then keeps reading looking for a new starting condition.

    The piece involves intrinsic looping in the structure of the music, similarly to how the biological processes do not function in a vacuum, but rely on a host organism to provide context to the RNA intrusion.

    The installed piece can be found at http://miriku.com/requiem, while the source code is available at https://github.com/miriku/requiem.

    Technical notes: the majority of the code is written in python, with the exception of the text parser which creates the 30 intermediate states which is written in perl. When ran using the ./go shell command, the python code will open all rna files, processes them, then output both a color coded html file and the midi file represented. The file ‘models.py’ contains the actual structure of the music: repeated sequences that contain a chordal structure, and a melody played on top; while the file ‘driver.py’ contains the actual mechanism of parsing of the text into midi. The final mp3s and pngs of the sheet music were both created by hand and are currently not automated.

    Finally, I genuinely apologize for any possible layout issues with your particular hardware/software setup. This was designed under time constraints as a standing installation using Safari in full-screen mode, and unfortunately cross-platform compatibility was not a priority. I welcome any pull requests with improvements.

    I genuinely thank you for your time.

     
  • .e 8:39 pm on May 24, 2015 Permalink
    Tags: ides, , sketching   

    Starting a Programming Project 

    This is what programming looks like to me, step 1

    IMG_2737

    Programming Sketches

    If I start coding before I sit down and make one of these, I’ll never get anywhere. I need to have a mental visual relationship between everything, before I can start.

    Visual memory is very important in programming for me. I really value IDEs that have one of those sublime-style “code maps” on the side, and ones that let me skip to bookmarks and function definitions easily, preferably with a single click. Not having to think about where I am in the file lets me concentrate on more useful things.

    Code map example, it's the thing on the right

    Code map example, it’s the thing on the right

    Another weird thing is that sketching process is so far it only works for me with pen and paper. I’d love to have an iPad with enough input resolution to properly let me sketch but so far none of the tools are good enough at it.

     
c
compose new post
j
next post/next comment
k
previous post/previous comment
r
reply
e
edit
o
show/hide comments
t
go to top
l
go to login
h
show/hide help
shift + esc
cancel