[atraub]

Background (If you care)

Spoiler

Wikipedia said:

"The Library of Babel" (Spanish: La biblioteca de Babel) is a short story by Argentine author and librarian Jorge Luis Borges (1899-1986), conceiving of a universe in the form of a vast library containing all possible 410-page books of a certain format.

Despite — indeed, because of — this glut of information, all books are totally useless to the reader, leaving the librarians in a state of suicidal despair.

The Library of Babel is an interesting story. It gave me an idea. What if there were such an art gallery? For simplicity's sake, let's say that our art gallery only has 10x10 pixel images. Here's a few questions for you:

• Can you devise a format to store our files that will keep the size as small as possible? Let's assume we're only using 16 colors.
  
  
• Can you devise a calculator to figure out the average number of bytes that will be required to store such an image? Can you determine how many possible images there will be? Can you figure out how many bytes it will take to store ALL the possible images? If you didn't devise your own file format, assume that we're using PBM's.
  
  
• Can you write a program that COULD generate all possible 10x10 16-color images? Probably wouldn't be a good idea to run it though.
  
  
• If you've done number 2 or are good at math, you'll see that these numbers grow very quickly. Can you devise an algorithm that will intelligently skip images that are similar to other existing images? Perhaps you can even parameterize it to have some sort of threshold.

The gauntlet has been thrown! Who has the strength to step up the hardest challenge I've ever devised? MWAHHAHAHAHA!

This post has been edited by atraub: 27 January 2011 - 09:07 AM

[Sergio Tapia]

inb4 Baavgai.

[baavgai]

Doesn't count without code.

I have a thought. It's a little evil and completely antithetical to any normal approach. I don't feel like writing it, so I'll explain it.

You're defined result domain is 16^(10x10), or 2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376 ( thank you, python). Simply store that number and then figure out the image by looking up the permutation. Granted, not a flexible solution.

Eco later offered the library in "The Name of the Rose". However, there's a more modern idea, don't know who to credit, that I'll call the Babel console. Imagine a text box, merely 80 characters across and 25 characters down. If you were to view every possible permutation of characters in that box, you'd read every page that has been written and will be written. Of course, it will take a while...

In find the page more approachable than the library. I like the pixelated image idea.

[atraub]

Very interesting Baavgai. I don't want to change the challenge, but perhaps a different forum leader in need of a good topic could adopt that idea .

Isn't Python's handling of Long's awesome?

Your total image calculation is correct due to the Rule of Product. Good going

This post has been edited by atraub: 27 January 2011 - 09:47 AM

[Simown]

How much credit would we get say: for a 2 x 2 image and then estimate what a 10 x 10 image would be?

Maybe:

generateImage(gridSize = 2)

A grid size parameter?

Which could theoretically produce a 10 x 10 image but wouldn't break my computer Only 65536 possible permutations then!

I'd be interested to attempt this.


Edit: My calculation was wrong.

This post has been edited by Simown: 27 January 2011 - 10:32 AM

[atraub]

Trying to produce a single 10x10 image will be easy, borderline trivial with a good algorithm. I don't think there's enough hard drive space in the world to hold them all though.

[Simown]

I have re-read the questions now, I guess they are all possible to code just one is not possible to run.

I'll certainly attempt it.

This post has been edited by Simown: 27 January 2011 - 10:40 AM

[atraub]

Correct! Well, they can all run, but 1 will cause you some trouble if you don't kill it

[diego_pmc]

atraub, on 27 January 2011 - 10:35 AM, said:

Trying to produce a single 10x10 image will be easy, borderline trivial with a good algorithm. I don't think there's enough hard drive space in the world to hold them all though.

And not only that, but it's not even physically possible. If there are 16¹⁰⁰ permutations of 10x10 images, even if each image could fit on no more than one atom there still wouldn't be enough atoms in the known universe to store all the images.

(According to physicists there are less than a googol of atoms in the known universe, a googol being 10¹⁰⁰.)

This post has been edited by diego_pmc: 27 January 2011 - 01:36 PM

[atraub]

We only have 2 options, we either need more atoms in the universe or we need to store them quantumly

Wait, 3rd option. We need another universe.

How many atoms are in the universe?

This post has been edited by atraub: 27 January 2011 - 12:07 PM

[atraub]

Diego, you just inspired me. I may have to make and feature a second post just from another thought that this lead to.

pyinthesky, unless I'm misunderstanding you, I think your math is a little off.

Each image is 10x10, thus 100 pixels. Each pixel has 16 possible colors. based on the rule of products that means that there are 16**100 combinations. 380 * (16**100) bits > 4.67GB

This post has been edited by atraub: 27 January 2011 - 12:16 PM

[atraub]

Ahhh, you're teetering dangerously close to part 2 of this post

A 1x10 vertical strip with 16 color combinations would be 16**10 or 1,099,511,627,776. Only a trillion or so combinations.

This post has been edited by atraub: 27 January 2011 - 12:42 PM