## Five Questions

Saturday, January 21, 2023

Many years ago, there was a blog post containing five programming problems every software engineer should be able to solve in less than 1 hour. I had bookmarked it at the time and didn’t notice the controversy it created on Reddit. The original link seems to be down – you can view a copy of it on the Wayback Machine – but there are various solutions posted online, including a solution in Python.

I finally got around to looking at it and writing up some solutions to the problems listed. Apparently, instead of solving this in 1 hour in Factor, it took me almost 8 years:

```
IN: scratchpad 2015 05 09 <date> days-since >integer .
2814
```

## Problem 1

*Write three functions that compute the sum of the numbers in a given list
using a for-loop, a while-loop, and recursion.*

In idiomatic Factor, this is just sum, and we would typically use sequence combinators, but instead here are a few solutions using lexical variables.

Using a for-loop, iterating forwards:

```
:: solve-1 ( seq -- n )
0 seq length [ seq nth-unsafe + ] each-integer ;
```

Using a while-loop, iterating forwards:

```
:: solve-1 ( seq -- n )
0 0 seq length :> n
[ dup n < ] [
[ seq nth-unsafe + ] [ 1 + ] bi
] while drop ;
```

Using recursion, iterating backwards:

```
:: (solve-1) ( accum i seq -- accum' )
accum i [
1 - seq [ nth-unsafe + ] 2keep (solve-1)
] unless-zero ;
: solve-1 ( seq -- n )
0 swap [ length ] keep (solve-1) ;
```

Some test cases to confirm behavior:

```
{ 0 } [ { } solve-1 ] unit-test
{ 1 } [ { 1 } solve-1 ] unit-test
{ 6 } [ { 1 2 3 } solve-1 ] unit-test
```

## Problem 2

*Write a function that combines two lists by alternatively taking elements.
For example: given the two lists [a, b, c] and [1, 2, 3], the
function should return [a, 1, b, 2, c, 3].*

We can alternately choose items from each list:

```
: solve-2 ( seq1 seq2 -- newseq )
[ min-length 2 * ] 2keep '[
[ 2/ ] [ even? ] bi _ _ ? nth-unsafe
] { } map-integers-as ;
```

Some test cases to confirm behavior:

```
{ { "a" 1 "b" 2 "c" 3 } } [
{ "a" "b" "c" } { 1 2 3 } solve-2
] unit-test
{ { "a" 1 "b" 2 "c" 3 } } [
{ "a" "b" "c" "d" } { 1 2 3 } solve-2
] unit-test
```

## Problem 3

*Write a function that computes the list of the first 100 Fibonacci numbers.
By definition, the first two numbers in the Fibonacci sequence are 0 and 1,
and each subsequent number is the sum of the previous two.*

There are many approaches, including using memoization, but instead we’ll just iterate from the starting values and use replicate to build up an output array.

```
: solve-3 ( n -- seq )
[ 0 1 ] dip [ dup rot [ + ] keep ] replicate 2nip ;
```

Some test cases to confirm behavior:

```
{ { } } [ 0 solve-3 ] unit-test
{ { 0 } } [ 1 solve-3 ] unit-test
{ { 0 1 } } [ 2 solve-3 ] unit-test
{ { 0 1 1 2 3 5 8 13 21 34 } } [ 10 solve-3 ] unit-test
{ 573147844013817084100 } [ 100 solve-3 sum ] unit-test
```

## Problem 4

Write a function that given a list of non negative integers, arranges them
such that they form the largest possible number. For example, given `[50, 2, 1, 9]`

, the largest formed number is `95021`

.

We can try each-permutation of the input numbers, looking for their largest numerical value when the digits are concatenated:

```
: solve-4 ( seq -- n )
0 swap [ number>string ] map
[ concat string>number max ] each-permutation ;
```

Some test cases to confirm behavior:

```
{ 95021 } [ { 50 2 1 9 } solve-4 ] unit-test
{ 5523 } [ { 52 5 3 } solve-4 ] unit-test
```

## Problem 5

*Write a program that outputs all possibilities to put + or - or
nothing between the numbers 1, 2, …, 9 (in this order) such that the
result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.*

This one is more complicated than the previous ones, but we can build it up piece by piece, using a test-case on each step to show how it works.

First, we want a word to interleave numbers amongst operators using `solve-2`

:

```
: insert-numbers ( operators -- seq )
[ length [1..b] ] [ solve-2 ] [ length 1 + suffix ] tri ;
{ { 1 f 2 + 3 f 4 } } [ { f + f } insert-numbers ] unit-test
```

Next, we want a word that will join adjacent digits – separated by `f`

:

```
GENERIC: digits, ( prev intermediate -- next )
M: number digits, [ 10 * ] [ + ] bi* ;
M: object digits, [ [ , 0 ] dip , ] when* ;
: join-digits ( seq -- seq )
[ [ ] [ digits, ] map-reduce , ] { } make ;
{ { 12 + 34 } } [ { 1 f 2 + 3 f 4 } join-digits ] unit-test
```

Since Factor is a kind of Reverse Polish notation, we’ll want to swap from infix to postfix:

```
: swap-operators ( seq -- seq )
dup rest-slice 2 <groups> [ 0 1 rot exchange ] each ;
{ { 12 34 + } } [ { 12 + 34 } swap-operators ] unit-test
```

The solution, then, is to use
all-selections
of addition, subtraction, and adjacency – interleaving the numbers, joining
adjacent digits, swapping operators, and then calling each sequence as a
quotation, filtering for the ones that return `100`

:

```
: solve-5 ( -- solutions )
{ + - f } 8 all-selections
[ insert-numbers join-digits swap-operators ] map
[ >quotation call( -- x ) 100 = ] filter ;
```

We can print the formula out by swapping the operators back to infix and printing them out:

```
: print-formula ( solutions -- )
[ present ] map swap-operators " " join print ;
: solve-5. ( -- )
solve-5 [ print-formula ] each ;
```

Spoilers! The printed solutions:

```
IN: scratchpad solve-5.
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 23 - 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
123 + 4 - 5 + 67 - 89
123 + 45 - 67 + 8 - 9
123 - 4 - 5 - 6 - 7 + 8 - 9
123 - 45 - 67 + 89
```