Consider a variation of the Stable Marriage Problem in which a participant only ranks some of the potential partners. Others not ranked are not considered for matching; the person would rather remain single than be matched with those he or she did not rank.
What is an algorithm to maximize the number of matches? Is this the "best" optimality criterion? I'm guessing game theoretic strategic behavior becomes relevant.
ASCII has 10 characters with narrow glyphs on proportional fonts. Perhaps useful as a dense representation of digits.
. , ' : ; | I i l !
Here are a few from Unicode. There are likely many more.
¡ ‘ ’ ‚ ‛
Here are a few more ASCII characters that are sort of narrow.
1 ( ) [ ] { }
ASCII has 32 punctuation characters. Perhaps useful for an encoding of binary that looks like line noise.
`-=[]\;' ,./~!@#$%^&*()_+ {}|:"<>?
Pessimistically, we can look at Unicode and mourn the thwartage of communication and ideas imposed by the lack of certain punctuation (Sapir-Whorf). The irony mark and the interrobang come to mind.
Optimistically, we can say we got more punctuation than we really needed, including weird characters like @ and ^. Here, in my opinion, are the 12 essential punctuation marks for English:
-;',./!*():?
Notably omitting double quotes, which can be written as two single quotes, and the dollar sign which can be written USD.
Including the asterisk, needed for section breaks and bullet points, functionally important for organizing text.
Plus space, newline, escape. 26+12+3=41. Plus 10 if digits.
Consider a Haskell extension providing this function:
compileTimeAnalyze :: (Code -> IO ()) -> a -> a
"compileTypeAnalyze f e" passes to user-defined function "f" the parse tree (and any other useful information such as types and symbol table) of the expression "e" and evaluates "f" at compile time. At run time, it simply evaluates "e".
The likely use is to emit warnings or errors if there is something domain-specifically wrong with the code that the compiler might not detect.
Inspired by debugging 2D graphics code. We often want the number of references to some X coordinate be the same as the number to the corresponding Y coordinate, or else there is likely a typo where we typed X instead of Y or vice versa.
We probably also want the user to be able to define
compileTimeAnalyzeModule :: Code -> IO()
which gets the entire contents of the module for static analysis. What about static analysis across many modules?
Template Haskell can probably do most of this.
Create a mockumentary about the "serious" problem of endorphin addiction, treating it as if it were an illegal drug like heroin.
People do exhibit addict behavior for their favorite endorphin-releasing activities.
Build a house with lots of concealed passageways and hidden rooms. Who has the knowhow for this kind of architecture and engineering? Is it disappearing? It is knowhow that may (or may not) benefit being kept secret.
Never know when the next Anne Frank might need an Underground Railroad.
The conceptually simple cipher of treating a message as a long number in one base and converting it to a different base does not appear among the historical elementary ciphers (substitution cipher, transposition cipher). Presumably it is because, using naive algorithms, radix conversion requires work quadratic in the length if the message (though it can be improved with divide and conquer). What sort of cryptanalytic techniques would work on it?
Change from base 37 (letters numbers space) to base 10, apply transposition cipher, change to base 26. Are certain pairs of bases more secure? I'm guessing relatively prime. Obviously converting from say base 100 to base 10 offers no security.
Was it ever tried as an early electro-mechanical cipher?
The numeral 0 is decimal 48 in ASCII, so encode base 100 with unsigned char values 48-147, achieving 2x better text compression compared to base 10 digits as text.
Solution in search of a problem.
Create a filesystem backed by files in other filesystems. However, unlike the simple way of allocating a single file and creating and mounting loopback a filesystem within it, let this be backed by multiple files, likely files in several different filesystems mounted within a single directory structure.
The motivation was starting with a bunch of partitions with a little bit of free space in each, wanting to combine all the free space to create the illusion of a single directory with lots of free space.
In addition, let the size of the inner filesystem not need to be chosen a constant at the time of creation. Instead, the space available is simply the sum of the space available in the outer filesystems.
View a list data structure as a filesystem. Running 'ls' gives the files numbered 0, 1, ... Or in base 256 depending on what options it was mounted. Variable word size, or maybe constant.
Seemingly fantastic waste of resources: every byte is a separate file. (Or word, or line, or record...)
Peace and love are not two distinct concepts but one and the same. Those who think they see peace but not love with it are not actually seeing peace.
Inspired by a Peace Love ___ symbols T-shirt.
The traditional scientific method mantra goes, theories or hypotheses can only be disproven, not proven.
However, if we include the ever-present possibility of experimental error (in every replicated experiment purporting to disprove it), theories can never be disproven for certainty, either.
"Everything is probabilities" is a worldview philosophically opposed to the scientific method. Though in practice, compatible and very helpful.
Inspired by Jenny McCarthy's disproven "vaccinations cause autism".
Devise a selfmate in 1 chess position which also maximizes the number of direct mate in 1 moves available. You had many ways to win, but you picked the one move that loses: not just loses, but forces your opponent to win.
However, the worst possible move in chess is to resign after giving checkmate, perhaps not realizing you had won. Devise a vaguely realistic position that that might happen: perhaps a forced move giving a distant discovered checkmate (so perhaps the previous position was a selfmate in 1), which, if it could be ignored, the checkmated player could quickly regain an overwhelming advantage.
This was on a freshly installed and dist-updated i386 Ubuntu 12.10 Quantal Quetzal .
apt-get install --no-install-recommends xmonad libghc-xmonad-contrib-dev gnome-panel indicator-applet-complete indicator-multiload
indicator-multiload is optional, but I like it.
~/.xmonad/xmonad.hs:
import XMonad import XMonad.Config.Gnome main=xmonad gnomeConfig
Logout, the choose the "GNOME with Xmonad" login option available above and to the right of the password field. indicator-multiload fails to start on its own at first. Run it from the command line. It will start correctly, automatically, on future logins.
These instructions also seem to work on Ubuntu 13.04 Raring Ringtail i386.
A standard chess problem format is Mate in N. Mate in N+1 is not considered a solution.
The dual problem type is to avoid mate in N, successfully solving the problem even if the opponent can inflict mate in N+1.
Practice your defensive tactics.
Automatically generate good problems of this form where the key defending moves are not "obvious".
Create a computer program which will defend chess problems, e.g., mate in N, against you, making sure to make you play against all possible defenses.
This could be done with a database stored with the problem, but also could be assisted by a chess engine which "compresses" the database; don't need to store moves that an engine will discover.
This has almost certainly already been done. The interesting aspect is that a medium much, much smarter than paper (the old way of distributing chess problems) significantly adds to the enjoyability and accessibility of an old art form.
Tsumego for go 囲碁
For each position of a chess game, compute the number of moves, or proportion of moves, that do not lead to being checkmated. Probably done by computers with MultiPV, but humans can help, too. Depict that value over the course of a game.
Artistically attempts to capture the riskiness of a position. Perhaps icons walking across a "floor" with thickness. Probably also want to include moves which are very negative but the computer hasn't found mate: Order moves top to bottom strongest to weakest and the color the opacity of the floor by the evaluation score.
The level of the floor could indicate current position evaluation, with "falls" for bad moves.
We can also speculate the future of a game in progress; the riskiness of the next several moves assuming optimal(ish) play.
Search for chess positions for which the computer evaluation radically changes depending on the depth of search. Classify each by tactical motif in hopes of developing heuristics of when to search deeper. All automatically.
Create a 120-sided disdyakis triacontahedral die as the sphere-like die with the largest number of faces. Anything larger is either cylindricalish or not elegant. 120 has many divisors, so it can be used to generate smaller random numbers.
In practice, it will probably too easily roll off the surface and is too difficult to manufacture without bias.
It is curious that 120 is a little less than perfect powers 11^2=121, 5^3=125 and 2^7=128, or even more curiously expressable as a difference of perfect powers of the same base: 120 = 11^2-11^0 = 5^3-5^1 = 2^7-2^3
What would the earth be like if one side constantly faced the sun?
In particular, how effectively would the oceans and atmosphere redistribute heat? What longitude and what season should face the sun for best redistribution?
What if we had a different arrangement of continents?
What if we had deeper oceans or thicker atmosphere?
Water curiously expands when it freezes into ice. Can we extract energy from this effect? I'm imagining a piston driving a linear generator.
How much energy can be extracted? Is it more than the heat of fusion?
If so, we can sort of create a perpetual motion machine by recycling some of the energy to melt the ice. I think it is not actually perpetual motion because it will stop when the cold reservoir is exhausted.
If not, we get a weird high pressure ice with the same density as water. Or perhaps the water refuses to freeze.
Create a robot to set up a Rube Goldberg device. The robot makes thousands of attempts, far more than a human would have patience for, to catch on film the device succeeding once. The robot clears and resets the device after each failure without requiring human intervention. Perhaps it learns from each failure, or it merely makes minute random adjustments each time.
Because the number of attempts can be very large, the device can have very low probability reactions, creating in the viewer the effect of "how'd they do that?"
Unfortunately, this perhaps can be too easily accomplished with special effects these days. Need something outside the reach of special effects.
Inspired by Pythagora Switch.
While it may be fun to listen to a single smart speaker give a polished speech, it might be better for your personal growth to listen to a debate, perhaps structured, between two smart speakers.
In the latter, you have an advocate against sleazy rhetorical techniques a single speaker might use on you.
Need to set up incentives for debaters to win. Develop this into an art form people will willingly watch and listen.
Already sort of done in debate as high school and college competition.
Kind of like chess, with opening theory forged in the heat of combat, ultimately moving forward.
Consider an on screen keyboard that not only provides letters but also common words like "the".
If a user types T H in sequence, the E key becomes disabled, forcing them to backspace and learn the THE shortcut.
An on-screen keyboard displays only a few large buttons, good by Fitts's Law. However, each button is labeled with the many characters, taking advantage of very high pixel density in recent mobile displays.
Pushing a button reveals more large buttons for some of those characters. Most characters are two keystrokes, some three. The positions are constant, allowing the user to touch type rapidly.
Consider an interface which scrolls, but instead of scrolling content off the screen, content near the edge becomes distorted, squished, so the entire content always remains on screen.
The motivation was for a chess GUI on small mobile devices. They have rectangular screens but a chess board is square. We need piece icons that remain recognizable even if distorted. The GUI could be portrait or landscape, so the distortion could be in either direction. Perhaps incorporate color. No such need for go 囲碁 with its very simple pieces.
Will players be able to see their familiar patterns despite the distortion of space? Diagonals become curved.
There probably exist many 2 and 3 character "words" composed of Unicode characters which have yet to be written on the internet according to search engines. (Compare this to the only 676 or 17576 two- or three-character words of English letters.) Possibly applicable to Document ReFinding Key.
Consider a bicycle race in which the organizer provides no infrastructure for measuring times. Each racer is independently responsible for measuring and reporting his or her own time.
Then, when a racer reports a time, the listener must decide whether to trust the racer. We force the issue of trust to be central, bringing in, of course, whether also to trust that the racer is not cheating by using performance enhancing drugs. You can cheat either way; the organizers are not stopping you.
Voluntary signaling mechanisms to cause trust will form, as predicted by the game theory of imperfect information games.
Create a library of documents promoting the concept of Lessig's Free Culture, hopefully all Creative Commons licensed. This thing should be able propagate itself.
Github or something like it? The reason being there may be multiple versions of documents as they get modified and adapted as permitted (encouraged) by some versions of Creative Commons. There is nontrivial librarian task.
Inspired by, although I've written text, wanting a poster or infographic.
Installed Debian Wheezy amd64 on a laptop. Gnome 3 Desktop Environment. So far, so good; essential hardware works: suspend (standby), Ethernet, WiFi.
Used mini.iso on a USB stick with the automatically created second partition for firmware as described in the Installation documentation. It requires a heart stopping leap of faith to be sure you've picked the right drive to cp the image to. Manually download (not apt-get) the required firmware package (which the installer will tell you), dpkg-deb -x to extract it.
No fancy partitioning or dual booting.
Installer tried to write GRUB to the wrong drive, namely the USB installer stick. Worked after going back and manually specifying the target drive. (Switched to a different console, opened a shell, examined where /target was mounted to figure out the right drive.)
Rebooted into system. Added non-free to apt.sources and installed the firmware packages via apt-get. It's kind of confusing how the installer installs a kernel with the right firmware (gathered from the second partition of the USB stick), so it works at first, but will probably fail whenever there is a kernel upgrade.
Does not have Ubuntu's option to encrypt home directories.
Symptom: aptitude full-upgrade says "Untrusted packages could compromise your system's security."
There is no Release.gpg in /var/lib/apt/lists
aptitude update reports "Ign" when attempting to download Release.gpg
I was using the "approx" package cache proxy. Go to the approx server and see that in /var/cache/approx "Release.gpg" is a zero-byte file with 0000 permissions. This is Debian bug 655986.
find . -perm 0000 -type f -exec rm '{}' \;
and the problem is solved.
Interchangeable parts are a wonderful invention, but a great many consumer products have individual parts inaccessible to the consumer, if he or she wants to replace a broken part.
Yet mass produced items have identical parts between items, so it is a perfect opportunity to deploy interchangeable parts.
It seems merely a logistical problem, solvable with technology, for a part to reach the consumer. What forces are causing market failure, if there is?
3D printing can making transferring a part as simple as transferring information about making the part. Mass produced parts almost certainly have specifications that could be easily published.
Perhaps a regulation that manufactured goods needs to be distributed with manufacturing information, kind of like ingredients for food, or source code for software.
Perhaps a strict separation between manufacturer and designer, and the manufacturer must be willing to sell a given part to anyone. Need to figure out how to do intellectual property, especially nowadays protected by trade secrets, but I don't think those problems are insurmountable.
Inspired by two broken wristwatches, too inexpensive to have professionally repaired.
We can see the worst prejudices in people in: who they choose to marry and have children with, who they let their children associate with, and how they act while drunk. Any others?
Measure these things to see what progress we are making in promoting equality in issues such racism, lifting the obscurity of political correctness. I suspect that the actual amount of progress we've made is "not much".
Create a comedy routine in the style of Jeff Foxworthy's "You might be a redneck if", except with the punch line, "then the terrorists have won".
Crowdsource items.
Create a map of a city marking streets which do not have parallel parking along the side of a street, consequently less likely for a bicyclist to be hit by an opening car door or having to unexpectedly swerve into traffic to avoid one.
Inspired by the problem of marking bike lanes next to parallel parking, possibly making bicyclists less safe than if they used the car lane.
Transparency is important to prevent abuse of power. Surely this thought has occurred to many people many times throughout history. Why do we keep forgetting it? It ought to be the first thing anyone thinks about whenever there is a discussion about power.
A problem with komi auction for chess matches is white forcing a draw all remaining games once the desired margin of victory has been clinched.
Is this a fundamental problem with chess?
Should the match be concluded at the point to spare spectators of the remaining silly games? If so, how much more should the komi be adjusted to compensate for this additional white advantage?
Add a large quantity of carbon into a star doing the carbon-nitrogen-oxygen fusion cycle. The additional catalyst accelerates fusion, perhaps with dramatic effect. A large quantity of carbon can be provided by a suitable white dwarf star. Moving it there is left as an exercise for the reader.
White removes a rook from the initial chess position; black removes a knight. Essentially, we are attempting to counterbalance the first move advantage with a handicap of an exchange. Is this fair?
Permit handicap castling with the nonexistent rook?
Get some Chess960-like randomness by randomly choosing which rook and which knight at the beginning of the game. Are some combinations of removals better than others? We can apply it directly to Chess960 to get 3840 possible starting positions or 7680 because color assignments can chosen randomly, too, if both colors actually are equal.
Whenever you see an issue depicted in black and white terms as opposed to shades of gray, be very skeptical; in fact it may be better for you to simply to assume it is a dangerous lie.
Nothing in this world is black and white*, so anyone who is depicting it that way is manipulating the truth for some purpose, perhaps to manipulate you to advance their own goals. Can they be trusted?
Game theoretically, we would then expect the manipulative liars to stop depicting as black and white. This is probably already happening.
*This itself is a black-and-white statement, and yes, I am clearly trying to manipulate you into advancing a goal of skepticism.
Rape, as an abstract economic problem, is about where a property line should be drawn. Should the victim have the right to decide with whom to have sex? Or should a perpetrator have the right to have sex with anyone? Whose property are "your" sex organs?
Apply the Coase Theorem -- the property line does not matter so long as there is one -- and the result at first is absolutely mind boggling: we should be indifferent as to whether society should have a free-for-all permitting rape, or that rape should be punished by the justice system as an encroachment onto the victim's personal body. But there's a catch.
The Coase Theorem assumes there are no transaction costs. However, in the case of sex, contracts to move the property line are forbidden because of the ban on prostitution: the transaction cost is "go to jail", very high. Economically, we have a government regulation causing market failure causing the tremendous social problem of rape, a problem that, on the face of it, seemed to have nothing to do with economics.
A woman has lots of consensual sex. Is this evidence that she is a slut? The rhetorical answer we are looking for is "yes".
A woman has lots of nonconsensual sex, i.e., rape. Is this evidence that she a slut? The rhetorical answer we are looking for is "no".
Suppose you lack information to definitively know whether the sex was consensual or not. Is she a slut? Maybe. And therein lies the problem.
"Maybe" assigns a positive probability to her being a slut, and assuming you are among the great many who feel that being a slut is a bad thing (how would you feel if the label were applied to you or someone you care about?), you have assigned the woman a positive probability of this highly negative label as a result of what may actually have been rape.
Interviews with survivors indicate that the social stigma of becoming labeled a slut, internalized into the feeling that one is an inferior person, is one of the greatest harms of rape. This harm is perpetrated not just by the rapist but also by every single person who believes that being a slut is a bad thing: that's you (with high probability).
Attempting to decrease the harm of rape by focusing on rapists has a feeling of "Blame Canada" to it. We would rather not think that the problem is also ourselves.
Previously, about Rush Limbaugh, and Steubenville.
What mechanisms exist to prevent background checks for gun ownership from become too onerous, violating civil liberties?
What mechanisms exist to prevent the exclusionary criteria against gun ownership from becoming too restrictive, preventing ownership to those who should be permitted? Particularly troubling is using "mental illness" as a criterion, potentially to be abused by classifying opposing political positions as mentally ill.
If anyone fails the background check, let the final decision be made by a dice roll: there is a small probability that gun ownership will be permitted despite failing the background check. Then, follow the applicant to see whether they actually cause harm with their gun to evaluate the accuracy of the background check. Inaccurate criteria should be dropped.
Gun control measures are often politically motivated and implemented without significant effort to measure whether measures are effective and without a mechanism to repeal those which are not. Actually, far more than gun control: all of politics.
A purely quantitative approach is not without its own flaws, perhaps masking deeper problems with society. Gun violence is a result of the war on drugs which is a result of racism. A quantitative approach will only reveal gun violence to be correlated with some politically correct proxy for race.
Can humans learn to read and write, with high facility, a language consisting entirely of numbers? At first, we consider a transliteration of English, reducing all letters, punctuation, whitespace, and font changes to a series of numeric codes.
Somewhat equivalently, a language with a very small written alphabet.
Inspired by the unwieldiness of text input and output especially for mobile devices. Compare the electronic complexity of a seven-segment numeric display versus a pixel display. Instead of adapting technology to human customs, adapt humans to technology.
Deploy a bunch of devices which communicate via radio to synchronize themselves to the same clock. Master-slave would be the obvious set up, but consider making the problem harder by assuming that no one device can "see" all the others. We need a distributed network.
Inspiration was a set of LED party lights which change color in sync. They offer the possibility of communicating with each other by light instead of radio.
Consider QR codes printed on microfilm as a form of durable digital storage. At what resolution should the codes be printed so that they may be reliably scanned in the future?
Is the knowhow for producing microfilm for preservation disappearing?
If you've done many similar things before, trust your gut instinct: it is probably accurate.
If you've never done similar things, your gut is probably full of prejudices, myths, and lies others have told you to manipulate you. It's probably better to adopt an analytical, rational approach for this decision.
