IBM Research | Ponder This | October 2015 challenges
Skip to main content

Ponder This

October 2015

<<September October November>>

Ponder This Challenge:

Counting the number of 1s in a 12-bit input is a function from 12 to 4 bits.
Our challenge this month is to implement it with a minimal number of 5-to-2 functions (a function that receives 5 bits input and emits 2 bits output).
The format we request is several lines. Each line consists of <5 letters> followed by <32 base-4 digits>,
followed by the last line with 4 space separated numbers.
The 5 letters are the input to the function (the first letter is the msb) and the 32 digits are the output (the msb is the first output). The last line states which bits are used as the output.
To explain the format, here is an implementation that compares 2 numbers that are 2-bit, using 2 functions of 3-to-2
acd02113302
bef21133123
7 8
The input is a,b,c,d; the first line defines e,f as a function of the 3 bits a,c,d; and the second line applies a different 3-to-2 function on b,e,f, yielding a 2-bit output (g,h).
The last line states that the output of the computation is 7,8, where 7(=g) is the msb and 8(=h) is the lsb.
In the real problem, the output contains 4 bits. In our example, the output has 2 bits.

If a=0, c=0, d=0 then e=0 and f=0
If a=0, c=0, d=1 then e=1 and f=0
If a=0, c=1, d=0 then e=0 and f=1
If a=0, c=1, d=1 then e=0 and f=1
If a=1, c=0, d=0 then e=1 and f=1
If a=1, c=0, d=1 then e=1 and f=1
If a=1, c=1, d=0 then e=0 and f=0
If a=1, c=1, d=1 then e=1 and f=0
The output (g,h) is 0,1 if, and only if, 2*a+b < 2*c+d
The output (g,h) is 1,0 if, and only if, 2*a+b = 2*c+d
The output (g,h) is 1,1 if, and only if, 2*a+b > 2*c+d

Update (06/10):

1. To be qualified as a solver, you need no more than 9 functions. Each function you save will earn you a "*".

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Challenge: 29/09/2015 @ 12:00 PM EST
Solution: 01/11/2015 @ 12:00 PM EST
List Updated: 15/11/2015 @ 12:00 PM EST

People who answered correctly:

***Michael Brand (30/09/2015 04:00 AM IDT)
***Uoti Urpala (30/09/2015 06:47 PM IDT)
Sean Egan (30/09/2015 09:13 PM IDT)
**luke hsieh (01/10/2015 06:11 AM IDT)
***James Dow Allen (01/10/2015 06:53 AM IDT)
Eitan Levine (01/10/2015 09:32 AM IDT)
*Joseph DeVincentis (01/10/2015 08:12 PM IDT)
*Edwin Karat (01/10/2015 08:34 PM IDT)
*Daniel Bitin (02/10/2015 01:35 PM IDT)
**Alexandre Gilotte (03/10/2015 06:36 PM IDT)
Shisen Luo (05/10/2015 01:37 AM IDT)
**Lorenz Reichel (06/10/2015 02:12 PM IDT)
**Shirish Chinchalkar (07/10/2015 03:19 AM IDT)
**Jesse Rearick (07/10/2015 06:40 AM IDT)
*Kang Jin Cho (07/10/2015 10:14 AM IDT)
*Francis Golding (07/10/2015 02:02 PM IDT)
*Frank Samm (10/10/2015 08:56 AM IDT)
*Andreas Puccio (10/10/2015 05:59 PM IDT)
***Liubing Yu (11/10/2015 04:19 AM PM IDT)
**Keith Reckdahl & Gary Gerken (11/10/2015 07:22 AM PM IDT)
*Dieter Beckerle (11/10/2015 08:55 AM PM IDT)
*Graham Hemsley (11/10/2015 09:27 AM PM IDT)
**Dan Dima (12/10/2015 12:47 AM PM IDT)
*Sergey Koposov (13/10/2015 10:38 PM PM IDT)
Isabella Cattinelli (14/10/2015 12:16 PM IDT)
*Don Dodson & David Dodson (14/10/2015 02:55 PM IDT)
*Peter Gerritson (14/10/2015 06:38 PM IDT)
***Radu-Alexandru Todor (14/10/2015 09:41 PM IDT)
*Leo Broukhis (14/10/2015 11:19 PM IDT)
*Hao Wu (15/10/2015 09:32 AM IDT)
Aviv Nisgav (15/10/2015 12:08 PM IDT)
***Dmitry Teytelman (16/10/2015 03:18 AM IDT)
*Harald Bögeholz (16/10/2015 10:56 AM IDT)
*Armin Krauss (16/10/2015 02:50 PM IDT)
*Clive Tong (16/10/2015 05:43 PM IDT)
***Luke Hsieh (16/10/2015 08:27 PM IDT)
*Chris Hibbert (18/10/2015 12:23 AM IDT)
*Di Luo (18/10/2015 08:48 AM IDT)
**Motty Porat (18/10/2015 09:15 PM IDT)
**Hongcheng Zhu (19/10/2015 01:59 AM IDT)
**Matthew Rips (19/10/2015 07:44 AM IDT)
***Hendrik Nigul (19/10/2015 08:13 AM IDT)
*Etienne Leloup (19/10/2015 09:32 PM IDT)
Ganor Tamir & Shouky Dan (20/10/2015 11:23 AM IDT)
***Leo Broukhis (21/10/2015 03:10 AM IDT)
**Raymond Lo (21/10/2015 12:01 PM IDT)
Stéphane Higueret (22/10/2015 03:00 PM IDT)
***Tom Harley (22/10/2015 04:07 PM IDT)
*Varun Ahluwalia (23/10/2015 03:28 AM IDT)
*Gregory Giecold (24/10/2015 05:06 AM IDT)
*Nyles Heise (24/10/2015 07:51 AM IDT)
***Motty Porat (25/10/2015 11:53 PM IDT)
*Ali Can Keserel (27/10/2015 01:25 PM IDT)
*Aviv Nisgav (28/10/2015 07:26 AM IDT)
**Benjamin Lui (31/10/2015 01:29 PM IDT)
**Arthur Nascimento (31/10/2015 05:35 PM IDT)
*David Greer (01/11/2015 12:02 PM IDT)
**David Dunkley (01/11/2015 02:52 PM IDT)