Suppose a structure made of 255 cells. Is it possible to arrange them in such a way where each cell has a unique neighborhood? The first structure is efficient because each cell is unique. But the second and third ones has similar shapes which means some cells aren't efficient enough. (First Image)I think I worded it weird so. What's the least amount of squares, structures, or rectangular area you need to make all 256 shapes? (Third Image, the square with no neighbours can be excluded of course.)I managed to get 89 of them (Green Cells, Second Image. Actually 90 if you include the neighbourless cell) but I don't know if the minimum really is 256THE HELL ARE THESE CAPTCHAS YOU PEOPLE ARE INSANE
I'M MAD ABOUT THE CAPTCHAS NOW WTF IS WRONG WITH YOU PEOPLE???? WHO DOES THIS?????? >be me>go to 4chan>make a post>get a captcha>???????????????????? GET A LIFE
meds
>>16957703Oh this is a neat question. Basically you are asking how to realize the most compact possible black and white bitmap where each of the 2^8 ways a pixel can be surrounded is realized exactly once? That sounds really tough. Like, I can wrap my head around 1D: suppose you wanna write a string of 1s and 0s such that every combination 111,110,011,010 occurs exactly once. It becomes immediately obvious that "010" can never be included in a string where all 1s touch. In your example, the neigborhood where all but the central pixel are white can never be part of the rest of the picture, so there can't be a "connected" solution.I suppose my 1D example would have this solution: "11101011". Then, all possible neighborhoods (4) are realized by a string of length 8 (or less, if I missed something).You could then ask "what is the maximum amount of neighborhoods you can get where all 1s are connected, and how long is the optimal string?" I suppose the answer would be "01110", meaning 3 neigborhoods and a length of 5. Your case seems like the 2D equivalent.
>>16957810"0111010" is more compact actually, so it is at most 7.
>>16957812Trying a proof:the solution would have to have at least four 1s to capture "111" and "010", which means it also must have at least 2 0s, meaning the ideal string is at least 6 and at most 7 long.You can just brute force all binary length 6 strings with exactly 4 1s and 2 0s which contain 111 as a substring: "001111", "010111", "011101", "011110", "100111", "101110", "111010", "111001", "111100". Those that don't miss 010 miss 110 or 011 instead.So 7 is the solution with the neighborless cell included.It also becomes clear that the number will vary widely even in 1D as you exclude select neighborhoods. So subsets of all possible neighboorhoods will give wild answers as a function of which ones.
>>16957703what, like a 2D cellular superpermutation?
>>16958275>superpermutationhttps://en.wikipedia.org/wiki/Superpermutation#Lower_bounds,_or_the_Haruhi_problem
