March 2015

Xyzzy · 2015-03-02, 19:03

http://domino.research.ibm.com/Comm/...March2015.html

TheMawn · 2015-03-03, 01:25

I have no idea what that question even means.

Ken_g6 · 2015-03-06, 00:42

This is a tough one. Suppose punched cards are expensive, and you want to be able to re-use them once before throwing them away. You want to be able to use a punched card to store 26 characters (A-Z), then punch some more holes in it (you can't remove holes) and completely replace what was there before, with any of those 26 characters you want. Storing A-Z once takes 5 bits per letter. How many bits per letter do you need to be able to overwrite each letter with any one other letter? (One would assume not more than 10, and probably less.) What kind of encoding do you use?

In CS terms, holes are "1"s, while non-holes are "0"s, so the goal is to have an encoding such that, for each encoded value, you can OR it with some number to produce every other encoded value.

The last bit of the question is whether you can write an explanation for your scheme, which uses N bits, in 2^N letters or less. Hence the "Bonus '*' for those who can fit an intelligible sentence into a correct answer."

I see an encoding that would work for 9 bits. If the 4 high bits are not set, take the low 5 bits. Skip over characters 15 and 16, so if the high bit is set subtract 2 to get the value you wanted. If any of the 4 high bits are set, take the high 5 bits instead and reverse them. If all 4 low bits are 1, invert the 5 high bits.

I suspect 8 bits is possible but I haven't found a way yet.

Batalov · 2015-03-06, 09:22

One could consider for starters a toy example: A toy alphabet is {A, B, C}, and 2 bits are needed for one-time writing, but how many for the double-writing?

X=3 bits; e.g. encode A=1, B=2, C=4 for writing once, and A[SUB]2[/SUB]=B|C=6, B[SUB]2[/SUB]=A|C=5, C[SUB]2[/SUB]=A|B=3 for re-writing => 3 bits. So the answer would be _ABCCBA*, where _ is space, and * is usused (or any letter can be put there).

I suspect that the full-size answer is 8 bits, but the satisfactory encoding string is elusive, so far.

LaurV · 2015-03-07, 02:43

A codification with 8 is quite easy and straight away. For example: you encode the A-Z in the usual way, with numbers from 1 to 26, except O (01111) and W (10111), see below, which will get 27 and 28. To re-punch, you consider the most significant 2 bits (holes) and another 3 bits (totally 8). For the two common bits, you can have them either matching your desired holes, or being unpunched and then you can punch them, or they are 01, 10, 11 and they don't match your desired new holes, in this case you can use re-punch first 3 LSB bits (you will only need 2 in fact) to re-encode (change the meaning) of common bits. A conflict will appear when you want to re-punch something into A, B and C, as you don't have holes in the last 3 MSB, so you don't know if the letter is still the original one, or it was repunched into A, B, or C. In this case, A[sub]2[/sub], B[sub]2[/sub], and C[sub]2[/sub], will have to have codes into (decimal) 27, 28, 29. Another conflict will appear to transform O (which is 01111), and W (which is 10111, so the 3 LSB are already punched) into something ending with 00 or 10 (respective 01), and you will need a different encoding for O and W. This method seems to be a bit (pun intended) inefficient. I suspect a codification with 7 exists, which is, to copy you, "elusive" for now...

LaurV · 2015-03-07, 04:30

Well, after the morning coffee and putting it on paper (the first time I was trying to deal with it in my head, that is why I missed G, beside of O and W). There is a solution with 7, and is based exactly on Batalov's solution, with can be easily generalized. It uses codes of one and two holes, which are 7+comb(7,2)=28, for the first punch, and their complements, i.e. 5 and 6 holes,, for the second punch. The trick is to deal with the few exceptions (conflicts) that appear. Still working on it.

LaurV · 2015-03-09, 04:08

Now you are all guilty of putting it into my head. Have anyone find a solution with 7 bits? (screw the spoilers, I never liked the black, it would be better be all white or so... and I used them only because other people used them, but now, as I don't show any solution, and actually I don't have a solution

, I don't see the utility of the spoiler).

We went out during the weekend, but last evening after returning and doing some chores around the house, before going to bed, I spent about 3-4 hours with paper and pencil, and even used Excel and Graphviz (to make a digraph of the 127 states, which is quite fast and only took me five minutes). I always run short of 2-3 letters, no matter how I combine them. This is, I can transform everything in everything, except two-three letters which can't be reached from other two-three letters. But in all cases I have 6-7 states left (which I can't use). So, in theory, the problem is still possible to be solved with 7 bits, as long as I couldn't prove it is not.

I went to bed thinking to it, but it didn't happen like a hundred years ago when I was younger and used to go to sleep with a problem and wake up in the morning with a solution (don't think to stupid things!)

Transforming my graph in an 8-bit solution is trivial, I only need to add few states with 8 bits, but I "feel" that the solution is with 7, and not with 8. Now I am quite busy at job, but tonight I will begin to put it into a program, and let the computer deal with (part of the) permutations for few days. It is staying on my brain and I can't get rid of it! Your fault!

Batalov · 2015-03-09, 04:53

I have the 8-er solution, which I also rhymed to the "the quick brown fox jumps..." phrase.
But then, I didn't submit it yet. Because I also think that maybe the 7-er is possible after all.

retina · 2015-03-09, 05:09

What about the state of nothing punched? There was no requirement stated to encode a space or anything outside of A-Z.

Ken_g6 · 2015-03-09, 14:55

Quote:

Originally Posted by LaurV

Well, after the morning coffee and putting it on paper (the first time I was trying to deal with it in my head, that is why I missed G, beside of O and W). There is a solution with 7, and is based exactly on Batalov's solution, with can be easily generalized. It uses codes of one and two holes, which are 7+comb(7,2)=28, for the first punch, and their complements, i.e. 5 and 6 holes,, for the second punch. The trick is to deal with the few exceptions (conflicts) that appear. Still working on it.

I was working on a similar approach to an 8-bit solution. Take up-to-2 of 7 bits for the initial encoding, requiring that mirrored solutions are excluded. (This appears to be short one character already now that I look at it!) Then add another bit to specify that a complement encoding is mirrored, so that a bit opposite an already used bit can be left unpunched. But the mirror of the central bit is still the central bit.

Batalov · 2015-03-10, 00:18

Quote:

Originally Posted by retina

What about the state of nothing punched? There was no requirement stated to encode a space or anything outside of A-Z.

I am pretty sure that this doesn't contradict the problem, especially as restated on 3/04.

2015-03-02, 19:03	#1
Xyzzy "Mike" Aug 2002 17411₈ Posts	March 2015 http://domino.research.ibm.com/Comm/...March2015.html

2015-03-07, 02:43	#5
LaurV Romulan Interpreter Jun 2011 Thailand 9154₁₀ Posts	A codification with 8 is quite easy and straight away. For example: you encode the A-Z in the usual way, with numbers from 1 to 26, except O (01111) and W (10111), see below, which will get 27 and 28. To re-punch, you consider the most significant 2 bits (holes) and another 3 bits (totally 8). For the two common bits, you can have them either matching your desired holes, or being unpunched and then you can punch them, or they are 01, 10, 11 and they don't match your desired new holes, in this case you can use re-punch first 3 LSB bits (you will only need 2 in fact) to re-encode (change the meaning) of common bits. A conflict will appear when you want to re-punch something into A, B and C, as you don't have holes in the last 3 MSB, so you don't know if the letter is still the original one, or it was repunched into A, B, or C. In this case, A[sub]2[/sub], B[sub]2[/sub], and C[sub]2[/sub], will have to have codes into (decimal) 27, 28, 29. Another conflict will appear to transform O (which is 01111), and W (which is 10111, so the 3 LSB are already punched) into something ending with 00 or 10 (respective 01), and you will need a different encoding for O and W. This method seems to be a bit (pun intended) inefficient. I suspect a codification with 7 exists, which is, to copy you, "elusive" for now... Last fiddled with by LaurV on 2015-03-07 at 03:15

2015-03-07, 04:30	#6
LaurV Romulan Interpreter Jun 2011 Thailand 2×23×199 Posts	Well, after the morning coffee and putting it on paper (the first time I was trying to deal with it in my head, that is why I missed G, beside of O and W). There is a solution with 7, and is based exactly on Batalov's solution, with can be easily generalized. It uses codes of one and two holes, which are 7+comb(7,2)=28, for the first punch, and their complements, i.e. 5 and 6 holes,, for the second punch. The trick is to deal with the few exceptions (conflicts) that appear. Still working on it. Last fiddled with by LaurV on 2015-03-07 at 04:32 Reason: spoiler, not strike, sorry....

2015-03-09, 04:08	#7
LaurV Romulan Interpreter Jun 2011 Thailand 21702₈ Posts	Now you are all guilty of putting it into my head. Have anyone find a solution with 7 bits? (screw the spoilers, I never liked the black, it would be better be all white or so... and I used them only because other people used them, but now, as I don't show any solution, and actually I don't have a solution , I don't see the utility of the spoiler). We went out during the weekend, but last evening after returning and doing some chores around the house, before going to bed, I spent about 3-4 hours with paper and pencil, and even used Excel and Graphviz (to make a digraph of the 127 states, which is quite fast and only took me five minutes). I always run short of 2-3 letters, no matter how I combine them. This is, I can transform everything in everything, except two-three letters which can't be reached from other two-three letters. But in all cases I have 6-7 states left (which I can't use). So, in theory, the problem is still possible to be solved with 7 bits, as long as I couldn't prove it is not. I went to bed thinking to it, but it didn't happen like a hundred years ago when I was younger and used to go to sleep with a problem and wake up in the morning with a solution (don't think to stupid things!) Transforming my graph in an 8-bit solution is trivial, I only need to add few states with 8 bits, but I "feel" that the solution is with 7, and not with 8. Now I am quite busy at job, but tonight I will begin to put it into a program, and let the computer deal with (part of the) permutations for few days. It is staying on my brain and I can't get rid of it! Your fault! Last fiddled with by LaurV on 2015-03-09 at 04:10

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
March 2018	Xyzzy	Puzzles	2	2018-04-08 13:45
March 2017	R. Gerbicz	Puzzles	1	2017-04-03 10:57
March 2016	Xyzzy	Puzzles	21	2016-06-09 20:26
March Madness 2006	Prime95	Lounge	20	2006-03-21 04:35
gmp 4.2 due in March	Mystwalker	GMP-ECM	4	2006-02-01 12:00

2015-03-03, 01:25	#2
TheMawn May 2013 East. Always East. 11×157 Posts	I have no idea what that question even means.

2015-03-06, 00:42	#3
Ken_g6 Jan 2005 Caught in a sieve 110001011₂ Posts	This is a tough one. Suppose punched cards are expensive, and you want to be able to re-use them once before throwing them away. You want to be able to use a punched card to store 26 characters (A-Z), then punch some more holes in it (you can't remove holes) and completely replace what was there before, with any of those 26 characters you want. Storing A-Z once takes 5 bits per letter. How many bits per letter do you need to be able to overwrite each letter with any one other letter? (One would assume not more than 10, and probably less.) What kind of encoding do you use? In CS terms, holes are "1"s, while non-holes are "0"s, so the goal is to have an encoding such that, for each encoded value, you can OR it with some number to produce every other encoded value. The last bit of the question is whether you can write an explanation for your scheme, which uses N bits, in 2^N letters or less. Hence the "Bonus '*' for those who can fit an intelligible sentence into a correct answer." I see an encoding that would work for 9 bits. If the 4 high bits are not set, take the low 5 bits. Skip over characters 15 and 16, so if the high bit is set subtract 2 to get the value you wanted. If any of the 4 high bits are set, take the high 5 bits instead and reverse them. If all 4 low bits are 1, invert the 5 high bits. I suspect 8 bits is possible but I haven't found a way yet.

2015-03-06, 09:22	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22057₈ Posts	One could consider for starters a toy example: A toy alphabet is {A, B, C}, and 2 bits are needed for one-time writing, but how many for the double-writing? X=3 bits; e.g. encode A=1, B=2, C=4 for writing once, and A[SUB]2[/SUB]=B\|C=6, B[SUB]2[/SUB]=A\|C=5, C[SUB]2[/SUB]=A\|B=3 for re-writing => 3 bits. So the answer would be _ABCCBA, where _ is space, and is usused (or any letter can be put there). I suspect that the full-size answer is 8 bits, but the satisfactory encoding string is elusive, so far.

2015-03-09, 04:53	#8
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 59×157 Posts	I have the 8-er solution, which I also rhymed to the "the quick brown fox jumps..." phrase. But then, I didn't submit it yet. Because I also think that maybe the 7-er is possible after all.

2015-03-09, 05:09	#9
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2²×19×79 Posts	What about the state of nothing punched? There was no requirement stated to encode a space or anything outside of A-Z.