Site Navigation

Solution 3: coding algorithms

  • Part A making patterns
    • Examine the code Oct1 and Oct2 (below).
      1. What do they do? Why are they considered zig-zag patterns?
          This uses a spiral algorithm with alternating colours. The zig-zag pattern comes from the psuedo-spacers--one twists one way followed by another than twists the other way.
      2. Which one is the most efficient in term of number of instructions? Explain.
          Oct2 is more efficient since it does not have the extra octagons that are not painted but are used only to check if the area has already been paintex.
      3. Which program contains more semantic information? Explain.
          Oct2 contains more semantic information because the path and pathback imply a relationship between the chunks of code. This helps us find meaning in the code by breaking it down into chunks that are named to indicate their purpose.
      4. In Oct2, modify path and pathBack to create the pattern in the figure below. Explain the relationship between path and pathBack. 
          path {
 sides 7
 paint purple
 2 left
 2{
    sides 4
    paint purple
 }
}
//-----------------------
pathBack {
 2{
    sides 4
    paint purple
 }
 sides 7
 paint purple
 right
}
      5. Modify path and pathBack to create your own interesting pattern. 
          path {
  sides 5
  paint purple
  left 
  sides 3
  paint purple
  left
  create extra
  right
}
//-----------------------
pathBack {
  sides 3
  paint purple
  create extra
  left
  sides 5
  paint purple
}
//-----------------------
extra {
  sides 4
  paint red
  sides 3
  paint red
}
      1. Which program has the fewer lines of code Oct3 or Oct2?
          Oct3. (40 versus 51)
      2. For the same area of the pattern which uses more paints?
          Oct3. Every triangle gets painted twice in Oct3 whereas only some of the triangles get painted twice.
      3. How does Oct3 differ from the standard expand program?
          It has an alternation of Odd1 and Odd2. This allows for the zig-zag to encorporated into the pattern.
      4. How difficult is it to create your interesting pattern using Oct3's algorithm?
          It should be very easy--adding in the the custom path and pathback.
      5. Write a program based on Oct3 that uses triangles instead of octagons for the basis of the pattern. 
          //-----------------------
Odd1 {
 use path1
 sides 3
 ifon none {
   paint orange
   4 {
     2 right
     create Odd2
   } 
 } { }
}
//----------------------
Odd2 {
 use path2
 sides 3
 ifon none  {
   paint red
   4 {
   2 right
   create Odd1
   }
 } {
}
}
//-----------------------
path1 {
 sides 5
 paint purple
}
//-----------------------
path2 {
 sides 5
 paint purple
 left
}
  • Part B computations
      1. Insert comments into the UniAdd codes so that the meaning / purpose of the code is clearer. 
        File content not available for UniAdd.java

      2. How many ifs in total are used to add 111 with 111?
          Since every step requires a if, counting the total number is just a matter of counting the distance each square travels. Breaking it down by task is probably the easiest:
        • transfers: 8 = 4 + 4 (3+ the ending if)
        • walkbacks: 12 = 1+2+3 + 1+2+3
        • walkUps: 9 = 2+2+2 + 1+1+1
        • addOnes: 21 = 1+2+3+4+5+6
        • Total = 50
      3. Sometimes the random numbers are too big or too small to be interesting. Convert the code so that the numbers to be added are more than 2 and less than 8. 
        number {
   4 { 
      choose 0.6 {
          use n1     
     } { }
   }
   3 use n1
}
      4. Translate the code so that the sum displays in binary. 
        addOne {
    sides 4
    ifon blue {
       paint yellow
       use addOne
    } {
       paint blue
    }       
}
      5. Rewrite rNum so that it creates random binary numbers between 4 and 32. 
        number {
   2 use getDigit
   2 { 
      choose 0.6 {
         use getDigit
      } { }
   }
   use n1
}
getDigit {
   choose 0.5 {
     use n1     
   } {
     use n0
   }
}
      6. Rewrite AddNum and it's subprograms so that it correctly adds binary numbers. 
        transfer {
   sides 4
   ifon none { }  {
     2 create transfer
     ifon blue {
        right 
        create walkBack
     }  {  
        right
        create zero
     }
   }
}
      7. Rewrite AddNum so it adds column-wise. 
        // uniAdd
start {
    sides 4
    paint red
    right
    sides 4
    paint black
    right
    create blackLine
    left
    2 {
       sides 4
       paint black
       right
       create number
       left
    }
    right
    create addNum
} 
blackLine {
   sides 4
   paint black
   use blackLine
}
number {
   4 { 
      choose 0.6 {
        choose 0.2 {
          use n1     
        } {
          use n0
        }
     } { }
   }
   use n1
}
n1{
  sides 4
  paint blue
}
n0{
  sides 4
  paint yellow
}
addOne {
    sides 4
    ifon blue {
       paint yellow
       use addOne
    } {
       paint blue
    }       
}       
addNum {
    create transfer
    right 
    sides 4
    left
    sides 4
    left
    create transfer
}
transfer {
   sides 4
   ifon none { }  {
     create transfer
     ifon blue {
        right 
        create walkBack
     }  {  
        right
        create zero
     }
   }
}
walkBack {
   sides 4
   ifon black {
      right
       sides 4
       left
      sides 4
      left
      create addOne
   } {
     create walkBack
   }
}
zero {
   sides 4
   ifon black {
       sides 4
       ifon none { 
          paint yellow
      } { }
   } {
     create zero
   }
}
      8. Compare the ifs used during the addition of 111 with 111 for each of the binary AddNums (non-columns and column-wise). The column-wise count is 26 (I cheated I turned the uses into creates and counted the clicks). The non-columns count is at least 111.
      9. What are the biggest number that can be added (without changing the program with scaling etc) in the original UniAdd and the binary version of the code? What if ternary (base 3) was used instead?
        • 10 squares means 10 is the biggest number in unary.
        • 10 squares means 1111111111 = 2^11-1 = 2047 is the biggest number in binary.
        • 10 squares means 2222222222 = 3^11-1 = 177138 is the biggest number in ternary.