Code golf seems to be all the rage these days, so I figured it might be fun to give it a try here. Let's try the following rules:
1) One challenge will be active at a time.
2) Each challenge should last for a few days, at the discretion of whoever started it.
3) Any commonly-used language is valid (TI-BASIC, ASM, C/C++, Python, Javascript, and Java might be a reasonable set from which to select).
4) You will be on the honor system for the originality of your solution (ie, not just Googling the answer).
5) All discussion and tentative solutions will be put in this topic.
6) Whoever selects a particular challenge can't enter that challenge, but can enter other ones.

Challenge 1: Binary Digits
Let's start with a simple one: Given a 32-bit unsigned (positive) integer, count the number of 0s in the binary representation of the number and display the result. You can assume that the number is given in a variable, like X or x.
Excellent idea.

TI-BASIC, 17

Code:
`sum(.5>fPart(X2^-cumSum(binomcdf(31,0 `

Standard method. not(int(2... and 1>2... are the same size, and round(,0 and ...seq(... are larger.
Rather unremarkable C (GCC, x86 -msse4.2). 34 characters or something.
Code:
`printf("%i",__builtin_popcnt(~x));`
In "hexified" z80 assembly:
06207829EBED6AEBDE0010F7

Code:
```;inputs: DEHL = 32 bit value to check ;output: a = number of 0s    ld b,32    ld a,b _   add hl,hl    ex de,hl    adc hl,hl    ex de,hl    sbc a,0    djnz -_```

24 characters (hex code), 12 bytes. For an extra three bytes, you could put a call to MirageOS' vputa.

In ARM assembly:

Code:
```@ input: r0 = 32 bit number to check @ output: r1 holds number of 0s    mov r1,#32 loop:    adds r0,r0,r0    subcs r1,r1,#1    bne loop```
16 bytes, 40-50 characters.
Written for clarity over source code size, though you could flip stuff around and remove some spaces to make it a bit smaller.

Code:
```digits :: Int -> Int digits x = sum [1 - (x `div` 2^y) `mod` 2 | y <- [0..31]] ```
Reminder:
Quote:
count the number of 0s in the binary representation of the number and display the result.

Rust. (Runnable)

Code:
`(0..32).fold(0,|a,i|a+((!x>>i)&1))`
I made it a bit smaller.
Code:
`(0..32).map(|i|(!x>>i)&1).sum()`

And with printing.

Code:
`println!("{}",<see above>)`

Or being kind of cheaty but more efficient (though the optimizer managed to bring even my above code down to just a constant load):

Code:
`println!("{}",unsafe{::std::intrinsics::ctpop32(!x)})`
Tari wrote:
Reminder:
Quote:
count the number of 0s in the binary representation of the number and display the result.

But mah purity!
*Sigh* Fine...

Code:
```digits :: Int -> IO () digits x = print \$ sum [1 - (x `div` 2^y) `mod` 2 | y <- [0..31]] ```
Okay, I'm bad at this, but Lua, 74 bytes

Code:
``` s=""while x>0 do s=(x%2)..s x=math.floor(x/2)end s=s:gsub("1","")print(#s) ```
Keeping this going a bit.

Challenge 2

Implement an RLE compressor frontend. Given a list/stream/whatever of input bytes emit pairs of (value, length) in an output list/stream/whatever.
For example, [1, 2, 2, 5, 9, 0, 0, 0, 0, 0, 1] becomes [(1,1), (2,2), (5,1), (9,1), (0,5), (1,1)].
Will the input bytes ever be negative?
They're bytes. Interpret as you like, as long as it's lossless.

Code:
```def g(i):     c=0     p=i[0]     for x in i:         if p!=x:             print((p,c))             p=x             c=0         c+=1     print((p,c))```
That's a boring and reasonable solution. How badly does it break if the input is empty?

I built a kind of weird iterator-based version in Rust:
Code:
```fn rle_frontend<I: Iterator<Item=u8>>(mut i: I) -> Vec<(u8, usize)> {     let h = match i.next() {         None => return vec![],         Some(x) => vec![(x, 1)]     };     i.fold(h, |mut a, x| {         if match a.last_mut().unwrap() {             &mut (y, ref mut n) if y == x => {                 *n += 1;                 false             }             _ => true         } { a.push((x, 1)) }         a     }) }```
Tari wrote:
That's a boring and reasonable solution. How badly does it break if the input is empty?

It'll throw an IndexError if 'i' is empty
I'm trying to think up a TI-BASIC solution using seq(), but so far I'm coming up blank. I'm afraid that perhaps seq() can only perform O(1) operations on lists, not O(n) operations.
KermMartian wrote:
I'm trying to think up a TI-BASIC solution using seq(), but so far I'm coming up blank. I'm afraid that perhaps seq() can only perform O(1) operations on lists, not O(n) operations.

cumSum and/or ΔList are almost certainly your friends here.

Assuming input in L1, the upper index on your seq should be

Code:
`sum(0≠ΔList(L1`
and not
Code:
`dim(L1)`

[edit 2]
Okay, haven't run this, but I'm 99% sure it works:

Code:
```augment({1},0≠ΔList(L1->L2 sum(L2->N SortD(L2seq(I,I,1,dim(L1->L2 N->dim(L2 SortA(L2 seq(I,L1(Ans(I))+iAns(I),1,N ```

[edit 3]
Meh: now actually works.

Code:
```augment({1},0≠ΔList(L1->L2 sum(L2->N L2seq(I,I,1,dim(L1->L2 SortD(L2 N->dim(L2 SortA(L2 ΔList(augment(L2,{1+dim(L1 iAns+seq(L1(L2(I)),I,1,N ```
Double post, but here's a cute implementation in Pyret:

Code:
```import my-gdrive("streams.arr") as S fun rle(in):   fun help(shadow in, pv, ct):     cases(S.Stream<Number>) in:       | s-link(h,r) =>         t = lam(): help(r(),h,1);         ask:           | ct == 0 then: t()           | h == pv then: help(r(), h, ct + 1)           | otherwise: S.s-link(S.pair(pv, ct), t);       | s-empty =>         t=lam():S.s-empty;         if ct == 0: t()         else: S.s-link(S.pair(pv,ct),t);;;   help(in, 0, 0);```

(the streams implementation is my own library and not a standard API, but the same RLE implementation would work almost trivially for the built-in list type, using even less code, since the tails wouldn't need to be thunked).

Pyret is a good language for golf, because the typing is optional (except for cases), and the end token has ; as a synonym. Here's the same program written verbosely:

Code:
```import my-gdrive("streams.arr") as S fun rle(inp :: S.Stream<Number>) -> S.Stream<S.Tuple<Number, Number>>:   fun help(shadow inp :: S.Stream<Number>, prev :: Number, count :: Number):     cases(S.Stream<Number>) inp:       | s-link(h :: Number,r :: (-> S.Stream<Number>)) =>         t = lam():           help(r(),h,1)         end         ask:           | count == 0 then:             t()           | h == prev then:             help(r(), h, count + 1)           | otherwise:             S.s-link(S.pair(prev, count), t)         end       | s-empty =>         t = lam():           S.s-empty         end         if count == 0:           S.s-empty         else:           S.s-link(S.pair(prev,count),             lam():               S.s-empty             end)         end     end   end   help(inp, 0, 0) end```

Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»
» All times are UTC - 5 Hours

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum