DEV Community

Daily Challenge #13 - Twice Linear

dev.to staff on July 11, 2019

Hey, everyone. If yesterday was our rest day, today is the warm-up. We have another great challenge from user g964 on CodeWars: Consider a sequ...
Read full post
Collapse
 
edh_developer profile image
edh_developer •

For n = 100,000 , on an ok laptop, it runs in roughly 45 seconds

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)
Collapse
 
yzhernand profile image
Yozen Hernandez •

Here's my solution in Perl. I actually think its a bit too slow, even when using state variables to cache the results in subsequent calls. Maybe I'll look into optimizing it later.

#!/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" );

I'll write an explainer for it when I get a few minutes later.

Collapse
 
coreyja profile image
Corey Alexander •

Here is my Rust solution! I think my answer is pretty good except I should be using a better data structure than a Vec here, since I really want to push/pop from both ends. If I did that I would be able to avoid needing to sort and reverse my vec, which would help on the processing speed!

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]
        );
    }
}
Collapse
 
brightone profile image
Oleksii Filonenko •

Take a look at std::collections::VecDeque :)

Collapse
 
coreyja profile image
Corey Alexander •

Thank you! I knew there was one that fit the bill better!

Collapse
 
ganderzz profile image
Dylan Paulus • • Edited

Nim

Time: ./main 0.04s user 0.01s system 39% cpu 0.113 total

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)
Collapse
 
edh_developer profile image
edh_developer •

Not familiar with nim. It looks like result is a list, and that duplicate values are being added to it. Is that not the case?

Collapse
 
ganderzz profile image
Dylan Paulus • • Edited

I think you're right! Was testing with too small of an input-set to see any duplicates. :)

Cheap fix (./main 341.16s user 0.52s system 99% cpu 5:42.40 total): 

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

    if not (y in result):
      result.add(y)
    if not (z in result):
      result.add(z)

  result.sort()

echo $dblLinear(100000)
Collapse
 
alvaromontoro profile image
Alvaro Montoro •

JavaScript

const twiceLinear = number => {
  let series = { 1: 1 };
  let keys = Object.keys(series);
  let index = 0;

  while (index < number) {
    series[ keys[index] * 2 + 1 ] = 1;
    series[ keys[index] * 3 + 1 ] = 1;
    index++;
    keys = Object.keys(series);
  }

  return keys;
}
Enter fullscreen mode Exit fullscreen mode

I've been running late lately... but here is a live demo on CodePen

Collapse
 
germavinsmoke profile image
GermaVinsmoke • • Edited

This one times out on bigger input because of generating Object.keys(series) every time inside the loop

Collapse
 
coreyja profile image
Corey Alexander •

Let us know if you like these mathematical challenges and we'll stick with the trend.

I like em, but I think it's fun to have a good mix of different types of challenges!

One suggestion is to provide more examples/test cases. Especially for the mathy ones, where the correct answers might not be super obvious to everyone, having many examples/test cases can definitely make it easier! Just a thought!

Collapse
 
nans profile image
Nans Dumortier • • Edited

Not sure I have well understood this one ... Am I correct with this JS function ? 🙈

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;
}

EDIT: added the line u = Array.from(new Set(u)) to get unique values !

Collapse
 
listnux profile image
ListNUX •

Not too good with maths, hope I understood well. Here is a (very inefficient, so I added a constraint to the max num to give) attempt in bash:

#!/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]}
Collapse
 
auroratide profile image
Timothy Foster •

Haskell, featuring tail recursion!

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)
Collapse
 
kerrishotts profile image
Kerri Shotts • • Edited

A little late to the party (3am my time), but oh well! Here's my submission: 

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];
}

Full code w/ some tests: gist.github.com/kerrishotts/029c8f...

This is one where it would have been super helpful to have some answers to compare against. Beyond the initial few digits, I'm just assuming things are correct, which may not be true.

Collapse
 
matrossuch profile image
Mat-R-Such •

Python

def dbl_linear(n):
    u=[1]
    if n == 0:
        return u
    else:
        for i in range(n):
            y,z=2*u[i]+1,3*u[i]+1
            u.append(y)
            u.append(z)
            u=sorted(u)
        return u
print(dbl_linear(10))
Collapse
 
abel189 profile image
Abel Mihailescu •

Nice challenge.

Collapse
 
edh_developer profile image
edh_developer •

This fails for larger values of n. For n = 100, for instance, it returns 463 rather than 447.