Two Guys Arguing

Mountains of Obfuscation

Posted in challenge by benjaminplee on 02.26.12

What would you do?

You have a couple hundred files across several nested folders that contains within them 10000+ obfuscated random and unique user names.  You also have a translation file of all of the obfuscated names and new ones you ned to have them replaced with.  Some files have all 10000+ obfuscated names in them.  Some have none or just a couple.

How would you update all of the files?

Obviously this isn’t a crazy hard problem; there are many ways to solve it.  I know how I solved it.  I am curious as how YOU would solve it.

Go!

 

[edit: added clarification]

A Solution from Purgatory (for the Matrix from Hell)

Posted in challenge, math, questions by benjaminplee on 01.02.11

This post attempts to recount some of my thought process which eventually (more than a year later) lead to the Matrix from Hell puzzle I posted about a few days ago.  If you don’t want to know my answer, don’t read the rest of this post.  My final solution is at the bottom.

You have been warned.

~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~

Below is a list of my general thought process and the main ideas/revelations/halucinations that I know helped me to my solution.  An annotated matrix is at the bottom with some of the ideas highlighted in different colors.

  • Should indices start at 0 or 1?
  • Values along either axis count up by 1 in both directions when the other =0
  • Values are duplicated over the f(x)=y axis –> Order of indices given to function is inmaterial since they can be swapped
    [The RED 5 can be seen duplicated over the diagonal]
  • Calculation of max/min index is O(1) so stop worry about it and “forget” the bottom half of the matrix (assume X>= Y)
  • Values generally increase as they go right/down but not always
  • f(x,x)=0, f(x,0)=x
  • Values are symmetrical perpendicular to f(x)=y IFF the bounding square in question is a power of 2
  • “Quad” patterns can be seen repeating for every power of 2.  In each “Quad” the top left quadrant is the same as the bottom right and the top right is the same as the bottom left.
    [Each "Quad" of the example matrix is outlined in BLUE with the quadrants in LIGHT BLUE. PINK shows the repetition]
  • power of 2 repeating nature of the values leads to thinking of binary trees
  • binary trees leads to thinking about a possible solution which could run in O(log2 n) time:
    • In a nut shell, for a given (X,Y), algorithm would find smallest boudning power of 2 including X and would walk back “Quad”s by each successivly smaller power of 2 “Quad” until the last one is met.  For each “Quad” determine which quadrant the value lives in and remap to root values.
    • Debate if this would really work for large numbers and if it could be reduced to constant time function by math that I have forgotton from college/HS
    • Dismiss b/c I can’t remember a way and base idea is > O(1)
  • Binary trace back algorithm idea makes me realize that it can be also looked at as the “binary” representation of a number (e.g. 01011011010) where each 1 represents a “Quad” where the value was in the upper right or bottom left and vica-verca.
    [Following the matrix value at (5,6) can be seen ORANGE.  The value 3 is in the bottom right  of the 1st "Quad", then BL, & TR. {BR BL TR} => {101} => {3}]
  • Remembered that f(x,y)=0 IFF x==y …. which means that difference between X and Y is important to value of f()
  • Eureka!
    • F(X, Y) = X xor Y
    • solution typed above in white on white to protect the innocent. highlight to view.

sample matrix with some of my thought process drawn out

That is it.  I never said it was pretty or made any sense.

Tagged with: , , , ,

Matrix Puzzle From Hell or: How I Learned to Stop Worrying and Love the Patterns

Posted in challenge, math by benjaminplee on 12.30.10
The Stage

About a year ago, Mr. King (@Adkron) posed a math puzzle on our team’s whiteboard first thing one morning.  The problem seemed at the same time very complex and strangely simple.  Amos said that he had found it surfing the web the night before and that it was from some company’s interview or resume-submitting questions.

After several passionate whiteboarding sessions including members of our team, and any poor souls who walked by (I believe Mr. Young falls into this group), no one had a solution.  Eventually the whiteboard was clearred for more “important” work but the puzzle lingered with me.  On several occasions over the past year I have redrawn the matrix on a pad of paper and spent and hour or two trying to decipher the patterns and make sense of the answer tickling at edge of my brain.

This past week, while drifting off to sleep, the puzzle popped back into my head.  After a few moments a number of ideas I had had months before fell together in just the right way for me to FINALLY figure out a solution.  Eureka! (I mentally shouted) and got out of bed to find a piece of paper to work through some more examples and prove myself right.

The Puzzle

Given a 2D matrix such that each cell’s value is defined as follows:

>> The smallest non-negative integer not already present to the “left” or “above” <<

Determine an constant time function ( O(1) ) which given X and Y indices will return the value of the matrix cell at (X,Y).

For the visual people in the crowd, the top left corner or said matrix looks something like this:

First 8x8 cells of matrix puzzle

First 8x8 cells of matrix puzzle

The picture only shows the top 8×8 of the defined matrix as an example.  We can see that whatever f(x,y) you come up with needs to equal the following example values

f(0,0) = 0
f(1,0) = 1
f(2,0) = 2
f(3,0) = 3
f(3,1) = 2
f(3,2) = 1
……

The real key here is that the solution needs to function in constant time: O(1).  This means that computing the matrix value at (6,3) should be the same cost computationally as computing the matrix value at (10000000,4500005).

Anyone can write a program to compute the whole matrix out to your point (in theory) but can you come up with a better solution? In less than a year?

The Solution

Not just yet.  I will post my thought process and eventual solution soon in a separate post.

** I didn’t think of this puzzle, nor guarantee that I am remembering it correctly **
** If you know who did or have any corrections, please leave a comment  below **


Tagged with: ,

NaNoBloMo Recap Part Deux

Posted in challenge by benjaminplee on 11.30.10

Sum up the last month of blogging in 120 characters or less (gotta leave space for a URL on the end)?

15 posts in 30 days; one neglected prego wife.  Finishing what your start; priceless.

Best skill you developed by writing 15 blog posts in 30 day?

How to think of, research, and write a blog post without waking up the wife.

Really, I started thinking more about how I can contribute back to open source projects I use every day.  I have to credit the QUnit team for accepting my changes and providing great support and feedback.  Also, contributing to a project that has real users other than myself has made me consider how other developers look at my code and what they need help with.

** Adding funny pics to my posts **

Favorite post of the last 30 days?

Single post? Popping a Register from a Stack: QuickPiet Macros  Ever since the April Lambda Lounge meeting I keep coming back to Piet and love trying to hack higher level features into a stack based language.  It took a lot of failed attempts to figure out how to implement registers but it was a lot of fun.

Series?  QUnit w/ Rhino posts.  At every step of the way I thought “Oh this should be simple and clever” and winded up being “God that took longer than I thought, but at least it was clever”.  Given the traffic over the past couple weeks, it looks like there is a decent amount of interest in running QUnit w/ Rhino … hopefully these have been helpful.  I want to finish QUnit-CLI with some good examples and working on NodeJS.

Idea? Nate’s Clojure posts.  I have not had time to delve into Clojure like I would like but need to give credit to Nate.  I didn’t understand a lot of his posts but they were always interesting.  And beat me hands down in traffic.

Im in ur blogs writin ur posts

Would you do this again next year?

Not sure.  I want to keep posting and working on getting my ideas out and helping others but it is really hard to commit to an every-other day post regiment.  I think a much better frequency would be 1 every week or so.

Which posts did you half-ass?

Pro Tips: IE Caching Can ByteNotes to self: Keep SVN in sync w/ Git The Poor Man’s Way, and Programming Anti-Patterns: Releasing Cthulhu.  Honestly, these were cop-out posts.  I know I will go back at reference them at some point, but I am not sure anyone else will.  See the previous question.

** Oh, and this post; kinda **

Any last words before spending the coming months trying to forget that you ever did this?

Peace Out!

 

 

 

 

 

Tagged with:

Copyright 1988

Posted in challenge by youngnh on 11.19.10

I found this in the book I’m working my way through. It’s a bit obvious, but see if you can’t tell what it does:

10   REM unknown
20   INPUT L$(1), L$(2), L$(3), L$(4)
30   PRINT
40   FOR I1=1 TO 4
50   FOR I2=1 TO 4
60   IF I2=I1 THEN 130
70   FOR I3=1 TO 4
80   IF I3=I1 THEN 120
90   IF I3=I2 THEN 120
100   LET I4=10 - (I1 + I2 + I3)
110   LPRINT L$(I1); L$(I2); L$(I3); L$(I4);
120   NEXT I3
130   NEXT I2
140   NEXT I1
150   END

The book is Umberto Eco’s Foucault’s Pendulum.

Chasing the Sun

Posted in challenge by youngnh on 11.17.10

As an incomplete response to Ben’s long-ago challenge, “Long Walk After the Sun”, I found 2 websites that gave me enough information to start calculating the answer.

The first is the Naval Oceanography Portal, a veritable plethora of astronomical almanacs, calculators and errata. In particular, their Sun Altitude/Azimuth Table Calculator is particularly useful. Plug in a date and town in the United States and it will calculate for you at down to minute resolution, exactly where in the sky you will find the sun from sunup to sundown.

Using their software to generate a table of headings, you would then know exactly which direction your hypothetical man would be traveling in at any given time of day.

The next useful online calculator I found was on the Federal Communications Commission’s website, of all places. It has a calculator which will determine “Terminal Coordinates Given a Bearing and a Distance”. You plug in a starting latitude and longitude, as well as a distance to travel and your bearing, and it will spit out the latitude and longitude you’ll end up at.

From Wikipedia, humans walk at a pace of about 5km/h, or about 83 meters per minute. Given a set of starting coordinates, you could look up a heading from the Azimuth/Altitude chart, and set the distance traveled to (83 meters x the number of minutes walking) and get a new location. If you had the patience to calculate a very large number of items, you could trace the path from sunrise on January 1st, 2009 to sundown on December 31st, 2009.

Or someone could write a scraper. Or better yet, look up the algorithms these sites use to calculate these sort of things and not hammer their servers for curiosity’s sake.

I did a few calculations by hand (and by “by hand” I mean I copied and pasted numbers into web forms) and here’s the track of a person following the sun today, November 17th, 2010 from sunrise at 5:50 AM until he gets tired and passes out at 8:00 AM

Time		Latitude		Longitude		Bearing (E of N)
05:50		38 38  0 N		90 15 0  W		105.8
06:00		38 37 53 N		90 14 27 W		107.3
06:10		38 37 45 N		90 13 54 W		108.8
06:20		38 37 36 N		90 13 21 W		110.2
06:30		38 37 27 N		90 12 49 W		111.8
06:40		38 37 17 N		90 12 17 W		113.3
06:50		38 37 06 N		90 11 45 W		114.8
07:00		38 36 55 N		90 11 14 W		116.4
07:10		38 36 43 N		90 10 43 W		118
07:20		38 36 30 N		90 10 13 W		119.6
07:30		38 36 17 N		90  9 43 W		121.3
07:40		38 36 03 N		90  9 14 W		123
07:50		38 35 48 N		90  8 45 W		124.7
08:00		38 35 33 N		90  8 17 W		126.5

Something that stands out is that in the northern hemisphere, the sun sweeps an arc from something like 60 to 300 degrees E of N in a single day. That’s during the summer. Winter months the sun is lower in the sky (spends less time above the horizon, so less time walking), and sweeps a smaller arc, but one still mostly centered south. Also, the bearing of the sun changes slower around noon. I’d venture to guess that the time you’d spend walking east and west wouldn’t be as long as the time you spent walking mostly south. In a single day, a person wouldn’t cover very much ground over the surface of the earth. There are over 100 kilometers between lines of latitude on the earth, so even traveling in straight lines, it’d take close to 2 ten-hour days to drop a line of latitude. Over the course of an entire year, though, that might add up to some serious displacement.

I’m now very interested in this problem, and as a shot-in-the-blue guess, I’m going to say that our wandering man would end up somewhere on the line where the sun traces a perfect East to West path overhead, as north of it he’d be drawn south and south of it he’d be drawn north. I’m not sure that’s the equator, though since the earth is tilted on it’s axis. Ah, more problems already brewing and I haven’t even properly finished this one yet. Time to stop typing.

A few other websites I stumbled across researching this post that provide some illuminating links:
The Griffith Observatory in Los Angeles, in particular this page which turned me on to the possibility of not having to derive all the math myself because humans have been looking at the sky since the dawn of their existence and who would’ve thunk that at least one of those dirty apes thought to write down what they saw.
This website’s FAQ has a tip for a dead-tree book with Astronomical Algorithms in it.

Tagged with:

First Cut – Piet Prezi Presentation

Posted in challenge by benjaminplee on 03.18.10

You can find the first cut of my Prezi based presentation on Piet and QuickPiet here:

http://prezi.com/fjqdfoigiipm/firstcutpiet/

I will update the link/presentation over the next week or so leading up to the next Lambda Lounge meeting.

Tagged with: , ,

Piet Roll Command

Posted in challenge by benjaminplee on 03.15.10

Roll-n-rolling with the Piet ROLL command

Mr. Young and a few others questioned how QuickPiet‘s command worked …. and to be honest, at first I didn’t either.  It turns out that the Piet ROLL command works fairly simply and is extremely powerful (according to npiet which I used as the basis for my testing).

The ROLL command pops two values off of the stack puts nothing back.  The top value from the stack defines how many “turns” the roll executes.  A turn will put the top value on the bottom and shift all other values “up” one place toward the top of the stack.  The second value defines the “depth” of the roll or how many elements should be included in each turn starting at the top of the stack.

As the main Piet page suggests, a ROLL to a depth of X and a single turn will effectively bury the top of the stack down X spots.  If that is as clear as mud, check out this image which shows two roll actions executed on a already populated stack.

Demonstration of the Piet ROLL command

Click to enlarge

[EDIT: Correction, the last roll in the above image shows a roll of depth 5, 2 turns. Not 3.  My bad.)

I used the nPiet command line Win32 interpreter to test this and the following program shown with 1 pixel per codel** and again with 20×20 pixels per codel.  nPiet is the most stable interpreter I have found and has some nice features like creating trace output images, tracing/logging statements, and automatically guessing codel sizes.  Below is the 20×20 codel version and nPiet trace output.

ROLL test program

ROLL test program

$ ./npiet.exe -v -t ben/roll-big.gif
info: verbose set to 1
info: trace set to 1
info: using file ben/roll-big.gif
info: got gif image with 320 x 120 pixel
info: codelsize guessed is 20 pixel
trace: step 0  (0,0/r,l nR -> 1,0/r,l dR):
action: push, value 1
trace: stack (1 values): 1
trace: step 1  (1,0/r,l dR -> 2,0/r,l lR):
action: push, value 2
trace: stack (2 values): 2 1
trace: step 2  (2,0/r,l lR -> 3,0/r,l nR):
action: push, value 3
trace: stack (3 values): 3 2 1
trace: step 3  (3,0/r,l nR -> 4,0/r,l dR):
action: push, value 4
trace: stack (4 values): 4 3 2 1
trace: step 4  (4,0/r,l dR -> 5,0/r,l lR):
action: push, value 5
trace: stack (5 values): 5 4 3 2 1
trace: step 5  (5,0/r,l lR -> 6,0/r,l nR):
action: push, value 3
trace: stack (6 values): 3 5 4 3 2 1
trace: step 6  (6,0/r,l nR -> 7,0/r,l dR):
action: push, value 2
trace: stack (7 values): 2 3 5 4 3 2 1
trace: step 7  (7,0/r,l dR -> 8,0/r,l lB):
action: roll
trace: stack (5 values): 3 5 4 2 1
trace: step 8  (8,0/r,l lB -> 9,0/r,l nB):
action: push, value 3
trace: stack (6 values): 3 3 5 4 2 1
trace: step 9  (9,0/r,l nB -> 10,0/r,l dB):
action: push, value 2
trace: stack (7 values): 2 3 3 5 4 2 1
trace: step 10  (10,0/r,l dB -> 11,0/r,l lG):
action: roll
trace: stack (5 values): 4 3 5 2 1
trace: entering white block at 12,0 (like the perl interpreter would)...
trace: step 11  (11,0/r,l lG -> 12,0/r,l WW):
trace: special case: we at a white codel - continuing
trace: white cell(s) crossed - continuing with no command at 12,2...
trace: step 12  (12,0/r,l WW -> 12,2/d,r lG):
info: program end

** Since small Piet programs are TINY, instead of using 1×1 pixels as the unit block or codel, Piet interpreters should be able to use codels of larger sizes.  Codels of larger sizes allow Piet programs to be easier to see and work with.

Tagged with: , ,

Challenge – QuickPiet Interpreter

Posted in challenge by benjaminplee on 03.14.10

Create an interpreter for a new Language based on Piet: QuickPiet

To pair off of Nate’s Rock Paper Scissors challenge, here is one I am offering up to him: create an interpreter which will execute QuickPiet commands.  What is QuickPiet?  QuickPiet is a very basic language based off of the commands found in the esoteric Piet programming language.

Piet_hello_big from http://www.dangermouse.net/esoteric/piet/samples.html

Big Piet Hello World (25 pixels / codel)

Piet programmers are written as images which can be interpreted as actions based on a stack.  Recently I signed up to give a talk at the April Fool’s Day meeting of the Lambda Lounge where several people will be giving short talks on esoteric and useless programming languages.  Programming in Piet poses several challenges including working only with a single stack and building up your logic into pixels and colors.  I should have a few posts on writing programs in Piet in the next week or so. Until then, I have been mainly struggling with how to accomplish real work with just a single stack and a very limited menu of commands to choose from.  QuickPiet is an attempt to make that process easier.

The challenge:

  • Write an interpreter for the QuickPiet language I have posted in a new GitHub Gist;  http://gist.github.com/332040.
    [Edit: The language spec is now in the base QuickPiet repo on GitHub]
  • The interpreter should allow the user to enter in QuickPiet commands from a file or GUI text box
  • The interpreter should allow the user to enter text to be handled by STDIN and should display to the user any characters sent to STDOUT
  • Ideally the interpreter would be written in a cross-platform way (e.g. JVM, Ruby, Javascript/HTML) but anything is valid
  • Extra points for GUIs and/or the ability to see how the stack changes through program execution and/or at the end

The “complete” spec can be found on the Gist page, but a very quick rundown is below:

  • Program execution is top down, except for GOTO commands
  • Each line can be blank (ignored), a label, a comment, or a command
  • Only one command per line
  • There are no explicit looping or other control structures
  • The interpreter maintains a single “infinitely large” stack which different commands can act on
  • Example commands include (IN, OUT, PUSH, POP, ADD, SUBTRACT, GOTO, etc)
  • Commands are case-insensitive, labels are not

If you have any questions or are willing to venture a solution please leave a comment.  I just had this idea this morning so I am very interested in any feedback you may have.  I am planning on working on my own solution and hope to have something put together today or tomorrow.

Click the tag links for QuickPiet and Piet below to see all posts

Tagged with: , ,

Rock Paper Scissors

Posted in challenge by youngnh on 12.09.09

Write an interactive game of Rock, Paper, Scissors.

Ben, I’m laying down a challenge. Actually, it’s not so much a challenge as I’m more interested in how you think and then using you as a data point in a larger post, but I’m gonna sell this as a challenge.

There will be two players, the program should prompt each in turn for their name and then each for their “throw” until notifying that one or the other has one.

$ java RockPaperScissors
Player 1 Name: Nate
Player 2 Name: Ben
[R]ock, [P]aper, or [S]cissors? R
[R]ock, [P]aper, or [S]cissors? P
Ben Wins!

The program should be easily modifiable to handle the following score scenarios:
“First to X” – winner is the first player to win X matches
“Best of X” – winner is the first one to win more than 50% of X matches, only the required number of matches should be played
“To X, win by Y” – winner is first one to win X or more matches, by a margin of Y

There’s no need to drag XML into this, command line options should be preferred.

$ java RockPaperScissors -to 5
$ java RockPaperScissors -bestof 5
$ java RockPaperScissors -to 5 -by 2

It should be written in Java, and I’m interested in how Test-Driven Development guides your design decisions, so it would be helpful if your commit log left a concise and explanatory trail of what you did and why. git rebase –interactive may be helpful in revising the past in this regard.

No tricks, here, just an excercise in writing small, complete software

Ben, if you’re up to it, or if you just want to see where I’m going with this, then fork my repo on github and do work, son.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: