A continuation of yesterday’s read - Dawn of a revolution by Walter Isaacson from September 20, 2013 - I wanted to experience how Bill Gates worked on the Altair BASIC back in 1973 when he wrote it with a felt-point pens, yellow legal pad paper, and presumably something like the ed text editor on a PDP-10.
For the actual programming problem at hand I used CodeForces 4B. To summarize:
- Given: we have N+1 lines of integer tuples - we’ll read them from stdout - we are given
- on line 1: number of days (
N) and total number of hours on line 1 - on lines 2 through N+1: min and max hours for each day
- on line 1: number of days (
- Find: we need to answer YES/NO (stdout) whether it is possible to create a schedule for the N days, which commits some number of hours every day between the min and max for each day given, where the total number of hours would equal the total number of hours from line 1
- Example:
- Input
2 5
0 1
3 5
- Output (the solution our binary would output):
YES
1 4
Reasons for choosing this particular programming assignment - it needed to require just enough amount of code to fit on a page. Writing a reverse proxy with ed may be too much. And yet writing Hello World or 2+2 is too boring to even begin.
A professional software engineering approach to this problem was the wrong start for this problem and a solution on ed or paper. Writing readable, testable, easy to understand code, with some abstractions is difficult in ed. But it was also it was deemed too slow per the CodeForces online judge.
Too Much Code
The more something is abstracted - the more jumping around is required. ed itself is meant for limited environment, with slow connectivity. Browsing through large source repos is extra hard with ed. LSP and/or ctags could help but that seems orthogonal to our deliberately constraint environment of using ed only.
Too Slow
When I write code at work I tend to create a lot of functions/methods etc. Each one ideally has a self-explanatory name and encapsulates some well-abstracted chunk of work to be done. In competitive programming this often is an anti-pattern. The professional programming anti-patterns are the pattern. One should strive for almost code-golf level of brevity. This seems to be true especially when coding in constraint text editors such as ed.
Writing on Paper!!
Writing code on paper is actually liberating. I allow myself to write code that almost compiles. There is no syntax highlighting and no error
underlining mechanisms. The permanence of the pen made me think twice before I committed a line to paper. Using lines to suggest moving blocks of code around was messy, but was helpful for testing visuospacial portion of this exercise. Turns out - I personally find it helpful to locate chunks of code in physical space on paper. At some point I thought I could start “programming with scissors” inspired by how John McPhee writes.
- felt-tip pen exercise was not so pleasant at all. Not sure what Bill Gates was thinking writing Altair BASIC with think-leaky primitives. I’d much rather use sharpened pencils. Perhaps he enjoyed coloring various sections of code? I wish a picture of his yellow legal pads was preserved in museum somewhere (definitely would be a great fit for the Computer History Museum).
- there is no copy/paste on paper - so we resort to drawing lines and referencing other chunks of paper. This is where I thought about using the scissors method of programming.
Fixing bugs with ed
It definitely takes some getting used to. The following commands became my best friends:
,n- show me the entire file with numbered lines (final version has 26 lines before the block of commentary - with lots of code golf so it fits in as few lines as readably possible)15s/>maxs/>=maxs/g- editing text using regular expressions is fun - you have to think about the change ahead of timeg/studyPlan/n- find all lines that contain studyPlan and show them with numbersg/studyPlan/s//plan/g- find all lines that contain studyPlan and replace studyPlan with planwwrite the filea- append a line - and don’t forget to end the appending with.then savewu- undo came in handy a few times when a regex went wrong10t3- copy line 10 to 3 - turns out t is copy, becausecis changec- change aline - more likerewritea line3m1- move line 3 to line 110d- delete line 10 - this was happy when I accidentally ended up appending ed commands to the source code (afollowed by a line followed bywactually appendsw; one has to.on a line by itself to end appending and then once in command mode -wto save).- end entry/append/change modeq- quit
The final code - good enough to pass the online judge:
#include "iostream"
using namespace std;
/* Solving 4B was done using pen+paper and then ed the standard editor */
/* This suffering was deliberate - to experience how things were done */
/* in 1974 when Bill Gates wrote Altair BASIC on a yellow legal pad */
/* using felt-tip pens. The code was transferred by Gates to a PDP-10 */
/* and then via punch-tape was taken to MITS in Albuquerque,NM by Paul */
/* Allen in 1975. */
int main() {
bool debug=false;
int days; int total; cin >> days >> total;
int maxs[days]; int plan[days];
for(int i=0; i<days; i++) cin >> plan[i] >> maxs[i];
int today=-1; bool done=false; int suma=0;
bool maxedOut=false;
if(days<=0) {cout << "days=" << days << " does not make sense" << endl; done=true; return 1; }
for(int i=0; i<days; i++) suma+=plan[i]; /* init the running sum */
while(!done) {
today++; if(today>=days) today=0;
if(plan[today]>=maxs[today]) {if(today==0) maxedOut=true; else maxedOut=maxedOut && true;}
else { plan[today]++; suma++; }
if(debug){ /* show some extra stuff - will break CodeForces Online Judge */
cout << "today=" << today << " suma=" << suma << " total=" << total;
cout << " max=" << maxs[today] << " maxedOut=" << maxedOut << " days=" << days << " ";
cout << " - "; for(int i=0; i<days; i++) cout << plan[i] << " "; cout << endl;
}
if(suma>=total) done=true;
else done=today == days-1 && maxedOut;
}
if (suma==total) {cout << "YES" << endl; for(int i=0; i<days; i++) cout << plan[i] << " "; cout << endl; }
else cout << "NO" << endl;
}