Five Questions

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