Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In many fonts (specifically in the Consolas font), 5 out of the 10 decimal digits have "holes" in them. We will call these holy digits:

46890

The 5 unholy digits are thus:

12357

An integer may thus be classified as "holy" if it only contains holy digits, and "unholy" otherwise. Because - is unholy, no negative integers can be holy.

Holy integers may be further classified based on how many holes they have. For example, the following digits have a holiness of 1:

469

And these digits have a holiness of 2:

80

We say that the overall holiness of an integer is the sum of the holiness of its digits. Therefore, 80 would have a holiness of 4, and 99 would have a holiness of 2.

The Challenge

Given two integers n > 0 and h > 0, output the nth holy integer whose holiness is at least h. You may assume that the inputs and outputs will be no greater than the maximum representable integer in your language or 2^64 - 1, whichever is less.

Here is a list of the first 25 holy integers with holiness h >= 1, for reference:

0, 4, 6, 8, 9, 40, 44, 46, 48, 49, 60, 64, 66, 68, 69, 80, 84, 86, 88, 89, 90, 94, 96, 98, 99

The first 25 holy integers with holiness h >= 2 are:

0, 8, 40, 44, 46, 48, 49, 60, 64, 66, 68, 69, 80, 84, 86, 88, 89, 90, 94, 96, 98, 99, 400, 404, 406
share|improve this question
    
Related - 1 2 – Mego Feb 17 at 20:23
24  
i was sitting here for like thirty seconds thinking "how the heck does 0 have a holiness of two" before i finally clicked on the wikipedia link to Consolas – undergroundmonorail Feb 17 at 21:20
    
Is the fifth 1-Holy number 9 or 40? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Feb 17 at 22:54
3  
Is it just coincidence that the 8th 8+-holy number is 8888? (yes, it probably is, but it amused me anyway...) – Toby Speight Feb 18 at 16:34
4  
In fact, since you can have any number of leading 0's before a number, one could make the case that 0 is infinitely holy. Although ∞ is apparently just as holy. But strangely, 666 is even holier... – Darrel Hoffman Feb 18 at 16:47

18 Answers 18

up vote 6 down vote accepted

Pyth, 32 bytes

e.fg*g.{`46890J`Z++lJ/J`8/J`0QE0

Explanation

                                 - autoassign Q = eval(input())
 .f                           E0 -  first eval(input()) terms of func V starting Z=0

     g.{`46890J`Z                -    Are all the digits in Z in "46890"?
               `Z                -      str(Z)
              J                  -     autoassign J = ^
     g                           -    is_subset(V,^)
      .{`46890                   -     set("46890")

    *                            -   ^*V (Only return non-zero if only contains holy numbers)

                 ++lJ/J`8/J`0    -    Get the holiness of the number
                   lJ            -      len(J)
                  +              -     ^+V
                     /J`8        -      J.count("8") 
                 +               -    ^+V
                         /J`0    -     J.count("0")
   g                         Q   -  ^>=Q (Is the holiness great enough)
e                                - ^[-1]

Try it here

Takes input in the form h \n n

share|improve this answer

Ruby, 109 105 95 82 bytes

->n,h{(?0..?9*99).select{|x|x.count('469')+2*x.count('80')>=h&&/[12357]/!~x}[n-1]}

This is the terrible "calculate from 0 to 99999999999..." approach that happens to be 13 bytes shorter than its lazy counterpart. However, this version is unlikely to finish before the heat death of the universe. Worth 13 bytes, anyway ¯\_(ツ)_/¯

You can test it for smaller values by changing ?9*99 to, say, '99999'.

Here's the old version (95 bytes, with lazy evaluation, which runs near-instantly rather than near-never):

->n,h{(?0..?9*99).lazy.select{|x|x.count('469')+2*x.count('80')>=h&&/[12357]/!~x}.first(n)[-1]}
->n,h{
(?0..?9*99)  # range '0' (string) to '9' repeated 99 times, way more than 2**64
.lazy        # make the range lazy, so we can call `select' on it
.select{|x|  # choose only elements such that...
 x.count('469')+2*x.count('80')  # naive holiness calculation
 >=h         # is at least h
 &&/[12357]/!~x                  # naive "is holy" calculation
}
.first(n)    # take the first n elements that satisfy the condition
[-1]         # choose the last one from this array
}
share|improve this answer
    
Gotta love lazy evaluation :) – Emigna Feb 17 at 21:19
    
Why not take instead of first? – Not that Charles Feb 17 at 22:37
    
@NotthatCharles take returns Lazy, which can't be indexed into. – Doorknob Feb 17 at 23:39

Python 3, 103

lambda n,h,l='4698080':[y for y in range(2**64-1)if(sum(l.count(x)-(x not in l)for x in str(y))>=h)][n]

Here's a solution that uses a more memory efficient approach, but otherwise uses the same algorithm if you want to test it.

l='4689080'
def f(n,h):
 c=i=0
 while i<n:
  if sum(l.count(x)-(x not in l)for x in str(c))>=h:u=c;i+=1
  c+=1
 return u

Test cases:

assert f(3, 1) == 6
assert f(4, 2) == 44
share|improve this answer
    
@Mego Cool. It seems to use a static amount of memory, so it's not in danger of running out of memory. I just wasn't sure since it's been running on my machine for half an hour already. – Morgan Thrapp Feb 17 at 21:16
    
It actually takes a decent chunk of time just to calculate 2**64-1; see stackoverflow.com/questions/34113609/… – Mego Feb 17 at 21:22
    
@Mego Oh, I didn't even think about that. Yeah, when I put the precomputed constant into the code, it starts chewing through a bit of RAM. – Morgan Thrapp Feb 17 at 21:24

PowerShell, 163 150 141 101 98 96 bytes

param($n,$h)for(--$i;$n){if(++$i-notmatch"[12357]"-and($i-replace"8|0",11).Length-ge$h){$n--}}$i

Takes input, then loops until $n is zero. We initially setting $i=-1 by using a pre-processing trick, which works because $i, having not previously been declared, is $null. Then we -- it, which causes PowerShell to evaluate it as $i = $null - 1, which is $i=-1.

Each loop we increment $i and then execute a lengthy if statement. The first part of the conditional verifies that $i doesn't have any of 12357 in it by using the -notmatch operator, to filter out the unholy numbers.

The second part of the conditional checks the quantity of holes in $i. It uses the -replace operator to replace each 8 or 0 with 11, and then compares whether the length is >= $h. We don't need to worry about stripping out the unholy numbers, since that's in the first part of the conditional, and the single-holed numbers are the same length as 1 anyway, so we don't need to replace them, either.

If that is still truthy, we decrement $n (as that means we've found another number that satisfies input requirements). Thus when the for condition is recalculated to check if $n is zero, that means we've found the nth one, so we exit the for loop, output $i and terminate.

Edit -- saved 13 bytes by using an array instead of string for $l and changing how $n is decremented/checked
Edit 2 -- saved an additional 9 bytes by checking for $n in the for conditional and moving the output outside the loop
Edit 3 -- saved a whopping 40 more bytes by radically changing how we calculate the holes
Edit 4 -- saved an additional 3 bytes by moving the ++ to be a pre-increment on the first part of the conditional
Edit 5 -- saved another 2 bytes thanks to TessellatingHeckler

share|improve this answer
    
Neat. Save another couple of bytes by changing to for(--$i;$n) and -replace"8|0" ? – TessellatingHeckler Feb 19 at 15:39
    
@TessellatingHeckler Yes, thank-you. That $i=-1 was driving me absolutely bonkers. I'm still trying to work out a way so we don't have to initialize $i in the first place, but things I've tried so far are longer (and, now given this, will likely be longer yet). – TimmyD Feb 19 at 15:43

CJam, 36 34 bytes

Thanks to aditsu for saving 2 bytes.

Wq~:X;{{)_Ab39643Zbf=_:*g*1bX<}g}*

Test it here.

share|improve this answer

Bash + GNU utilities, 67

  • 20 bytes saved thanks to @TobySpeight!
seq 0 NaN|sed -r "h;/[12357]/d;s/8|0/&&/g;/^.{$1}/!d;x"|sed $2!d\;q
  • seq simply generates integers starting from 0 upwards
  • sed -r:
    • h copy the input line to the hold space
    • /12357/d delete unholy numbers
    • s/8|0/&&/g replace doubly holy digits with twice themselves. Thus singly holy digits are counted once and doubly holy digits are counted twice.
    • /^.{$1}/!d If not matching at least $1 holes, delete and continue to the next line
    • x bring original number back to the pattern space
    • implicit print
  • sed
    • $2!d on any lines before line $2, delete and continue to the next line
    • q must be at line $2 - quit (and implicit print)

Ideone.

share|improve this answer
1  
Shave 9: sed -r "h;/[12357]/d;s/8|0/&&/g;/^.{$1}/!d;x". And another 4: sed $2!d\;q. And if you're happy with an upper bound of just 4611686018427387904, you could get away with seq 0 $[1<<62] – Toby Speight Feb 18 at 16:24
1  
Ooh, my seq accepts NaN as a value: I now have seq 0 NaN|sed -r "h;/[12357]/d;s/8|0/&&/g;/^.{$1}/!d;x"|sed $2!d\;q, scoring 67. – Toby Speight Feb 18 at 16:32
    
@TobySpeight wow thats amazing! – Digital Trauma Feb 18 at 17:14
    
@TobySpeight : missing a \ before the !, otherwise: -sh: !d\: event not found – Olivier Dulac Feb 18 at 17:32
1  
@OlivierDulac ` before !` is not needed in a script. It is only needed when running this directly on the command-line, which I don't think is a requirement. – Digital Trauma Feb 18 at 17:41

MATL, 39 40 bytes

x~q`QtV4688900V!=stA*s2G<?T}N1G=?F1$}tT

Inpunts are n and h in that order.

Try it online!

We need to keep track of two numbers: current candidate number (to check its holiness) and amount of numbers found that are holy enough. The first is the top od the stack, and the latter is kept as the number of elements in the stack. When the program finishes, only the top needs to displayed.

x~q          % implicitly take two inputs. Delete one and transform the other into -1
`            % do...while loop
  Q          %   add 1 to current candidate number
  tV         %   duplicate and convert to string
  4688900V!  %   column char array of '4', '6' etc. Note '8' and '0' are repeated 
  =          %   compare all combinations. Gives 2D array
  s          %   sum of each column: holiness of each digit of candidate number
  tA*        %   are all digits holy? Multiply by that
  s          %   sum of holiness of all digits, provided they are all holy
  2G<        %   is that less than second input (h)?
  ?          %   if so: current candidate not valid. We'll try the next
    T        %     push true to be used as loop condition: next iteration
  }          %   else: current candidate valid
    N1G=     %     does stack size equal first input (n)?
    ?        %     if so: we're done
      F1$    %       push false to exit loop. Spec 1 input, to display only top
    }        %     else: make a copy of this number
      tT     %       duplicate number. Push true to continue with next iteration
             %     implicit end if 
             %   implicit end if 
             % implicit end do...while. If top of stack is truthy: next iteration
             % implicit display
share|improve this answer

R, 109 107 bytes

f=function(n,h){m=-1;while(n){m=m+1;if(!grepl("[12357]",m))if(nchar(gsub("([08])","\\1\\1",m))>=h)n=n-1};m}

With new lines and indentations:

f=function(n,h){
    m=-1
    while(n){
        m=m+1
        if(!grepl("[12357]",m))
            if(nchar(gsub("([08])","\\1\\1",m))>=h)
                n=n-1
    }
    m
}

Usage:

> f(4,3)
[1] 68
> f(4,2)
[1] 44
> f(6,2)
[1] 48
> f(10,2)
[1] 66
share|improve this answer

JavaScript (ES6), 110 bytes

f=(n,h,r=[],i=0)=>r.length<n?f(n,h,/[12357]/.test(i)|[...''+i].reduce((t,c)=>t+1+!(c%8),0)<h?r:[...r,i],i+1):r

Tail recursive solution that accumulates holy numbers in an array.

Out of interest, not requiring the number to be wholly(!) holy makes the holiness count more awkward, but it still saves 10% overall:

f=(n,h,r=[],i=0)=>r.length<n?f(n,h,[...''+i].reduce((t,c)=>+"2000101021"[c]+t,0)<h?r:[...r,i],i+1):r
share|improve this answer
    
@edc65 Whoops, I swapped over the i and r parameters at one point, and failed to edit the change in correctly. – Neil Feb 18 at 14:06

JavaScript ES6, 191 bytes

Sure, this isn't the most efficient way. But you know me, I love generators <3

H=(x,o=x+"")=>(F=/^[46890]+$/).test(o)&&[...o].map(y=>d+=(F.test(y)+/8|0/.test(y)),d=0)&&d;(n,h)=>(a=(function*(h){q=0;while(1){if(H(q)>=h)yield q;q++}})(h),eval("a.next().value;".repeat(n)))

Slightly ungolfed:

H = (x, o = x + "") => (F = /^[46890]+$/).test(o) && [...o].map(y => d += (F.test(y) + /8|0/.test(y)), d = 0) && d;
Q = (n, h) => (a = (function*(h) {
    q = 0;
    while (1) {
        if (H(q) >= h) yield q;
        q++
    }
})(h), eval("a.next().value;".repeat(n)))
share|improve this answer

C# 6, 168 bytes

(n,h)=>{for(int i=0;i<=int.MaxValue;i++){string d=$"{i}";if(d.Any(y=>"12357".Contains(y)))continue;n-=d.Sum(y=>y=='0'||y=='8'?2:1)>=h?1:0;if(n==0)return i;}return -1;}

This is a Lambda Expression of type Func< int, int, int>. This code is otimized for min size (not performatic).

Below, the beautified code in method declaration (with more performance):

    int GetHolyNumber(int n, int h)
    {
        for (int i = 0; i <= int.MaxValue; i++)
        {
            string d = $"{i}";
            char[] cs = "12357".ToArray();
            if (d.Any(y => cs.Contains(y))) continue;

            n -= d.Sum(y => y == '0' || y == '8' ? 2 : 1) >= h ? 1 : 0;

            if (n == 0)
                return i;
        }
        return -1;
    }
share|improve this answer
    
Hi Bobson, sorry if I misunderstood, but do not detect faults that you pointed out in my code? It returns the nth element required, and only he, and zero if it is valid, assuming that the inputs are n = 1 and h <= 2. If I understand the challenge, must return only this one element and not all up to him. But I have misunderstood me and lost in English :D thanks – Paulo César B. Sincos Feb 22 at 17:11
    
No, you're entirely right. I was mislead by the lists-for-reference, and missed the fact that it was just asking for the nth digit. Carry on! – Bobson Feb 22 at 19:13

JavaScript (ES6), 87

(n,h)=>eval("for(i=0;[...i+''].map(d=>r-=~!(d%8),r=0),/[12357]/.test(i)|r<h||--n;)++i")

Less golfed

f=(n,h)=>{
  for (i=0;
    // this is the loop condition
    /[12357]/.test(i) // go on if not holy
    ||([...i+''].map(d=>r-=~!(d%8),r=0),r<h) // go on if not holy enough
    ||--n; // ok, found one! go on if we need to find more
  )
    ++i; // loop body - using eval this is the returned value
  return i; // not using eval, an explicit return is needed
}  

Test

f=(n,h)=>eval("for(i=0;[...i+''].map(d=>r-=~!(d%8),r=0),/[12357]/.test(i)|r<h||--n;)++i")

function test() {
  var a,b
  [a,b]=I.value.match(/\d+/g)
  R.textContent = f(a,b)
}

test()
N, H: <input id=I value="25 2" oninput="test()"> >>
<span id=R></span>

share|improve this answer

Lua, 169 bytes

function a(n,h)H=0N=0I=-1while N<n do I=I+'1'H=0 if not I:find('[12357]') then _,b=I:gsub('[469]',1)_,c=I:gsub('[08]',1)H=b+2*c end N=H>=h and N+1 or N end print(I) end

Ungolfed:

function a(n,h) -- nth term, holiness
    H=0N=0I=-1 -- Really ugly, but hey, it works. Set up 3 vars
    while N<n do -- While nth term is lower than desired term
        I=''..I+1 -- Convert number to string (can't coerce since it will become a float)
        if not I:find('[12357]') then -- If the number doesn't have those numbers
            _,b=I:gsub('[469]',1) -- _ is the new string, b is the number of changes
            _,c=I:gsub('[08]',1) -- Same as above. Use 1 to replace to save chars
            H=b+2*c -- Increase holiness appropriately
        end
        N=H>=h and N+1 or N -- If current holiness >= desired holiness, increment N
    end 
    print(I) -- Once the loop ends, print the current term
end
share|improve this answer

Lua, 155 141 140 Bytes

Takes both inputs by command-line argument(first argument is n, then h)

Edit: Thanks to @DavisDude, who helped me shaving 14 bytes off and reminded me I didn't have to print all the holy numbers up to n, but only the nth.

a={}x=0while(#a<arg[1])do b,c=(x..""):gsub("[08]","")e,d=b:gsub("[469]","")a[#a+1],x=c*2+d>=arg[2]and #e<1 and x or nil,x+1 end print(a[#a])

Ungolfed and explanations

x,a=0,{}                      -- initialise a counter, and the array which 
                              -- contains the holy numbers found
while(#a<arg[1])              -- iterate while we found less holy numbers than n
do
  b,c=(x..""):gsub("[08]","") -- replace [08] by "", b=the new string
                              -- c=the number of subsitution
  e,d=b:gsub("[469]","")      -- same thing for [469]
  a[#a+1]=c*2+d>=arg[2]       -- insert the number into a if:nb[08]*2+nb[469]>h
             and #e<1         -- and e is empty (no unholy numbers)
             and x or nil
      x=x+1                   -- increment x
end
print(a[#a])                  -- print the last element of a
share|improve this answer
    
You could take off some chars by doing print(a[arg[1]]) – DavisDude Feb 19 at 17:37
    
@DavisDude I was dumb, when I wrote this, I though I had to print out the entire list of unholy numbers up to n. Actually, print(a[#a]) saves even more bytes. Thanks for the comment ! – Katenkyo Feb 22 at 7:21
    
You are write. For some reason that didn't even occur to me. – DavisDude Feb 22 at 20:34
    
You can take off one char by writing x=0a={} instead of x,a=0,{}. – Leaky Nun Mar 30 at 10:41
1  
@KennyLau Actually, you can't because 0a would be interpreted as an hexadecimal number, but I can do a={}x=0while without a problem :) – Katenkyo Mar 30 at 11:14

Oracle SQL 11.2, 229 bytes

WITH v(c,p,i,j,n)AS(SELECT 0,-1,0,0,0 FROM DUAL UNION ALL SELECT c+1,c,REGEXP_COUNT(c||'','[4,6,9]'),REGEXP_COUNT(c,'[8,0]'),n+DECODE(LENGTH(p),i+j,DECODE(SIGN(i+j*2-:h),-1,0,1),0)FROM v WHERE p<c AND n<:n)SELECT MAX(p)-1 FROM v;

Un-golfed

:h -> required min holy value
:n -> nth number 

curv   -> current number
precv  -> previous number
prech1 -> number of holy 1 letters in previous number 
prech2 -> number of holy 2 letters in previous number
n      -> how many numbers with at least the required holy value 

WITH v(curv,precv,prech1,prech2,n)AS 
(
  SELECT 0 curv, -1 precv, 0 prech1, 0 prech2, 0 n FROM DUAL     -- Start with 0
  UNION ALL
  SELECT curv+1,   -- Next number
         curv,     -- Current Number 
         REGEXP_COUNT(curv||'','[4,6,9]'),  -- number of holy 1 letters
         REGEXP_COUNT(curv,'[8,0]'),        -- number of holy 2 letters
         n+DECODE(LENGTH(precv),prech1+prech2,DECODE(SIGN(prech1+prech2*2-:h),-1,0,1),0) -- Is the previous number holy enough ?
  FROM   v 
  WHERE  precv<curv   -- Needed to trick oracle cycle detection 
         AND n<:n     -- Until clause
)
SELECT MAX(precv)-1 FROM v 
share|improve this answer

Python 2, 96 bytes

f=lambda n,h,k=0,s="0046889":-0**n or-~f(n-(sum(map(s.count,`k`))>=h<set(str(k))<=set(s)),h,k+1)

The holyness condition on k is checked by

  • sum(map(s.count,`k`))>=h, which counts the number of holes by summing the counts for each character in s="0046889", where 0 and 8 appear twice.
  • set(str(k))<=set(s)), which checks that the numbers are all holy. str is used rather than backticks to avoid the suffix L for longs.

These are chained into a single equality using the Python 2 fact that numbers are smaller than sets.

The function is defined recursively to count up numbers k, decreasing the counter n each time a holy number of hit unless it hits 0. It could then return the k that triggered this, but it's shorter to keep the count recursively by adding 1 each time, though an off-by-one requires a base count of -1 to fix.

share|improve this answer

Haskell, 94 bytes

c is the holiness of a digit, v the holiness of a number, n!h does the rest.

c=([2,0,0,0,1,0,1,0,2,1]!!)
v n|n>9=c(mod n 10)+v(div n 10)|1<2=c n
n!h=[i|i<-[0..],v i<=h]!!n

Note: I think this is the only answer without the characters 4,6,8.

share|improve this answer

Swift

func f(n: Int, h: Int) {
    var m = 0
    let a = [1,2,3,5,7]
    for j in 0..<Int.max {
        var c = 0
        for i in (j.description.characters.map{(String($0) as NSString).integerValue}) {
            c += (a.contains(i)) ? 0 : (i == 8 || i == 0) ? 2 :1
        }
        if c >= h { m += 1; if m >= n {print(j); break}}
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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