haas:fall2019:unix:projects:pct1

This shows you the differences between two versions of the page.

haas:fall2019:unix:projects:pct1 [2019/04/29 18:46] 127.0.0.1 external edit |
haas:fall2019:unix:projects:pct1 [2019/08/15 10:22] (current) wedge |
||
---|---|---|---|

Line 13: | Line 13: | ||

To continue to cultivate your problem solving, critical thinking, analytical, and observation skills. | To continue to cultivate your problem solving, critical thinking, analytical, and observation skills. | ||

- | The aim here is on observation, analysis, and documentation. You are solving and documenting a problem by hand, NOT writing any sort of program. | + | The aim here is on observation, analysis, and documentation. You are solving and documenting a problem by hand, thinking your way through to solution, NOT copying something, NOR writing any sort of program. |

=====Background===== | =====Background===== | ||

The true nature of problem solving frequently involves critical thinking, analytical, and observation skills. Where problems are not solved by memorizing some pre-defined set of answers and regurgitating them mindlessly, but in crafting an elaborate solution from subtle cues and tested, experimental realizations. | The true nature of problem solving frequently involves critical thinking, analytical, and observation skills. Where problems are not solved by memorizing some pre-defined set of answers and regurgitating them mindlessly, but in crafting an elaborate solution from subtle cues and tested, experimental realizations. | ||

Line 19: | Line 19: | ||

This project puts you in contact with such endeavours. | This project puts you in contact with such endeavours. | ||

- | We ramp up the abstraction a bit by altering the number base involved. No longer can you assume decimal values. Be on the lookout for specified bases, and solve in accordance with the available counting digits in that number base. | ||

====Long Division==== | ====Long Division==== | ||

Letter division is a category of logic problem where you would take an ordinary math equation (in long form), and substitute all the numbers for letters, thereby in a direct sense masking the numeric values present that correctly enable the problem to work from start to completion. It is your task, through exploring, experimenting, and playing, to ascertain the numeric value of each letter (as many as 10, one for each numeric value 0-9). | Letter division is a category of logic problem where you would take an ordinary math equation (in long form), and substitute all the numbers for letters, thereby in a direct sense masking the numeric values present that correctly enable the problem to work from start to completion. It is your task, through exploring, experimenting, and playing, to ascertain the numeric value of each letter (as many as 10, one for each numeric value 0-9). | ||

- | For this project we will be focusing on long division, something you learned (and perhaps last experienced, before becoming mindlessly addicted to pressing buttons on a calculator, in grade school). It entails a whole number (integer) division, involving aspects of multiplication, addition (through borrowing), and subtraction (primarily) to arrive at a quotient and a remainder. | + | We will be focusing on long division, something you learned (and perhaps last experienced, before becoming mindlessly addicted to pressing buttons on a calculator), in grade school. It entails a whole number (integer) division, involving aspects addition (through borrowing), and subtraction (primarily) to arrive at a quotient and a remainder, and if applicable: multiplication. |

+ | | ||

+ | There is also a logical/relational aspect to these puzzles, which may well be less familiar territory to some. But so incredibly important when exploring a process and communicating such notions to the computer. | ||

Division is unique in that it produces two 'answers', each serving particular uses in various applications. | Division is unique in that it produces two 'answers', each serving particular uses in various applications. | ||

Line 38: | Line 39: | ||

<code c> | <code c> | ||

- | x = 87654321/1224; | + | x = 87654321 / 1224; |

</code> | </code> | ||

Line 82: | Line 83: | ||

Clearly it is important to have a handle on and understanding of the basic long division process before attempting a letter division problem. So, be sure to try your hand at a few practice problems before proceeding. | Clearly it is important to have a handle on and understanding of the basic long division process before attempting a letter division problem. So, be sure to try your hand at a few practice problems before proceeding. | ||

- | ====Letter Division in other bases: an example==== | + | ====Letter Division: an example==== |

- | Following will be a sample letter division problem, and a documented work-through (solution) of it, much as you will be doing for this project (and to be sure: the aim here is not merely to solve it, but to DOCUMENT HOW YOU SOLVED IT, so just like the 'steps' files you did in various projects, you might want to keep notes as you go along to save you time and sanity). | + | Following will be a sample letter division problem, and a documented work through of it, much as you will be doing for this project (and to be sure: the aim here is not merely to solve it, but to DOCUMENT HOW YOU SOLVED IT. You might want to keep notes as you go along to save you time and sanity). |

Here goes: | Here goes: | ||

<code> | <code> | ||

- | BYI | + | GLJK |

- | +------ | + | +--------- |

- | ZTT | EKKTK | + | KJKK | GLMBRVLR |

- | -ZTT | + | -VKOKL |

- | === | + | ===== |

- | TYYT | + | LJBGV |

- | -TYXT | + | -OKVKG |

- | ==== | + | ===== |

- | TIK | + | JJGKL |

- | + | -LKBKV | |

- | base: 8 | + | ===== |

- | letters: BEIKTXYZ | + | KVRMR |

+ | -JKRKB | ||

+ | ===== | ||

+ | VKMK | ||

+ | | ||

+ | letters: BGJKLMOPRV | ||

</code> | </code> | ||

- | First off, note how this is NO DIFFERENT from the numeric problem above: just instead of numbers, which we've associated some concepts with, here we have letters (being in base 8, each letter maps to a unique number, 0-7). The trick will be to figure out which letter maps to which number. | + | First off, note how this is NO DIFFERENT from the numeric problem above: just instead of numbers, which we've associated some concepts with, here we have letters (each letter maps to a unique number, 0-9). The trick will be to figure out which letter maps to which number. |

So, let us begin. | So, let us begin. | ||

Line 116: | Line 122: | ||

| 6 | | | | 6 | | | ||

| 7 | | | | 7 | | | ||

- | | + | | 8 | | |

- | Again, unlike the other pct letter division puzzles we've looked at, which by default were in base 10 (decimal), these puzzles will be in a base OTHER than that, so we need to be cognizant of the number of available counting digits. Base 8 (octal) has eight counting digits: 0-7. | + | | 9 | | |

Another thing I like to do is set up a more visual representation of what each letter COULD be. I do so in the following form: | Another thing I like to do is set up a more visual representation of what each letter COULD be. I do so in the following form: | ||

<code> | <code> | ||

- | B = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | B = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | E = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | G = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | I = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | J = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | K = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | K = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | T = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | L = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | X = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | M = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | Y = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | O = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | Z = { 0, 1, 2, 3, 4, 5, 6, 7 } | + | P = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

+ | R = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } | ||

+ | V = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } | ||

</code> | </code> | ||

Then, as I figure things out (either what certain are, but mostly, which ones they are NOT), I can mark it up accordingly. | Then, as I figure things out (either what certain are, but mostly, which ones they are NOT), I can mark it up accordingly. | ||

- | ===Determining B and I from initial glances=== | + | Right from the start, we can already make some important connections; looking at EACH of the subtractions taking place, in the left-most position, we see an interesting phenomenon taking place- G-V=0, L-O=0, J-L=0, and K-J=0. |

- | Right from the start, we can already make some important connections: | + | |

+ | Now, since EACH letter is its own unique numeric value, subtracting one letter from another on its own won't result in a value of 0, but being borrowed from will. | ||

+ | | ||

+ | That is: 7-6=1, but (7-1)-6=0. THAT is what is going on here. | ||

+ | | ||

+ | So what we can infer from this, is some very important connections: | ||

+ | | ||

+ | * V is one less than G (I'll write it as: V < G) | ||

+ | * O is one less than L (O < L) | ||

+ | * L is one less than J (L < J) | ||

+ | * J is one less than K (J < K) | ||

+ | | ||

+ | Does that make sense? From looking at the puzzle, those four relations can be made. | ||

+ | | ||

+ | Now, FURTHERMORE, some of those connections are thereby connected. Look at the 'L' and 'J' connections: | ||

+ | | ||

+ | * O < L, but also: L < J | ||

+ | * L < J, but also: J < K | ||

+ | | ||

+ | That implies a further connection, so we can chain them together: | ||

+ | | ||

+ | * O < L < J < K | ||

+ | | ||

+ | So from that initial observation and connection, we now have two disconnected relationships: | ||

+ | | ||

+ | * V < G | ||

+ | * O < L < J < K | ||

+ | | ||

+ | From what we've done so far, we do not know where V,G fall in respect to O,L,J,K. They might be less than, OR greater than. We won't know without further information. | ||

+ | | ||

+ | Yet, even WITH this information, we can update our letter ranges: | ||

- | * the presence of the divisor value as our first subtraction. ZTT * B = ZTT. That's a dead giveaway that B is 1 (just as was the case in the other letter division puzzles). | + | * since V is less than G, we know V can NOT be 9. |

- | * furthermore, the bottom rightmost symbol subtraction: T - T = I. For a position unable to be taken from (nothing to the right), it can neither be greater than nor less than itself (T is T is T). So, what do you get when you subtract the same value from yourself? ZERO. I is 0. | + | * similarly, G can NOT be 0. |

+ | * O cannot be 9, 8, 7, because we know O is 3 less than K. So even though we don't know what K actually is, because K COULD be 9, we know what O, L, and J can NOT be. | ||

+ | * L cannot be 9 or 8 | ||

+ | * J cannot be 9 | ||

+ | * on the other side, K cannot be 0, 1, or 2 | ||

+ | * J cannot be 0 or 1 | ||

+ | * L cannot be 0. | ||

- | Updating our chart, we get: | + | So, if we update our range chart accordingly: |

<code> | <code> | ||

- | B = { 1 } | + | B = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } |

- | E = { 2, 3, 4, 5, 6, 7 } | + | G = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | I = { 0 } | + | J = { 2, 3, 4, 5, 6, 7, 8, } |

- | K = { 2, 3, 4, 5, 6, 7 } | + | K = { 3, 4, 5, 6, 7, 8, 9 } |

- | T = { 2, 3, 4, 5, 6, 7 } | + | L = { 1, 2, 3, 4, 5, 6, 7, } |

- | X = { 2, 3, 4, 5, 6, 7 } | + | M = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | Y = { 2, 3, 4, 5, 6, 7 } | + | O = { 0, 1, 2, 3, 4, 5, 6, } |

- | Z = { 2, 3, 4, 5, 6, 7 } | + | P = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

+ | R = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } | ||

+ | V = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } | ||

</code> | </code> | ||

- | Really no difference than before. In many ways, especially when taking a purely logical/relational approach, there won't be any difference (doing actual math: multiplication, addition, subtraction will also work the same, although we need to be mindful of the counting digits of the base). | + | Moving on, dealing with details of discovering those one-off relations, that tells us something about the NEXT subtractions: that they borrow (which means they are LESS THAN the thing being subtracted from them): |

- | Some further analysis nets us the following relations: | + | * L is less than K (which we actually know to be 2 less than K), so L - K needs to BORROW |

+ | * J is less than K (which we know is 1 less than K), so J - K needs to BORROW | ||

+ | * V is apparently also less than K (which we didn't previously know), so V - K needs to BORROW | ||

+ | * now knowing than V << K, we can connect our other relational fragment in (I use the double '<<' to denote "less than" by an unknown amount, because while we know V is less than K, we don't know by how much). | ||

- | * top left subtraction (nothing for it to borrow from, so a guaranteed "greater than or equal to"). With that said: | + | So: V < G << O < L < J < K |

- | * Z << E | + | |

- | * T << E | + | |

- | * bottom subtraction, the third in from the left, after the T-T and Y-Y. Because the Y-Y cancelled out (zero), we no it wasn't taken from, so Y is greater than X: | + | |

- | * X << Y | + | |

- | * T << Y | + | |

- | From this we can determine: | + | This allows us some further whittling of our ranges: |

- | * E is not 2 or 3 (since 0 and 1 are defined, and our relations show there are two identified additional letters that come before E). | + | * V cannot be 9, 8, 7, 6, or 5 |

- | * Neither Z nor T is 7 (because they are identified as being less then E). | + | * G cannot be 9, 8, 7, or 6 |

- | * Y is also not 2 or 3, due to X and T being identified as less than it, and neither X nor T are 0 or 1. | + | * O cannot be 0, or 1 |

- | * Neither X nor T is 7 (because they are identified as being less than Y). | + | * L cannot be 0, 1, or 2 |

- | * Additionally, because we've got TWO connections on T (it is less than E, AND it is less than Y), T also cannot be 6. | + | * J cannot be 0, 1, 2, or 3 |

- | | + | * K cannot be 0, 1, 2, 3, or 4 |

- | We can update our chart based on this: | + | |

<code> | <code> | ||

- | B = { 1 } | + | B = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } |

- | E = { 4, 5, 6, 7 } | + | G = { 1, 2, 3, 4, 5, } |

- | I = { 0 } | + | J = { 4, 5, 6, 7, 8, } |

- | K = { 2, 3, 4, 5, 6, 7 } | + | K = { 5, 6, 7, 8, 9 } |

- | T = { 2, 3, 4, 5 } | + | L = { 3, 4, 5, 6, 7, } |

- | X = { 2, 3, 4, 5, 6 } | + | M = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

- | Y = { 4, 5, 6, 7 } | + | O = { 2, 3, 4, 5, 6, } |

- | Z = { 2, 3, 4, 5, 6 } | + | P = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } |

+ | R = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } | ||

+ | V = { 0, 1, 2, 3, 4, } | ||

</code> | </code> | ||

- | ===Whittling down K and T=== | + | Already we can see that V and G are likely lower numbers, and O, L, J, and K are likely higher numbers. |

- | We also have a lead on K, thanks to two identical subtractions taking place, in the top term: | + | What else do we have? Let's keep going: |

+ | | ||

+ | We cannot instantly proceed to the next subtraction in as obvious a progression, as we'll need more information on the various letters involved. | ||

+ | | ||

+ | ===Finding K (and J and L and O as well)=== | ||

+ | However, looking at the puzzle, I'm interested in seeing if we can find any obvious examples of 0. You know, letter minus same letter sort of things. Because they will typically end up equalling 0 (or 9). | ||

+ | | ||

+ | Why 9? Because of a borrow! | ||

+ | | ||

+ | ((5-1)+10)-5 = (4+10)-5 = 14 - 5 = 9 | ||

+ | | ||

+ | ... that can be quite revealing too! | ||

+ | | ||

+ | And it would appear we have one wonderful candidate in the bottom-most subtraction: | ||

<code> | <code> | ||

- | KK | + | KVRMR |

- | TT | + | -JKRKB |

- | == | + | ===== |

- | YY | + | VKMK |

</code> | </code> | ||

- | See that? While in isolation, we don't have any clear read on K's relationship to T (we don't immediately know if the leftmost E-Z=T is being taken from), from these two identical examples, we can now tell: | + | Lookie there: R-R = K. |

- | * T << K, because if K was less than T, it would need to borrow, and because the rightmost K-T equals the left K-T (they both equal Y), no borrowing is happening (because there's nothing further to the right to take from the rightmost K). | + | Usually, that would result in a 0. BUT, we also know that K can NOT be 0 (looking at our range table above). |

- | * similarly, Y << K. | + | |

- | This causes some updates in our relational chains: | + | So, that means it is being borrowed from, and it itself has to borrow, so we now also know that M is less than K (M << K). |

- | * Z << E | + | And, as indicated above: |

- | * T << E | + | |

- | * X << Y << K | + | |

- | * T << Y << K | + | |

- | In our chart, T cannot be 7, 6, or 5 (since there are now THREE identified values greater than T- E, Y, and K). | + | ((R-1)+10)-R = 9! |

- | Also, K is not 2, 3, or 4, due to there being three values less than K- T, X, and Y. | + | We now know that K = 9! |

- | Even though T is less than E, we do not know E's relationship to Y or K (it could be greater than K or it could be less than K), so we cannot act on that particular facet of the problem yet. | + | That suddenly reveals a whole lot to us, due to our relational chains we've built. Let's update: |

- | The updated chart: | + | | 0 | | |

+ | | 1 | | | ||

+ | | 2 | | | ||

+ | | 3 | | | ||

+ | | 4 | | | ||

+ | | 5 | | | ||

+ | | 6 | O | | ||

+ | | 7 | L | | ||

+ | | 8 | J | | ||

+ | | 9 | K | | ||

+ | | ||

+ | Also, with the new introduction of M being less than K: | ||

<code> | <code> | ||

- | B = { 1 } | + | B = { 0, 1, 2, 3, 4, 5, } |

- | E = { 4, 5, 6, 7 } | + | G = { 1, 2, 3, 4, 5, } |

- | I = { 0 } | + | J = { 8 } |

- | K = { 5, 6, 7 } | + | K = { 9 } |

- | T = { 2, 3, 4 } | + | L = { 7 } |

- | X = { 2, 3, 4, 5, 6 } | + | M = { 0, 1, 2, 3, 4, 5, } |

- | Y = { 4, 5, 6, 7 } | + | O = { 6 } |

- | Z = { 2, 3, 4, 5, 6 } | + | P = { 0, 1, 2, 3, 4, 5, } |

+ | R = { 0, 1, 2, 3, 4, 5, } | ||

+ | V = { 0, 1, 2, 3, 4, } | ||

</code> | </code> | ||

- | ===Narrowing down T and Y=== | + | And, our relational chains: |

- | At this point, we've largely exhausted our logical/relational analysis, and will need to make use of some of the math. There are NO borrows happening in this problem, so onto the multiplication: | + | |

- | Since B is 1, we'll skip to the Y multiplication: | + | * V < G << O < L < J < K |

+ | * M << O < L < J < K | ||

+ | | ||

+ | Because we don't yet know any relation of M compared to V or G, we have to keep them separate for now. | ||

+ | | ||

+ | We also have a second disqualifier for K being 0... the ones place subtraction in that bottom-most subtraction: | ||

+ | | ||

+ | R - B = K. | ||

+ | | ||

+ | There's nothing further to the right that could borrow from this problem, so it can only exist in two states: | ||

+ | | ||

+ | * R is greater than B | ||

+ | * R is less than B | ||

+ | | ||

+ | Since we know that K is 9, there's NO OTHER pair of single digit numbers we can subtract to get 9, which tells us that: | ||

+ | | ||

+ | * R is less than B (R << B) | ||

+ | | ||

+ | Currently both R and B can be 0-5 (although now, B is 1-5, and R is 0-4). We'd need to find a combination where (R+10)-B is 9: | ||

+ | ^ R: 0 ^ R: 1 ^ R: 2 ^ R: 3 ^ R: 4 | | ||

+ | | (0+10) | (1+10) | (2+10) | (3+10) | (4+10) | | ||

+ | | 10 | 11 | 12 | 13 | 14 | | ||

+ | | ||

+ | And from that, we're subtracting B, which is 1, 2, 3, 4, or 5. The answer has to be 9. | ||

+ | | ||

+ | So: | ||

+ | | ||

+ | 10-1=9, 11-2=9, 12-3=9, 13-4=9, and 14-5=9 | ||

+ | | ||

+ | Hey, look at that... B is one greater than R (not just R << B, BUT: R < B) | ||

+ | | ||

+ | Our relational chains: | ||

+ | | ||

+ | * V < G << O < L < J < K | ||

+ | * M << O < L < J < K | ||

+ | * R < B << O < L < J < K | ||

+ | | ||

+ | And our chart, of sorts: | ||

<code> | <code> | ||

- | T:2 3 4 | + | B = { 1, 2, 3, 4, 5, } |

- | xY:4 5 6 7 | + | G = { 1, 2, 3, 4, 5, } |

- | == ======== | + | J = { 8 } |

- | T:2 3 4 | + | K = { 9 } |

+ | L = { 7 } | ||

+ | M = { 0, 1, 2, 3, 4, 5, } | ||

+ | O = { 6 } | ||

+ | P = { 0, 1, 2, 3, 4, 5, } | ||

+ | R = { 0, 1, 2, 3, 4, } | ||

+ | V = { 0, 1, 2, 3, 4, } | ||

</code> | </code> | ||

- | Now, while this is multiplication, it is NOT decimal multiplication. We need to multiply in octal. Therefore it might help to have our multiplication tables handy for base 8 for values 2-7: | + | If you look, the only letter we've not yet directly interacted with yet is 'P', although we already know enough about it (that it is 0-5, less than O, L, J, and K). And if you look closely, you'll notice that 'P' isn't even present in the letter division problem! So its identity will rely entirely on the proving of the other values. |

+ | | ||

+ | Let's continue on: | ||

+ | | ||

+ | M-K=M, BECAUSE we know M << K, AND BECAUSE we know the subtraction to the right is borrowing from it (because R < B), we have something like this: (M-1+10)-K=M | ||

+ | | ||

+ | Can't really do much more with it at this point, but it is important to know to help us identify the borrows needing to happen. | ||

+ | | ||

+ | ===Finding our zero value (R and B)=== | ||

+ | Why don't we go ahead and find 0? If you look in the subtraction above the bottom one, we have another "letter minus same letter" scenario, and it doesn't equal K! | ||

<code> | <code> | ||

- | 2 3 4 5 6 7 | + | JJGKL |

- | x------------------ | + | -LKBKV |

- | 2 | 4 6 10 12 14 16 | + | ===== |

- | 3 | 6 11 14 17 22 25 | + | KVRM |

- | 4 | 10 14 20 24 30 34 | + | |

- | 5 | 12 17 24 31 36 43 | + | |

- | 6 | 14 22 30 36 44 52 | + | |

- | 7 | 16 25 34 43 52 61 | + | |

</code> | </code> | ||

- | Okay, checking each possibility for TxY=T (first value needs to equal one's place of result): | + | We KNOW that V << L, so no borrow is happening there. |

- | * 2x4 = 10 (one's place is not a 2, so this isn't it) | + | |

- | * 2x5 = 12 (a possibility!) | + | |

- | * 2x6 = 14 (nope) | + | |

- | * 2x7 = 16 (nope) | + | |

- | * 3x4 = 14 (nope) | + | |

- | * 3x5 = 17 (nope) | + | |

- | * 3x6 = 22 (a possibility!) | + | |

- | * 3x7 = 25 (nope) | + | |

- | * 4x4 = 20 (nope; also, not possible, since T and Y cannot be the same value) | + | |

- | * 4x5 = 24 (nope) | + | |

- | * 4x6 = 30 (nope) | + | |

- | * 4x7 = 34 (nope) | + | |

- | Out of twelve possible multiplications, only TWO are valid possibilities: 2x5 and 3x6 | + | Therefore, K-K, or 9-9, equals 0. So R is 0! |

- | That means we can eliminate some values: | + | ... and B is 1! Because of our identified relationship. |

- | * T can NOT be 4 | + | |

- | * Y can NOT be 4 or 7 | + | |

- | Updating our chart: | + | Updating things! |

+ | | ||

+ | | 0 | R | | ||

+ | | 1 | B | | ||

+ | | 2 | | | ||

+ | | 3 | | | ||

+ | | 4 | | | ||

+ | | 5 | | | ||

+ | | 6 | O | | ||

+ | | 7 | L | | ||

+ | | 8 | J | | ||

+ | | 9 | K | | ||

+ | | ||

+ | Also, with the new introduction of M being less than K: | ||

<code> | <code> | ||

- | B = { 1 } | + | B = { 1 } |

- | E = { 4, 5, 6, 7 } | + | G = { 3, 4, 5, } |

- | I = { 0 } | + | J = { 8 } |

- | K = { 5, 6, 7 } | + | K = { 9 } |

- | T = { 2, 3 } | + | L = { 7 } |

- | X = { 2, 3, 4, 5, 6 } | + | M = { 2, 3, 4, 5, } |

- | Y = { 5, 6 } | + | O = { 6 } |

- | Z = { 2, 3, 4, 5, 6 } | + | P = { 2, 3, 4, 5, } |

+ | R = { 0 } | ||

+ | V = { 2, 3, 4, } | ||

</code> | </code> | ||

- | ===Finding K, T, and Y=== | + | *NOTE: G is NOT 2, because G is greater than V (one greater, in fact), so we can similarly whittle that off. |

- | With a reduced set of values, we can revisit one of our subtractions, the K-T=Y, specifically. | + | |

- | * K can be 5, 6, or 7 | + | Relational chains can look as follows now: |

- | * T can be 2 or 3 | + | |

- | * Y can be 5 or 6 | + | |

- | So let us try every possible subtraction combination: | + | * R < B << V < G << O < L < J < K |

+ | * R < B << M << O < L < J < K | ||

+ | * R < B << P << O < L < J < K | ||

- | * 5-2=3 (nope; 3 is not a possible Y value) | + | Basically just down to V, G, P, and M. |

- | * 5-3=2 (nope) | + | |

- | * 6-2=4 (nope) | + | |

- | * 6-3=3 (nope; also T and Y cannot be the same) | + | |

- | * 7-2=5 (possibility!) | + | |

- | * 7-3=4 (nope) | + | |

- | And lookie here! The ONLY identified possibility occurs when K is 7, T is 2, and Y is 5! Let's update our chart accordingly: | + | ===Finding V and G=== |

+ | And I think we have the means to find V: notice the second to last subtraction, the "LKBKV". You know where we get that from? Multiplying the divisor (KJKK) by J (since it is the third subtraction taking place). | ||

+ | | ||

+ | We KNOW the numeric values of K and J, in fact we know the values of L, K, and B. The only thing we don't know is 'V', and since V is in the one's place, that makes things super easy for us. | ||

+ | | ||

+ | KJKK = 9899 | ||

+ | J = 8 | ||

+ | | ||

+ | So: 9899 x 8 = 79192 = LKBKV! | ||

+ | | ||

+ | V is 2! | ||

+ | | ||

+ | Which means, because V < G, that G is 3! | ||

+ | | ||

+ | Updating our records: | ||

+ | | ||

+ | | 0 | R | | ||

+ | | 1 | B | | ||

+ | | 2 | V | | ||

+ | | 3 | G | | ||

+ | | 4 | | | ||

+ | | 5 | | | ||

+ | | 6 | O | | ||

+ | | 7 | L | | ||

+ | | 8 | J | | ||

+ | | 9 | K | | ||

+ | | ||

+ | Also, with the new introduction of M being less than K: | ||

<code> | <code> | ||

- | B = { 1 } | + | B = { 1 } |

- | E = { 4, 6 } | + | G = { 3 } |

- | I = { 0 } | + | J = { 8 } |

- | K = { 7 } | + | K = { 9 } |

- | T = { 2 } | + | L = { 7 } |

- | X = { 3, 4, 6 } | + | M = { 4, 5, } |

- | Y = { 5 } | + | O = { 6 } |

- | Z = { 3, 4, 6 } | + | P = { 4, 5, } |

+ | R = { 0 } | ||

+ | V = { 2 } | ||

</code> | </code> | ||

- | ===Finding E and Z=== | + | Relational chains can look as follows now: |

- | Further optimizations are possible: | + | |

- | * because we know that Z << E, Z can NOT by 6. | + | * R < B < V < G << M << O < L < J < K |

- | * 4-3=1, 4-4=0, neither of which are 2 (T). | + | * R < B < V < G << P << O < L < J < K |

- | * 6-3=3 (no), 6-4=2 (yes) | + | |

- | So, we can identify E as 6, and Z as 4. The chart: | + | ===Finding M and discovering P=== |

+ | And then there were 2. We really just need to find M, or P, and we're done. And since there are no 'P' values in the puzzle, we need to target M. So let's look for some candidates: | ||

+ | | ||

+ | Hey, how about this: | ||

<code> | <code> | ||

- | B = { 1 } | + | JJGKL |

- | E = { 6 } | + | -LKBKV |

- | I = { 0 } | + | ===== |

- | K = { 7 } | + | KVRM |

- | T = { 2 } | + | |

- | X = { 3, } | + | |

- | Y = { 5 } | + | |

- | Z = { 4 } | + | |

</code> | </code> | ||

- | ===Finding X (due to eliminating any other possibilities)=== | + | One's place subtraction: L - V = M. |

- | That leaves no other possibilities for X, placing it at 3. | + | We KNOW L (7) is greater than V (2), so no borrow is happening. |

- | Our key: | + | L-V=M |

+ | 7-2=5 | ||

- | | 0 | I | | + | M is 5. That means P is 4 by process of elimination. |

+ | | ||

+ | Puzzle completed: | ||

+ | | ||

+ | | 0 | R | | ||

| 1 | B | | | 1 | B | | ||

- | | 2 | T | | + | | 2 | V | |

- | | 3 | X | | + | | 3 | G | |

- | | 4 | Z | | + | | 4 | P | |

- | | 5 | Y | | + | | 5 | M | |

- | | 6 | E | | + | | 6 | O | |

- | | 7 | K | | + | | 7 | L | |

+ | | 8 | J | | ||

+ | | 9 | K | | ||

+ | | ||

+ | Also, with the new introduction of M being less than K: | ||

+ | | ||

+ | <code> | ||

+ | B = { 1 } | ||

+ | G = { 3 } | ||

+ | J = { 8 } | ||

+ | K = { 9 } | ||

+ | L = { 7 } | ||

+ | M = { 5 } | ||

+ | O = { 6 } | ||

+ | P = { 4 } | ||

+ | R = { 0 } | ||

+ | V = { 2 } | ||

+ | </code> | ||

+ | | ||

+ | Relational chains can look as follows now: | ||

+ | | ||

+ | * R < B < V < G < P < M < O < L < J < K | ||

+ | | ||

+ | I wasn't able to show it as well in text on the wiki, but I also made a point to mark up each subtraction to show whether a borrow occurred or not: | ||

+ | | ||

+ | {{ :undefined:borrows.jpg?400 |}} | ||

To be sure, there are likely MANY, MANY ways to arrive at these conclusions. What is important is being observant, performing little experiments, seeing if there can be any insights to have, even if whittling away knowing what things can NOT be. | To be sure, there are likely MANY, MANY ways to arrive at these conclusions. What is important is being observant, performing little experiments, seeing if there can be any insights to have, even if whittling away knowing what things can NOT be. | ||

Line 354: | Line 519: | ||

=====Getting started===== | =====Getting started===== | ||

+ | In the **pct0/** sub-directory of the UNIX Public Directory, under a directory by the name of your username, you will find the following file: | ||

- | In the **pct1/** sub-directory of the UNIX Public Directory, under a directory by the name of your username, you will find the following files: | + | * **pct0.puzzle** |

- | * **bonus** | + | Copy this file into your local project directory. |

- | * **practice0** | + | |

- | * **practice1** | + | |

- | * **practice2** | + | |

- | * **practice3** | + | |

- | * **puzzle** | + | |

- | | + | |

- | Copy these file into your project directory. | + | |

There is also a **MANIFEST** file in the parent directory (the **pct0/** sub-directory), which will contain MD5sums of the various puzzle keys, provided to help you in verifying your puzzle key. | There is also a **MANIFEST** file in the parent directory (the **pct0/** sub-directory), which will contain MD5sums of the various puzzle keys, provided to help you in verifying your puzzle key. | ||

- | For this project, the only puzzle you HAVE to solve in order to be eligible for full credit will be the one contained in the **puzzle** file. | + | For this project, you have to solve, DOCUMENT, AND VERIFY the provided puzzle in order to be eligible for full credit will be the one contained in the **puzzle** file. |

- | Should you desire, there's an opportunity to gain some bonus points, which can be earned by successfully solving and documenting your solution to the puzzle contained within the file **bonus** and reporting it to me as appropriate. | ||

- | |||

- | As you gear up to work on the project-required puzzle (or additionally the bonus puzzle), I have provided a sampling of practice puzzles that you can try your hand on in order to get more experience working with these type of puzzles. Doing them will not net you any points, nor will not doing them diminish your totals for this project. I would recommend doing them, though, as the more exposure you have within this domain, the more patterns become identified, further facilitating your chances of success. | ||

=====Process===== | =====Process===== | ||

- | Solve and document the puzzle. | + | Solve, document, and verify the puzzle. |

On your own. | On your own. | ||

Seek to discover and explore and understand, NOT to just come up with an answer. | Seek to discover and explore and understand, NOT to just come up with an answer. | ||

- | =====Your Solution===== | ||

- | As this project focuses more on the critical thinking process than being heavy in unravelling a problem using UNIX commands, your solution will be in 2 parts: | ||

- | * your puzzle key, in a textfile called 'puzzle.key' containing ONLY the capital letters corresponding in order to the 0-9 values (and a trailing newline). | + | =====Your Submission===== |

- | * your documentation of your solving and exploration of the puzzle. If you did this on paper, I'll want it digitized and submitted as a file with this project. The file, if is text form, should be called 'puzzle.solution'; if an image, please append the image format to the end of the filename. | + | As this project focuses more on the critical thinking process than being heavy in unravelling a problem, your submission will be in 3 parts: |

+ | | ||

+ | * your puzzle key, in a textfile called 'pct0.puzzle.key' containing ONLY the capital letters corresponding in order to the 0-9 values (and a trailing newline). | ||

+ | * your documentation of your solving and exploration of the puzzle. If you did this on paper, will need to transcribe it out into clearly readable, organized, and followable text directions. The file, in text form, should be called 'pct0.puzzle.solution'. Images of your notes will NOT be accepted for submission. | ||

====puzzle key==== | ====puzzle key==== | ||

- | As indicated, you are to place the determined key to your puzzle in a regular text file called 'puzzle.key', and will contain ONLY the capital letters, in order from 0-9, of your puzzle (and a trailing newline). | + | As indicated, you are to place the determined key to your puzzle in a regular text file called 'pct0.puzzle.key', and will contain ONLY the capital letters, in order from 0-9, of your puzzle (and a trailing newline). |

For example, using the example puzzle above: | For example, using the example puzzle above: | ||

Line 404: | Line 561: | ||

<cli> | <cli> | ||

- | lab46:~/src/unix/pct0$ echo "RBVGPMOLJK" > puzzle.key | + | lab46:~/src/unix/pct0$ echo "RBVGPMOLJK" > pct0.puzzle.key |

lab46:~/src/unix/pct0$ | lab46:~/src/unix/pct0$ | ||

</cli> | </cli> | ||

Line 411: | Line 568: | ||

<cli> | <cli> | ||

- | lab46:~/src/unix/pct0$ cat puzzle.key | + | lab46:~/src/unix/pct0$ cat pct0.puzzle.key |

RBVGPMOLJK | RBVGPMOLJK | ||

lab46:~/src/unix/pct0$ | lab46:~/src/unix/pct0$ | ||

Line 425: | Line 582: | ||

Your documentation should, while there may be supporting information, provide some identified path that showed the steps you went through to identify each letter, be it directly or indirectly. | Your documentation should, while there may be supporting information, provide some identified path that showed the steps you went through to identify each letter, be it directly or indirectly. | ||

- | You are free to write out your solution with pen on paper (that is how I usually do these puzzles); but if you do so, you MUST digitize it and submit it as an image file when you submit this project. | + | You are free to write out your solution with pen on paper (that is how I usually do these puzzles); but if you do so, you MUST transcribe it to text and submit it in that format. Images will NOT be accepted. |

+ | | ||

+ | The aim here is not to dump a bunch of data on me, but instead present me with connected and pertinent information that documents your process of progression through the puzzle from start to finish. This is in the same vein as programming in a language on a computer. A computer program is a detailed description of a process to solving some problem in a format the receiver can understand. | ||

- | The aim here is not to dump a bunch of data on me, but instead present me with connected and pertinent information that documents your process of progression through the puzzle from start to finish. | ||

=====Verification===== | =====Verification===== | ||

- | Want to check to see if your key is correct (ie all letters in the right order)? | + | In addition to documenting the process of solving the puzzle, and coming up with a solution, you are to manually verify your solution by taking the numeric identities of each letter, plugging them back into the original puzzle, solving it, and converting the obtained quotient and remainder back into letter form to compare with those in the puzzle provided to you. If they match, you have successfully solved the puzzle. If they do not match, some error exists that should be addressed and corrected. |

- | ====Generate MD5 sum==== | + | The verification can go at the bottom of your solution file, after you've documented your puzzle from start to completion. |

- | You can do so, by generating an MD5 sum of your 'key' file and grepping for it in the MANIFEST file: | + | |

- | <cli> | + | An example of a verification text is as follows: |

- | lab46:~/src/unix/pct0$ md5sum puzzle.key | cut -d' ' -f1 | + | |

- | 1395327d0826e3145b4f285a2b936707 | + | |

- | lab46:~/src/unix/pct0$ | + | |

- | </cli> | + | |

- | Obviously, YOUR MD5 sum will be DIFFERENT from this, because this is the MD5 sum of the puzzle key explored at the top of this project page. | + | ====Verifying our key==== |

+ | The best way to verify the puzzle with our key is to convert the dividend and divisor to its numeric equivalent, perform the division, and compare the resulting quotient and remainder against those found in the letterified puzzle: | ||

- | NOTE: MD5 sums of your bonus and practice puzzles are also present in the MANIFEST file, so you can perform verifications on them in the same manner. | + | * divisor: KJKK --> 9899 |

+ | * dividend: GLMBRVLR --> 37510270 | ||

- | ====Look for matching MD5 sum in MANIFEST==== | + | And let's do some long division! |

- | Let's say the path to the **pct0/** sub-directory of the public directory is in a variable called PROJECTDIR; if so, you can check your MD5 sum for a match in MANIFEST as follows: | + | |

- | <cli> | + | <code> |

- | lab46:~/src/unix/pct0$ cat ${PROJECTDIR}/MANIFEST | grep $(md5sum puzzle.key | cut -d' ' -f1) && echo "MATCH FOUND" || echo "NO MATCHES FOUND" | + | +--------- |

- | MATCH FOUND | + | 9899 | 37510270 |

- | lab46:~/src/unix/pct0$ | + | </code> |

- | </cli> | + | |

- | If you have a match, congratulations, you unravelled the puzzle correctly. Just remember: evaluation is heavily based on your documentation of the process, not whether or not you can arrive at the correct answer key. | + | 9899 goes into 37510 three times: |

+ | <code> | ||

+ | 3 | ||

+ | +--------- | ||

+ | 9899 | 37510270 | ||

+ | -29697 | ||

+ | ===== | ||

+ | 78132 | ||

+ | </code> | ||

+ | |||

+ | It might be convenient to have a quick factor reference for 9899 handy: | ||

+ | |||

+ | * 9899 * 0 = 0 | ||

+ | * 9899 * 1 = 9899 | ||

+ | * 9899 * 2 = 19798 | ||

+ | * 9899 * 3 = 29697 | ||

+ | * 9899 * 4 = 39596 | ||

+ | * 9899 * 5 = 49495 | ||

+ | * 9899 * 6 = 59394 | ||

+ | * 9899 * 7 = 69293 | ||

+ | * 9899 * 8 = 79192 | ||

+ | * 9899 * 9 = 89091 | ||

+ | |||

+ | 9899 fits into 78132 seven times (69293): | ||

+ | |||

+ | <code> | ||

+ | 37 | ||

+ | +--------- | ||

+ | 9899 | 37510270 | ||

+ | -29697 | ||

+ | ===== | ||

+ | 78132 | ||

+ | -69293 | ||

+ | ===== | ||

+ | 88397 | ||

+ | </code> | ||

+ | |||

+ | Once again, looking at the list of factors, we see that the best fit for 9899 into 88397 is 79192 (a factor of 8): | ||

+ | |||

+ | <code> | ||

+ | 378 | ||

+ | +--------- | ||

+ | 9899 | 37510270 | ||

+ | -29697 | ||

+ | ===== | ||

+ | 78132 | ||

+ | -69293 | ||

+ | ===== | ||

+ | 88397 | ||

+ | -79192 | ||

+ | ===== | ||

+ | 92050 | ||

+ | </code> | ||

+ | |||

+ | Finally, a factor of 9 (89091) fits in best: | ||

+ | |||

+ | <code> | ||

+ | 3789 <-- quotient | ||

+ | +--------- | ||

+ | 9899 | 37510270 | ||

+ | -29697 | ||

+ | ===== | ||

+ | 78132 | ||

+ | -69293 | ||

+ | ===== | ||

+ | 88397 | ||

+ | -79192 | ||

+ | ===== | ||

+ | 92050 | ||

+ | -89091 | ||

+ | ===== | ||

+ | 2959 <-- remainder | ||

+ | </code> | ||

+ | |||

+ | Converting our quotient and remainder back to letters: | ||

+ | |||

+ | * quotient: 3789 --> GLJK | ||

+ | * remainder: 2959 --> VKMK | ||

+ | |||

+ | And comparing against the problem we were given: | ||

+ | |||

+ | * quotient: GLJK <-> GLJK | ||

+ | * remainder: VKMK <-> VKMK | ||

+ | |||

+ | Success! | ||

=====Submission===== | =====Submission===== | ||

By successfully performing this project, you should be submitting files that satisfy the following requirements: | By successfully performing this project, you should be submitting files that satisfy the following requirements: | ||

- | * a 'puzzle.key' file formatted as indicated elsewhere in this project document | + | * a 'pctX.puzzle.key' file formatted as indicated elsewhere in this project document |

- | * a 'puzzle.solution' file containing organized and informative detailing of your path to solution | + | * a 'pctX.puzzle.solution' file containing organized and informative detailing of your path to solution |

- | Additionally, although optional, if you'd like to do similar for the bonus puzzle: | + | NOTE: Please substitute the actual project number in place of the 'X' in pctX. |

- | * a 'bonus.key' file formatted as indicated elsewhere in this project document | + | |

- | * a 'bonus.solution' file containing organized and informative detailing of your path to solution | + | |

To submit this project to me using the **submit** tool, run the following command at your lab46 prompt: | To submit this project to me using the **submit** tool, run the following command at your lab46 prompt: | ||

<cli> | <cli> | ||

- | $ submit unix pct1 puzzle.key puzzle.solution | + | $ submit unix pctX pctX.puzzle.key pctX.puzzle.solution |

- | Submitting unix project "pct1": | + | Submitting unix project "pctX": |

- | -> puzzle.key(OK) | + | -> pctX.puzzle.key(OK) |

- | -> puzzle.solution(OK) | + | -> pctX.puzzle.solution(OK) |

- | | + | |

- | SUCCESSFULLY SUBMITTED | + | |

- | </cli> | + | |

- | | + | |

- | or, if submitting results for the bonus puzzle as well: | + | |

- | | + | |

- | <cli> | + | |

- | $ submit unix pct1 puzzle.key puzzle.solution bonus.key bonus.solution | + | |

- | Submitting unix project "pct1": | + | |

- | -> puzzle.key(OK) | + | |

- | -> puzzle.solution(OK) | + | |

- | -> bonus.key(OK) | + | |

- | -> bonus.solution(OK) | + | |

SUCCESSFULLY SUBMITTED | SUCCESSFULLY SUBMITTED | ||

Line 494: | Line 716: | ||

<code> | <code> | ||

- | 78:pct1:final tally of results (78/78) | + | XX:pctX:final tally of results (XX/XX) |

- | *:pct1:puzzle.key file submitted with correct values [7/7] | + | *:pctX:puzzle.key file submitted with correct values [#/#] (lower half of one-third) |

- | *:pct1:puzzle.key file formatted according to project specifications [6/6] | + | *:pctX:puzzle.solution documents discovery of each letter [#/#] (two-thirds) |

- | *:pct1:puzzle.solution is organized and easy to read [35/35] | + | *:pctX:puzzle.solution verifies solution through performing problem [#/#] (upper half of one-third) |

- | *:pct1:puzzle.solution adequately documents discovery of each letter [30/30] | + | |

</code> | </code> | ||

+ | |||

+ | Additional points of consideration: | ||

+ | |||

+ | * if any restrictions are in force and they are ignored in the solving of the problem, up to 50% of credit can be deducted. | ||

+ | * if solution is messy and disorganized, up to 50% of credit can be deducted. |

haas/fall2019/unix/projects/pct1.txt · Last modified: 2019/08/15 10:22 by wedge

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International