Challenge: Help out St. Peter

  • (2 Pages)
  • +
  • 1
  • 2

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

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1743
  • View blog
  • Posts: 5,896
  • Joined: 03-August 09

Challenge: Help out St. Peter

Post icon  Posted 21 July 2016 - 12:01 PM

*
POPULAR

Big thanks to jon.kiparsky for helping me write this challenge. He helped me organize this a bit better and even wrote half the dialogue (which I paraphrased a bit)

You, J. Random Hacker, have just died. You see St. Peter at the gate...along with a *lot* of other people. Eventually you get to the gates.

St. Peter: Hey! You were a programmer; I need some help! If you help me out then you'll get into heaven despite your nefarious past. You see, we don't just process deaths from your universe, but ALL universes.
You look out and see an infinite number of lines of varying length.
St. Peter: Each line is a from a different Universe. Some are short, some keep going on forever like yours. I have to personally check each person into heaven so I need them to all be in one line. Trouble is they don't arrive that way. I need you to figure out how to put all these people in a single line so that no one gets left out!
J. Random Hacker: Sure that's easy! All I need to do is just go down the first line, and then when that ends go down the second line, and so forth!
St. Peter: Well, that's not going to work, I'm afraid. If the first line is finite, then eventually you'll get to the second line. And if the second line is finite eventually you get to the third. But let's suppose the third line is not finite - then we never get to the fourth line, no matter how long we wait.
J. Random Hacker: (thinks a while...) Okay, I've got it. Instead of going down each line in sequence, I'll take the first person from the first line, and then the first person from the second line, and so on until I run out of lines!
St. Peter: No, still no good. Remember, there might be an infinite number of universes.
J. Random Hacker: Hm... that's a tricky one... Is that even possible?
St. Peter: A guy that came in a bit before you named Georg Cantor. He said it was possible but left the proof as an exercise to the reader.

Your challenge is to write a program that takes an arbitrary (even "infinite") number of lines (think streams, generators, etc...) from each universe and combines them all into one line so that St. Peter can process them, not miss anybody, and will always eventually get to each person no matter which universe they went to or when or how many people lived in that universe.

You can do this in any language. Python has generators that will suffice for this, Haskell's lazy lists will work, Scala has Streams, C# has IEnumerables, Java 8 has Streams; basically just find a representation that will work in your language. If you want to do this in C or C++ I think the best representation is a really strange function pointer type. The representation of People doesn't matter. An integer/string type would suffice. In python a generator of generators would be needed. In C# IEnumerable<IEnumerable<...>>. in Haskell [[...]] . Translate as appropriate to your language of choice.

Have fun!

This post has been edited by ishkabible: 21 July 2016 - 07:12 PM
Reason for edit:: punctuation


Is This A Good Question/Topic? 8
  • +

Replies To: Challenge: Help out St. Peter

#2 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1250
  • View blog
  • Posts: 4,042
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 12:47 PM

Sounds fun - I'll take a look tonight.
Was This Post Helpful? 0
  • +
  • -

#3 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1250
  • View blog
  • Posts: 4,042
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 02:32 PM

So, question:
Spoiler

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2517
  • View blog
  • Posts: 4,001
  • Joined: 21-June 11

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 02:37 PM

There is a way to deal with this.
Was This Post Helpful? 0
  • +
  • -

#5 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1250
  • View blog
  • Posts: 4,042
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 02:59 PM

I suspect I'm just looking at "guarantee" or "infinite" in a different way. We'll see how it goes.
Was This Post Helpful? 0
  • +
  • -

#6 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1743
  • View blog
  • Posts: 5,896
  • Joined: 03-August 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 03:09 PM

Say there was only one infinite line. He would eventually get to every person in the line in that case because each person is some finite distance away from the front of the line. Perhaps that clarifies what is meant by "Eventually gets to"

This post has been edited by ishkabible: 21 July 2016 - 07:13 PM
Reason for edit:: grammer

Was This Post Helpful? 0
  • +
  • -

#7 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1250
  • View blog
  • Posts: 4,042
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 03:13 PM

That's sort of what I was thinking.

Do we need to account for lines being temporarily exhausted, and then more people arriving? The hints at laziness, generators, and enumerations makes me think no, though I can see methods of handling that.
Was This Post Helpful? 0
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1743
  • View blog
  • Posts: 5,896
  • Joined: 03-August 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 03:21 PM

oh no don't worry about that. You can just block until more input comes in if your representation has that issue. basically assume you'll always have more input if the list is infinite.

That said it's an interesting slight modification to this problem where, there might be no more dead people in line but more will come later and yet you want to keep processing dead people. That probably fits with more real world examples of this sort of thing.
Was This Post Helpful? 0
  • +
  • -

#9 xclite  Icon User is offline

  • I wrote you an code
  • member icon


Reputation: 1250
  • View blog
  • Posts: 4,042
  • Joined: 12-May 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 03:51 PM

Yeah. With the primitives in Clojure it's just easier to assume that there are no breaks, but I think I have an easy way to simulate and deal with lulls.
Was This Post Helpful? 0
  • +
  • -

#10 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1743
  • View blog
  • Posts: 5,896
  • Joined: 03-August 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 03:53 PM

can't wait to see this done in clojure!

This post has been edited by ishkabible: 21 July 2016 - 03:59 PM

Was This Post Helpful? 0
  • +
  • -

#11 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2517
  • View blog
  • Posts: 4,001
  • Joined: 21-June 11

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 05:18 PM

Is there something like a spoiler period for these kinds of challenges, where people who already know the solution shouldn't post theirs?
Was This Post Helpful? 0
  • +
  • -

#12 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1743
  • View blog
  • Posts: 5,896
  • Joined: 03-August 09

Re: Challenge: Help out St. Peter

Posted 21 July 2016 - 07:08 PM

nope, just use spoiler tags and go ahead and post!

For instance here's a solution in python that only handles the non-jagged case (infinite stream of infinite streams)

Spoiler

This post has been edited by ishkabible: 21 July 2016 - 07:25 PM

Was This Post Helpful? 0
  • +
  • -

#13 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2517
  • View blog
  • Posts: 4,001
  • Joined: 21-June 11

Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 02:49 AM

Here's my solution in Haskell, which should be able to handle inner and outer lists of any size (including infinite of course):

Spoiler

Was This Post Helpful? 0
  • +
  • -

#14 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5922
  • View blog
  • Posts: 20,247
  • Joined: 05-May 12

Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 05:46 AM

Perhaps I'm not understanding the problem, or I'm not understanding the solutions provided so far.

From the OP:

View Postishkabible, on 21 July 2016 - 03:01 PM, said:

J. Random Hacker: (thinks a while...) Okay, I've got it. Instead of going down each line in sequence, I'll take the first person from the first line, and then the first person from the second line, and so on until I run out of lines!
St. Peter: No, still no good. Remember, there might be an infinite number of universes.


But my reading of solutions proposed in posts #12 and #13 each pull the first person from each line for each universe. So with infinite universes, you'll never make it back to the first universe.


Ah! Now the light bulb comes on while I take a much closer look at the code.
Spoiler

Was This Post Helpful? 1
  • +
  • -

#15 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2517
  • View blog
  • Posts: 4,001
  • Joined: 21-June 11

Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 08:12 AM

View PostSkydiver, on 22 July 2016 - 02:46 PM, said:

Spoiler


Spoiler

Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2