RogerBW's Blog

Perl Weekly Challenge 108: Memory Bell 13 April 2021

I’ve been doing the Perl Weekly Challenges. The latest involved bad things and triangular numbers. (Note that this is open until 18 April 2021.)

TASK #1 › Locate Memory

Write a script to declare a variable or constant and print its location in the memory.

Bad! Dirty! No! There is no good reason to do this in a high-level language: if it seems to solve your problem, you are solving the wrong problem and it will come back and bite you later. (With very minor exceptions when you're building the language and trying to work out what's going on.)

Therefore I only did it in Perl and Raku:

printf('0x%x',0+\$foo);

and

say sprintf('0x%x',$foo.WHERE);

though I will point out that even the documentation for the latter method explicitly states:

Please note that in the Rakudo implementation of Raku, and possibly other implementations, the memory location of an object is NOT fixed for the lifetime of the object. So it has limited use for applications, and is intended as a debugging tool only.

Don't do this, folks.

TASK #2 › Bell Numbers

Write a script to display top 10 Bell Numbers. Please refer to wikipedia page for more informations.

Bell numbers were named, though not discovered, by Eric Temple Bell – probably no relation though he was from the same part of Scotland as some of my wife's ancestors.

I took "top 10" to mean "first 10". There's a pretty straightforward row by row calculation method described on that page, so that was what I did.

sub bell {
  my $count=shift;
  my @a=([1]);
  foreach my $row (1..$count-1) {
    my @b=$a[-1][-1];
    foreach my $col (1..$row) {
      push @b,$b[$col-1]+$a[-1][$col-1];
    }
    push @a,\@b;
  }
  return [map {$_->[0]} @a];
}

and the others are similar; Raku wants you to use *-1 to mean the last of something, and I can sort of see their point, though using the asterisk feels odd. Python and Ruby are happy with -1.

Oddly, in Rust I wasn't able to get the final map to work so I ended up building an output vector. (Also, [-1] becomes .last().unwrap() and futzes about with references and pointers. Arg. Which is why I ended up explicitly declaring the types of my array contents.)

fn bell(count: usize) -> Vec<u64> {
    let mut a: Vec<Vec<u64>>=vec![vec![1]];
    for row in 1..count {
        let mut b: Vec<u64>=vec![*a.last().unwrap().last().unwrap()];
        for col in 1..=row {
            b.push(b[col-1]+&a.last().unwrap()[col-1]);
        }
        a.push(b);
    }
    let mut out: Vec<u64>=vec![];
    for i in a {
        out.push(i[0]);
    }
    return out;
}

Full code on github.


  1. Posted by Peter at 10:11am on 13 April 2021

    It's premature optimisation for a problem which doesn't have large N, but it can be done with iterators, keeping a maximum of just the last two rows in memory, so memory usage is O(N) rather than O(N^2). The algorithm remains O(N^2):

    fn next_row(row: &[usize]) -> impl Iterator + '_ {
        let mut acc = *row.last().unwrap_or(&1);
        let left_it = iter::once(acc);
        let rest_it = row.iter().map(move |&prev| {
            acc += prev;
            acc
        });
        left_it.chain(rest_it)
    }

    fn bells() -> impl Iterator { let mut acc = vec![]; iter::from_fn(move || { acc = next_row(&acc).collect(); acc.first().cloned() }) }

    [test]

    fn test_next_row() { let next = next_row(&[]).collect::>>(); asserteq!(next, vec![1]); let next = next_row(&[5, 7, 10, 15]).collect::>>(); asserteq!(next, vec![15, 20, 27, 37, 52]); }

    [test]

    fn test_bells() { let bells = bells().take(10).collect::>>(); asserteq!(bells, vec![1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]); }

    More usefully—although again not for something small and disposable—this approach avoids array accesses so the bounds checks are eliminated and would run faster.

  2. Posted by RogerBW at 10:16am on 13 April 2021

    Yeah, I think I've got to the point that I need to stop just making my existing code work in Rust and try to learn the language properly.

  3. Posted by RogerBW at 11:23am on 19 April 2021

    Not much to comment on this time: task 1 is horrid, and there's an obvious best approach for task 2 which most people used. (Exhaustively calculating the possible partitions is too much like work.)

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life julie enfield kickstarter learn to play leaving earth linux liquor lovecraftiana mecha men with beards museum music mystery naval non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1