Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS1730 UNIX/Linux Fundamentals</fs></WRAP>
</WRAP>

======Project: PRACTICING CRITICAL THINKING (pct1)======

=====Errata=====

  * revision #: <description> (DATESTAMP)

=====Objective=====
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.
=====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.

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====
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.

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

Here is an example (using numbers):

First up, we're going to divide 87654321 (the dividend) by 1224 (the divisor). Commonly, especially if punching into a calculator, we might express that equation as:

<code>
87654321/1224
</code>

Or in a language like C, assigning the quotient to the variable **x** (an **int**eger):

<code c>
    x = 87654321/1224;
</code>

But, we're not actually interested in the 'answer' (quotient or remainder); we are interested in the PROCESS. You know, the stuff the calculator does for you, which in order to perform this project and better explore the aspects of critical thinking, we need to take and encounter every step of the way:

<code>
          71613
     +---------
1224 | 87654321
      -8568
       ====
        1974
       -1224
        ====
         7503
        -7344
         ====
          1592
         -1224
          ====
           3681
          -3672
           ====
              9
</code>

Here we obtain the results (focusing on the quotient up top; as the remainder quite literally is what remains once we're done- we're specifically NOT delving into decimal points, but instead doing integer division, which as previously stated has MANY important applications in computing) through a step by step process of seeing how many times our divisor (1224) best and in the smallest fashion fits into some current value of the dividend (or intermediate result thereof).

For instance, seeking the smallest "best fit" of 1224 into 87654321, we find that 1224 fits best SEVEN times (1224 * 7 = 8568, which is the CLOSEST we can get to 8765... 1224 * 8 = 9792, which would be too big (and way too small for 87654). Clearly, we are seeking those values that best fit within a multiple of 0-9, staying away from double digits of multiplication (although, we COULD do it that way and still arrive at the same end result).

So: 8765-8568 = 197.

We have our first result, yet: there's still values in the dividend (87654321) remaining to process, specifically the 4321, so we take them one digit at a time.

The next available, unprocessed digit in 4321 is '4', so we 'drop that down' and append it to our previous result (197), giving us: 1974.

We now see how many times (via single digit multiplication), our divisor (1224) can fit into 1974. As it turns out, just once.

So: 1974-1224 = 750.

And we keep repeating the process until there are no more digits from the dividend to drop down; at which point, we are left with a remainder (in the above problem, the lone '9' at the very bottom; THAT is the remainder).

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====
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).

Here goes:

<code>
        BYI
    +------
ZTT | EKKTK
     -ZTT
      ===
      TYYT
     -TYXT
      ====
        TIK

base: 8
letters: BEIKTXYZ
</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.

So, let us begin.

One aim is to obtain the key to the puzzle, the mapping of the letters to numbers, so I will typically set up an answer key as follows:

|  0  |  |
|  1  |  |
|  2  |  |
|  3  |  |
|  4  |  |
|  5  |  |
|  6  |  |
|  7  |  |

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.

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>
B = { 0, 1, 2, 3, 4, 5, 6, 7 }
E = { 0, 1, 2, 3, 4, 5, 6, 7 }
I = { 0, 1, 2, 3, 4, 5, 6, 7 }
K = { 0, 1, 2, 3, 4, 5, 6, 7 }
T = { 0, 1, 2, 3, 4, 5, 6, 7 }
X = { 0, 1, 2, 3, 4, 5, 6, 7 }
Y = { 0, 1, 2, 3, 4, 5, 6, 7 }
Z = { 0, 1, 2, 3, 4, 5, 6, 7 }
</code>

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:

  * 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).
  * 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.

Updating our chart, we get:

<code>
B = {    1                   }
E = {       2, 3, 4, 5, 6, 7 }
I = { 0                      }
K = {       2, 3, 4, 5, 6, 7 }
T = {       2, 3, 4, 5, 6, 7 }
X = {       2, 3, 4, 5, 6, 7 }
Y = {       2, 3, 4, 5, 6, 7 }
Z = {       2, 3, 4, 5, 6, 7 }
</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).

Some further analysis nets us the following relations:

  * top left subtraction (nothing for it to borrow from, so a guaranteed "greater than or equal to"). With that said:
    * 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:

  * 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).
  * Neither Z nor T is 7 (because they are identified as being less then E).
  * 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.
  * Neither X nor T is 7 (because they are identified as being less than Y).
  * 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.

We can update our chart based on this:

<code>
B = {    1                   }
E = {             4, 5, 6, 7 }
I = { 0                      }
K = {       2, 3, 4, 5, 6, 7 }
T = {       2, 3, 4, 5       }
X = {       2, 3, 4, 5, 6    }
Y = {             4, 5, 6, 7 }
Z = {       2, 3, 4, 5, 6    }
</code>

===Whittling down K and T===

We also have a lead on K, thanks to two identical subtractions taking place, in the top term:

<code>
    KK
    TT
    ==
    YY
</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:

  * 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).
  * similarly, Y << K.

This causes some updates in our relational chains:

  * Z << E
  * 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).

Also, K is not 2, 3, or 4, due to there being three values less than K- T, X, and Y.

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.

The updated chart:

<code>
B = {    1                   }
E = {             4, 5, 6, 7 }
I = { 0                      }
K = {                5, 6, 7 }
T = {       2, 3, 4          }
X = {       2, 3, 4, 5, 6    }
Y = {             4, 5, 6, 7 }
Z = {       2, 3, 4, 5, 6    }
</code>

===Narrowing down T and Y===
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:

<code>
 T:2 3 4 
xY:4 5 6 7
== ========
 T:2 3 4
</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:

<code>
      2  3  4  5  6  7
   x------------------
 2 |  4  6 10 12 14 16
 3 |  6 11 14 17 22 25
 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>

Okay, checking each possibility for TxY=T (first value needs to equal one's place of result):
  * 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

That means we can eliminate some values:
  * T can NOT be 4
  * Y can NOT be 4 or 7

Updating our chart:

<code>
B = {    1                   }
E = {             4, 5, 6, 7 }
I = { 0                      }
K = {                5, 6, 7 }
T = {       2, 3             }
X = {       2, 3, 4, 5, 6    }
Y = {                5, 6    }
Z = {       2, 3, 4, 5, 6    }
</code>

===Finding K, T, and Y===
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
  * T can be 2 or 3
  * Y can be 5 or 6

So let us try every possible subtraction combination:

  * 5-2=3 (nope; 3 is not a possible Y value)
  * 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:

<code>
B = {    1                   }
E = {             4,    6    }
I = { 0                      }
K = {                      7 }
T = {       2                }
X = {          3, 4,    6    }
Y = {                5       }
Z = {          3, 4,    6    }
</code>

===Finding E and Z===
Further optimizations are possible:

  * because we know that Z << E, Z can NOT by 6.
  * 4-3=1, 4-4=0, neither of which are 2 (T).
  * 6-3=3 (no), 6-4=2 (yes)

So, we can identify E as 6, and Z as 4. The chart:

<code>
B = {    1                   }
E = {                   6    }
I = { 0                      }
K = {                      7 }
T = {       2                }
X = {          3,            }
Y = {                5       }
Z = {             4          }
</code>

===Finding X (due to eliminating any other possibilities)===

That leaves no other possibilities for X, placing it at 3.

Our key:

|  0  |  I  |
|  1  |  B  |
|  2  |  T  |
|  3  |  X  |
|  4  |  Z  |
|  5  |  Y  |
|  6  |  E  |
|  7  |  K  |

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.

Your performance on this project will be directly tied to being able to document your process through the puzzle; I have provided this writeup in order to show you an example of what that process may look like.

=====Getting started=====

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:

  * **bonus**
  * **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.

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.

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=====
Solve and document the puzzle.

On your own.

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 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.

====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).

For example, using the example puzzle above:

|  0  |  R  |
|  1  |  B  |
|  2  |  V  |
|  3  |  G  |
|  4  |  P  |
|  5  |  M  |
|  6  |  O  |
|  7  |  L  |
|  8  |  J  |
|  9  |  K  |

We'll want to put them, in order, in our key file:

<cli>
lab46:~/src/unix/pct0$ echo "RBVGPMOLJK" > puzzle.key
lab46:~/src/unix/pct0$ 
</cli>

Want to know what a proper 'key' file should look like? This:

<cli>
lab46:~/src/unix/pct0$ cat puzzle.key
RBVGPMOLJK
lab46:~/src/unix/pct0$ 
</cli>

JUST the letters (and a trailing newline).

====solution documentation====
As stated, a very large part of this project's evaluation will be based on your clear and detailed documentation of how you determined each letter's mapping in the solution key of your puzzle.

Just providing the 'key' will not result in success.

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.

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=====
Want to check to see if your key is correct (ie all letters in the right order)?

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

<cli>
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.

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.

====Look for matching MD5 sum in MANIFEST====
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>
lab46:~/src/unix/pct0$ cat ${PROJECTDIR}/MANIFEST | grep $(md5sum puzzle.key | cut -d' ' -f1) && echo "MATCH FOUND" || echo "NO MATCHES FOUND"
MATCH FOUND
lab46:~/src/unix/pct0$ 
</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.

=====Submission=====
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 '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:
  * 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:

<cli>
$ submit unix pct1 puzzle.key puzzle.solution
Submitting unix project "pct1":
    -> puzzle.key(OK)
    -> 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
</cli>

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

I'll be looking for the following:

<code>
78:pct1:final tally of results (78/78)
*:pct1:puzzle.key file submitted with correct values [7/7]
*:pct1:puzzle.key file formatted according to project specifications [6/6]
*:pct1:puzzle.solution is organized and easy to read [35/35]
*:pct1:puzzle.solution adequately documents discovery of each letter [30/30]
</code>
Lab46 Wiki

User Tools

Site Tools

Page Tools
