Challenge: Help out St. Peter

  • (2 Pages)
  • +
  • 1
  • 2

29 Replies - 12332 Views - Last Post: 31 July 2016 - 06:13 AM

#16 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1230
  • View blog
  • Posts: 4,016
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 08:20 AM

Clojure solution is on the way - just writing up some "test" cases to demonstrate functionality in the face of actual infinity.
Was This Post Helpful? 0
  • +
  • -

#17 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 11:39 AM

Here's the original function I wrote in Haskell that prompted this challenge. It's not very reader friendly or well written but it's what I clobbered together when first thinking about how to do this. In case anyone was wondering this can show up in practice because it showed up in practice for me!
Spoiler

This post has been edited by ishkabible: 22 July 2016 - 11:47 AM

Was This Post Helpful? 0
  • +
  • -

#18 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5824
  • View blog
  • Posts: 19,829
  • Joined: 05-May 12

Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 01:15 PM

I was originally thinking of using C# yield calls, but I couldn't think of how to prevent stalling on empty lines. I may have to use Queue<T> instead to represent the lines. At least with that I can peek to see if the line is empty.
Was This Post Helpful? 0
  • +
  • -

#19 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 04:31 PM

Will Queue<T> work? How do you make it infinite? This is a real question on my part not me trying to guide you away from it. I'm not familiar enough with C# to know the answer.

Also you should be able to use yield/IEnumerator still but it's tricky for multiple reasons
Spoiler

This post has been edited by ishkabible: 22 July 2016 - 04:34 PM

Was This Post Helpful? 0
  • +
  • -

#20 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Challenge: Help out St. Peter

Posted 24 July 2016 - 05:08 AM

I'd use IObservable<T> with .SelectMany

Link
Was This Post Helpful? 1
  • +
  • -

#21 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5824
  • View blog
  • Posts: 19,829
  • Joined: 05-May 12

Re: Challenge: Help out St. Peter

Posted 24 July 2016 - 12:04 PM

ishkabible: .NET Framework Queue<T> are just like all the other .NET Framework containers: They'll keep on going until they run out of memory.
Spoiler


AdamSpeight2008: Thank you for that link. I'd been setting aside learning about the Reactive Framework, so it was very satisfying for me to go and try to catch up and learn what the framework is all about.
Spoiler

Was This Post Helpful? 0
  • +
  • -

#22 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1230
  • View blog
  • Posts: 4,016
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 26 July 2016 - 05:29 PM

Now that I'm back from vacation:

Spoiler

Was This Post Helpful? 1
  • +
  • -

#23 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1469
  • View blog
  • Posts: 8,174
  • Joined: 07-September 06

Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 11:28 AM

Hm, am I missing something?
Spoiler

Was This Post Helpful? 0
  • +
  • -

#24 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1230
  • View blog
  • Posts: 4,016
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 11:54 AM

Spoiler

Was This Post Helpful? 0
  • +
  • -

#25 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2500
  • View blog
  • Posts: 3,955
  • Joined: 21-June 11

Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 11:55 AM

Spoiler

Was This Post Helpful? 0
  • +
  • -

#26 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 12:07 PM

View PostBetaWar, on 28 July 2016 - 06:28 PM, said:

Hm, am I missing something?
Spoiler


Every person has a finite position in their line and that line has a finite position amongst the other lines. It is generally not considered proper to take something that is countably infinite and describe it as 2 positions separated by an infinite amount of positions. Basically, you have no knowledge of the "last" line because there is no "last" line. Any line you are able to select will have a finite amount of lines between it and the starting line. Thus the proposed solution will work. You can pick any person and we can calculate when they will be processed. Since we can calculate when anyone will be processed that means everyone will be processed.
Was This Post Helpful? 0
  • +
  • -

#27 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1469
  • View blog
  • Posts: 8,174
  • Joined: 07-September 06

Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 12:22 PM

That pre-supposes that you aren't in a scenario where there are infinite lines _before_ the given person you want to determine if they will ever get let through.

It is like saying that between lines 0 and infinity, you know that line 87 will eventually be hit, but that doesn't take into account the infinity between 0 and 1.

Now, practically there may be a solution, but mathematically I don't believe there is.
Was This Post Helpful? 0
  • +
  • -

#28 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2500
  • View blog
  • Posts: 3,955
  • Joined: 21-June 11

Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 12:37 PM

View PostBetaWar, on 28 July 2016 - 09:22 PM, said:

That pre-supposes that you aren't in a scenario where there are infinite lines _before_ the given person you want to determine if they will ever get let through.


Assuming the number of universes is countably infinite, that's a given. Though admittedly I don't think that requirement was stated explicitly.

Note that in practical terms, any kind of enumerator/iterator/stream/lazy datastructure that can exist in a program will at most be countably infinite.
Was This Post Helpful? 1
  • +
  • -

#29 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 01:02 PM

Quote

It is like saying that between lines 0 and infinity, you know that line 87 will eventually be hit, but that doesn't take into account the infinity between 0 and 1.

This is an uncountably infinite scenario so it is irrelevant to the problem. There is line 0 and line 1. These two lines are consecutive and have no lines between them, much less infinite lines between them.

Quote

That pre-supposes that you aren't in a scenario where there are infinite lines _before_ the given person you want to determine if they will ever get let through.


As I described above this line of thinking is not permitted. To simplify the issue, suppose I just start counting 1,2,3,4... and so on. So long as I am capable of counting endlessly I will reach every positive integer. To prove it, for any number you select we can tell when it will be counted. Can you point to a number that will not be counted? Based on your objection, you basically point to "infinity+1" and claim that number will not be counted. Unfortuneately, that is not a number so it fails to disprove that every number will be counted. Any number you can point to will be counted, therefore every number will be counted.

In our scenario, the people in the lines can be enumerated and then we count through them to process all people just as we can count every integer.
Was This Post Helpful? 0
  • +
  • -

#30 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Challenge: Help out St. Peter

Posted 31 July 2016 - 06:13 AM

This is exactly the kind of discussion I was hoping would come up. Dealing with these notions of infinity and finally understanding them is really interesting IMO. I'm going to try to clear up some confusion here. What sepp2k has been saying is all correct. What mojo666 said about position and having no "last" is correct.

1) There is no uncountability going on here. That's in fact what this exercise proves in a sense! That is if you have an infinity of infinities you don't actually have a greater infinity! These programs, if proven correct, actually prove that any product of countable/finite sets will be at most countably infinite (and at least if one of the things in the product was infinite).

2) I didn't specify what kind of ordinal we were indexing these streams by (statment explained below). I unfortunately took that ordinal to be the natural numbers without clarifying. I assumed it would be clear. Going forward if someone talks about an infinite data structure they're probably refereeing to the sort that can be indexed by natural numbers in someway (be it an infinite tree, list etc...). In this context "line" was supposed to convey that but it doesn't really do that does it? For instance BetaWar mentions "what about the last person" or "what if an infinity came before that?". So this gets tricky. The infinity we are dealing with here is that of the natural numbers, sometimes called omega when in the right set theoretic contexts. These other sorts of infinity BetaWar refers to are in fact consistent notions of infinity called ordinals. If there is 1 last guy in line? that's omega + 1, if theres an infinity before an infinity? that's 2*omega. In a certain sense (read "not actully correct what is to follow but a good intuition") what I asked to occur here was for you to inductively define a map over omega * omega (and a lot of other stuff because I asked for jagged lines) into omega.
I was about to say that had I asked you to do this with omega + 1 or 2*omega that this would not have bene possible. That would be the case had I demanded streams be the representation because while mathematically a stream of length 2*omega makes sense a computer represented stream of such a length does not. But this doesn't mean we can't make a new data structure that represents this! We can, computability, define functions from higher ordinals to objects and map them bijectively into functions from lower ordinals to the same objects. If you guys are interested in working with streams index by higher ordinals I'd bake up another challenge.

3) as hinted at, you should basically think of streams as functions from natural numbers to objects. Of course streams end sometimes and functions from naturals do not end. With a bit of tweaking you can work out the same structure purely in terms of functions however. That's the take away here. You can understand and cope with these notions of infinity by having the right type be the domain of a function.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2