| Merkles and Social Engineering |
| Written by Joe Celko |
|
Joe Celko has come up with a math puzzle based on one of the current political hot topics - but let the team from International Storm Door & Software explain the problem of faced by planners who want to introduce policies to reduce segregation and discrimination.
Thomas C. Schelling (1969)
“This will not work!”, exclaimed Melvin Frammis. Bugsy Cottman, the junior programmer under Melvin at International Storm Door & Software, immediately replied, “Hey, I can debug before it goes into production! Don't worry, boss!” “Actually, this is not about your code for once. I am reading an article from Fox News” said Melvin, showing Bugsy and Jane Smith from Marketing, the following paragraph: “The Department of Housing and Urban Development is imposing a new rule that would allow the government to track diversity in neighborhoods across the country and then push policies to change those it deems discriminatory. The policy, called "Affirmatively Furthering Fair Housing”, would require the agency to gather data on segregation and discrimination in every neighborhood and try to remedy it.”
(click on image for Fox News Report from August 7, 2013) “From the same people who tried to remedy the housing problem with a sub-prime, no down payment policy!” said Jane, “My family's neighborhood disappeared in a cloud of foreclosures and their property went under water. And then..” Melvin knew where this was going, having heard it all before, “No, I mean this is mathematically absurd. Let me get pedantic on you. You play video games where you are in an imaginary world, right? Ever hear of the an economist Thomas C. Schelling? He created a simple artificial neighborhood to study a generation ago.” “How simple? Did he have trolls living next to Ogres; that never works out!” said Bugsy. “Think more abstract and simple,” said Melvin. "The world is a square grid and the citizens are either Red Merkles or Blue Merkles. Every square has a Merkle living there.” “Oh, like John Conway's Game of Life!” said Jane. “All you geeks were playing with it when I took my only programming class in High School!” “Same idea, but different rules!” said Melvin. “We will fill Merkleville randomly with an equal number Red Merkles and Blues. You can program that much can’t you, Bugsy?” “Mel, all you have described is a static, random pattern of red and blue dots on a screen,” said Bugsy. “I can do that and even print it on tee shirts, but why? Shouldn't it do something?” “We need a happiness rule for Merkleville!” announced Melvin. “Every Merkle wakes up and looks North, South, East and West to see his neighbors. If he is in a corner or on a edge, do a wrap-round just like you did in Conway's Life. If a Conway Merkle exits to the right, it reappears on the left, and if it exits at top, it reappears on the bottom.” Bugsy had grabbed an old Life program and modified it. Bugsy might not get his code right the first time, but he codes fast! He says he is “agile” or “extreme” or whatever is cool this week for fast and sloppy. Now, for the happiness rule: A Merkle is happy only if its four neighbors (this is called an Ulam neighborhood) include at least (n) Merkles of his own color. Any two unhappy Merkles can swap, if they both increase or maintain their happiness. "There is no cost to moving, no restrictive covenants, no neighborhood associativity or other examples of nosy neighbors running your life,” snarled Melvin. “This is a pure abstract model.” Nobody wanted to hear Melvin's 45 minute rant about the “Lawn Nazi” in his subdivision who was measuring the height of Mel's grass when Satan, Mel's Doberman Pincher, mistook the man's ruler for a stick and came out to play with the stranger in his yard. That is Mel's version of what happened. Satan “plays” very hard with strange people in his yard; Mel has cellphone video that nobody wants to see again. But I digress. In Merklevill, very quickly, Red Merkles gravitate to solid red neighborhood, and Blue Merkles gravitate to solid blue neighborhood. Once the neighborhoods are established, the border between the districts shifts a little as Red Merkles and blue Merkles jockey to move away from the boundary. “So could we start with 'colorists' Merkles that want an (n = 4) neighborhood?” asked Jane. “Yep!” said Melvin. “But it does not matter. No two runs begin from the same random starting settlement or make the same random swaps, and the Merkle's moves affect every subsequent swap, no two runs are alike.” Bugsy was adding some extra touches to his program, when he said: “Okay, I can program perfectly tolerant Merkles who seek (n <= 2) neighbors of his own color. The Department of Housing and Urban Development's magical population of Merkles who are free of any desire for segregation and discrimination. They seek an integrated neighborhood, half red, half blue. My Merkles have been forced by me to seek mathematically pure diversity! ” Melvin smiled, “Run the program. The individual preferences of your Merkles will produce a collective outcome indistinguishable from a colorist housing policy. The differences are the speed that it takes to get to the segregation.” “Damn!” said Jane. “How does it work?” “You get discernible colored clusters, then the boundaries harden. The Merkles would be perfectly happy to be in the minority; they want only to avoid being completely alone.” said Mel. -”That is all it takes!”
Dear Reader: Write a program that simulates Merkleville. Play with values of (n) and different happiness rules for Red and Blue Merkles. If you've not already met experienced developer Melvin Frammis and his junior programmer sidekick, Bugsy Cottman you'll find they were initially introduced in the Elevator Puzzle, the first in Joe Celko's series of Sharpen Your Coding Skills and they have posed us further challenges ever since: Programmer Puzzle - Hermit Boxes Jigsaw Puzzles and The MacMahon Squares Vertex Coverings And The Cool Kids Problem
If you want to send in solutions to any of them either use the Comments section or email editor@i-programmer.info.
Joe Celko is best known as the database expert who writes books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code. To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@i-programmer.info |
