Some Professor Layton Prolog!

Time to combine two of my favorite things: Professor Layton and obscure languages! There was one puzzle (of the hardest difficulty) that I could have spent 40 minutes working out, but instead spent an hour and half solving in Prolog (for those unfamiliar with Prolog, check out this post for a description of what this magic language is!).

I'll post the puzzle and solution here; hopefully someone finds it fun!

No 151 from Professor Layton and the Diabolical Box: Colin's Score

Four students took a test where every question had two possible answers, A or B. Each question was worth 10 points, for a total of 100 points.

The students' test results were posted as seen below, but the teacher forgot to tally Colin's score. Colin was heading to the teacher's office when Mary called him back, saying they could figure out his score using the results from the other tests. Can you figure out Colin's score?

Mary: 70 points

1	2	3	4	5	6	7	8	9	10
B	B	A	B	A	B	B	A	B	B

Dan: 50 points

1	2	3	4	5	6	7	8	9	10
B	A	A	A	B	A	B	A	A	A

Lisa: 30 points

1	2	3	4	5	6	7	8	9	10
B	A	A	A	B	B	B	A	B	A

Colin: ?? points

1	2	3	4	5	6	7	8	9	10
B	B	A	A	A	B	B	A	A	A

-----

Below is the program I wrote to solve it. Verbose by contemporary language standards, but almost no thinking required, and the answer in an instant! Note the original version didn't have so many comments; these are to guide the curious reader. Sadly, github's gists don't know how to color Prolog syntax. Also, due to this terribly lame layout, I would suggest the 'view raw' feature at the bottom of the gist to see it in plaintext glory.



Edit: I also gist-ed my Prolog poker solver, which I wrote about in my first Prolog post. It was my very first prolog, and there are probably shorter ways of doing what I did, but hey! Give it a looksee and hope you enjoy it ^_^

Social Golfer problem

One summer I spent working with a professor, the father of a friend heard my plans and remarked (to my friend, not to me)

I can't think of anything less intellectually stimulating than writing computer code for 7 hours a day.

After some thinking, my guess was they were probably confusing programming with data entry. Moments like these make me realize how much I take computer literacy for granted, especially among older folk. The Supreme Court makes similar mistakes, to much lulz.

I frequently find it helpful then to describe a problem that we work on, since lots of them can be easily described without mathematical notation. One of these has been a real hair-puller these last few days, called the Social Golfer Problem.

Problem Statement

The premise is this: you're organizing a golf tournament with 9 people in it. They play every week in groups of 3, and want to play for three weeks.

Here's the catch: they are social golfers, meaning if possible, they never want to play with the same people twice. Your job is to organize the tournament; you have to arrange who plays with whom every week.

So rather than use names, we'll just use numbers. The first week could look something like this:

	Group 1	Group 2	Group 3
Week 1	1   2   3	4   5   6	7   8   9

Since players 1, 2, and 3 are playing together in the first group, next week you need to organize the tournament a little differently to make sure 1 isn't in a group with 2 or 3, 5 isn't in a group with 4 or 6, and so on. A complete tournament schedule might look like this:

	Group 1	Group 2	Group 3
Week 1	1   2   3	4   5   6	7   8   9
Week 2	1   4   7	2   5   8	3   6   9
Week 3	1   5   9	2   6   7	3   4   8

So here's the question: could you organize a tournament like this with 100 people, in groups of 10, for 10 weeks?

Because if you could, you could get published in a Computer Science paper. Whether or not its even possible to schedule such a tournament is an open problem.

For Solving Hard Problems, we have to write a program that takes three numbers

• g - the number of groups in a week.


• s - the size of each group.


• w - the number of weeks.

and either prints a schedule for a social golfing tournament, or tells you its impossible.

It's a really cute problem. Hopefully in a few days, when it's done and gone, I can write about how I wrote the program. In the meantime, how would you go about it?

On Programming Interviews

Lots of great things have been written on the subject of programming interviews, but since I'll be entering the workforce very soon, I've taken away a few notes on how I would like to conduct them in the future, having just run the job search gauntlet.

Regarding phone screens, I learned a lot from Steve Yegge's post on his process. To summarize, he believes the candidate should demonstrate some basic proficiency and understanding in five areas to get the on-site: coding, OO design, scripting/regexes, data structures, and binary. It's alright if the candidate struggles a little, but if their answer to 'describe a function to sort an array of integers' is 'Collections.sort(array),' you might want to think twice about bringing them in.

Another advantage of living in 2010 is that we can actually see some code during a phone screen: one interviewer had me use EtherPad while on the phone with them, and I would probably do something similar.

More generally, diversity in the phone screen process will help you eliminate candidates who can talk big in one or a few fields, but don't have (or can't form) a more complete picture of what's going on.

If the candidate makes it to on-site, I would extend the diversity principle, but probably ask a few questions not listed above (if they demonstrated that they can write a regular expression in the phone screen, they don't need to show me one on-site). Here you could look at another round of fun brain-warpers that Joel Spolsky points out: pointers and recursion. I would love to write out a few problems as he has that just show they can read/write programs that use these techniques.

Brain teasers are a contested form in the interviews, but I love them too. Well, good ones anyways. I would like a candidate who smiles when they know a puzzle is headed their way. They would be very hintable, so I'm not anticipating an 'aha!' moment. An example of one of these that I think would rock, comes from Skorks:

Write a quine, in whatever language you like (for those who don't know, a quine is a program that prints its own source code without reading itself).

Now I've written about it, I probably wouldn't use it. A risk you run with any type of programming question that is meant to challenge is that they've run into it before, or researched the standard questions before arriving. While there's nothing wrong with researching beforehand, you probably want to see the candidate think, not just what they can remember. For this reason:

• Pick nonstandard problems. For coding samples, probably avoid direct library functions, or anything from here. They should be simple, so maybe library functions with a twist. A favorite of mine was "write a function that takes a string, and returns whether the braces, brackets and parenthesis are matched." Challenging, but appropriate, and more applicable to any job than reversing a string.


• Have backups. One interviewer asked me what a good data structure would be for the search function of an address book. Given that I'd just finished the Facebook Breathalyzer puzzle, we were finished with what might have been twenty minutes of material in five.

A few more notes:

• I personally don't like whiteboard coding. I get nervous, can't edit/iterate the function rapidly, and can't go at an appropriate speed. So when my time comes, I might minimize that. Regardless, you can't be an actor unless you audition, so it'll stay.


• A short quiz, on paper, would probably be included. This wouldn't be multiple-choice or anything silly, just a block of code, and ask the candidate to comment on all of its qualities.

The only flaw in my plan is, with all the material I've mentioned, I'd probably need more than 45 minutes to get a feel for a candidate, and I doubt I'd be given more than that at a time. I'll have to find a way to resolve this ^_^