Os números sagrados

44

Em muitas fontes (especificamente na fonte Consolas ), 5 dos 10 dígitos decimais têm "buracos". Vamos chamar esses dígitos sagrados:

46890

Os 5 dígitos profanos são assim:

12357

Um número inteiro pode, portanto, ser classificado como "sagrado" se contiver apenas dígitos sagrados e "profano" caso contrário. Por -ser profano, nenhum número inteiro negativo pode ser sagrado.

Inteiros sagrados podem ser classificados ainda com base em quantos buracos eles têm. Por exemplo, os seguintes dígitos têm uma santidade de 1:

469

E esses dígitos têm uma santidade de 2:

80

Dizemos que a santidade geral de um número inteiro é a soma da santidade de seus dígitos. Portanto, 80teria uma santidade de 4 e 99teria uma santidade de 2.

O desafio

Dado dois inteiros n > 0e h > 0, produza o nth santo inteiro cuja santidade é pelo menos h. Você pode assumir que as entradas e saídas não serão maiores que o número máximo máximo representável no seu idioma ou 2^64 - 1, o que for menor.

Aqui está uma lista dos primeiros 25 inteiros sagrados com santidade h >= 1, para referência:

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

Os primeiros 25 inteiros sagrados com santidade h >= 2são:

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
Mego
fonte
Relacionado - 1 2
Mego
26
eu estava sentado aqui para como 30 segundo pensando "como o diabo não 0tem uma santidade de dois" antes de eu finalmente clicado no link wikipedia para Consolas
undergroundmonorail
O quinto número 1-Santo é 9 ou 40?
Conor O'Brien
3
É apenas coincidência que o oitavo número 8 + é 8888? (sim, provavelmente é, mas me divertiu qualquer maneira ...)
Toby Speight
5
De fato, como você pode ter qualquer número de 0 inicial antes de um número, pode-se afirmar que 0 é infinitamente sagrado. Embora apparently seja aparentemente tão sagrado. Mas, estranhamente, 666 é ainda mais santo ...
Darrel Hoffman

Respostas:

6

Pitão, 32 bytes

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

Explicação

                                 - 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]

Experimente aqui

Recebe entrada no formulário h \n n

Azul
fonte
12

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]}

Essa é a terrível abordagem "calcular de 0 a 99999999999 ...", que é 13 bytes mais curta que seu equivalente lento. No entanto, é improvável que esta versão termine antes da morte pelo calor do universo. Vale 13 bytes, enfim ¯ \ _ (ツ) _ / ¯

Você pode testá-lo para valores menores, alterando ?9*99para, digamos '99999',.

Aqui está a versão antiga (95 bytes, com avaliação lenta, que é executada quase instantaneamente em vez de quase nunca):

->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
}
Maçaneta da porta
fonte
Conseguiu amar avaliação preguiçosa :)
Emigna
Por que não em takevez de first?
Não que Charles
takeRetorna @NotthatCharles Lazy, que não pode ser indexado.
Maçaneta
6

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]

Aqui está uma solução que usa uma abordagem mais eficiente em termos de memória, mas usa o mesmo algoritmo se você quiser testá-lo.

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

Casos de teste:

assert f(3, 1) == 6
assert f(4, 2) == 44
Morgan Thrapp
fonte
@Mego Cool. Parece usar uma quantidade estática de memória, portanto não corre o risco de ficar sem memória. Eu só não tinha certeza, já que ele está em funcionamento na minha máquina há meia hora.
Morgan Thrapp 17/02
Ele realmente leva um pedaço decente de tempo apenas para calcular 2**64-1; consulte stackoverflow.com/questions/34113609/…
Mego
@ Mega Oh, eu nem pensei nisso. Sim, quando eu coloco a constante pré-computada no código, ela começa a mastigar um pouco de RAM.
Morgan Thrapp
6

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

Pega a entrada e depois volta até $nzero. Inicialmente, definimos $i=-1usando um truque de pré-processamento, que funciona porque $i, não tendo sido declarado anteriormente, é $null. Então nós --, o que faz o PowerShell avaliá-lo como $i = $null - 1, o que é $i=-1.

Cada loop incrementamos $ie depois executamos uma ifdeclaração longa . A primeira parte do condicional verifica $ise não há nada 12357disso usando o -notmatchoperador para filtrar os números profanos.

A segunda parte do condicional verifica a quantidade de furos $i. Ele usa o -replaceoperador para substituir cada 8ou 0com 11, e, em seguida, compara se o comprimento for> = $h. Não precisamos nos preocupar em eliminar os números profanos, já que isso é a primeira parte do condicional, e os números com um único orifício têm o mesmo comprimento de 1qualquer maneira, portanto, também não precisamos substituí-los.

Se isso ainda é verdade, diminuímos $n(como isso significa que encontramos outro número que atende aos requisitos de entrada). Assim, quando a forcondição é recalculada para verificar se $né zero, significa que encontramos a enésima , então saímos do forloop, saímos $ie terminamos.

Edit - salvou 13 bytes usando uma matriz em vez de string $le alterando como $né diminuído / verificado.
Edit 2 - salvou 9 bytes adicionais verificando $nno forcondicional e movendo a saída para fora do loop
Edit 3 - salvou um gritante Mais 40 bytes mudando radicalmente a maneira como calculamos os furos.
Edit 4 - salvou mais 3 bytes movendo-o ++para um pré-incremento na primeira parte da edição condicional
5 - salvou outros 2 bytes graças a TessellatingHeckler

AdmBorkBork
fonte
Arrumado. Salve mais alguns bytes alterando para for(--$i;$n)e -replace"8|0"?
TessellatingHeckler 19/02
@TessellatingHeckler Sim, obrigado. Isso $i=-1estava me deixando absolutamente maluco. Ainda estou tentando descobrir uma maneira de não precisarmos inicializar $iem primeiro lugar, mas as coisas que tentei até agora são mais longas (e, agora, considerando isso, provavelmente ainda serão mais longas).
AdmBorkBork 19/02
5

CJam, 36 34 bytes

Obrigado ao aditsu por economizar 2 bytes.

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

Teste aqui.

Martin Ender
fonte
4

Utilitários Bash + GNU, 67

  • 20 bytes salvos graças a @TobySpeight!
seq 0 NaN|sed -r "h;/[12357]/d;s/8|0/&&/g;/^.{$1}/!d;x"|sed $2!d\;q
  • seqsimplesmente gera números inteiros a partir de 0cima
  • sed -r:
    • h copie a linha de entrada para o espaço de espera
    • /12357/d excluir números profanos
    • s/8|0/&&/gsubstitua dígitos duplamente sagrados por duas vezes. Assim, dígitos únicos santos são contados uma vez e dígitos duplamente santos são contados duas vezes.
    • /^.{$1}/!dSe não corresponder a pelo menos $1orifícios, exclua e continue na próxima linha
    • x trazer o número original de volta ao espaço do padrão
    • impressão implícita
  • sed
    • $2!dem qualquer linha antes da linha $2, exclua e continue na próxima linha
    • qdeve estar na linha $2- sair (e impressão implícita)

Ideone.

Trauma Digital
fonte
1
Raspar 9: sed -r "h;/[12357]/d;s/8|0/&&/g;/^.{$1}/!d;x". E outros 4: sed $2!d\;q. E se você está feliz com um limite superior de apenas 4611686018427387904, você pode se safar comseq 0 $[1<<62]
Toby Speight
1
Ooh, meu seqaceita NaNcomo um valor: agora tenho seq 0 NaN|sed -r "h;/[12357]/d;s/8|0/&&/g;/^.{$1}/!d;x"|sed $2!d\;q67 pontos.
Toby Speight
@TobySpeight uau isso é incrível!
Digital Trauma
@TobySpeight: falta um \ antes do!, Caso contrário: #-sh: !d\: event not found
Olivier Dulac
1
@OlivierDulac ` before ! `Não é necessário em um script . Isso é necessário apenas ao executar isso diretamente na linha de comando, o que não acho que seja um requisito.
Digital Trauma
3

MATL , 39 40 bytes

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

Entradas são ne hnessa ordem.

Experimente online!

Precisamos acompanhar dois números: número atual do candidato (para verificar sua santidade) e a quantidade de números encontrados que são sagrados o suficiente. O primeiro é o topo da pilha e o último é mantido como o número de elementos na pilha. Quando o programa termina, apenas a parte superior precisa ser exibida.

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
Luis Mendo
fonte
3

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}

Com novas linhas e recuos:

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
}

Uso:

> f(4,3)
[1] 68
> f(4,2)
[1] 44
> f(6,2)
[1] 48
> f(10,2)
[1] 66
plannapus
fonte
3

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

Solução recursiva de cauda que acumula números sagrados em uma matriz.

Fora de interesse, não exigir que o número seja totalmente santo (!) Torna a santidade mais embaraçosa, mas ainda economiza 10% no total:

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
Neil
fonte
@ edc65 Opa, troquei os parâmetros ie rem um ponto e não consegui editar a alteração corretamente.
Neil
1

JavaScript ES6, 191 bytes

Claro, essa não é a maneira mais eficiente. Mas você me conhece, eu amo geradores <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)))

Ligeiramente não destruído:

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)))
Conor O'Brien
fonte
1

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;}

Esta é uma expressão lambda do tipo Func <int, int, int>. Este código é otimizado para o tamanho mínimo (não performatic).

Abaixo, o código embelezado na declaração do método (com mais desempenho):

    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;
    }
Paulo César B. Sincos
fonte
Oi Bobson, desculpe se eu entendi errado, mas não detecte falhas que você apontou no meu código? Ele retorna o n-ésimo elemento necessário, e somente ele e zero se for válido, assumindo que as entradas são n = 1 eh <= 2. Se eu entender o desafio, deve retornar apenas esse elemento e não tudo com ele . Mas eu me entendi mal e perdi em inglês: D obrigado
Paulo César B. Sincos 22/02
Não, você está totalmente certo. Fiquei enganado com as listas de referência e perdi o fato de estar apenas pedindo o nono dígito. Continue!
Bobson 22/02
1

JavaScript (ES6), 87

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

Menos golfe

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
}  

Teste

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>

edc65
fonte
1

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
DavisDude
fonte
1

Lua, 155 141 140 Bytes

Recebe as duas entradas pelo argumento da linha de comando (o primeiro argumento é n, depois h)

Edit: Obrigado a @DavisDude, que me ajudou a raspar 14 bytes e me lembrou que eu não precisava imprimir todos os números sagrados até n, mas apenas o enésimo.

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 e explicações

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
Katenkyo
fonte
Você poderia tirar alguns caracteres fazendoprint(a[arg[1]])
DavisDude
@DavisDude Eu era burro, quando escrevi isso, mas tive que imprimir a lista inteira de números profanos até n. Na verdade, print(a[#a])economiza ainda mais bytes. Obrigado pelo comentário !
22416
Você é escrever. Por alguma razão que nem me ocorreu.
DavisDude
Você pode retirar um caractere escrevendo em x=0a={}vez de x,a=0,{}.
Leaky Nun
1
@KennyLau Na verdade, você não pode, porque 0aseria interpretado como um número hexadecimal, mas eu posso fazer isso a={}x=0whilesem problemas :) #
30416
0

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;

Sem golfe

: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 
Jeto
fonte
0

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)

A condição de santidade ativada ké verificada por

  • sum(map(s.count,`k`))>=h, que conta o número de furos somando as contagens de cada caractere em s="0046889", onde 0e 8aparece duas vezes.
  • set(str(k))<=set(s)), que verifica se os números são todos santos. stré usado em vez de backticks para evitar o sufixo Lpor muito tempo.

Eles são encadeados em uma única igualdade usando o fato de Python 2 de que os números são menores que os conjuntos.

A função é definida recursivamente para contar números k, diminuindo o contador ncada vez que um número sagrado de acerto, a menos que acerte 0. Em seguida, ele poderia retornar o kque desencadeou isso, mas é mais curto manter a contagem recursivamente adicionando 1cada vez, embora um fator de um por um exija uma contagem básica de -1para corrigir.

xnor
fonte
0

Haskell, 94 bytes

cé a santidade de um dígito, va santidade de um número, n!hfaz o resto.

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

Nota: Eu acho que esta é a única resposta sem os caracteres 4,6,8.

Michael Klein
fonte
0

Rápido

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}}
    }
}
Sumeet
fonte