Autogrames en català

Autogrames en català
Un autograma és una frase que s'autodescriu. Vegeu-ho a la Viquipèdia: Autograma.
La forma més habitual és un recompte de les lletres que conté, utilitzant els noms sencers per descriure cada número.

Si es busca recursivament, s'obté bastant ràpidament aquesta, després de gairebé 10000 iteracions (més o menys mig minut):

Aquesta frase té cinc As, cinc Cs, tres Ds, quinze Es, dues Fs, nou Is, sis Ns, dues Os, quatre Qs, set Rs, vint-i-set Ss, tretze Ts, vuit Us, tres Vs i tres Zs.


També és possible trobar aquesta, però requereix milions d'iteracions (uns 20 minuts):

Aquesta oració té set As, quatre Cs, quatre Ds, dotze Es, nou Is, quatre Ns, sis Os, cinc Qs, sis Rs, vint-i-sis Ss, dotze Ts, set Us, dues Vs i tres Zs.


I ja està. Pot semblar una tasca senzilla, però no n'he trobat cap més en català a les xarxes ni he estat capaç de crear-ne cap altre exemple, ni tampoc cap de les variants.

A més, cal esmentar que a part de les possibles formes de descriure la frase, també existeixen altres variants com múltiples frases que es referencien l'una a l'altra, o reflexicons, és a dir, recomptes de lletres però sense una frase inicial. Tampoc se'n coneix cap en català.
Podeu veure més informació i exemples en altres idiomes aquí: Autograms: Self-Enumerating Sentences

Totes les possibles requereixen un temps computacional massa elevat. Si en comptes de buscar-les recursivament es fa de forma exhaustiva tal com descriu breument l'article, el temps computacional és encara molt pitjor.

Aclaració sobre la recursivitat :


Convindria buscar alternatives, com adaptar algun codi anglès que ja estigui optimitzat, de forma que funcioni amb frases en català.

Altres idees :


Animo a qui vulgui a intentar-ho!
Re: Autogrames en català
Codi amb recursivitat (Ruby):

Codi:

module AutogramData
  module_function
  
  Sentence = "aquesta frase te (i)" # frase, oracio, sentencia, locucio
  
  Letters = {
    "a" => ["a", "as"],
    "b" => ["b", "bs"],
    "c" => ["c", "cs"],
    "d" => ["d", "ds"],
    "e" => ["e", "es"],
    "f" => ["f", "fs"],
    "g" => ["g", "gs"],
    "h" => ["h", "hs"],
    "i" => ["i", "is"],
    "j" => ["j", "js"],
    "k" => ["k", "ks"],
    "l" => ["l", "ls"],
    "m" => ["m", "ms"],
    "n" => ["n", "ns"],
    "o" => ["o", "os"],
    "p" => ["p", "ps"],
    "q" => ["q", "qs"],
    "r" => ["r", "rs"],
    "s" => ["s", "ss"],
    "t" => ["t", "ts"],
    "u" => ["u", "us"],
    "v" => ["v", "vs"],
    "w" => ["w", "ws"],
    "x" => ["x", "xs"],
    "y" => ["y", "ys"],
    "z" => ["z", "zs"]
  }
  
  Letters_Keys = Letters.keys.sort
  
  Numbers = { # Sense guionet
    1 => "una",
    2 => "dues",
    3 => "tres",
    4 => "quatre",
    5 => "cinc",
    6 => "sis",
    7 => "set",
    8 => "vuit",
    9 => "nou",
    10 => "deu",
    11 => "onze",
    12 => "dotze",
    13 => "tretze",
    14 => "catorze",
    15 => "quinze",
    16 => "setze",
    17 => "disset",
    18 => "divuit",
    19 => "dinou",
  }
  def expand_numbers(n, name, add="")
    for i in n..(n+9)
      if i % 10 == 0
        Numbers[i] = name
      else
        Numbers[i] = name + add + Numbers[i - n]
      end
    end
  end
  expand_numbers(20, "vint", "i")
  expand_numbers(30, "trenta")
  expand_numbers(40, "quaranta")
  expand_numbers(50, "cinquanta")
  
  def main
    @stored = []
    @iteration = 0
    hash_count = count_letters(Sentence)
    @stored << hash_count
    @last = ""
    @current = Sentence + hash_to_s(hash_count)
    @result_found = false
    loop do
      find_next_iteration
      break if @result_found == true
    end
  end
  
  def find_next_iteration
    @iteration += 1
    if @iteration % 1000 == 0
      p @iteration
      Graphics.update
    end
    hash_count = count_letters(@current)
    if @stored.include?(hash_count) && @stored[-1] != hash_count
      i = 0
      loop do
        i += 1
        test_hash = hash_count.clone
        if avoid_loop(i, hash_count, test_hash)
          hash_count = test_hash
          break
        end
      end
    end
    @stored << hash_count
    @current = Sentence + hash_to_s(hash_count)
    if @last == @current
      p "MATCH FOUND!"
      p @current
      @result_found = true
      return
    end
    @last = @current
  end
  
  def avoid_loop(i, hash_count, test_hash)
    for k in Letters_Keys
      test_hash[k] = hash_count[k] + i
      return true if !@stored.include?(test_hash)
      test_hash[k] = hash_count[k] - i
      return true if !@stored.include?(test_hash)
    end
    return false
  end
  
  def count_letters(str)
    result = {}
    for k in Letters_Keys
      result[k] = str.count(k)
    end
    return result
  end
  
  def hash_to_s(hash)
    result = ""
    for k in hash.keys.sort
      next if hash[k] == 0
      if hash[k] == 1
        result.concat(Numbers[1] + " " + Letters[k][0] + "; ")
      else
        result.concat(Numbers[hash[k]] + " " + Letters[k][1] + "; ")
      end
    end
    return result
  end
end

class String
  def count(k)
    result = 0
    ary = self.split("")
    for i in 0...ary.size
      result += 1 if ary[i] == k
    end
    return result
  end
end

begin
  AutogramData.main
  loop do
    Graphics.update
  end
end


Codi amb freqüència de les lletres (Ruby):

Codi:

module AutogramData
  module_function
  
  Sentence = "aquesta frase te (i)"
  
  Numbers = { # Sense guionet
    1 => "una",
    2 => "dues",
    3 => "tres",
    4 => "quatre",
    5 => "cinc",
    6 => "sis",
    7 => "set",
    8 => "vuit",
    9 => "nou",
    10 => "deu",
    11 => "onze",
    12 => "dotze",
    13 => "tretze",
    14 => "catorze",
    15 => "quinze",
    16 => "setze",
    17 => "disset",
    18 => "divuit",
    19 => "dinou",
  }
  def expand_numbers(n, name, add="")
    for i in n..(n+9)
      if i % 10 == 0
        Numbers[i] = name
      else
        Numbers[i] = name + add + Numbers[i - n]
      end
    end
  end
  expand_numbers(20, "vint", "i")
  expand_numbers(30, "trenta")
  expand_numbers(40, "quaranta")
  expand_numbers(50, "cinquanta")
  expand_numbers(60, "seixanta")
  expand_numbers(70, "setanta")
  expand_numbers(80, "vuitanta")
  expand_numbers(90, "noranta")
  
  Short_Numbers = Numbers.clone.reject{|k,v| k > 20}
  
  Letters = {
    "a" => ["a", "as"],
    "b" => ["b", "bs"],
    "c" => ["c", "cs"],
    "d" => ["d", "ds"],
    "e" => ["e", "es"],
    "f" => ["f", "fs"],
    "g" => ["g", "gs"],
    "h" => ["h", "hs"],
    "i" => ["i", "is"],
    "j" => ["j", "js"],
    "k" => ["k", "ks"],
    "l" => ["l", "ls"],
    "m" => ["m", "ms"],
    "n" => ["n", "ns"],
    "o" => ["o", "os"],
    "p" => ["p", "ps"],
    "q" => ["q", "qs"],
    "r" => ["r", "rs"],
    "s" => ["s", "ss"],
    "t" => ["t", "ts"],
    "u" => ["u", "us"],
    "v" => ["v", "vs"],
    "w" => ["w", "ws"],
    "x" => ["x", "xs"],
    "y" => ["y", "ys"],
    "z" => ["z", "zs"]
  }
  Letters_Keys = Letters.keys.sort
  Letter_Sing = Letters.values.map{|x| x[0]}
  Letter_Plur = Letters.values.map{|x| x[1]}
  def calc_letter_freq
    str = Short_Numbers.values.join + Letter_Plur.join
    result = {}
    for k in Letters_Keys
      result[k] = str.count(k).to_f / str.size
    end
    return result
  end
  Letter_Frequency = calc_letter_freq
  
  def calc_size_median(ary)
    return ary.sort{|a,b| b.size - a.size}[(ary.size / 2)].size
  end
  
  Number_Len_Med = calc_size_median(Short_Numbers.values)
  Letter_Len_Med = calc_size_median(Letter_Plur)
  
  def plain_size(str)
    result = 0
    for k in Letters_Keys
      result += str.count(k)
    end
    return result
  end
  
  def unused_letters(str)
    result = []
    for k in Letters_Keys
      result.push(k) if str.count(k) == 0
    end
    return result
  end
  
  def main
    str = Sentence.clone
    # Unused Letters
    unused_let = unused_letters(str + Numbers.values.join)
    for k in Letters_Keys
      if !unused_let.include?(k)
        ary = Letters[k].join.split("").uniq
        for a in ary
          unused_let.delete(a)
        end
      end
    end
    # Expected total letters
    t_let = (Letters_Keys.size - unused_let.size)
    # Expected total length
    t_len = plain_size(str) + Number_Len_Med * t_let + Letter_Len_Med * t_let
    # Expected counts for each letter
    exp_counts = {}
    for k in Letters_Keys
      value = (Letter_Frequency[k] * t_len).to_i
      vm = [value, 1].max
      range_max = (vm + vm.to_f / 100).ceil + 1
      range_min = (vm - vm.to_f / 100).floor - 1
      range_max = 0 if unused_let.include?(k)
      exp_counts[k] = [[range_min, 0].max, value, range_max]
    end
    p exp_counts
    # Apply exhaustive search (NOT IMPLEMENTED)
    #exhaustive_search(str, exp_counts)
  end
end

class String
  def count(k)
    result = 0
    ary = self.split("")
    for i in 0...ary.size
      result += 1 if ary[i] == k
    end
    return result
  end
end

begin
  AutogramData.main
  loop do
    Graphics.update
  end
end


Valors en la frase "Aquesta frase té X" mitjançant aquest mètode, contra els reals obtinguts amb recursivitat:

LletraMínimEsperatMàximReal
A1355
B0000
C1355
D3573
E9111315
F0032
G0000
H0000
I5799
J0000
K0000
L0000
M0000
N4686
O2462
P0000
Q0244
R1357
S25272927
T8101213
U5798
V1353
W0000
X0030
Y0000
Z3573

Com es pot veure en aquest cas encara es necessita un interval més gran, però en general la predicció és prou bona.