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
Occasionally I play Solitaire on my iPod. After losing several games in a row (by lose, I mean I can't find anything more to do and I haven't finished the game) I wondered what percentage of games can be won and if there is any "better" methodology or rules to doing it that will yield a higher number of wins versus another.
Pure guessing leads me to believe that there are games that can't be won and that there are games that "could" be won if things are done in the right order, but can also be put into a state that you can no longer win from.
I am assuming that you are playing a "normal" game where you have 7 columns to work with (left most having one "up" card, the second having an "up" card and a "down" card ....), 4 foundation areas where you must place the cards by suit starting with Ace, and that you flip cards out of your deck 3 at a time (only able to play the top card). The version on my iPod default to NOT letting you move cards from the "foundation" areas but you could do it either way.
The puzzle I pose to everyone is to figure out what percentage of possible games are "winnable" or some approximation.
Also, can you determine any specific methodologies to increase the likely hood of winning a game over others?
Submitted by Me.
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.Adapted from the original found in the ACM ICPC Problem Set w/o a solution.
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
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.....
We have a square grid of n rows and n columns, i.e. it contains n*n squares in all. Each square can be either on or off. now we have a toggle operation such that if it is applied on any square it toggles all the squares that have a side common to the square(including the square itself). So, in a 3*3 matrix we have initially all off then when we perform toggle on say (2,2) then (1,2) (2,1) (2,2) (2,3) (3,2) are turned on.So, for any value of n supplied by user, we have to find a sequence of operations so that if all the squares intially are off they are turned on after that sequence.
For example, the sequences for n=1, 2, and 3 are:
n=1 (1,1)
n=2 (1,1) (1,2) (2,1) (2,2)
n=3 (1,1) (1,3) (2,2) (3,1) (3,3)
Taken from here w/0 a solution
^^ Interesting site with a lot of good questions/puzzles.
Don't read too many of them, b/c I will probably use them later :-p
Bonus (from me, not from the original puzzle) is find an algorithm that will produce a sequence that will work for an arbitrarially sized nxn matrix and only turns on a single specified square (e.g. leave a 5x5 matrix, initially off, with only the (1,3) spot on.
Also, what if the matrix was in an arbitrary initial state besides all being off and trying to turn them all on at the same time. What if some were on and others were off .... could an algorithm be devised which could take that board to a given state through a series of actions as described above?
I have no idea if either is possible....
If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?
eight
eighteen
eighteenmillion
eighteenmillioneight
eighteenmillioneighteen
eighteenmillioneighteenthousandand the last is
twothousandtwohundredtwo
The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point? [Bonus points for algorithms that will find the result for an arbitrary position, not just the 51st - Ben]
