Daily Challenge #13 - Twice Linear

import time

n = 100000

print "n = %d" % n

def insert(l,val):
    index = len(l) - 1
    done = False

    while not done and index >= 0:
        if l[index] == val:
            done = True
        elif l[index] < val:
            l.insert(index + 1,val)
            done = True
        else:
            index -= 1

    if not done:
        l.insert(0,val)


list = [1]
index = 0

start = time.time()

while index < n:
    x = list[0]
    y = (2 * x) + 1
    z = (3 * x) + 1

    insert(list,y)
    insert(list,z)

    # Remove unnecessary entries from the list, which otherwise
    # grows to unreasonable size for large values of n.
    list.remove(x)
    while (index + len(list)) > n :
        list.pop()

    index += 1

end = time.time()

print "result = %d" % list[0]
print "elapsed time (seconds) = %3.6f" % (end - start)

#!/usr/bin/env perl

use v5.24;
use strict;
use warnings;
use feature qw(signatures);
no warnings "experimental::signatures";
use List::Util qw(first uniq);

sub dbl_linear ($n) {
    state @u = (1);
    state $last_n = 0;

    return $u[$n] if $u[$n];

    for my $i ( $last_n .. $n ) {
        my $val = $u[$i];
        @u = sort { $a <=> $b } uniq (@u, map {$_ * $val + 1} (2, 3));
    }

    $last_n = $n;
    return $u[$n];
}

use Test::More tests => 5;
is( dbl_linear(0), 1,  "u(0) == 1" );
is( dbl_linear(1), 3,  "u(1) == 3" );
is( dbl_linear(6), 13, "u(6) == 13" );
is( dbl_linear(100), 447, "u(100) == 447" );
is( dbl_linear(1000), 8488, "u(1000) == 8488" );

fn twice_linear(size: usize) -> Vec<u32> {
    let mut processed: Vec<u32> = vec![];
    let mut unprocessed: Vec<u32> = vec![];

    let mut current = 1;
    while processed.len() < size {
        processed.push(current);

        // This block of code is NOT the most effiecient
        // I should switch to a data store that can push/pop
        // from both ends effieciently, as to avoid needing
        // the sort AND the revserse
        unprocessed.push(current * 2 + 1);
        unprocessed.push(current * 3 + 1);
        unprocessed.sort();
        unprocessed = unprocessed.iter().rev().cloned().collect();

        current = unprocessed.pop().unwrap();
    }

    processed
}

pub fn twice_linear_at(u: usize) -> u32 {
    twice_linear(u + 1).pop().unwrap()
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn it_works_for_the_base_cases() {
        assert_eq!(twice_linear_at(0), 1);
        assert_eq!(twice_linear_at(1), 3);
        assert_eq!(twice_linear_at(2), 4);
    }

    #[test]
    fn it_works_for_the_example() {
        assert_eq!(twice_linear_at(3), 7);
        assert_eq!(twice_linear_at(4), 9);
        assert_eq!(twice_linear_at(5), 10);
        assert_eq!(twice_linear_at(6), 13);
        assert_eq!(twice_linear_at(7), 15);
        assert_eq!(twice_linear_at(8), 19);
        assert_eq!(twice_linear_at(9), 21);
        assert_eq!(twice_linear_at(10), 22);
        assert_eq!(twice_linear_at(11), 27);
    }

    #[test]
    fn it_can_also_return_the_vec() {
        assert_eq!(
            twice_linear(12),
            vec![1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27]
        );
    }
}

import sequtils, algorithm

proc dblLinear(u: int): seq[int] =
  result.add(1)

  for i in 0..<u:
    let y = 2 * result[i] + 1
    let z = 3 * result[i] + 1

    result.add(y)
    result.add(z)

  result.sort()

echo $dblLinear(100000)

const doubleLinear = (n) => {
  let u = [1];
  let i = 0;
  while(i < n) {
    u = [...u, u[i] * 2 + 1, u[i] * 3 + 1];
    u = Array.from(new Set(u))
    u.sort((a, b) => a - b);
    i++;
  }
  return u;
}

#!/bin/bash

declare -a numbersarr
numbersarr[0]=1

echo "Array position \"n\""
read -r myn
# make sure we are given a number and the number is not too large
re="^[0-9]+$"
if ! [[ $myn =~ $re ]] || [ $myn -gt 100 ]; then
  echo "not a number or number too big" >&2; exit 1
fi

arrl=1

while [ $arrl -le $myn ]; do
  for i in "${numbersarr[@]}"; do
    let x=2\*i+1
    let y=3\*i+1
    numbersarr+=( $x $y )
  done
  sorted_unique=($(echo "${numbersarr[@]}" |xargs -n1 | sort -gu | xargs))
  arrl="${#sorted_unique[@]}"
done

# declare -p sorted_unique
echo " >> item in pos ${myn}: "${sorted_unique[$myn]}

import Data.Set (Set)
import qualified Data.Set as Set

u :: Int -> Set Int
u layers = u' layers (Set.singleton 1)
  where
    u' 0 s = s
    u' layer s = u' (layer - 1) (Set.unions [s, Set.map (\x -> 2*x+1) s, Set.map (\x -> 3*x+1) s])

dbl_linear :: Int -> Int
dbl_linear n = Set.elemAt n (u layers)
  where layers = ceiling $ logBase 2 $ fromIntegral (n + 1)

function dblLinear(n) {
    const series = [1];

    const calc = x => ({
        y: 2 * x + 1,
        z: 3 * x + 1
    });

    const ascendingOrder = (a, b) => a - b;

    for (let idx = 0; idx <= n; idx++) {
        let x = series[idx];
        const { y, z } = calc(x);
        for (let v of [y, z]) {
            if (series.indexOf(v) < 0) {
                series.push(v);
                series.sort(ascendingOrder);
                series.splice(n+1);
            }
        }
    }
    return series[n];
}