### Daily Coding Puzzles - Nov 4th - Nov 9th

#### Ali Spittel on November 09, 2018

Every day on Twitter, I post coding puzzles. These are quick coding challenges that increase in difficulty across the span of the week -- with Mond... [Read Full] ## Wednesday

Array.diff (6 KYU):

Your goal in this kata is to implement a difference function, which subtracts one list from another and returns the result.

CodeWars

Ruby

``````a - b
``````

Ah, cannot `unsee` this answer... 😆

That's amazing!

On the other hand, Ruby probably allocated about 10,000 object references under the hood and used 1gb of memory to make that happen. 😄

Honestly, I just came out here to have a good time and I'm feeling so attacked right now 😅😅😅

Haha nice. Honestly, I'm just so used to copy/pasting emojis from slack and discord. Fun fact, when you do that, it copies the colon emoji syntax, not the unicode glyph 😅🙃

@bendhalpern some numbers (using /usr/bin/time -l on OSX):

``````Go: 0.0s, 1.5Mb
Go run: 0.10s, 24Mb
Node: 0.06s, 19Mb
Ruby: 0.08s, 11Mb
Crystal: 0.0s, 1.5Mb
Crystal run: 0.4s, 10.4Mb
``````

Oh, I know almost nothing about Go. I'm specifically using these exercises to learn the syntax. No clue if and how what I'm doing can be optimized. Go is famously, weirdly restrictive and intentionally verbose.

Similar effort when done in APL! :)

kkkkk it's very simple dude :D

Rust

• With Liftime. The returned Vec<&T> has elements borrowed and valid until the list1 is valid.
``````fn diff<'a, T>(list1: &'a [T], list2: &[T]) -> Vec<&'a T>
where
T: PartialEq,
{
list1.into_iter().filter(|e| !list2.contains(e)).collect()
}
``````
• Without lifetime We return a new Vec free from any list provided, by cloning the data. The generic data type only allows the data type that implements Clone trait to be passed.
``````fn diff2<T>(list1: &[T], list2: &[T]) -> Vec<T>
where
T: PartialEq + Clone,
{
list1
.into_iter()
.map(|x| x.clone())
.filter(|e| !list2.contains(&e))
.collect()
}
``````

Python!

``````def array_diff(a, b):
return [l for l in a if l not in b]
``````

List comprehensions are truly a gift.

YES -- they are so elegant.

Or with sets!

``````def array_diff(a, b):
return list(set(a) - set(b))
``````

Go

``````func Difference(a []int, b []int) (diff []int) {
m := make(map[int]bool)

for _, item := range b {
m[item] = true
}

for _, item := range a {
if _, presence := m[item]; !presence {
diff = append(diff, item)
}
}
return
}
``````

### Common Lisp

I'll use lists because... well, it's Lisp, right?

``````(set-difference '(1 2 2 2 3) '(2))
;; => (3 1)
``````

Can't beat a good standard library ;)

It wasn't as easy as doing a set difference as the `a` needed to keep the duplicate values.

Below is the answer in C#.

`Where` is the same as `filter` in JavaScript.

``````using System.Linq;
using System.Collections.Generic;

public class Kata
{
public static int[] ArrayDiff(int[] a, int[] b)
{
var hash = new HashSet<int>(b);
return a.Where(_ => !hash.Contains(_)).ToArray();
}
}
``````

APL

`````` a ~ b
``````

``````function array_diff(a, b) {
let counter = {};
for(let i of b) {
counter[i] = true;
}
let result = a.filter(item => counter[item] !== true);
return result;
}
``````

Here's one in Dart:

``````arrayDiff(List a, List b) => a..retainWhere((i) => !b.contains(i));
``````

Hey all, Why I don't see any java code here?

## Thursday

Scramblies (5 KYU):

Complete the function scramble(str1, str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false

CodeWars

F#

``````let scramble str1 str2 =
let letterLookup = str1 |> Seq.countBy id |> Map.ofSeq
let requiredCounts = str2 |> Seq.countBy id
requiredCounts |> Seq.forall (fun (letter, requiredCount) ->
match letterLookup |> Map.tryFind letter with
| None -> false // letter missing
| Some count -> requiredCount <= count
)
``````

Edit: I had previously posted a version that had ever-so-slightly more performance but was more code. I'm also including that version below since it solves the problem differently.

``````let scramble str1 str2 =
let letterPool = str1 |> Seq.sort |> List.ofSeq
let requiredLetters = str2 |> Seq.sort |> List.ofSeq
let rec loop requiredLetters letterPool =
match requiredLetters, letterPool with
| [], _ -> true // found all
| _ :: _, [] -> false // pool ran out
| letter :: _, next :: pool when letter > next ->
loop requiredLetters pool // skip next in pool
| letter :: required, next :: pool when letter = next ->
loop required pool
| _, _ -> false // letter not available in the pool
loop requiredLetters letterPool
``````

Here are the tests (console).

``````    [
"rkqodlw", "world", true
"cedewaraaossoqqyt", "codewars", true
"katas", "steak", false
]
|> List.iter (fun (str1, str2, expected) ->
let actual = scramble str1 str2
let e = if expected = actual then "√" else "X"
printfn "%s %A ==> %b, %b" e (str1, str2) expected actual
)
// √ ("rkqodlw", "world") ==> true, true
// √ ("cedewaraaossoqqyt", "codewars") ==> true, true
// √ ("katas", "steak") ==> false, false
``````

Nice! yeah -- I only sometimes think about the efficiencies of these. They're contrived and we're doing them for fun. Part of me cares, part of me doesn't haha

Go

``````func Scramble(str1 string, str2 string) (result bool) {
m := make(map[string]int)

for _, item := range strings.Split(str1, "") {
m[item] += 1
}

for _, item := range strings.Split(str2, "") {
if val, ok := m[item]; !ok || val == 0 {
return false
} else {
m[item] -= 1
}
}

return true
}
``````

Python!

``````def scramble(s1,s2):
for letter in set(s2):
if s1.count(letter) < s2.count(letter):
return False
return True
``````

``````function scramble(str1, str2) {
let letterHolder = {};
for (let letter of str1) {
if(letterHolder[letter]) letterHolder[letter]++;
else letterHolder[letter] = 1;
}
for (let letter of str2) {
if(!letterHolder[letter]) return false
else letterHolder[letter]--;
}
return true;
}
``````

Solved it awhile ago in C#.

Warning: Really ugly...

``````using System;
using System.Collections.Generic;
using System.Linq;

public class Scramblies
{
public static bool Scramble(string s1, string s2)
{
Func<string, Dictionary<char, int>> toMap = s =>
s.GroupBy(c => c)
.Select(g => new { g.Key, Count = g.Count() })
.ToDictionary(pair => pair.Key, pair => pair.Count);

var map1 = toMap(s1);
var map2 = toMap(s2);

foreach (KeyValuePair<char, int> p2 in map2)
{
if (!map1.ContainsKey(p2.Key)) return false;

if (map1[p2.Key] < p2.Value) return false;
}

return true;
}
}
``````

Not a fancy solution, but it seems to work 😃

``````function scramble(s1, s2) {
if (s1.length < s2.length) return false;

const _s2 = s2.split("");

s1.split("").forEach(val => {
if (_s2.includes(val)) _s2.splice(_s2.indexOf(val), 1);
});

return _s2.length == 0;
}
``````

### Common Lisp

``````
(defun scramble (source target)
(let ((source (coerce source 'list))
(target (coerce target 'list)))
(cond ((null target) t)
((member (first target) source)
(scramble (remove (first target) source :count 1)
(rest target))))))

(mapcar #'(lambda (args) (apply #'scramble args))
'(("rkqodlw" "world")
("cedewaraaossoqqyt" "codewars")
("katas" "steak")
("scriptjavx" "javascript")
("scriptingjava" "javascript")
("scriptsjava" "javascripts")
("javscripts" "javascript")
("aabbcamaomsccdd" "commas")
("commas" "commas")
("sammoc" "commas")))
;; => (T T NIL NIL T T NIL T T T)
``````

## Tuesday

Product of Array Items (7 KYU):

Calculate the product of all elements in an array.

CodeWars

Does F# require you to name the `arr` parameter explicitly or can you simply do the following:

``````let product = Array.reduce (*)
``````

I've been curious about F# for some time but haven't really done a deep dive.

Yes, you can do that in F#. (You probably know this, but for the sake of onlookers) it is called point-free notation. It can be handy for small functions like this. But I noticed when I use it too much, my code can become hard to understand.

Especially for code examples, I rarely use it because it can confuse readers.

I decided to not use reduce so that I could return early if I hit a zero.

``````function product(values) {
if(!values || values.length === 0) return null;
let prod = values;
for(let i=1; i<values.length; i++) {
if(values[i] === 0) return 0;
prod *= values[i];
}
return result;
}
``````

A simple aggregation of data (using `reduce`) worked like a charm.

``````namespace Kata {
using System;
using System.Linq;
public class ArrayMath
{
public static int Product(int[] values)
{
return values.Aggregate((product, current) => product * current);
}
}
}
``````

### Common Lisp

as `*` in Common Lisp can take as many arguments as you like...

``````(apply #'* (list 1 2 3 4 5))
;; => 120
``````

Javascript

``````function arrayProduct(arr) {
return arr.reduce((acc, val) => acc * val);
}
``````

### JavaScript

``````const product = arr => arr.reduce((acc, x) => acc * x)
``````

Python!

``````def product(numbers):
if not numbers: return None
running_product = 1
for number in numbers:
running_product *= number
return running_product
``````

Go

``````func Product(nums []int)(x int) {
x = 1

for _, num := range nums {
x *= num
}
return
}

``````

## Friday

The Last Word (CodeJam):

You are the next contestant on this show, and the host has just showed you the string S. What's the winning last word that you should produce?

CodeJam

F#

``````let lastWord s =
let update (first, word) letter =
if letter >= first then (letter, string letter + word)
else                    (first, word + string letter)
s |> Seq.fold update ('A', "") |> snd
``````

Testing it (console)

``````    [
"CAB", "CAB"
"JAM", "MJA"
"CODE", "OCDE"
"ABAAB", "BBAAA"
"CABCBBABC", "CCCABBBAB"
"ABCABCABC", "CCCBAABAB"
"ZXCASDQWE", "ZXCASDQWE"
]
|> List.iter (fun (input, expected) ->
let actual = lastWord input
let e = if expected = actual then "√" else "X"
printfn "%s %s ==> %s, %s" e input expected actual
)
// √ CAB ==> CAB, CAB
// √ JAM ==> MJA, MJA
// √ CODE ==> OCDE, OCDE
// √ ABAAB ==> BBAAA, BBAAA
// √ CABCBBABC ==> CCCABBBAB, CCCABBBAB
// √ ABCABCABC ==> CCCBAABAB, CCCBAABAB
// √ ZXCASDQWE ==> ZXCASDQWE, ZXCASDQWE

``````

Awesome -- this one (for me) was a lot easier than they made it sound!

I think the possible "gotcha" here is that they do not want a reverse alphabetically sorted string, which, if you're not careful about the requirements, could be what you try to build and have it trip you up.

## Common Lisp

``````(defun last-word (word)
(let ((cs (coerce word 'list)))
(coerce (reduce #'(lambda (word c)
(if (char> (first word) c)
(append word (list c))
(cons c word)))
(rest cs)
:initial-value (list (first cs)))
'string)))
``````

Quick little test...

``````(mapcar #'last-word (list "CAB"
"JAM"
"CODE"
"ABAAB"
"CABCBBABC"
"ABCABCABC"
"ZXCASDQWE"))
;; => ("CAB" "MJA" "OCDE" "BBAAA" "CCCABBBAB" "CCCBAABAB" "ZXCASDQWE")
``````

Rust

``````use std::io::{self, prelude::*};

fn find_last_word(s: &str) -> String {
s.chars()
.fold(vec![], |mut last, letter| {
if let Some(&c) = last.last() {
if (c as u8) > (letter as u8) {
last.insert(0, letter);
} else {
last.push(letter);
}
} else {
last.push(letter);
}
last
}).iter()
.rev()
.into_iter()
.collect()
}

fn main() {
let stdin = io::stdin();

for (i, line) in stdin.lock().lines().skip(1).enumerate() {
if let Ok(text) = line {
match io::stdout()
.write(format!("Case #{}: {}\n", i + 1, find_last_word(&text)).as_bytes())
{
Ok(_) => (),
Err(why) => panic!(why),
}
}
}
}
``````

usage: `last_word(.exe) < small.in > small.txt`

Python!

``````def get_last_word(word):
last_word = word
for letter in word[1:]:
if letter >= last_word:
last_word = letter + last_word
else:
last_word = last_word + letter
return last_word

out_file = open('output.txt', 'w')
case_number = 0

for word in open('A-small-practice (3).in', 'r'):
if case_number != 0:
out_file.write("Case #{}: ".format(case_number) + get_last_word(word))
case_number += 1
``````

TypeScript

``````function processLastwordData(input :string) : void {
const inputArray = input.split('\n');
let resultStr = "";
const cases = parseInt(inputArray);
for(let i=1; i <= cases; i++) {
resultStr += `Case #\${i}: \${lastWord(inputArray[i])}\n`
}
process.stdout.write(resultStr);
}

function lastWord(str : string) : string {
let outStr = str;
for(let i=1; i<str.length; i++) {
if(str.charCodeAt(i) >= outStr.charCodeAt(0)) outStr = str[i] + outStr;
else outStr = outStr + str[i];
}
return outStr;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
let _input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processLastwordData(_input);
});

``````

Go

``````func Last(w string) (result []string) {
l := strings.Split(w, "")
result = []string{l}

for _, item := range l[1:] {
if val := result; item > val {
result = append([]string{item}, strings.Join(result, ""))
} else {
result = append(result, item)
}
}
return
}
``````

## Monday

Number Drills: Blue and red marbles (8 KYU):

You've decided to write a function, guess_blue() to help automatically calculate whether you should guess "blue" or "red". The function should take four arguments.

CodeWars

Go

``````func Guess(bStart int, rStart int, bGone int, rGone int)(probability float32) {
var b = bStart - bGone
var r = rStart - rGone

probability = float32(b) / float32(r + b)
return
}
``````

### Common Lisp

``````(defun guess-blue (blue-in red-in blue-out red-out)
(let ((blue (- blue-in blue-out))
(red (- red-in red-out)))
(/ blue (+ red blue)))

(guess-blue 5 5 2 3)
;; => 3/5
``````

the fun of a language with rationals:

``````(guess-blue 1 2 0 0)
;; => 1/3
``````

``````function guessBlue(blueStart, redStart, bluePulled, redPulled) {
let currentBlue = blueStart - bluePulled;
let currentRed = redStart - redPulled;
return currentBlue / (currentBlue + currentRed);
}

``````

Python!

``````def guess_blue(blue_start, red_start, blue_pulled, red_pulled):
blue = blue_start - blue_pulled
red = red_start - red_pulled
return blue / (red + blue)
``````

## Meta!

Ooh. I tried to do Advent of Code in Go last year, but AoC was probably too steep a challenge for a language I didn't know at all. This is a much more manageable entrypoint. Thanks for this! 🤗

For sure! I may try and incorporate those next month! We'll see! Go is so much fun, I should do more with it!

Possibly dumb question - what does KYU stand for?

That's a great question -- I'm not totally sure, but it's the ranking system CodeWars uses, so I include it -- 8 KYU are the most beginner friendly, 1 KYU takes a really long time.

code of conduct - report abuse  