Tuesday, March 22, 2011

The pricing dilemma

There is a fair bit of talk on the pricing of things, self-publishing. In pretty much every entertainment industry from games, books, music to movies.

In some areas there are the great perceived villains, be they the RCAA/publishers or the software pirates(depending on which side one may be on). Then there are the products themselves.

Recently with shakeups from self-publishing, and bands releasing albums for donations or movies being released to bittorrent officially, things are clearly changing. For the consumer this certainly seems to be for the better. I really want to believe this is the case but somewhere down in my mind I have a niggling feel that SOMETHING is wrong.

Let me elaborate. Today I read this blog http://jakonrath.blogspot.com/2011/03/ebooks-and-self-publishing-dialog.html regarding self-publishing and cutting the costs of books down. I also read this little entry http://2dboy.com/2011/02/08/ipad-launch/ which basically details how charging less made them more.

Undercutting?
This isn't really all that complicated a concept, nor is it advanced. As far as I can see, it is plain old undercutting. It is economically viable so long as others aren't also doing it since it places the undercutter at a significant price advantage, which can clearly push a lot more sales.

but what happens when others follow suit?
Some people buy both games for the price they might have used for just one of them a bit earlier.
Others will likely still only buy the product they wanted as the monetary cost was never a disincentive.

Still, more product should be bought... Probably. And the developers cut of profits should be significantly greater, always a good thing.

Market glut
I'd say there are at least three buying models for various people.
- Those that budget entertainment purchases based on disposable income and will inevitably spend to that limit, choosing the best perceived value they can.
- Those that budget the amount of time they will spend on entertainment, that are not overly affected by the cost so long as it is not ridiculous.
- Those that have no particular budgetary concerns and simply buy anything beyond a perceived value threshold.

Now of these three, I see the first group buying around the same amount of stuff, as they still have the same maximum budget. So undercutting will only displace spending between various people.
The second group was never overly concerned about the pricing, and thus will spend less as they are more time limited than anything else. I myself probably belong to this group so I may be overestimating their numbers?
The third group is the only one likely to increase spending as more items past their cost/performance threshold are available with a decrease in cost.

A lot of people will be able to get all the "entertainment" they need at a lower total cost, and will then shift their extra spending to other sectors, be they larger houses, food, whatever. Great for consumers so far.

Consequences

Some of the entertainment industries are already pretty tough competition with many artists/authors more or less doing it out of their love for the subject matter. The vast majority of actors are doing poorly with a small minority at the top, and the games industry is notorious for crunch hours and working conditions that could at best be considered "poor" compared to other IT sectors. And this could likely make it worse.

If lowered prices were to result in a market glut where the new standard for sales is priced to sell loads, but everyone follows suit, more people will move to the time limited sector and the initially artificially inflated numbers will deflate somewhere between their starting point and inflated point, with sales going down. With a perception of "xyz should only cost this much", returning to the old model can't happen, and the only way to go is to decrease production values, resulting in shoddy product.

What I'm getting at
I'm inevitably going to be a minority here, but I do rather enjoy games, and I like good games with a lot of effort put into them. While I got a few train rides of entertainment from world of goo and angry birds, they have hardly captivated me in the way recent great games like fallout, baldurs gate, gta3 and whatnot have done.

I just don't want the competition to kill off innovation entirely, and hope I'm not the only one that feels this way. Only time will tell how this goes

Saturday, February 5, 2011

The nature of human sorting

Been revising/learning from the text Introduction to Algorithms lately.

As many books seem to do it explains insertion sort by the example of a hand of cards, where as you get each card, you place it into the appropriate place. This is a good use of insertion sort because there is little overhead as any hand is bound to be rather small, finding the correct location will be fast.

This brought me to thinking how I have in the past sorted other things. Such as my music collection or magazines.

Looking back, it certainly hasn't been anything like insertion sort. I would generally pull a load of cds out of my rack, then separate them into piles by either name or genre, then sort out each pile. If it was larger I may have split it again, and after that point, sorted them by insertion sort. Sounds a lot like an optimised quicksort with an insertion sort for n<x. Of course instead of splitting at each stage into 2 piles I would split into a number of piles that I intuitively felt would make sense(eg piles of a-f, g-k, l-r, s-z).

Reexamining this has been quite interesting and I guess I should be happy with myself for using an efficient sorting algorithm for my cds. It should be interesting to examine in what other ways these algorithms are reflected in things people naturally do. When we solve mazes do we mentally solve them as a computer would(e.g as a graphing problem)? A lot of these algorithms have some pretty strong parallels in normal intelligent behavior yet it can be quite hard to pick up on initially in a book.

Wednesday, November 10, 2010

Do not track... the end of free services?

NyTimes put up an article about the ongoing attempts to improve online privacy.

Welp. While in principle I think that privacy is important, and people have a right to it, I don't think people are going to like the alternative.

Google, yahoo, facebook, all those service people use for free and love, are supported by advertising. Targeted advertising even. And that only works because of some amount of user tracking.

So, what will happen if/when tracking becomes impossible thanks to mandatory "do not track" buttons? These companies providing the services need to switch to another revenue model. With tracking out of the window, monetising data is out of the question. As is targetted advertising... So we're left with primitive advertising(and more ad coverage on pages to cover for lower rates!?), or for pay services.

Is this helping anyone? I don't think so.

There are already ways to disable tracking. Disable your cookies, disable flash cookies/datastore. But this isn't really a place government should in any way be getting involved with. Increased consumer awareness could be good. Allow them to choose. People who are comfortable with being tracked in exchange for a service can continue, and people who would prefer to pay for the service can go ahead in peace. Simply removing tracking as an option altogether is just a good way to kill off free services.

Monday, November 1, 2010

Be part of the problem, or the solution

Well, I'm still alive.

I've just decided that unless I'm actually going to write an opinionated rant about something it's not going to be very interesting so I'm not really updating about whatever latest book I've read or am reading(though "The elements of computing systems" is awesome so far!)

Anyway, today, a little bit of a rant.

I *hate* Shift-JIS.

We're in the era of unicode now, or at least should be. It can represent any character you can think of, is fully ascii compatible, well supported in all development API's, and yet so many places are still using ancient artifacts from the past.

I work at a Japanese company so unfortunately, I have to deal with Shift-JIS and EUC-JP a lot. Generally in the context of turning them into UTF-8. Whether it's taking search queries and figuring out their encoding or dealing with buggy source code because someone thought it would be a good idea to mix encodings in varying source files, encodings other than unicode upset me a lot.

Apparently some big shops still haven't entered the modern era either. Try loading a UTF-8 encoded csv file with japanese in it into excel.

Garbage!

Thanks Microsoft. It's kind of sad because overall excel is a good product. Anyway, OpenOffice(or LibreOffice now that a lot of the devs ran from oracle) loads em great. And it gives you an option to select encoding if you do decide to use one of this dinosaur age encodings(I'm sure there's a setting for this somewhere but I don't use excel anymore and the people that reported the problem to me couldn't find one, which means neither will the vast majority of users).

So, when our software puts out CSV files for customers, how do we encode them?

In Shift-JIS. It makes me hurt. But what can we do when the vast majority of people use Excel? What does one do in a situation like this?

Tuesday, September 21, 2010

Google DevQuiz, the shiritori problem

 So, I mentioned I'd have a look at the dev quiz problems and I'm going to have a quick look over one of them.

 The problem in question is playing "Shiritori" against their server using a limited dictionary. First one to be unable to respond loses.
  As I'm sure most non-japanese readers are not familiar with the game, it is a simple word association game. The next word you respond with must begin with the same later the previous word ended with, so one might go:

Apple->elephant->tower->rat->...

No word may be repeated twice and if you can't respond, you lose.

The game is generally delineated by a subject such as sports or famous people or whatever... In the case of google, the limiting set would be a limited dictionary that you and the server share. Here is the set from the easy(trivial exercise).

psouvqk  <- start word
khbpmr
kozljf
krgauzfzlgm
kkfria
rdqbrwyvbf
rzsllm
fcdpksoc
feeesamqti
fmxfwtqa
fdqyteakd
cudyi
cfaxwprqywu
czeltzvu
iapjqat
isttjds
isexgjyllo
tejubs
tkjkxecsw
sfdezjjxj
shdlkdsjpb
slpbtiox
jvhgdyvb
jlumkmgl
jcsfqql
jsvknhxwbjh
bpddtv
bhtkvcuph
vzlocep
mdnjqve
elfduspou
utvptuuukqz
zzlrtwetw
wsoguy
wwgcgqwxo
yyfofqglzvj
ybiyodwxysl
llottukq
qsgmdelg
gucmqmkiarn
anmxhykbad
djyicuzu
ooxkbyzdxh
hiodhnmqox
xdisedp
pauopwwan

This one could actually be solved with a piece of paper as the branching is very limited. Most words are directly connected to the next one. Of course writing code from the start to solve it is reusable in the harder questions.

The next one is not nice if you try to trace the possible paths on paper.

cjunqesksk
kabeoppnt
gihcboqk
cjorrhkg
ntzptexc
dgmizn
mwsgd
trpiqowsm
kkqarpan
gkyzgbfd
cvhrlkmwpm
njprgqt
dxeheowsk
msmtvrg
tdrygvhxc
kbscviwmdpd
gzqwm
cddemqxfvgt
nrfavlpwock
djtswyfksg
mpescdobc
tocztzehxn

Less words! But much more branching... There was actually a trend of a single "end-game" that if succesfully entered you could work it in paper perhaps but the whole thing was begging for a read-ahead program.

I'm going to spare the detail, but by implementing a dictionary to store the remaining words, and then running a recursive algorithm to check whether each path is "alive", one can simply pick the live paths all the way until the opponent loses. With this word set it is still doable without any pattern analysis or serious optimisation. I still used C++ as I imagined the next stage could be more demanding and require expanding on my current work(it did).

Anyway, here's the core classes pulled from the header files:


class Game {
private:
 Dictionary legalWords;  /* list of legal words that haven't been used */
 vector<string> usedWords; /* list of words that have been used */

 int turn;     /* turn counter used to determine player or ai turn */

 void useWord(string word);

 void undoLast();
 int isComputerTurn();
 int isChoiceAlive(string choice, int steps);
public:
 Game();
 void startGame();
 void displayTurn();
 int selectNext(vector<string> choiceList);
};

class Dictionary {
private:
 list<string> words[ALPH_LIST_NO];
 int names;

 string firstWord;
public:
 /*
  Construct the dictionary from a file
 */
 Dictionary(char * filename);

 Dictionary() {
  names = 0;
 }

 /*
  Loads all names from a file, returning the number read,
  or 0 for a failure
 */
 int loadFromFile(char * filename);

 /*
  Display the contents of the dictionary
 */
 void displayContents();

 int addWord(string word);
 int removeWord(string word);

 /*
  Return the first word for empty strings
 */
 vector<string> getPossibleNext(string cur);
};


The important part of the code is really the bit about checking whether a choice is alive. The rest is just trivial implementation.

/**
 Recursively check whether a specific choice can be used safely
 Any case where there is a set of choices by the ai that can lead to
 game over means the choice is dead.
 The function simulates actual play, trying each path. 
 For player turns any subpath means the path is alive
 For ai turns any subpatch being dead means the path is dead
*/
int Game::isChoiceAlive(string choice, int steps) {
 if(steps <= 0) {
  return 1;
 }

 useWord(choice);
 steps--;


 vector<string> nextWords = legalWords.getPossibleNext(choice);
  
 int result = 1;
 if(isComputerTurn()) {
  if(nextWords.size() == 0) {
//   DEBUG("ran out of words at: " << choice);

   result = 1;
  } else if(choice[0] == 'x' || choice[0] == 'k' || choice[0] == 'b') {
   // h leads to a dead loop
   
   result = 1;
  } else {

   vector<string>::iterator it;
   // check all words. on the computers turn if any choice is dead
   // we assume the computer will pick it and thus lead to a dead end
   for(it = nextWords.begin(); it != nextWords.end(); it++) {
    if(!isChoiceAlive(*it, steps)) {
     result = 0;
          
     break;
    }
   }
  }
 } else {
  if(nextWords.size() == 0) {
   // no player choices so game over
//   DEBUG("ran out of words at: " << choice << "\n");
   result = 0;
   DEBUG("Player ran out of words\n");
  } else {

   vector<string>::iterator it;
   // default to failure
   result = 0;

   for(it = nextWords.begin(); it != nextWords.end(); it++) {
    if(isChoiceAlive(*it, steps)) {
     result = 1;
     break;
    }
   }
  }
 }

 undoLast();
 return result;
}

One will note that this works by recursively calling itself until a path is determined to either by alive(1) or dead(0). This depends on whose turn it is. For the player choice so long as one sub-path is alive, the whole path is alive. On the other hand on the servers turn, one path that results in a dead player is a dead path(since we assume the server plays a perfect game, which it probably does). To restore the state of the dictionary, any items popped out of the dictionary(with useWord) are returned back to it using undoLast().

This results in an elegant solution to the problem. It certainly could use some optimizations but it returns a response to each server move very quickly so such are not necessary. I would be curious to benchmark the Visual Studio STL implementationfor this purpose.

The final question signficantly extends the number of words:

zjfurojiwt
tpenjyluge
txxkygwaqgv
ttloiso
exsosv
edmpo
ejvzpaf
vgaxvtbzo
vzgcsrihdof
vfqkkfefsz
orxbf
ocsbkecrutz
oiuvsvdzny
fmualz
fttay
fjlin
zxqry
zwlhuaavn
zbfbu
yzkhgqjwn
ylapbgu
yztpihmont
nmmeycwxu
nvchbixbft
nhube
uvokit
ulrsdme
ullkbwv
tqgbupfbx
xbxaj
xqkfbyg
xlsjah
euxgwijb
bygjlosw
buoqdwoeda
bltxp
vtvbiphxlk
kbucm
kvpbutfxnci
kpiidygnc
oqcfhx
fcnylfqb
zhptjfbk
ywhozx
nuceayubb
uornsk
jwkcw
jtebgzhijgm
jiyeziidgeg
jhdgofa
jkqvxudtkpi
jvdfqjh
jpsbykp
jymncyc
jeuawoyqfeq
jxwdyctpbr
jtkius
wyehnlfcewj
wvwnxm
wkwpoxug
wauwusmlca
wbvheei
wrvuppgxeh
wqpdckip
wuearboc
wpixxq
wgysr
waegpptsls
myrjybpaj
miksbvyrpw
mgbidg
mrzowglfa
mncqxmi
mqkxjtcnrhh
mymuttlap
muzynhc
mmgkyupq
mhvcustr
mgyxalfjoks
grfnkukj
grvpecw
glafmam
gkktjoquda
gxcumli
gnojpqlfwh
gcykxbcp
gfukbmc
grrnxq
gmadnr
gkeeyspumss
awwgeyfvj
axcvtmpsw
arcjpzm
azpqqvg
aakhi
acxurh
agiaariapp
ajzlurevxyc
akvsq
acnzqsglor
alvilkvzvs
ipsyrchhmwj
iqpgfhzzw
icypxogrm
ibcytxveblg
iatrdra
izgujgoph
iknbjgp
icewc
inbfvdmq
intkzlyeer
ibqnfshys
hkpuj
hspyw
hvkom
hsrewtg
hxxfa
huozi
htihddyp
hkumyc
hfaadvq
hkzmvdcxr
hvtfs
pesyj
pzqdepzw
ptybxgm
pahfbcdtg
ppnhzyspa
phfqjdxybi
psmkslfah
pagszdvdc
petdq
ptgevrrebr
pcdbqtls
cfzfmjhj
czczzhaxw
cgbpozgm
cwctwg
cyfamuchyaa
cxxqydweki
cwnzkiah
ccactp
cbylbq
chogthyr
cswakbs
qpslvrrgnj
qltanybow
qtqpmximzwm
qhkbwlig
qgmyza
qkvozmngii
qjdqvh
qfdntswgjfp
qujuqkczgrc
qjbrsxwcjhr
qkajthhs
rqgvj
rmbcwvenyw
rwiuwlulm
rplfg
rikfpsra
rrjfki
rkinlvh
raditmwbp
rabaxvlzoc
ryzzijueq
rxtwzcs
svosgyukelj
suvjdw
szfizfvlem
scwyaooag
syrfklha
scnyeai
slwhbymh
shsguslpxpp
sskxiec
srzgnsoooq
svmgiir
qasspaquyt
qzptilhpgyo
qauxwqly
rvwse
rjrnhyvdf
rjuvgruzpn
sptgdchfahv
sssuuafpiz
skhsmu

Trying to simply run through the massive number of choices is going to take a long, long time. I initially tried to solve this by compromising and figuring that the server may only be looking a number of steps ahead so optimised my own code and got it to look around 8-10 ahead(I can't remember at this time). This wasn't sufficient, but I noticed losing patterns would lead into a back and forth where the opponent keeps sending the same letter back to you.
On examination you can find there are one more words that end with certain letters than those that begin with them. Thus if one can force the computer to select one of these words, a path can be considered "alive". This reduces a huge amount of branching, and in fact is enough to allow a full simulation, and the final 6 points for the question. The edit to isChoiceAlive is quite simple, note the "if(choice[0] == 'k' || ... ) code.

int Game::isChoiceAlive(string choice, int steps) {
 if(steps <= 0) {
  return 1;
 }

 useWord(choice);
 steps--;


 vector<string> nextWords = legalWords.getPossibleNext(choice);
  
 int result = 1;
 if(isComputerTurn()) {
  if(nextWords.size() == 0) {
//   DEBUG("ran out of words at: " << choice);

   result = 1;
  } else if(choice[0] == 'x' || choice[0] == 'k' || choice[0] == 'b') {
   // h leads to a dead loop
   
   result = 1;
  } else {

   vector<string>::iterator it;
   // check all words. on the computers turn if any choice is dead
   // we assume the computer will pick it and thus lead to a dead end
   for(it = nextWords.begin(); it != nextWords.end(); it++) {
    if(!isChoiceAlive(*it, steps)) {
     result = 0;
          
     break;
    }
   }
  }
 } else {
  if(nextWords.size() == 0) {
   // no player choices so game over
//   DEBUG("ran out of words at: " << choice << "\n");
   result = 0;
   DEBUG("Player ran out of words\n");
  } else if(choice[0] == 'x' || choice[0] == 'k' || choice[0] == 'b') {
   // h leads to a dead loop
   
   result = 0;
  } else {

   vector<string>::iterator it;
   // default to failure
   result = 0;

   for(it = nextWords.begin(); it != nextWords.end(); it++) {
    if(isChoiceAlive(*it, steps)) {
     result = 1;
     break;
    }
   }
  }
 }

 undoLast();
 return result;

Sunday, September 5, 2010

Concrete mathematics

 Got the results in from the DevQuiz. All appears to be correct and I've got a place, woo! I'm in two minds about the difficulty of the questions. On one hand, they were challenging enough to make one think, but I don't think that they were overall "hard" even for the final questions, as I could still get away with fairly generic programs. On the other hand it did take a fair amount of time to do all the questions... I hope developer day is awesome and worth the time spent on the questions

 That aside, I picked up Concrete Mathematics a couple of days along with The Art of  Computer Programming.   I don't imagine I'll have the time to read the latter for a while, but I've started poking through Concrete Mathematics(yeah I'll get back to sicp eventually. Too many books, too little time). I really like how they've added in the student "graffiti". Some of it is very helpful in grasping a concept and other parts keep the text interesting even if they aren't directly useful. It's been a while since I've had to do some serious math (I guess a few of the questions in part 1 of sicp count), so it's got my brain going for a ride, but it's interesting stuff, and I still love to see a formula come together in an elegant manner. Not gotten far in yet, but definitely recommended for those interested.

Thursday, August 26, 2010

Recent activity: Google DevQuiz and why you probably shouldn't use Visual C++

 Google Developer Day Tokyo is on end of September.

 After previous years where signup was first come first served, this year they're filtering people by using a "developer quiz". Seems a reasonable enough move to make. I've noticed a few people who are interested in going just for the prospect of a chance at a "free phone" since there is some speculation they'll be giving away an android handset again this year(If I'm not mistaken they already gave them out at this years I/O).

 Despite starting early, and getting the first half done well before the deadline, I got distracted by other things for a while and ended up doing the remaining half in the last day. Got all my solutions in, and at least according to the automated grader I cleared all the problems successfully. I can only hope that I don't lose  points for bad code or something(because my "test of concept" prototype ended up getting hacked into my final solution...). I'll probably throw up some of the code here later with light commentary.

 Unfortunately I lost a fair bit of time to poor problem comprehension as they were stated only in Japanese. I'm quite comfortable with it, but considering there's a reasonable amount of English speakers participating, it would have been nice to have English version of the questions.

 Since I was doing my work on a pc I don't normally use for development, I thought I'd give Visual C++ a go for old times sake(when I was doing a lot of DirectX/Win32 programming at university)... See how it was now.

 Unfortunately I was rather disappointed. While IDE's like eclipse have come ahead leaps and bounds, Visual C++(or at least the express edition) is slow and clumsy. Often for apparently no good reason it would just slow down, and syntax checking and highlighting is terribly buggy. While it is the express edition with a cut-down feature set, I don't think that "adding bugs" is the same as feature cuts. I used to have a lot of appreciation for Visual Studio as one of the better Microsoft products, but right now it does little to please and much to annoy.

 On a final note, I recently picked up "Lions' Commentary on UNIX 6th Edition". I've only just gotten started on it, but it's a real trip to the past. The old school(pre-ANSI) C is a real shocker, and having to learn PDP-11 assembly is a bit of an irritation, but what I've read so far has been interesting and educating.