When is something too DISTINCT?

Lets say you have a database product table with the following columns: id (numeric key), name (text), type (text), distributer(foreign key).

Lets also say you need to find all of the product types for a given category. Oh, and you need a candidate product_id for each product type (doesn't matter which one, but it must be a key of a record who has that type).

What is the best way to write a SQL query to find this information? You can interpret "best" to mean "most efficient", "most readable" or whatever you want.


As an explicit example:

Given the following data:
ID - NAME - TYPE - CATEGORY
1 - Super Truck - Toy - 100
2 - Cool Doll - Doll - 100
3 - Finger Paint - Drawing - 100
4 - Lame Block - Toy - 222
5 - Stinky Doll - Doll - 100

The query should return the following:
ID - TYPE
1 - TOY
(2 or 5) - Doll
3 - Drawing

I will post my "hack" later.

itoa

Sorry to anyone who doesn't like the programming puzzles...

Write an itoa function in C w/o using sprintf or the (non)standard itoa.

itoa takes in an integer and returns a character array representation of that integer, ex: 1234 -> ['1', '2', '3', '4']

If you're not a programmer you can spell out your solution in words, buts its way easier that way...

I'll share my solution in the comments later if you want it

Is it quit'n time yet?

The angle between the hour and minute hands of an analog clock is always between 0 and 180 degrees, inclusive. For example, at 12:00 the angle between the hands is 0 degrees. At 6:00 the angle is 180 degrees, and at 3:00 the angle is 90 degrees.

Write a function that given an arbitrary time in the form of two integers (the first representing an hour between 1 and 12 inclusive and the second as minutes between 0 and 59 inclusive) will return the angle between the hands accurate to at least one fractional digit.

e.g.
f(12, 0) = 0.0 degrees
f(6, 0) = 180.0 degrees
f(12, 30) = 165.0 degrees

Adapted from the original found in the ACM ICPC Problem Set w/o a solution.

Toggle This! Continued...

I made some progress on the previous puzzle that I didn't think would fit in a comment ...

After trying to aproach the problem from a pattern standpoint and being unable to come up with a simple (if X, do Y, else do Z...) kind of solutions and after talking with my dad and reading his ideas about the mathematics behind a solution I decided to write up a brute force solution that might at least get the creative juices flowing.

Some of my thought process was:

• As my dad pointed out, toggling the same place more than once give you nothing (you may and probably will need to have tiles toggled more than once by a combination of their neighbors and thereselves, but never in a sequence should the same location appear more than once)
• Since every location can either be toggled or not toggled in a solution, there are therefore theoretically 2^(n*n) solutions for an nxn table (a lot!)
• The vast majority are bad solutions, and bad solutions for many reason (ie have multiple holes)
• A solution needs to have a minimal number of locations in its sequence
• The easiest way to find possible solutions is to iteritively try each possible solution.
• It is possible to determine that a particular candidate solution is trash much sooner than the end when applying the toggles in an iterative manor (if you are building your solution column by column and row by row, then you can find that a solution is bad if any square is left off and none of the 5 squares that can toggle it are left to do)
• By finding bad solutions early, we don't need to worry about determining if the rest of the bad sequence is bad ..... its bad to the bone! This reminded me and stemmed out of a thought about Alpha-beta pruning in AI decision trees.

I therefore wrote up code which would try to build solution sequences in a brute force and interative manor ... but that would "prune" out bad solutions as early as possible and therefore run much more efficient than a pure brute force algorithm which would produce a whole candidate and then evaluate it.

The code I wrote can be found here and here (with non formatted code here and here).

The results were promising, but quickly unverifiable as being complete (its hard to verify a large number of solutions and given that I haven't looked up other solutions, hard to verify as being all of them). Results of my code with n = 1...10 can be found here with there solutions and some summary information.

I am concerned that there is such a desparity in numbers of solutions, but that may just be because of the small sample size I have to work with.

I would have run the code for much larger N, but my solution is proving problematic. Since it is based on recursion and for large N, the possible levels of recursion needed are very very large ... I ended up getting Stack Overflow errors from the JVM. Yep, O(2^(n^2)) is pretty bad ;). I am currently working on a version which wouldn't use recursion which I think will fair much better and be purely CPU bound. The current version is VERY fast and if the JVM wouldn't freak out at the large stack size, could be run very quickly on large N. I will also try tweeking my JVM settings to allocate a much larger stack and smaller heap and try it that way. Heap size looks to be bound by a constant*n*n which is about as good as you can get given the problem.

[ADDED] Also, it seems although I haven't verified it, that working through the matrix in some pattern other than row/column could possible find the problem areas even sooner for the majority of cases. I tried writing up code to "dove-tail?" the sequence (e.g. 0,0 1,0 0,1 2,0 1,1 0,2....) but it had a bug and I reverted back to the current method. I also considered doing a spiral in or out but since I don't know that it will help, I haven't tried yet...

Anyone with coding experience, please glance over my code and let me know if you find any stupid mistakes, optimizations, or cleverness I didn't include. Also let me know if you have found any other solutions, have any other ideas, or basically have any thoughts on the subject. I would rather be told I am wrong about something than go on thinking I am right. :)

....... How about someone else try and find a puzzle for tomorrow (even if this one isn't solved). I don't mind finding them but I want to make sure everyone/anyone is getting what they are interested in and is still wanting to do this.....

No Temps!

Puzzle -

Switch the values of two variables without using a third temporary variable.

Sample Input -

var A = 5
var B = 10

Sample Output -

var A = 10
var B = 5