Les numéros Holier

22

Comme nous l'avons appris de The Holy Numbers , il y a 5 chiffres saints ( 0, 4, 6, 8, 9), et les entiers positifs composés uniquement de ces chiffres sont saints. De plus, la sainteté d'un nombre est la somme des trous dans le nombre ( +2pour chaque 0ou 8, et +1autrement).

Maintenant, il y a une propriété supplémentaire à prendre en considération, pour représenter véritablement et avec précision la sainteté d'un nombre. Vous voyez, ce n'est pas seulement le nombre de trous dans le chiffre qui importe, mais aussi l'endroit où le nombre se produit.

Considérez le nombre 88. Selon nos anciennes règles, il aurait une sainteté de 4. Mais ce n'est pas juste! La 8gauche fait plus de travail que l'autre 8- 10 fois le travail! Il devrait être récompensé pour son travail. Nous le récompenserons avec des points de sainteté supplémentaires égaux à la sainteté totale de tous les chiffres à sa droite (y compris les points de sainteté supplémentaires accordés par cette règle aux chiffres à sa droite), moins 1.

Voici d'autres exemples à prendre en considération:

Number: 8080
Digital holiness: (2 + 7 - 1) + (2 + 3 - 1) + (2 + 1 - 1) + (2 + 0 - 1)
Total holiness: 15

Number: 68904
Digital holiness: (1 + 5 - 1) + (2 + 2 - 1) + (1 + 1 - 1) + (2 + 0 - 1) + (1 + 0 - 1)
Total holiness: 10

Tous les chiffres sont récompensés de manière appropriée pour leur travail avec une sainteté supplémentaire, et tout va bien. Nous appellerons cette propriété "holarité renforcée".

Dans le grand langage Python, un algorithme pour calculer l'holarité améliorée pourrait ressembler à ceci:

# assumes n is a holy number
def enhanced_holarity(n):
    if n < 10:
        return 1 if n in [0, 8] else 0
    else:
        digits = list(map(int,str(n)[::-1]))
        res = []
        for i,x in enumerate(digits):
            res.append(enhanced_holarity(x))
            if i > 0:
                res[i] += sum(res[:i])
        return sum(res)

Le défi

Étant donné un entier n > 0, sortez les premiers nnombres saints, triés par holarité améliorée ascendante, en utilisant la valeur numérique comme bris d'égalité. Vous pouvez supposer que l'entrée et la sortie ne seront pas supérieures à l'entier représentable maximum dans votre langue ou 2^64 - 1, selon le moindre des deux.

Pour référence, voici quelques cas de test (entrée, puis sortie):

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

100
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 444, 446, 449, 464, 466, 469, 494, 496, 499, 644, 646, 649, 664, 666, 669, 694, 696, 699, 0, 8, 84, 86, 89, 844, 846, 849, 864, 866, 869, 894, 896, 899, 40, 48, 60, 68, 90, 98, 404, 406, 409, 484, 486, 489, 604, 606, 609, 684, 686, 689, 80, 88, 804, 806, 809, 884, 886, 889, 440, 448, 460, 468, 490, 498, 640, 648, 660, 668, 690, 698, 840, 848, 860, 868, 890, 898, 400, 408, 480, 488, 600, 608, 680, 688, 800, 808, 880, 888

200
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 444, 446, 449, 464, 466, 469, 494, 496, 499, 644, 646, 649, 664, 666, 669, 694, 696, 699, 944, 946, 949, 964, 966, 969, 994, 996, 999, 4444, 4446, 4449, 4464, 4466, 4469, 4494, 4496, 4499, 4644, 4646, 4649, 4664, 4666, 4669, 4694, 4696, 4699, 0, 8, 84, 86, 89, 844, 846, 849, 864, 866, 869, 894, 896, 899, 40, 48, 60, 68, 90, 98, 404, 406, 409, 484, 486, 489, 604, 606, 609, 684, 686, 689, 904, 906, 909, 984, 986, 989, 4044, 4046, 4049, 4064, 4066, 4069, 4094, 4096, 4099, 80, 88, 804, 806, 809, 884, 886, 889, 440, 448, 460, 468, 490, 498, 640, 648, 660, 668, 690, 698, 940, 948, 960, 968, 990, 998, 4404, 4406, 4409, 4484, 4486, 4489, 4604, 4606, 4609, 4684, 4686, 4689, 840, 848, 860, 868, 890, 898, 400, 408, 480, 488, 600, 608, 680, 688, 900, 908, 980, 988, 4004, 4006, 4009, 4084, 4086, 4089, 800, 808, 880, 888, 4440, 4448, 4460, 4468, 4490, 4498, 4640, 4648, 4660, 4668, 4690, 4698, 4040, 4048, 4060, 4068, 4090, 4098, 4400, 4408, 4480, 4488, 4600, 4608, 4680, 4688, 4000, 4008, 4080, 4088
Mego
la source
10
Cette idée de trou est holistique.
Calvin's Hobbies
Que voulez-vous dire par "la sortie ne sera pas supérieure à ..."? Comme dans la sortie, il n'y aura pas de nombre supérieur à 2^64 - 1? Si tel est le cas, il vaut probablement la peine de déterminer quelle entrée génère en premier de tels nombres, afin que les gens puissent tester leurs réponses.
FryAmTheEggman
@FryAmTheEggman Pas supérieur à signifie inférieur ou égal à. Je mettrai à jour le message avec des maximums pour différentes tailles entières.
Mego
Votre code python ne fonctionne pas pour 6, il produit un holines de 0.
shrx

Réponses:

2

Python 2, 138 122 octets

Cela recherche des nombres saints jusqu'à 5 N pour un N d' entrée , ce qui est ridiculement lent:

e=lambda s:s and(s[0]in'08')+e(s[1:])*2or 0
lambda N:sorted([`x`for x in range(5**N)if set(`x`)<=set('04689')][:N],key=e)

Ici, la limite est de 5 N 2 , et vous pouvez réellement exécuter les cas de test, au prix d'un seul octet:

e=lambda s:s and(s[0]in'08')+e(s[1:])*2or 0
lambda N:sorted([`x`for x in range(5*N*N)if set(`x`)<=set('04689')][:N],key=e)

Le premier extrait est valide, comme 5 N ≥ 5 N 2 pour tous les entiers positifs N .

Lynn
la source
Oh, attends, j'ai raté quelque chose .. Trop fatigué pour ça.
seequ
3

Lua, 317 octets

J'ai eu quelques problèmes à faire ça, certaines choses à Lua ne fonctionnent pas comme je pense. Je vais devoir essayer de jouer avec eux si je veux jouer au golf. Vous pouvez tester lua en ligne en remplaçant arg[1]par le nombre d'éléments que vous souhaitez :).

function f(y)h=0(y..''):reverse():gsub(".",function(c)h=c:find("[08]")and 1+h or h end)return h end
x,a=0,{}while(#a<arg[1]+0)do a[#a+1],x=(x..''):find("^[04689]*$")and x or nil,x+1 end
for i=1,#a do m=1
for j=1,#a do x=a[m]m=(f(x)~=f(a[j])and f(x)>f(a[j])or x>a[j])and j or m
end end print(a[m])table.remove(a,m)end

Non golfé et explications

function f(y)                     -- function returning the enhanced holiness of a holy number
  h=0                             -- h is the cumulated holyness of processed digits
  (y..''):reverse()               -- reverse the digits in y
         :gsub(".",function(c)    -- iterate over each digits
     h=c:find("[08]")and 1+h or h -- ternary based on the digit being [08] or [469]
   end)                           
  return h                        -- return h
end

x,a=0,{}                          -- initialise a counter, and the array of holy numbers
while(#a<arg[1]+0)                -- iterate until we have n holy numbers
do
  a[#a+1]=(x..'')                 
      :find("^[04689]*$")         -- if we can't find an unholy digit
             and x or nil         -- insert x into a
  x=x+1                           -- increment x anyway
end

for i=1,#a                        -- iterate n times(current size of a)
do
  m=1                             -- m is the index of the lowest value
  for j=1,#a                      -- iterate over a
  do
    x=a[m]                        -- x is shorter to write than a[m]
    m=(f(x)~=f(a[j])              -- nested ternaries, translated in
        and f(x)>f(a[j])          -- nested if below
        or x>a[j])and j or m      
  end
  print(a[m])                     -- output a[m]
  table.remove(a,m)               -- remove it from the table a
end

Les ternaires imbriqués utilisés pour la nouvelle valeur de m peuvent être traduits en if imbriqués comme:

if(f(a[m])~=f(a[j])) then         -- if a[m] and a[j] don't have the same holyness
  if(f(a[m])>f(a[j])) then m=j end-- compare by holyness
else
  if(a[m]>a[j]) then m=j end      -- else, compare by numeric value

De plus, j'aurais aimé remplacer le niché foren utilisant table.sort, mais, pour une raison que je ne sais pas, ce qui suit ne fonctionne pas malgré le fait de ne pas produire une boucle infinie ou d'écraser la fonction de tri.

table.sort(a,function(i,j)
    return f(i)~=f(j)              
         and f(i)>f(j)          
         or i>j
end)
Katenkyo
la source
1

JavaScript (ES6), 166 165 octets

f=n=>[...Array(n)].map((_,i)=>i.toString(5)).sort((a,b)=>e(a)-e(b),e=n=>'0b'+[...n.replace(/./g,c=>'10010'[c])].reverse().join``).map(n=>+n.replace(/./g,c=>"04689"[c]))

Edit: enregistré 1 octet en retournant un tableau de chaînes.

Non golfé:

function base5_to_extended_holiness_binary(c) {
    return "10010"[c];
}
function extended_holiness(n) {
    var binary = n.toString(5).replace(/./g, base5_to_extended_holiness_binary);
    binary = s.split("").reverse().join("");
    return parseInt(s, 2);
}
function extended_holiness_sort(a, b) {
    return extended_holiness(a) - extended_holiness(b);
}
function base5_to_holy_number(c) {
    return "04689"[c];
}
function list_by_extended_holiness(n) {
    var array = new Array(n);
    for (var i = 0; i < n; i++)
         array[i] = i;
    array = array.sort(extended_holiness_sort);
    for (var i = 0; i < n; i++)
        array[i] = parseInt(array[i].toString(5).replace(/./g, base5_to_holy_number);
    return array;
}
Neil
la source