type1fool

type1fool

Hello, Elixir gang. I’m starting to get the hang of Elixir, which has been challenging since I’m not coming from Ruby. I have been struggling to find a solution for a particular problem. I need to generate a list of strings which increments over the alphabet. So["A", "B", "C"] is a very basic example.

When the end of the alphabet is reached, I want the result to look like this: [..."X", "Y", "Z", "AA", "BB"...]. The goal is to create a function like this: generate_list(first_letter, count).

I tried using the Alphabetify package, but it was pretty slow, and didn’t quite give me the results I needed. String.duplicate got me almost there, but I still wasn’t getting the right output.

Does anyone have an idea or package suggestion for this problem? I’ve hit a wall on this one.

Where I’m at :thinking:

letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" |> String.split("", trim: true)

def generate_list(first_letter, count)
when is_binary(first_letter)
when is_integer(count) do
    # letters
    # |> Stream.cycle
    # |> Stream.take(count)

    starting_index = letters |> Enum.find_index(fn x -> x == first_letter end)

    # 0..count
    # |> Enum.map(fn x ->  end)
end

Showing Posts 1 to 10

blatyo

blatyo

Conduit Core Team

This should do it. The first_letter part isn’t super efficient, but the rest should be.

EDIT: Fix divisor

def generate_list(first_letter \\ "A", count) when is_binary(first_letter) and is_integer(count) do
  ?A..?Z 
  |> Enum.map(&to_string([&1])) 
  |> Stream.cycle() 
  |> Stream.with_index() 
  |> Stream.map(fn {string, index} ->
    String.duplicate(string, div(index, 26) + 1)
  end)
  |> Stream.drop_while(&(&1 != first_letter))
  |> Enum.take(count)
end
type1fool

type1fool OP

:exploding_head: This is great, though it’s duplicating Z on the first pass.

iex(11)> generate_list("W", 10)
["W", "X", "Y", "ZZ", "AA", "BB", "CC", "DD", "EE", "FF"]

I changed div(index, 25) to div(index, 26) and the problem is solved. It correctly appends additional characters too:

iex(15)> generate_list("W", 10)
["W", "X", "Y", "Z", "AA", "BB", "CC", "DD", "EE", "FF"]
iex(20)> generate_list("ZZ", 60)
["ZZ", "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG", "HHH", "III", "JJJ", "KKK", "LLL", "MMM", "NNN", "OOO", "PPP", "QQQ", "RRR", "SSS", "TTT", "UUU", "VVV", "WWW", "XXX", "YYY", "ZZZ", "AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "FFFF", "GGGG", "HHHH", "IIII", "JJJJ", "KKKK", "LLLL", "MMMM", "NNNN", "OOOO", "PPPP", "QQQQ", "RRRR", "SSSS", "TTTT", "UUUU", "VVVV", "WWWW", ...]

Thank you @blatyo for this clean solution!

kelvinst

kelvinst

That’s indeed a really good solution. But I got interested by the possibility of improving its performance and here are the results:

defmodule LettersAndNumbers do
  def list(from \\ 0, count) do
    from
    |> stream()
    |> Enum.take(count)
  end

  def stream(from \\ 0)

  def stream(from) when is_bitstring(from) or is_list(from) do
    from
    |> letters_to_number()
    |> stream()
  end

  def stream(from) do
    from
    |> Stream.iterate(&(&1 + 1))
    |> Stream.map(&number_to_letters/1)
  end

  def number_to_letters(number) do
    [rem(number, 26) + 65]
    |> to_string()
    |> String.duplicate(div(number, 26) + 1)
  end

  def letters_to_number(letters) when is_bitstring(letters) do
    letters
    |> String.to_charlist()
    |> letters_to_number()
  end

  def letters_to_number([char | _] = letters) do
    ((length(letters) - 1) * 26) + (char - 65)
  end
end

PS.: I also did some changes to the API, but basically, instead of cycling through the alphabet and navigating it with an index, I mathematically transform numbers into letters by adding 65 to them and duplicating them div(number, 26) + 1 times like you did.

type1fool

type1fool OP

@kelvinst Nice! I like this approach and I can’t wait to benchmark these two solutions.

kelvinst

kelvinst

Yeah, it would be nice to benchmark them, since I’m not sure my solution will really be faster. I mean, of course it’s faster with a high “first_letter” because it will not iterate discarding everything, but I’m not sure if the calcs I’ve done didn’t add any extra complexity per iteration.

type1fool

type1fool OP

This is my first foray into benchmarking, so these results may be unreliable.

Operating System: macOS"
CPU Information: Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.6.1
Erlang 20.2.4

Benchmark suite executing with the following configuration:
warmup: 3 s
time: 7 s
memory time: 0 μs
parallel: 1
inputs: 100K, 1K, 1M
Estimated total run time: 1 min


Benchmarking LettersAndNumbers.list/2 with input 100K...
Benchmarking LettersAndNumbers.list/2 with input 1K...
Benchmarking LettersAndNumbers.list/2 with input 1M...
Benchmarking generate_list/2 with input 100K...
Benchmarking generate_list/2 with input 1K...
Benchmarking generate_list/2 with input 1M...

##### With input 100K #####
Name                               ips        average  deviation         median         99th %
generate_list/2                   1.44      692.72 ms     ±4.56%      682.07 ms      747.01 ms
LettersAndNumbers.list/2          1.43      697.56 ms     ±4.66%      687.10 ms      787.46 ms

Comparison:
generate_list/2                   1.44
LettersAndNumbers.list/2          1.43 - 1.01x slower

##### With input 1K #####
Name                               ips        average  deviation         median         99th %
generate_list/2                 3.31 K      302.43 μs    ±23.01%         285 μs      695.32 μs
LettersAndNumbers.list/2        2.17 K      459.98 μs    ±14.67%         439 μs      750.16 μs

Comparison:
generate_list/2                 3.31 K
LettersAndNumbers.list/2        2.17 K - 1.52x slower

##### With input 1M #####
Name                               ips        average  deviation         median         99th %
generate_list/2                 0.0141       1.18 min     ±0.00%       1.18 min       1.18 min
LettersAndNumbers.list/2        0.0141       1.18 min     ±0.00%       1.18 min       1.18 min

Comparison:
generate_list/2                 0.0141
LettersAndNumbers.list/2        0.0141 - 1.00x slower

Benchmark Code:

defmodule TicketMarket.MutationBenchmarks do
  alias TicketMarket.LettersAndNumbers
  alias TicketMarket.MutateLayout

  inputs = %{
    "1K" => 1_000,
    "100K" => 100_000,
    "1M" => 1_000_000,
  }

  Benchee.run %{
    "LettersAndNumbers.list/2" => fn(count) -> LettersAndNumbers.list(0, count) end,
    "generate_list/2" => fn(count) -> MutateLayout.generate_list("A", count) end
  },
    formatters: [
      # Benchee.Formatters.HTML,
      Benchee.Formatters.Console
    ],
    time: 7,
    warmup: 3,
    inputs: inputs
end

It’s interesting that both approaches get exponentially slower as the count increases. I do like the simplicity of generate_list/2, so that may be the way I end up going. I don’t expect the count to be higher than 1000, so either function would be usable.

If you have any thoughts about the benchmark, let me know.
Thanks again!

kelvinst

kelvinst

So, the thing is that you didn’t bench the case were mine is supposedly faster, which would be with a high starting letter.

type1fool

type1fool OP

This is true. I’ll run it again tonight with a higher starting letter.

kelvinst

kelvinst

Also, be sure to get a high letter like “O” |> String.duplicate(40000) which is the number 1039988.

type1fool

type1fool OP

Indeed you are correct. Starting with a crazy high letter benefits the LettersAndNumbers approach. Thi scenario would not ever happen. The highest letter would be something like "ZZZZ". Fun experiment nonetheless.

inputs = %{
    # "10" => 10,
    # "100" => 100,
    "1K" => 1_000,
    "100K" => 100_000,
    "1M" => 1_000_000,
  }

  Benchee.run %{
    "LettersAndNumbers.list/2" => fn(count) -> LettersAndNumbers.list(1039988, count) end,
    "generate_list/2" => fn(count) -> MutateLayout.generate_list("O" |> String.duplicate(40_000), count) end
  },
    formatters: [
      # Benchee.Formatters.HTML,
      Benchee.Formatters.Console
    ],
    time: 7,
    warmup: 3,
    inputs: inputs

RESULTS:

Operating System: macOS"
CPU Information: Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.6.1
Erlang 20.2.4

Benchmark suite executing with the following configuration:
warmup: 3 s
time: 7 s
memory time: 0 μs
parallel: 1
inputs: 100K, 1K, 1M
Estimated total run time: 1 min


Benchmarking LettersAndNumbers.list/2 with input 100K...
Benchmarking LettersAndNumbers.list/2 with input 1K...
Benchmarking LettersAndNumbers.list/2 with input 1M...
Benchmarking generate_list/2 with input 100K...
Benchmarking generate_list/2 with input 1K...
Benchmarking generate_list/2 with input 1M...

##### With input 100K #####
Name                               ips        average  deviation         median         99th %
LettersAndNumbers.list/2        0.0712       0.23 min     ±0.00%       0.23 min       0.23 min
generate_list/2                 0.0132       1.27 min     ±0.00%       1.27 min       1.27 min

Comparison:
LettersAndNumbers.list/2        0.0712
generate_list/2                 0.0132 - 5.40x slower

##### With input 1K #####
Name                               ips        average  deviation         median         99th %
LettersAndNumbers.list/2          8.40    0.00199 min     ±2.23%    0.00198 min    0.00209 min
generate_list/2                 0.0162       1.03 min     ±0.00%       1.03 min       1.03 min

Comparison:
LettersAndNumbers.list/2          8.40
generate_list/2                 0.0162 - 518.33x slower

##### With input 1M #####
Name                               ips        average  deviation         median         99th %
LettersAndNumbers.list/2       0.00465       3.59 min     ±0.00%       3.59 min       3.59 min
generate_list/2                0.00365       4.57 min     ±0.00%       4.57 min       4.57 min

Comparison:
LettersAndNumbers.list/2       0.00465
generate_list/2                0.00365 - 1.27x slower

Where Next? Top

Trending in Questions Top

stjefim
Hello! Suppose you are building workflow (order / task / payment) processing system with the following requirements: Each workflow con...
New
itzmidinesh
Hi all, I’m working on a Phoenix project where I need to make external HTTP requests and I’m trying to choose between Req and HTTPoison....
New
yarrichar
I’m very new to Elixir, so sorry if this is a silly question: I am wondering what happens to the mailbox of a process when the machine i...
New
pragdave
How do I tell Hologram not to escape HTML when substituting into templates? {Textile.render(@product.long_description)} escapes the HTM...
New
Fl4m3Ph03n1x
Background When trying to execute mix release on a Windows 11 machine for a Phoenix project I get the following error: * assembling mark...
New
leoschweizer
Hi, we run different LLM models across a cluster, with each node loading a configurable subset. Model-specific queues let nodes consume ...
New
rlipscombe
I’d like to create a file with 600 permissions (rw-------), but there’s a race condition if I create it and then change the permissions. ...
New

Other Trending Topics Top

dominicletz
Hey there, I haven’t seen a list of useful Elixir specific skills for the popular AI tools yet so I’m starting one here with my first. ...
New
raa-ziq
Hi everyone :waving_hand: I wanted to share something I’ve been building — NowBlind, a random chat app designed to help people discover ...
New
mudasobwa
I fully migrated to my own harness from Anthropic/Gemini and I think it’s time to share it. Welcome DSH, the DeepSeek Harness, fully writ...
New
KristerV
Hey. Is there anyone here who creates agents in their apps? Not talking about using agents, but creating them. I’m finding it pretty diff...
New
OndrejValenta
(I just needed to vent somewhere and LinkedIn is full of hope, or hype, I’m not sure which exactly) AI dream has many faces, but general...
New
kip
Localize is the next generation localisation library for Elixir. Think of it as ex_cldr version 3.0. The first version will be released ...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews