Three Homework Problems
September 18, 2015
We have three simple exercises today to help beginning programmers with their homework; all three exercises have appeared on beginning-programmer forums in the last week:
1) Write a recursive function to find the sum of the first n odd integers. For instance, if n = 2, the first two odd integers are 1 and 3, and their sum is 4.
2) Write a function to count the frequence of characters in a string. For instance, given the string “hello” the function should return counts of 1, 1, 2 and 1 for h, e, l and o.
3) Write functions that encrypt and decrypt messages in a Caesar cipher. Input consists of upper-case letters and spaces; the “key” is an integer giving the number of letters to shift. For instance, the message ATTACK AT DAWN with a shift of 5 is enciphered as FYYFHP FY IFBS.
Your task is to solve the three homework exercises given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Scala:
// https://programmingpraxis.com/2015/09/18/three-homework-problems-2/ // 1) def sumNOdd(n: Int): Int = if (n < 1) 0 else ((n - 1) * 2 + 1) + sumNOdd(n - 1) // by the way =n*n // 2) def freq(s: String, c: Char): Int = s.filter(_ == c).size // 3) def caesarEnc(s: String, key: Char): String = s.map(c => if (c != ' ') ((c - 'A' + key - 'A') % ('Z' - 'A' + 1) + 'A').toChar else ' ') caesarEnc("ATTACK AT DAWN", 'F') //> res13: String = FYYFHP FY IFBS def caesarDec(s: String, key: Char): String = s.map(c => if (c != ' ') ('A' + (c - key + 'Z' - 'A' + 1) % ('Z' - 'A' + 1)).toChar else ' ') caesarDec(caesarEnc("ATTACK AT DAWN", 'F'), 'F')//> res14: String = ATTACK AT DAWNI hope this isn’t another formatting disaster, but I flipped out thirty years ago when a homework exercise assumed ASCII encoding without comment (one of my worst overreactions, I walked out of the whole course when my solution was criticized for not making that unstated assumption), and I feel the need of a friendly objection today when a suggested solution assumes that any character fits in an octet. Here’s counting UTF-8 Greek letters from today’s Βικιπαίδεια front page :) In Python 3, copy-pasting in Lubuntu to Firefox from an Emacs running in Red Hat over SSH. Who do we blame if it gets mangled? Everything looks fine to me at the moment, a second before posting.
text = '''Ο Σαίρεν Κίρκεγκωρ, στα Δανικά Søren Aabye Kierkegaard, 5 Μαΐου 1813 – 11 Νοεμβρίου 1855), ήταν Δανός φιλόσοφος και θεολόγος του 19ου αιώνα. Θεωρείται ο πρώτος υπαρξιστής φιλόσοφος.''' from collections import Counter print(*Counter(c for c in text if c.isalpha()) .most_common(15), sep = '\n')The output:
('ο', 13) ('α', 11) ('ρ', 7) ('ι', 7) ('ς', 6) ('τ', 6) ('ε', 6) ('υ', 5) ('ν', 5) ('e', 4) ('φ', 4) ('κ', 4) ('σ', 4) ('ό', 4) ('ί', 4)def sum_odd(n): if n < 1: return 0 else: return 2*n-1 + sum_odd(n-1) def count_frequence(s): from collections import Counter return dict(Counter(s)) def ceasar(s, shift): import string alphabet = list(string.ascii_letters) return "".join(alphabet[(alphabet.index(c)+shift)%len(alphabet)] if c in alphabet else c for c in s) print sum_odd(2) print count_frequence("hello") print ceasar("dont attack gallia!", 5) # output: # 4 # {'h': 1, 'e': 1, 'l': 2, 'o': 1} # itsy fyyfhp lfqqnf!1 in SML, 2 and 3 in Perl:
(* tail recursive solution that counts upwards from 1 O(N) - only touches each odd number up to N *) fun sumFirstNOdds n = let fun loop curr count acc = if count = n then acc else case (curr mod 2) of 1 => loop (curr + 2) (count + 1) (acc + curr) | _ => loop (curr + 1) count acc in loop 1 0 0 end (* closed form formula SUM( odd(x) | x >= 1 and x <= N ) = N^2 *) fun sumFirstNOdds2 n = n * n; use strict; use warnings; # O(n) word frequency using ascii ordinal values sub frequency { my ($s) = @_; my @ascii_table = (0) x 128; foreach my $char ( split //, $s ) { $ascii_table[ ord $char ]++; } return @ascii_table; } print join(',', frequency('hello')), "\n"; # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, # 0,0,1,0,0,1,0,0,0,2,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 # 'e' 'h' 'l' 'o' sub encrypt { my ($plaintext, $shift) = @_; my @letters = ('A' .. 'Z'); return join '', map { ($_ ge 'A' && $_ le 'Z') ? $letters[(ord($_) + $shift - ord('A')) % @letters] : $_ } split //, $plaintext; } sub decrypt { my ($plaintext, $shift) = @_; return encrypt($plaintext, -$shift); } print decrypt(encrypt('ATTACK AT DAWN',5),5), "\n"; # ATTACK AT DAWNA Haskell version, using part of Jussi Piitulainen’s text for the character frequency problem.
import Data.Char (chr, ord) import Data.List (group, sort, sortBy) import Data.Ord (Down(..), comparing) import Text.Printf (printf) -- The sum of the first n odd numbers. A more idiomatic way to write it would -- be: -- oddSum n = sum [1, 3 .. 2*n-1] -- -- but I interpret the question as asking for explicit recursion. oddSum :: Int -> Int oddSum n = go (2*n-1) where go i | i > 0 = i + go (i-2) | otherwise = 0 -- The number of occurrences of each element of a list, sorted by decreasing -- frequency. freq :: (Eq a, Ord a) => [a] -> [(a, Int)] freq = order . map (\xs@(x:_) -> (x, length xs)) . group . sort where order = sortBy (comparing (Down . snd)) -- A pair of functions to perform Caesar encryption and decryption for a given -- key. caesar :: Int -> (String -> String, String -> String) caesar n = let m = n `mod` 26 in (crypt m, crypt (26 - m)) where crypt k = unwords . map (cryptWord k) . words cryptWord k = map (toChar . rot k . fromChar) fromChar x = ord x - ord 'A' toChar x = chr (x + ord 'A') rot k x = (x + k) `rem` 26 main :: IO () main = do -- Sum of odd numbers let n = 7 printf "Sum of the first %d odd numbers: %d\n\n" n (oddSum n) -- Letter frequencies let s = "Ο Σαίρεν Κίρκεγκωρ, στα" printf "Letter frequencies for: %s\n" s mapM_ (uncurry (printf " %c %d\n")) (freq s) putStrLn "" -- Caesar encryption and decryption let key = 5 (encrypt, decrypt) = caesar key sourceText = "ATTACK AT DAWN" cipherText = encrypt sourceText plainText = decrypt cipherText printf "Caesar encryption and decryption with key %d.\n" key printf " %s => %s\n" sourceText cipherText printf " %s => %s\n" cipherText plainText$ ./hmwrk3 Sum of the first 7 odd numbers: 49 Letter frequencies for: Ο Σαίρεν Κίρκεγκωρ, στα 3 ρ 3 ί 2 α 2 ε 2 κ 2 , 1 Κ 1 Ο 1 Σ 1 γ 1 ν 1 σ 1 τ 1 ω 1 Caesar encryption and decryption with key 5. ATTACK AT DAWN => FYYFHP FY IFBS FYYFHP FY IFBS => ATTACK AT DAWNEX1.
#include
int sum(int n)
{
if(n==1)
return 1;
else
return (2*n -1)+sum(n-1);
}
int main()
{
int n;
printf(“Enter the no of odd integer needed\n”);
scanf(“%d”,&n);
printf(“Result = %d\n”,sum(n));
}
if you don’t want to use recursive function then simplest method is
#include
int main()
{
int n;
printf(“Enter the no of odd integer needed\n”);
scanf(“%d”,&n);
printf(“Result = %d\n”,n*n);
}
#include
int main()
{
char str[20];
int i,j,count=1;
printf(“Enter the string\n”);
scanf(“%s”,str);
for(i=0;str[i];i++)
{
for(j=0;j %d\n”,str[i],count);
count=1;
}
}
EX 3.
#include
int main()
{
char str[20];
int i;
printf(“Enter the string”);
scanf(“%[^\n]”,str);
for(i=0;str[i];i++)
{
if(str[i]==’ ‘)
continue;
if((str[i]+5)>90)
str[i] =(str[i]+5-26);
else
str[i] = str[i]+5;
}
printf(“%s\n”,str);
}