30
\$\begingroup\$

(Title with thanks to @ChasBrown)

Sandbox

The Background

This challenge is inspired by a question that I recently posted on Puzzling Stack Exchange. Please feel free to follow the link if you are interested in the original question. If not then I won't bore you with the details here.

The Facts

Every printable standard ASCII character has a decimal value between 32 and 126 inclusive. These can be converted to their corresponding binary numbers in the range 100000 to 1111110 inclusive. When you sum the bits of these binary numbers you will always end up with an integer between 1 and 6 inclusive.

The Challenge

Given an integer between 1 and 6 inclusive as input, write a program or function which will output in any acceptable format all of the printable standard ASCII characters where the sum of the bits of their binary value is equal to the input integer.

The Examples/Test Cases

1 -> ' @'
2 -> '!"$(0ABDHP`'
3 -> '#%&)*,1248CEFIJLQRTXabdhp'
4 -> ''+-.3569:<GKMNSUVYZ\cefijlqrtx'
5 -> '/7;=>OW[]^gkmnsuvyz|'
6 -> '?_ow{}~'

An ungolfed Python reference implementation is available here (TIO).

The Rules

  1. Assume the input will always be an integer (or string representation of an integer) between 1 and 6 inclusive.
  2. You may write a program to display the results or a function to return them.
  3. Output may be in any reasonable format but must be consistent for all inputs. If you choose to output a quoted string then the same type of quotes must be used for all inputs.
  4. Standard loopholes prohibited as usual.
  5. This is code golf so shortest code in each language wins.
\$\endgroup\$
  • \$\begingroup\$ Are we allowed to return/print a list of the decimal ascii values or do we need to have them in the form of characters (eg. 63 vs ?)? \$\endgroup\$ – Benjamin Urquhart Apr 23 at 19:27
  • 1
    \$\begingroup\$ Must be the actual characters. \$\endgroup\$ – ElPedro Apr 23 at 19:29
  • 7
    \$\begingroup\$ "the same type of quotes must be used for all inputs" Python, for example, uses single quotes (') for the string representation of a string by default, but uses double quotes (") if the string contain a single quote and no double quotes. Not that this specific case will matter much, as you're probably better off returning the actual string instead of its representation, and you can still use single quotes in such a string for input anyway, but I feel it's worth mentioning here. \$\endgroup\$ – Erik the Outgolfer Apr 23 at 19:59
  • \$\begingroup\$ @EriktheOutgolfer Agreed. That is why I thought it might be interesting just to throw that in as an extra rule :-) \$\endgroup\$ – ElPedro Apr 23 at 23:03
  • 1
    \$\begingroup\$ @ElPedro I wasn't sure what to do as it is probably a good idea to have some quotes, as there is a space in the first example, but the usual quotes both appear in the output:) Edit: maybe use french guillemets (« »)? :D \$\endgroup\$ – flawr Apr 24 at 13:11

50 Answers 50

2
\$\begingroup\$

Haskell, 77 bytes

import Data.Char
b 0=0
b k=mod k 2+b(div k 2)
f n=[chr k|k<-[32..126],b k==n]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Z80Golf, 25 bytes

00000000: cd03 806f 0e20 517d 45cb 3a9b 10fb de30 ...o. Q}E.:....0
00000010: 2002 79ff 0ce2 0600 76                   .y.....v

Try it online!

  call $8003    ; A = getchar(), e.g. '5'
  ld l, a       ; L = A
  ld c, ' '     ; C = ' '
next:           ; do {
  ld d, c       ;   D = C
  ld a, l       ;   A = L, e.g. '5'
  ld b, l       ;   B = L (way more than enough)
more:           ;   while (--B ≠ 0) {
  srl d         ;       shift D right, bit 0 goes into Carry
  sbc a, e      ;       A -= 0 + Carry
  djnz more     ;   }
done:
  sbc a, '0'    ;   A -= '0' + Carry
  jr nz, omit   ;   if A == 0:
  ld a, c       ;       putchar(C)
  rst $38
omit:
  inc c         ;   C++
  jp po, next   ; } until overflow, i.e. stop when C becomes 0x80 = -128
  halt
\$\endgroup\$
2
\$\begingroup\$

Haskell, 61 bytes

f n=[toEnum k|k<-[32..126],sum[k`div`2^i`mod`2|i<-[0..6]]==n]

Try it online!

The type of f is f :: (Enum t) => Int -> [t]. That's more general than necessary, and it means you need to e.g. putStrLn the result for Haskell to infer that you want a [Char] result.

I don't know what the rules say about that, but replacing toEnum k with ['\0'..]!!k is a workaround costing 3 bytes.

\$\endgroup\$
2
\$\begingroup\$

Forth (gforth), 81 bytes

: f 127 32 do 0 i begin 2 /mod >r + r> ?dup 0= until over = if i emit then loop ;

Try it online!

Code Explanation

: f           \ start a new word definition
  127 32      \ set up loop parameters
  do          \ loop from 32 to 126
    0 i       \ set up values for counting bits
    begin     \ start an indefinite loop
      2 /mod  \ divide by 2 and get quotient and remainder
      >r + r> \ add the remainder to the counter
      ?dup 0= \ check if quotient equals zero
    until     \ end the loop if it is
    over =    \ check if the result equals the input number
    if        \ if it is
      i emit  \ output the char for the current ascii value
    then      \ end the if
  loop        \ end the counted loop
;             \ end word definition
\$\endgroup\$
2
\$\begingroup\$

Scala, 88 87 bytes

(y:Int)=>32 to 126 map{x=>BigInt(x).bitCount->x}filter(_._1==y)map(_._2.toChar)mkString
\$\endgroup\$
  • \$\begingroup\$ I'm not that familiar with Scala, but are static calls possible like in Java? And if yes, can bytes be saved by changing (y:Int)=> to (y:Integer)=> and Integer.bitCount(x) to y.bitCount(x)? \$\endgroup\$ – Kevin Cruijssen Apr 24 at 13:04
  • \$\begingroup\$ @KevinCruijssen Can't use Integer but I can cast the value to BigInt and use bitCount on that. Thanks! \$\endgroup\$ – Soapy Apr 24 at 14:03
2
\$\begingroup\$

C (GCC) - 134 Bytes

#include <stdio.h>
#include <stdlib.h>
int main(int _,char**v){for(char c=32;c<127;c++)__builtin_popcount(c)-atoi(v[1])||putchar(c);}

Compile with gcc chars.c -o chars, and run the resulting program with the number of bits as the command-line argument.

Compiles with no warnings.

This program utilizes the __builtin_popcount builtin that is present in GCC, which resolves to a POPCNT instruction on most x86 hardware built in the last dozen or so years.

\$\endgroup\$
2
\$\begingroup\$

C(MSVC) 50 bytes

i;f(n){for(i=31;i++<127;n-__popcnt(i)||puts(&i));}

C(gcc), 60 bytes

i;f(n){for(i=31;i++<127;n-__builtin_popcount(i)||puts(&i));}

Try it online

\$\endgroup\$
  • \$\begingroup\$ Can you not use || instead of ?n:? \$\endgroup\$ – Neil Apr 24 at 8:38
  • \$\begingroup\$ Thank you @Neil \$\endgroup\$ – Johan du Toit Apr 24 at 9:15
  • \$\begingroup\$ You can remove one byte by combining the increment with the check: i;f(n){for(i=32;i++<127;n-__builtin_popcount(i)||puts(&i));} \$\endgroup\$ – LambdaBeta Apr 24 at 18:19
2
\$\begingroup\$

Perl 5 - 42+1

This is a modification of @Xcali solution, saving one character. Perl's unpack has a built-in bit counting mechanism, no need for the mod-9 trick.

#!perl -a
map{$_=chr;unpack('%B*')-"@F"||say}32..126
\$\endgroup\$
2
\$\begingroup\$

Stax, 7 bytes

æq≥çq╪╖

Run and debug it

Ungolfed, unpacked, and commented, it looks like this.

Vp  constant for all printable ascii characters
{   start filter block
 :1 "pop-count" of codepoint
 x= equals the input
f   execute filter

Run this one

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Client && NodeJs), 222 bytes

Try it online

x=>[...Array(127).keys()].slice(32).reduce((a,d)=>(a.push({y:[...d.toString(2)].map(x=>+x),z:String.fromCharCode(d)}),a),[]).map(i => (i.y.reduce((a,b)=>(a.y+=+b,a),{y:0,z:i.z}))).reduce((a,b)=>(b.y==x?a.push(b.z):0,a),[])
\$\endgroup\$
1
\$\begingroup\$

T-SQL, 153 bytes

Query returns 1 row for each character.

DECLARE @ INT=6

SELECT char(number)FROM
spt_values,(values(1),(2),(4),(8),(16),(32),(64))x(x)WHERE
type='P'and number/32in(1,2,3)GROUP BY number
HAVING sum(number/x%2)=@

Try it online

186 bytes

Putting all characters in same row:

DECLARE @ INT=6

SELECT string_agg(char(h),'')FROM(SELECT
iif(sum(number/x%2)=@,number,-1)h
FROM spt_values,(values(1),(2),(4),(8),(16),(32),(64))x(x)WHERE
type='P'and number/32in(1,2,3)GROUP BY number)c

Try it online

\$\endgroup\$
1
\$\begingroup\$

Attache, 25 bytes

${{x=1~Bin[Ord@_]}\ascii}

Try it online!

Alternatives

26 bytes: ${{x=1~(Bin@Ord@_)}\ascii}

26 bytes: ${{x=Sum@Bin@Ord@_}\ascii}

28 bytes: ${Char!{x=Sum@Bin@_}\32:126}

28 bytes: ascii&${{y=Sum@Bin@Ord@_}\x}

34 bytes: ascii&{Mask[_2=Sum@Bin=>Ords@_,_]}

35 bytes: ascii&{Mask[_2=1&`~@Bin=>Ords@_,_]}

Explanation

${{x=1~Bin[Ord@_]}\ascii}
${                      }   lambda with named parameter `x` (for scoping)
  {              }\ascii    select all ascii characters...
     1~                       where the number of 1s
       Bin[Ord@_]             in the character's binary representation
   x=                         equals the parameter
\$\endgroup\$
1
\$\begingroup\$

6502 Assembly (NES), 29 bytes

Outputs as tiles to the screen.

Machine code: (xx represents branch displacement bytes which I would probably get wrong assembling by hand)

A2 1F
E8
30 xx
86 01
A9 00
06 01
F0 xx
69 00
10 xx
69 00
C5 00
D0 xx
8E 07 20
D0 xx
60

Assembly:

; Output buffer address in $2006 PPU_ADDR. bits in address 0.
    ldx #31 ; initialize first printable character
@loop:
    inx
    bmi @done ; stop at 128 (127 won't match on input 1-6)
    stx 1 ; initialize address 1 with character
    lda #0
@bits:
    asl 1 ; load a bit into carry
    beq @next
    adc #0 ; add the carry to a
    bpl @bits ; branch always
@next:
    adc #0
    cmp 0
    bne @loop
    stx $2007
    bne @loop
@done:
    rts
\$\endgroup\$
1
\$\begingroup\$

Clean, 65 bytes

import StdEnv
$n=[c\\c<-[32..127]|sum[(c>>p)rem 2\\p<-[0..6]]==n]

Try it online!

Defines $ :: Int -> [Int] giving a list of codepoints.

\$\endgroup\$
1
\$\begingroup\$

Rust - 112 bytes

fn a(i:u32)->String{std::str::from_utf8(&(0..128u8).filter(|x|x.count_ones()==i).collect::<Vec<u8>>()).unwrap()}

Going for worst reasonable answer. Rust does not allow simple conversions from ints to chars to strings.

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 92 bytes

f=(b,c=32)=>c<127?(c.toString(2).match(/1/g).length-b?String.fromCharCode(c):"")+f(b,c+1):""

I like Number.prototype.toString(n).

f=(b,c=32)=>                                                                                 //function declaration, starting at character code 32.
            c<127?                                                                           //check for out of range
                  (c.toString(2)                                                             //if the number in binary has
                                .match(/1/g).length                                          //number of 1 bits
                                                   -b?                                       //equal to b
                                                      String.fromCharCode(c):"")             //then add the character
                                                                                +f(b,c+1)    //next character

  :"" //base case for out of range(127)
\$\endgroup\$
1
\$\begingroup\$

C++ (gcc), 124 113 bytes

-11 bytes thanks to @ceilingcat

#import<string>
auto a(int n){std::string f;for(int i=30,j,k;++i<127;f+=i*!j,j=n)for(k=i;k;k/=2)j-=k&1;return f;}

Try it online!

Iterates through the printable character codes, finds those that match the number of 1 bits desired, returns the string containing those characters concatenated.

\$\endgroup\$
  • \$\begingroup\$ Out of curiosity, why does i start at 30 instead of 31? It's currently looping in the range (30,127), but shouldn't this be (31,127)? \$\endgroup\$ – Kevin Cruijssen Apr 24 at 6:45
  • \$\begingroup\$ You don't have to add the #include statements to your code length, TIO 97 bytes \$\endgroup\$ – Johan du Toit Apr 24 at 9:46
  • 1
    \$\begingroup\$ @KevinCruijssen: this relies on j being zero-initialized; the j=n condition is only run after the first loop, so since j is 0 the first time around, the first loop does nothing. Hence the first value that is actually checked is 32. \$\endgroup\$ – Neil A. Apr 24 at 23:55
  • 1
    \$\begingroup\$ @JohanduToit why don't I have to add the #import statement? Aren't imports considered part of the code (since they are necessary for it to function)? \$\endgroup\$ – Neil A. Apr 24 at 23:56
  • \$\begingroup\$ @NeilA. sorry, you are correct. You can still save one byte by using a 'for' loop instead of the 'while'. \$\endgroup\$ – Johan du Toit Apr 25 at 5:40
1
\$\begingroup\$

dc, 52 bytes

sn31[dP]sP[1+dd[2~rd0<B]dsBx[+z3<S]dsSxln=PC6>M]dsMx

Try it online!

sn to store our target bit count from top-of-stack into register n. 31 starts us off at our first ASCII value (the main macro increments it immediately). [dP]sP is a printing macro, we call this when the bit count is equal to the target. Into our main macro, M... 1+dd increments top-of-stack and duplicates it twice. [2~rd0<B]dsBx uses integer division by two w/ remainder to break a decimal value down into binary bits on the stack. [+z3<S]dsSx sums stack items until we're back to three values on the stack - our summation and two copies of our ASCII value. ln=P compares the summation with n, our target bit count, and runs the printing macro P if they're equal. C6>M keeps running M through ASCII value 126.

One thing to note that I sometimes forget about when golfing in dc is that there's no harm in burying macros B and S inside of M since they're always going to run at least once per run of M. This saves a byte in each case - dsBx instead of sB outside of macro M and then lBx inside.

\$\endgroup\$
  • 1
    \$\begingroup\$ Have never heard of dc before but it looks cool. +1 for the good explanation. \$\endgroup\$ – ElPedro May 2 at 21:51
  • \$\begingroup\$ @ElPedro, it's a fun language to mess around with. Somewhat golfy in that commands are all a single character, but then you get into issues like conditionals only being able to run macros. So if you want to print if something ==0, you can't 0=p but rather must make a macro that prints [p]sp and then call that. Stack movement is also very limited. A lot of little things working against you that makes it a fun challenge. \$\endgroup\$ – brhfl May 3 at 12:56
1
\$\begingroup\$

Clam, 11 bytes

p#:\bcqQ'a-

Prints an array of characters

Explanation

            - Implicit Q = first input
p           - Print...
        'a- - ASCII characters (dictionary access)
 #          - Where...
   \        - The sum of...
    b       - The binary bits of...
     cq     - The charcode of the character
  :         - Equals...
       Q    - Q
\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 43 bytes

y->filter(x->count_ones(Int(x))==y,' ':'~')

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.