# RogerBW's Blog

 Perl Weekly Challenge 97: Caesar Substrings 27 January 2021 I’ve been doing the Perl Weekly Challenges. The latest involved implementing the Caesar cipher and breaking up binary strings. (Note that this is open until 31 January 2021.) TASK #1 › Caesar Cipher You are given string `\$S` containing alphabets `A..Z` only and a number `\$N`. Write a script to encrypt the given string `\$S` using Caesar Cipher with left shift of size `\$N`. Left shift? How odd. Ah, it's the example on Wikipedia. Well, fair enough. I see two basic approaches here: one is to map the string down to a series of char values, transform them, then bring them back up to make a string. One could do that. Instead, I built a hash to map from plaintext character to encrypted character, falling back to the character itself if there's no hash entry. I hardcoded the number of alphabet entries, but shifted this a bit later on in other languages. ``````sub cc { my \$s=shift; my \$n=shift; my @plain=('A'..'Z'); my @cipher=(@plain,@plain); splice @cipher,0,(26*2-\$n)%26; my %m=map {\$plain[\$_] => \$cipher[\$_]} (0..\$#plain); return join('',map {\$m{\$_} || \$_} split '',\$s); } `````` Raku is basically the same. ``````sub cc(\$s,\$n) { my @plain=('A'..'Z'); my @cipher=(@plain,@plain).flat; splice @cipher,0,(26*2-\$n)%26; my %m=map {@plain[\$_] => @cipher[\$_]},(0..@plain.end); return (map {%m{\$_} || \$_},\$s.comb()).join(''); } `````` In Python I measured the size of the character set (and discovered that I couldn't get a range of chars), and had to write out the hash tests in full. ``````def cc(s,n): plain=list([chr(i) for i in range(ord('A'),ord('Z')+1)]) cmap=dict() asize=len(plain) for p in range(asize): c=(p+asize*2-n) % asize cmap[plain[p]]=plain[c] out="" for i in range(len(s)): if s[i] in cmap: out += cmap[s[i]] else: out += s[i] return out `````` Ruby was pretty much a reimplementation of Python. ``````def cc(s,n) plain=('A'..'Z').to_a cmap=Hash.new asize=plain.length 0.upto(asize-1) do |p| c=(p+asize*2-n) % asize cmap[plain[p]]=plain[c] end out="" s.split('').each do |ss| if cmap.has_key?(ss) then out += cmap[ss] else out += ss end end return out end `````` As was Rust, with a bit of fiddling back and forth between `usize` and other types. (usize, after all, can't go negative…) ``````fn cc(s: &str, n: i8) -> String { let plain=(b'A'..=b'Z').map(|b| b as char).collect::>(); let mut cmap: HashMap=HashMap::new(); let asize=plain.len(); for p in 0..asize { let c=(((p as i8)+(asize as i8)*2-n) % (asize as i8)) as usize; cmap.insert(plain[p],plain[c]); } let mut out: String="".to_string(); for ss in s.chars() { if cmap.contains_key(&ss) { out.push(*cmap.get(&ss).unwrap()); } else { out.push(ss); } } return out.to_string(); } `````` TASK #2 › Binary Substrings You are given a binary string `\$B` and an integer `\$S`. Write a script to split the binary string `\$B` of size `\$S` and then find the minimum number of flips required to make it all the same. ("Binary string" means here "string consisting of a series of 1 and 0 characters".) Splitting a string to something other than characters or words. There's unusual. The fiddly bit here is that they don't all have to become the same as the first one; any one string might be the one into which they all get flipped (consider for example the series `000, 111, 111, 111` which should return 3 not 9). So I ended up calculating an edit distance between each pair of items (much more the usual sort of thing than last week's Levenshtein), and cacheing them because the distance from A to B will be the same as from B to A. The cheapest row of edits is the one to use. ``````sub bs { my \$b=shift; my \$s=shift; my @bb=grep /./,split /(.{\$s})/,\$b; if (length(\$bb[-1]) != \$s) { return -1; } my \$mc; my %cost; foreach my \$x (0..\$#bb-1) { \$cost{\$x}{\$x}=0; foreach my \$y (\$x+1..\$#bb) { \$cost{\$x}{\$y}=\$cost{\$y}{\$x}=diff(\$bb[\$x],\$bb[\$y]); } my \$tc=sum(map {\$cost{\$x}{\$_}} 0..\$#bb); if (!defined \$mc || \$tc < \$mc) { \$mc=\$tc; } } return \$mc; } `````` That `diff` function would be a good candidate for cacheing too. Or optimisation if we were using real binary - XOR the two arguments, then bit-count the result. ``````sub diff { my (\$a,\$b)=@_; my @ac=split '',\$a; my @bc=split '',\$b; my \$d=0; foreach my \$i (0..\$#ac) { if (\$ac[\$i] ne \$bc[\$i]) { \$d++; } } return \$d; } `````` Raku is basically the same here, with some tweaks for syntax. (And `comb(n)` splits a string into n-sizes units.) ``````sub bs(\$b,\$s) { my @bb=\$b.comb(\$s); if (chars(@bb[@bb.end]) != \$s) { return -1; } my \$mc=-1; my %cost; for (0..@bb.end-1) -> \$x { %cost{\$x}{\$x}=0; for (\$x+1..@bb.end) -> \$y { %cost{\$x}{\$y}=%cost{\$y}{\$x}=diff(@bb[\$x],@bb[\$y]); } my \$tc=sum(map {%cost{\$x}{\$_}},0..@bb.end); if (\$mc==-1 || \$tc < \$mc) { \$mc=\$tc; } } return \$mc; } sub diff(\$a,\$b) { my @ac=\$a.comb; my @bc=\$b.comb; my \$d=0; for (0..@ac.end) -> \$i { if (@ac[\$i] ne @bc[\$i]) { \$d++; } } return \$d; } `````` For Python I worked out the string slicing in full rather than using a map, and used `defaultdict` to get an autovivified hash of hashes; string slicing came free. ``````def diff(a,b): d=0 for i in range(len(a)): if a[i] != b[i]: d += 1 return d def bs(b,s): bb=list() i=0 while i i64 { let mut d: i64=0; for (s,t) in a.chars().zip(b.chars()) { if s != t { d+=1; } } return d; } fn bs(b: &str, s: i64) -> i64 { let mut bb: Vec=vec![]; let mut i=0; while i
Produced by aikakirja v0.1