Gallery of Babel

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 4217 Views - Last Post: 29 January 2011 - 03:11 PM Rate Topic: -----

#1 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Gallery of Babel

Post icon  Posted 27 January 2011 - 08:39 AM

Background (If you care)
Spoiler


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


Is This A Good Question/Topic? 0
  • +

Replies To: Gallery of Babel

#2 Sergio Tapia  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1252
  • View blog
  • Posts: 4,168
  • Joined: 27-January 10

Re: Gallery of Babel

Posted 27 January 2011 - 09:09 AM

inb4 Baavgai. :D
Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5800
  • View blog
  • Posts: 12,636
  • Joined: 16-October 07

Re: Gallery of Babel

Posted 27 January 2011 - 09:40 AM

Doesn't count without code. :P

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.
Was This Post Helpful? 1
  • +
  • -

#4 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Gallery of Babel

Posted 27 January 2011 - 09:45 AM

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

Was This Post Helpful? 0
  • +
  • -

#5 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Gallery of Babel

Posted 27 January 2011 - 10:29 AM

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 :P 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

Was This Post Helpful? 0
  • +
  • -

#6 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Gallery of Babel

Posted 27 January 2011 - 10:35 AM

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.
Was This Post Helpful? 0
  • +
  • -

#7 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Gallery of Babel

Posted 27 January 2011 - 10:39 AM

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

Was This Post Helpful? 0
  • +
  • -

#8 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Gallery of Babel

Posted 27 January 2011 - 10:40 AM

Correct! :D Well, they can all run, but 1 will cause you some trouble if you don't kill it ;)
Was This Post Helpful? 1
  • +
  • -

#9 diego_pmc  Icon User is offline

  • D.I.C Addict

Reputation: 81
  • View blog
  • Posts: 565
  • Joined: 13-May 09

Re: Gallery of Babel

Posted 27 January 2011 - 11:54 AM

View Postatraub, 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 16100 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. :D

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

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

Was This Post Helpful? 1
  • +
  • -

#10 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Gallery of Babel

Posted 27 January 2011 - 11:56 AM

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

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

Was This Post Helpful? 0
  • +
  • -

#11 Guest_pyinthesky*


Reputation:

Re: Gallery of Babel

Posted 27 January 2011 - 12:10 PM

Each image is 10x10. Each image can be 10 combinations of 10^10 * 16 combinations. This would require a database of around 4.67GB.

log(10^10 * 16)/log(2) -> 38 bits to address a single stored combination.

Since any image is composed of 10 of these combinations, you only need 38 * 10 = 380 bits to store any unique image.
Was This Post Helpful? 0

#12 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Gallery of Babel

Posted 27 January 2011 - 12:14 PM

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

Was This Post Helpful? 0
  • +
  • -

#13 Guest_pyinthesky*


Reputation:

Re: Gallery of Babel

Posted 27 January 2011 - 12:16 PM

View Postpyinthesky, on 27 January 2011 - 12:10 PM, said:

Each image is 10x10. Each image can be 10 combinations of 10^10 * 16 combinations. This would require a database of around 4.67GB.

log(10^10 * 16)/log(2) -> 38 bits to address a single stored combination.

Since any image is composed of 10 of these combinations, you only need 38 * 10 = 380 bits to store any unique image.



Appologies,4.67GB comes from 10^10 *4(this 4 represents the 4 bits required to create 16 colors) / (8 * 1024 * 1024 * 1024)
Was This Post Helpful? 0

#14 Guest_Guest*


Reputation:

Re: Gallery of Babel

Posted 27 January 2011 - 12:18 PM

View Postatraub, on 27 January 2011 - 12:14 PM, said:

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



see later post for the GB math ... but i'm assuming one database where you only create every combination you can make from a [1x10] vertical strip. Once you have this 4.67gb worth of every possible vertical strip, you need only have the 10 addresses to make any one image.
Was This Post Helpful? 0

#15 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Gallery of Babel

Posted 27 January 2011 - 12:38 PM

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

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2