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

## No comments:

Post a Comment