DEV Community

Daily Challenge #12 - Next Larger Number

dev.to staff on July 10, 2019

Apologies on missing yesterday's challenge. We have a fun one to hop in on today. If you haven't been following the series, feel free to give thi...
Collapse
 
jacoby profile image
Dave Jacoby

Perl 5

#!/usr/bin/env perl

use strict;
use warnings;
use utf8;
use feature qw{ postderef say signatures state switch };
no warnings
    qw{ experimental::postderef experimental::smartmatch experimental::signatures };

use Algorithm::Permute;
use JSON;

my $json = JSON->new->pretty->canonical;

my $base = 2019;
my @base = split m{},$base;
my $iter = Algorithm::Permute->new(\@base);
my @list;
while ( my @num = $iter->next ) {
    push @list, join '', @num;
}
for my $n ( sort @list ) {
    next if $n <= $base;
    say $n;
    exit;
}
Collapse
 
choroba profile image
E. Choroba

Why JSON?

Collapse
 
jacoby profile image
Dave Jacoby

Because debugging and forgetting to remove it when done.

Collapse
 
kaspermeyer profile image
Kasper Meyer

Ruby solution

Trying out Object#then, which was introduced recently in Ruby 2.6, just for the fun of it.

require "minitest/autorun"

class NextBiggerNumber
  def self.from number
    number.to_s.split('')
      .then { |result| result.permutation }
      .then { |result| result.map(&:join) }
      .then { |result| result.map(&:to_i) }
      .then { |result| result.sort }
      .then { |result| result[result.index(number) + 1] }
  end
end

class NextBiggerNumberTest < MiniTest::Test
  def test_next_bigger_number_with_two_digits
    assert_equal 21, NextBiggerNumber.from(12)
  end

  def test_next_bigger_number_with_three_digits
    assert_equal 531, NextBiggerNumber.from(513)
  end

  def test_next_bigger_number_with_four_digits
    assert_equal 2091, NextBiggerNumber.from(2019)
  end
end
Collapse
 
kerrishotts profile image
Kerri Shotts

Here's mine.

First, a function for permuting the digits (using recursion):

const permute = arr => {
    if (arr.length < 2) {
        return (typeof arr === "string" ? [arr] : arr);
    }

    if (typeof arr === "string") {
        return permute(arr.split("")).map(arr => arr.join(""));
    }

    const result = [];
    for (let i = 0; i < arr.length; i++) {
        const unused = arr.map(i => i);
        const candidate = unused.splice(i, 1);
        const permuteUnused = permute(unused);
        for (let r of permuteUnused) {
            result.push([...candidate, ...Array.isArray(r) ? r : [r]]);
        };
    }
    return result;
}

Next, a sorting function:

const numericalOrder = (a, b) => {
    const nA = Number(a);
    const nB = Number(b);
    return nA < nB ? -1
    : nA > nB ? 1
    : 0;
}

And finally, the function to calculate the next largest number itself, relying on the idea that if we sort in numerical ascending order and filter out all the items less than the requested number, then the first one remaining must be our next largest number.

const nextLargerNumber = n => {
    const digits = n.toString();
    const nextValidNumbers = permute(digits)
        .sort(numericalOrder)
        .filter(a => Number(a) > n);
    if (nextValidNumbers.length < 1) {
        return null;
    }
    return Number(nextValidNumbers[0]);
}

Full code and tests in gist: gist.github.com/kerrishotts/a0a96d...

Collapse
 
coreyja profile image
Corey Alexander

Took a long drive up for vacation yesterday so I wasn't able to get this types out! I think I know what I'm gonna implement so just gotta see if I can't type it out today! Can't get oo far behind on these challenges! I owe two now !

Collapse
 
coreyja profile image
Corey Alexander

Got it done! Was able to write out what I was thinking last night without too much hassle, pretty happy with how it came out.

Could have tried not converting to chars in the middle, but it worked out pretty nicely still I think!

pub fn next_largest(n: u32) -> Option<u32> {
    let s = n.to_string();

    let mut chars: Vec<_> = s.chars().collect();

    for i in (0..chars.len() - 1).rev() {
        let first = chars[i].to_digit(10).unwrap();
        let second = chars[i + 1].to_digit(10).unwrap();

        if second > first {
            chars.swap(i, i + 1);
            let s: String = chars.iter().collect();

            return Some(s.parse().unwrap());
        }
    }

    None
}

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

    #[test]
    fn it_works_for_examples_that_have_no_largest() {
        assert_eq!(next_largest(4), None);
        assert_eq!(next_largest(100), None);
        assert_eq!(next_largest(9876), None);
    }

    #[test]
    fn it_works_for_the_examples() {
        assert_eq!(next_largest(12), Some(21));
        assert_eq!(next_largest(2019), Some(2091));
        assert_eq!(next_largest(513), Some(531));
    }

    #[test]
    fn it_works_for_large_numebrs() {
        assert_eq!(next_largest(36852367), Some(36852376));
        assert_eq!(next_largest(123456789), Some(123456798));
        assert_eq!(next_largest(5010), Some(5100));
    }
}
Collapse
 
coreyja profile image
Corey Alexander

I notice a lot of people did theirs differently so I thought I'd explain what I did!

One of the things I noticed that led to my solution, was the fast that the next largest number, was 1 'sort' away from the number we had. What I mean is if we imagine our number as an array of its digits, the number we wanted was 1 swap away AND would make our 'array' more sorted than it was before!

This made me realize that a modified bubble sort was exactly what I was looking for! So below I conconted something loosely based on a bubble sort. It starts at the end of the number and moves backward seeing if it can make a swap. If it does, it returns the swapped value. If we make it to the beggining of the list we know there wasn't a larger number and simply return None!

Collapse
 
oscherler profile image
Olivier “Ölbaum” Scherler

I wanted to do it like this (in Erlang), but didn’t figure out how to. Nice.

Thread Thread
 
oscherler profile image
Olivier “Ölbaum” Scherler

I think you have a mistake: next_largest(351) should return 513, and you return 531.

That’s where I gave up with the swapping approach.

Collapse
 
jacoby profile image
Dave Jacoby

Perl 6

#!/usr/bin/env perl6

my $base = 2019;
my @numbers = split('',$base);

my @perm;
for @numbers.permutations -> @n { @perm.push( @n.join('') )}


for @perm.unique.sort -> $p {
    next unless $p > $base;
    say $p ;
    exit;
}
Collapse
 
oscherler profile image
Olivier “Ölbaum” Scherler

I’m learning Erlang.

At first, I wanted to use digit swapping, like @coreyja , but it was harder than I initially thought (e.g. 351 needs two swaps, because the next larger number is 513, not 531.)

To validate the swapping method, I wrote a blunt version that converts a number into an array of digits, lists all the permutations, sorts them and finds the next occurence. For that I searched for a permutation function. It uses generators and list comprehensions, and I haven’t taken the time to understand it yet, but I’ll definitely try that in future challenges.

So my current solution is the blunt one (and I removed the unit tests for the intermediate functions, that are useful for development but not interesting for the solution).

-module( next ).

-include_lib("eunit/include/eunit.hrl").

% convert an integer to an array of digits
digits( N ) when N >= 0 ->
    digits( N, [] ).
digits( N, Digits ) when N < 10 ->
    [ N | Digits ];
digits( N, Digits ) ->
    digits( N div 10, [ N rem 10 | Digits ] ).

% convert an array of digits to an integer
number( Digits ) ->
    number( Digits, 0 ).
number( [ D | Rest ], N ) ->
    number( Rest, N * 10 + D );
number( [], N ) ->
    N.

% list all permutations of an array, taken from
% http://erlang.org/doc/programming_examples/list_comprehensions.html#permutations
perms( [] ) -> [ [] ];
perms( L )  -> [ [ H | T ] || H <- L, T <- perms( L -- [ H ] ) ].

% return the first element occuring after N in a list
find_next( N, [ N, M | _ ] ) ->
    M;
find_next( N, [ _ | Rest ] ) ->
    find_next( N, Rest );
find_next( _, [] ) ->
    none.

next( N ) ->
    Digits = digits( N ),
    Next = find_next( Digits, lists:sort( perms( digits( N ) ) ) ),
    case Next of
        none -> none;
        _ -> number( Next )
    end.

next_test_() -> [
    ?_assertEqual( none, next( 5 ) ),
    ?_assertEqual( 51, next( 15 ) ),
    ?_assertEqual( 536, next( 365 ) ),
    ?_assertEqual( 21, next( 12 ) ),
    ?_assertEqual( 531, next( 513 ) ),
    ?_assertEqual( 513, next( 351 ) ),
    ?_assertEqual( none, next( 531 ) ),
    ?_assertEqual( 2091, next( 2019 ) )
].
Collapse
 
peter279k profile image
peter279k

Here is my simple solution with PHP:

function nextBigger($n) {
  // your code here
  if (strlen($n) === 1) {
    return -1;
  }

  $answer = 0;
  $maxNumber = findMaxNumber($n);

  if ($maxNumber === $n) {
    return -1;
  }

  $nInfoArray = [];
  $strCountArray = [];

  $index = 0;
  $str = (string)$n;
  for (; $index < strlen($str); $index++) {
    if (array_key_exists((string)$str[$index], $nInfoArray) === true) {
      $nInfoArray[(string)$str[$index]] += 1;
    } else {
      $nInfoArray[(string)$str[$index]] = 1;
      $strCountArray[(string)$str[$index]] = 0;
    }
  }

  for ($min=$n+1; $min<=$maxNumber; $min++) {
    $str = (string)$min;
    $strIndex = 0;
    $findAlert = false;
    for(; $strIndex<strlen($str); $strIndex++) {
      if (strpos((string)$n, (string)$str[$strIndex]) !== false) {
        $strCountArray[(string)$str[$strIndex]] += 1;
        if ($strCountArray[(string)$str[$strIndex]] > $nInfoArray[(string)$str[$strIndex]]) {
            $findAlert = true;
        }
      } else {
        $findAlert = true;
        break;
      }
    }

    foreach ($strCountArray as $key => $value) {
      $strCountArray[$key] = 0;
    }

    if ($findAlert === true) {
      continue;
    }

    $answer = $min;
    break;
  }

  if ($answer === $n) {
    return -1;
  }

  return $answer;
}

function findMaxNumber($n) {
  $maxNumberArray = [];
  $string = (string)$n;

  for($index=0; $index<strlen($string); $index++) {
    $maxNumberArray[] = $string[$index];
  }

  sort($maxNumberArray);

  $maxNumberArray = array_reverse($maxNumberArray);

  return (int)implode($maxNumberArray);
}
Collapse
 
shayau profile image
Shaya • Edited

This was my solution on CodeWars (JS):

//helper functions
const nearestUp = (input, lookup) => lookup.sort((a, b) => a - b).find(n => n > input);
const isArrayDecreasing = (array) => !(array.reduce((n, item) => n !== false && item >= n && item))

//main function
const nextBigger = n =>  {
  const numberSplitted = String(n).split('');
  for (let i = numberSplitted.length-1; i > 0; i--) {

    if (isArrayDecreasing([numberSplitted[i], numberSplitted[i-1]])){
      let nextHigherNumber = numberSplitted.splice(0, i-1);
      const firstToReplace = nearestUp(numberSplitted[0], numberSplitted);

      numberSplitted.sort((a , b) => a - b);
      nextHigherNumber.push(firstToReplace);
      numberSplitted.splice(numberSplitted.indexOf(firstToReplace), 1);

      nextHigherNumber = nextHigherNumber.concat(...numberSplitted)[0] === '0' ? -1 : Number(nextHigherNumber.concat(...numberSplitted).join(''));
      return nextHigherNumber;
    }
  }
  return -1;
}
Collapse
 
kvharish profile image
K.V.Harish • Edited

My solution in js


const nextLargerNumber = (num) => {
  const largerNumber = parseInt(`${num}`.split('').sort().reverse().join(''));
  return num == largerNumber ? -1 : largerNumber;
};

Collapse
 
praneetnadkar profile image
Praneet Nadkar • Edited

I know I am late.
This what I did in C#

static void Main()
{
     Console.WriteLine("Enter any integer: ");
     var read = Console.ReadLine();
     var referrer = new string(read.ToCharArray().OrderBy(i => i).ToArray());
     var input = read.ToCharArray().Select(x => int.Parse(x.ToString())).ToList();
     var first = int.Parse(read);
     var last = int.Parse(string.Join("", input.OrderByDescending(i => i).ToArray()));
     var permutations = Enumerable.Range(first, last).ToList();
     var container = new List<int>();
     foreach (var item in permutations)
     {
       var reference = new string(item.ToString().ToCharArray().OrderBy(i => i).ToArray());

       int c = string.Compare(referrer, reference);
       if (c != 0) continue;        
        container.Add(int.Parse(item.ToString()));
     }

     var inputNumberIndex = container.IndexOf(int.Parse(read));
     if (inputNumberIndex >= 0)
     {
        if (container.Count == 0) Console.WriteLine(container.FirstOrDefault());

        var findIndex = inputNumberIndex + 1;
        Console.WriteLine(container[findIndex]);
     }
     else
     {
       Console.WriteLine("-1");
     }


   Console.ReadKey();
 }
Collapse
 
tanguyandreani profile image
Tanguy Andreani • Edited

Ruby

Put this together on my phone sorry for formatting.

This one doesn’t generate all the permutations of all the digits.

[9999, 12, 513, 2019].each do |initial|
  next_larger = initial.to_s.reverse
  next_larger.length.times do |i|
    next_larger.length.times do |j|
      # luckily for us, ascii numbers are stored
      # in the same order as actual numbers
      if next_larger[j] > next_larger[i]
        tmp = next_larger[j]
        next_larger[j] = next_larger[i]
        next_larger[i] = tmp
      end
    end
  end
  next_larger.reverse!

  puts "#{initial}\t#{next_larger}" if initial != next_larger.to_i
end

repl.it/@daxyq/DailyChallenge12

Collapse
 
alvaromontoro profile image
Alvaro Montoro

Ooops. Today I caught the challenge a bit late... I sketched something, hopefully I'll finish it by tomorrow before the next challenge :-/

Collapse
 
coreyja profile image
Corey Alexander

I didn't get to this one till today too, and I still own one from a few days ago! So don't feel too bad lol