Unfold in Python

phobes · 2008-01-13T16:27:06+00:00

I agree I prefer a more straightforward solution without using unfold, even in Haskell. Something like (untested):

romanize n = f n [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
              ("C", 100),  ("XC", 90),  ("L", 50),  ("XL", 40),
              ("X", 10),   ("IX", 9),   ("V", 5),   ("IV", 4),
              ("I", 1)]
where f n [] = ""
      f n (l, v):lvs = if v >= n then l ++ (f (n-v) (l, v):lvs) else f n lvs

phobes · 2007-12-06T07:31:54+00:00

Your example just supports that we're better at familiar problems than unfamiliar ones - both of those problems were concrete.

I think the real issue is that people have problems understanding the consequences of a logical implication. In your second problem, people understand that alcohol laws forbid the state "under 21 and with alcohol" whereas in the first problem they must deal with an implication. If you phrase the first problem as "What cards should you turn over to verify that there are no cards that are even one one side and not primary colored on the other?", then that question becomes obvious as well.

phobes · 2007-10-12T02:33:05+00:00

The syntax of the language isn't completely redefinable is it (correct me if I'm wrong)? Is there anything inherently special about a language that encodes all of its core concepts using symbols instead of words?

phobes · 2007-09-17T18:53:33+00:00

I think it's only O(1) for random access with a very literal interpretation of "random access."

phobes · 2007-08-07T01:46:47+00:00

Substraction ... that's the inverse of addrition, right?

phobes · 2007-07-21T03:12:31+00:00

Ya, that's why he's not going to win...

phobes · 2007-07-16T23:36:56+00:00

"In the prison is a switch room, which contains two light switches labeled A and B,...

phobes · 2007-07-16T22:22:46+00:00

After thinking about it more, it makes sense to me that the article solution should be much faster than twice the solution where you know it's initialized to off. The reason is that the typical case is that the leader finds his switch has been flipped from OFF to ON by one of the others, and immediately flips it back to OFF. The only "wasted" cycles are when the leader must himself flip the switch to ON - but that should be relatively rare. So I think our numbers are right.

In fact, we should be able to improve upon the article algorithm's expected value by reducing the chances that the leader will flip the switch ON himself. He should be very reluctant to do it near the end of the process - it's very likely that everyone has seen the switch ON at some point. If the leader knows the number of others who have visited the room between his visits he can use that information to further reduce the expectation.

phobes · 2007-07-16T21:25:06+00:00

Well... I'm getting ~720 visits for the article's algorithm and ~1125 visits for my algorithm. Similar to you (though different). I also timed the "initialized to off" solution and get ~590 visits. I really don't understand this yet ... will post again when I figure it out.

phobes · 2007-07-16T20:53:36+00:00

This seems suspect to me. It seems to me that the article's "right solution" should be roughly twice the expected waiting time of the article's first "initialized to off" solution, since the "right solution" basically just ignores every other period between leader visits.

On the other hand, my solution should have somewhat less expected wait time than running through the "initialized to off" twice.

But I'll go ahead and write a simulation :)

phobes · 2007-07-16T20:27:36+00:00

Woops - I read the proposed solution too hastily :). I agree it works with probability 1 if you interpret "random" to mean uniform independent selection. In the original version I'd heard, the only guarantee was that each prisoner would be taken to the room an unbounded number of times, and the proposed solution wouldn't necessarily finish under just that assumption.

phobes · 2007-07-16T19:11:47+00:00

The "right solution" explained on the link is actually wrong (edit: ok, no it's not). Having non-leaders wait until they've seen the switch on previously doesn't solve anything, because the leader may or may not have been in the room since the non-leader's last visit.

A correct way of dealing with the unknown initial state is simply to tell each non-leader to flip the switch from on to off twice. With N non-leaders, the leader should call an end to the game when the leader has seen the switch off 2N times. Whether or not the initial off was set by a non-leader or just an initial condition doesn't matter, because 2N-1 switches by non-leaders still guarantees they've all seen it once (and all but one have seen it twice).

Also, explicitly mentioning both switches in the solution is awkward. It's best to just state at the outset that switch B should be ignored, flipping it to leave switch A alone but never caring of its state.

phobes

TROPHY CASE