loading...
Cover image for Daily Coding Puzzles - Oct 29th - Nov 2nd

Daily Coding Puzzles - Oct 29th - Nov 2nd

aspittel profile image Ali Spittel Updated on ・1 min read

Every day on Twitter, I post coding puzzles. These are quick coding challenges that increase in difficulty across the span of the week -- with Monday being the most beginner friendly and Friday being super tough. I love seeing other people's solutions as well, and so people post their solutions as well to the problem in any programming language.

Here's more about them.

I wanted to try posting these here. I'm going to post each question from this week as a comment below, and then we will thread answers under those questions. Please feel free to post your solutions to the ones you are interested in below! Then, you can comment with insights into people's solutions below that! I will also add a meta thread if you have advice on how to format this in the future!

Excited to see your solutions!

Discussion

pic
Editor guide
Collapse
aspittel profile image
Ali Spittel Author

Monday

Count of positives / sum of negatives (8 KYU):

Return an array, where the first element is the count of positives numbers and the second element is sum of negative numbers.

link

Collapse
dance2die profile image
Sung M. Kim

Solved it awhile ago (forgot about it).

Here is a C# answer.

using System.Linq;
using System;

public class Kata
{
    public static int[] CountPositivesSumNegatives(int[] a)
    {
        // guard clause for edge cases
        if (a == null || a.Length == 0) return new int[0];

        int count = 0;
        int sum = 0;
        // ".ToList()" is required to iterate the sequence
        a.Select(n => n > 0 ? count++ : sum += n).ToList();

        return new[] {count, sum};
    }
}

And just re-solved it using JavaScript

function countPositivesSumNegatives(input) {
    return (input && input.length >= 1) 
      ? input.reduce((acc, n) => {
          n > 0 ? acc[0]++ : acc[1] += n;
          return acc;
        }, [0, 0]) 
    : [];
}
Collapse
asparallel profile image
AsParallel

The C# version is likely better solved with the linq aggregate monad. Less ram, no side effects.

Thread Thread
dance2die profile image
Sung M. Kim

Thanks for the suggestion there, @asparallel .

Here is the updated C# code (with the same logic as JavaScript one) using .Aggregate.

using System.Linq;
using System;

public class Kata
{
    public static int[] CountPositivesSumNegatives(int[] a)
    {
        return (a == null || a.Length == 0) 
          ? new int[0]
          : a.Aggregate(new [] {0, 0}, (acc, n) => {
              if (n > 0) acc[0]++;
              else acc[1] += n;
              return acc;
            });
    }
}
Thread Thread
asparallel profile image
AsParallel

Further optimization I'd probably press for, use a tuple to move the entire aggregation onto the stack:

  public static IList<int> CountPositivesSumNegatives(int[] values)
  {
    if (values == null || values.Length == 0) return new int[0];

    var result = values.Aggregate((0, 0), (seed, value) =>
    {
      if (value > 0) seed.Item1++;
      else seed.Item2 += value;
      return seed;
    });

    return new[] { result.Item1, result.Item2 };
  }
Thread Thread
dance2die profile image
Sung M. Kim

Ah ha. Tuple being a value type, it is better optimized.
Thanks for the tips there 👊

Collapse
tux0r profile image
tux0r
(defun monday (in-param)
    (list
        ;; positive numbers:
        (apply #'+ (remove-if-not #'plusp in-param))

        ;; negative numbers:
        (apply #'+ (remove-if #'plusp in-param))))

Usage:

* (monday (list 1 2 5 -2 -7))

(8 -9)
Collapse
gypsydave5 profile image
David Wickes

Common Lisp FTW!

Collapse
choroba profile image
E. Choroba
#! /usr/bin/perl
use warnings;
use strict;

use List::Util qw{ sum0 };

sub cpsn {
    return unless @_;
    my @neg = grep $_ <= 0, @_;
    return @_ - @neg, sum0(@neg)
}

use Test::More tests => 5;
is_deeply [cpsn()], [];
is_deeply [cpsn(-1)], [0, -1];
is_deeply [cpsn(0, 0)], [0, 0];
is_deeply [cpsn(2)], [1, 0];
is_deeply [cpsn(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -11, -12, -13, -14, -15)],
          [10, -65];
Collapse
kaelscion profile image
kaelscion

Python 3 solution update. Posted to the wrong part of the discussion :P


def count_and_sum(arr, x):
    if not arr == None and len(arr) > 0:
        ct = len([i for i in arr if i > x])
        sum_neg = sum([i for i in arr if i <= x])
        return [ct, sum_neg]
    else:
        return([])
Collapse
thejessleigh profile image
jess unrein

Idk that this is an actual good Go solution - I'm not a Go expert so it can be hard for me to tell sometimes. It's so idiomatically verbose!

func Count(a []int) (r []int) {
    r = make([]int, 0)

    if len(a) == 0 {
        return
    }

    var pos int = 0
    var neg int = 0

    for _, item := range a {
        if item >= 0 {
            pos += 1
        } else {
            neg += item
        }
    }

    r = append(r, pos)
    return append(r, neg)
}
Collapse
aspittel profile image
Ali Spittel Author

Refactored to the code-golfiest thing ever with help of @joshcheek !

const countPositivesSumNegatives=i=>(i||[]).reduce(([c=0,s=0],v)=>v>0?[++c,s]:[c,s+v],[])
Collapse
tux0r profile image
tux0r

The golfiest version would probably be in Dyalog APL - even with newlines:

A←1 2 3 ¯4 ¯5 ¯6
X←+/(~A<0)/A
Y←+/(~A>0)/A
O←X Y

Output:

    O
6 ¯15
Thread Thread
gypsydave5 profile image
David Wickes

I will one day be able to look at APL without my brain leaking out of my ears.

Today is not that day.

Thread Thread
tux0r profile image
tux0r

This was my first time trying to actually do something with it. It was fun and it still sucked my brains out. (Both of them.)

Thread Thread
joshcheek profile image
Josh Cheek

Oh holy shit! I was looking at it for several minutes and it started making sense! Maybe because I thought through problem with @aspittel , or maybe this APL is more sensible (the last one I saw, someone had spilled a bag of unicode across its source).

I'm using Ruby's comment syntax because IDK how to do it in APL

# Haskell uses arrows for assignment in `do` blocks.
# Whitespace delimited numbers are a thing in lisp.
# The high bar looks a lot like a minus sign, so:

A←                 # set into the variable A
A←1 2 3 ¯4 ¯5 ¯6   # the list of numbers: [1, 2, 3, -4, -5, -6]


# Haskell iplements + as a function that you can pass around
# The slash looks like and is used like a shell pipeline.
# Tilde is logical negation in many syntaxes.
# `A` in `A<0` is like SQL, which uses the
# table name to refer to that table's current row.

X←             # set into the variable X
X←+/           # the sum of
X←+/(~         # the numbers which aren't
X←+/(~A<0)/    # negative
X←+/(~A<0)/A   # from the list A

Y←            # set into the variable Y
Y←+/          # the sum of
Y←+/(~        # the variables that aren't
Y←+/(~A>0)/   # positive
Y←+/(~A>0)/A  # from the list A

O←X Y    # set X and Y as the output
Thread Thread
tux0r profile image
tux0r

maybe this APL is more sensible (the last one I saw, someone had spilled a bag of unicode across its source).

That's the thing with first tries: You mostly write code which is relatively easy to understand. The APL symbol for comments is , by the way. And I have no idea how to write it without a Unicode table. ;-)

Thank you for your explanation. I finally understand wtf I was doing. (I know that I could probably have obfuscated it even more, "not negative" is longer than "positive", but I think I still won.)

Collapse
kspeakman profile image
Kasey Speakman

F#

let update (count, sum) value =
    if value > 0 then (count + 1), sum
    else              count, (sum + value)

// usage, start with 0 count/sum, update them for each value
let (count, sum) = Array.fold update (0, 0) inputArr

This returns a tuple instead of an array, which I believe is an improvement.

Collapse
sdicke profile image
Sebastian Martin Dicke

Haskell

countPositivesSumNegatives :: [Int] -> [Int]
countPositivesSumNegatives input =
    let positives = length $ filter (>= 0) input in
    let negatives = sum $ filter (<0) input in
    [positives, negatives]
Collapse
clandau profile image
Courtney

TypeScript

export function countPositivesSumNegatives(input: number[]) : number[] {
  let positiveCount = 0, negativeSum = 0;
  if(!input || !input.length) return [];
  for(let num of input) {
      if(num <= 0) negativeSum += num;
      else positiveCount++;
    }
  return [positiveCount, negativeSum];
}
Collapse
bodonferenc profile image
Ferenc Bodon

Q/kdb+ solution (let l be the input list):

(sum l > 0; sum l where l < 0)
Collapse
aspittel profile image
Ali Spittel Author

Tuesday

Ones and Zeros (7 KYU):

Given an array of one's and zero's convert the equivalent binary value to an integer.

link

Collapse
dance2die profile image
Sung M. Kim

Here is a C# version

Note: Aggregate is equivalent to reduce in JavaScript or other languages
and seed value is the first argument unlike in JavaScript, in which it's the last argument.

using System;
using System.Linq;
namespace Solution
{
    class Kata
    {
        public static int binaryArrayToNumber(int[] a)
        {
            return Convert.ToInt32(a.Aggregate("", (acc, n) => acc + n.ToString()), 2);
        }
    }
}
Collapse
bodonferenc profile image
Ferenc Bodon

Q/kdb+ solution (let l be the input list):

with list multiplication:

sum l * 2 xexp reverse til count l

with adverb over:

{y + 2*x} over l
Collapse
kspeakman profile image
Kasey Speakman

F#

Edit: shortened

let update value (sum, mult) =
    sum + (value * mult), mult * 2

// usage, processes array right to left
let (sum, _) = Array.foldBack update inputArr (0,1)
Collapse
tux0r profile image
tux0r

Common Lisp again:

(setf bits '(1 0 0 0)) ;; or something
(reduce (lambda (x y) (+ (* 2 x) y)) bits)

Output:

8

This is entirely type-agnostic and will not overflow for large input arrays.

Collapse
choroba profile image
E. Choroba
#! /usr/bin/perl
use warnings;
use strict;

sub bin2int {
    my ($i, $r);
    $r += 2 ** $i++ * pop while @_;
    return $r
}

use Test::More tests => 9;
is bin2int(0, 0, 0, 1), 1;
is bin2int(0, 0, 1, 0), 2;
is bin2int(0, 1, 0, 1), 5;
is bin2int(1, 0, 0, 1), 9;
is bin2int(0, 0, 1, 0), 2;
is bin2int(0, 1, 1, 0), 6;
is bin2int(1, 1, 1, 1), 15;
is bin2int(1, 0, 1, 1), 11;
is bin2int((1) x 20), 2 ** 20 - 1;
Collapse
aspittel profile image
Ali Spittel Author

My Python solution:

def binary_array_to_number(arr):
    return int(''.join(str(i) for i in arr), 2)
Collapse
tux0r profile image
tux0r

This will cause problems on Python 2 where int has a maximum value which is easily exceeded.

Thread Thread
aspittel profile image
Ali Spittel Author

true -- I'm on Python 3 though and the test cases are all small

Thread Thread
tux0r profile image
tux0r

"Nobody will notice" is a developer's worst enemy. ;-)

Collapse
gmartigny profile image
Guillaume Martigny

Plain JS:

function arrayToInt (arr) {
  return Number.parseInt(arr.join(""), 2);
}
Collapse
clandau profile image
Courtney
const binaryArrayToNumber = arr => {
  return parseInt(arr.join(''), 2);
};
Collapse
aspittel profile image
Ali Spittel Author

Thursday

Calculating with Functions:

This time we want to write calculations using functions and get the results. For example:

seven(times(five())); // must return 35

link

Collapse
simoroshka profile image
Anna Simoroshka
const make = (f, n) => f ? f(n) : n;
const one = f => make(f, 1);
const two = f => make(f, 2);
const three = f => make(f, 3);
const four = f => make(f, 4);
const five = f => make(f, 5);
const six = f => make(f, 6);
const seven = f => make(f, 7);
const eight = f => make(f, 8);
const nine = f => make(f, 9);
const ten = f => make(f, 10);

const plus = a => b => b + a;
const minus = a => b => b - a;
const times = a => b => b * a;
const dividedBy = a => b => b / a;

thanks, it's fun :)

Collapse
dance2die profile image
Sung M. Kim

Ugly but worked :p
JavaScript

function zero() { return arguments.length === 1 ? arguments[0](0) : 0; }
function one() { return arguments.length === 1 ? arguments[0](1) : 1; }
function two() { return arguments.length === 1 ? arguments[0](2) : 2; }
function three() { return arguments.length === 1 ? arguments[0](3) : 3; }
function four() { return arguments.length === 1 ? arguments[0](4) : 4; }
function five() { return arguments.length === 1 ? arguments[0](5) : 5; }
function six() { return arguments.length === 1 ? arguments[0](6) : 6; }
function seven() { return arguments.length === 1 ? arguments[0](7) : 7; }
function eight() { return arguments.length === 1 ? arguments[0](8) : 8; }
function nine() { return arguments.length === 1 ? arguments[0](9) : 9; }

function plus() {var val = arguments[0]; return function(left) { return left + val; }}
function minus() {var val = arguments[0]; return function(left) { return left - val; }}
function times() {var val = arguments[0]; return function(left) { return left * val; }}
function dividedBy() {var val = arguments[0]; return function(left) { return left / val; }}
Collapse
choroba profile image
E. Choroba
#! /usr/bin/perl
use warnings;
use strict;

sub one   { _num(@_, 1) }
sub two   { _num(@_, 2) }
sub three { _num(@_, 3) }
sub four  { _num(@_, 4) }
sub five  { _num(@_, 5) }
sub six   { _num(@_, 6) }
sub seven { _num(@_, 7) }
sub eight { _num(@_, 8) }
sub nine  { _num(@_, 9) }
sub zero  { _num(@_, 0) }

sub _num { ref $_[0] ? $_[0]->($_[1]) : $_[0] }

sub plus       { my $x = shift; sub {     shift() + $x } }
sub minus      { my $x = shift; sub {     shift() - $x } }
sub Times      { my $x = shift; sub {     shift() * $x } }
sub divided_by { my $x = shift; sub { int(shift() / $x) } }

use Test::More tests => 4;

is four(plus(nine())), 13;
is eight(minus(three())), 5;
is seven(Times(five())), 35;
is six(divided_by(two())), 3;
Collapse
aspittel profile image
Ali Spittel Author

Python solution:

def perform_operation(operations, number):
    if not operations: return number
    if operations["sign"] == "*":
        return operations["value"] * number
    if operations["sign"] == "+":
        return operations["value"] + number
    if operations["sign"] == "-":
        return number - operations["value"] 
    if operations["sign"] == "/":
        return  number // operations["value"]

zero = lambda operations=None : perform_operation(operations, 0)
one = lambda operations=None : perform_operation(operations, 1)
two = lambda operations=None : perform_operation(operations, 2)
three = lambda operations=None : perform_operation(operations, 3)
four = lambda operations=None : perform_operation(operations, 4)
five = lambda operations=None : perform_operation(operations, 5)
six = lambda operations=None : perform_operation(operations, 6)
seven = lambda operations=None : perform_operation(operations, 7)
eight = lambda operations=None : perform_operation(operations, 8)
nine = lambda operations=None : perform_operation(operations, 9)

get_operation = lambda operation, num : {"sign": operation, "value": num}
plus = lambda num : get_operation("+", num)
minus = lambda num : get_operation("-", num)
times = lambda num : get_operation("*", num)
divided_by = lambda num : get_operation("/", num)

Though I prefer this one from the CodeWars solutions!

def zero(f = None): return 0 if not f else f(0)
def one(f = None): return 1 if not f else f(1)
def two(f = None): return 2 if not f else f(2)
def three(f = None): return 3 if not f else f(3)
def four(f = None): return 4 if not f else f(4)
def five(f = None): return 5 if not f else f(5)
def six(f = None): return 6 if not f else f(6)
def seven(f = None): return 7 if not f else f(7)
def eight(f = None): return 8 if not f else f(8)
def nine(f = None): return 9 if not f else f(9)

def plus(y): return lambda x: x+y
def minus(y): return lambda x: x-y
def times(y): return lambda  x: x*y
def divided_by(y): return lambda  x: x/y
Collapse
gypsydave5 profile image
David Wickes

seven(times(five())); // must return 35

Why not "must return thirtyFive - a function which is thirty-five"?

Related: Church Numerals.

Collapse
chubbard profile image
Charlie Hubbard

A groovy version that will do it out to billions. For example:

import static WordMath.*
words {
   oneBillionTwoMillionThreeThousandFiveHundredSixtyFour( plus( one() ) )
}

The only unfortunate thing is in order to support methodMissing it has to be done on instance methods so the words closure hides that fact

class WordMath {

    Map<String,Integer> NAMES_TO_VALUE = [
        "one": 1,
        "two": 2,
        "three": 3,
        "four": 4,
        "five": 5,
        "six": 6,
        "seven": 7,
        "eight": 8,
        "nine": 9,
        "ten": 10,
        "eleven": 11,
        "twelve": 12,
        "thirteen": 13,
        "fourteen": 14,
        "fifteen": 15,
        "sixteen": 16,
        "seventeen": 17,
        "eighteen": 18,
        "nineteen": 19,
        "twenty": 20,
        "thirty": 30,
        "fourty": 40,
        "fifty": 50,
        "sixty": 60,
        "seventy": 70,
        "eighty": 80,
        "ninety": 90,
        "hundred": 100,
        "thousand": 1_000,
        "million": 1_000_000,
        "billion": 1_000_000_000
    ]

    static Integer words(Closure c) {
        c.delegate = new WordMath()
        c()
    }

    def plus( Integer v ) {
        return { v2 -> v2 + v }
    }

    def minus( Integer v ) {
        return { v2 -> v2 - v }
    }

    def times( Integer v ) {
        return { v2 -> v2 * v }
    }

    def dividedBy( Integer v ) {
        return { v2 -> v2 / v }
    }

    def methodMissing( String name, args ) {
        Integer value = parseValue( name )
        if( args.size() > 0 ) {
            args[0]( value )
        } else {
            return value
        }
    }

    Integer parseValue(String name) {
        Integer value = 0
        Integer buffer = 0
        name.replaceAll(/([A-Z])/, ' $1').toLowerCase().split(" ").each { String  number ->
            Integer v = NAMES_TO_VALUE[ number ]
            if( v ) {
                if( v < 100 ) {
                    buffer += v
                } else {
                    buffer *= v
                    if( v > 999 ) {
                        value += buffer
                        buffer = 0
                    }
                }
            } else {
                println("Unknown number ${number}!")
            }
        }
        return value + buffer
    }
}
Collapse
clandau profile image
Courtney

Apparently I've done this kata before...but I don't know if that even helped me this time. It's so hard to wrap my brain around.

function zero() {
  return arguments.length ? arguments[0](0) : 0;
}
function one() {
  return arguments.length ? arguments[0](1) : 1;
}
function two() {
return arguments.length ? arguments[0](2) : 2;
}
function three() {
  return arguments.length ? arguments[0](3) : 3;
}
function four() {
  return arguments.length ? arguments[0](4) : 4;
}
function five() {
  return arguments.length ? arguments[0](5) : 5;
}
function six() {
  return arguments.length ? arguments[0](6) : 6;
}
function seven() {
  return arguments.length ? arguments[0](7) : 7;
}
function eight() {
  return arguments.length ? arguments[0](8) : 8;
}
function nine() {
  return arguments.length ? arguments[0](9) : 9;
}

function plus(b) {
  return function(a) { return Math.floor(a + b) }
}
function minus(b) {
  return function(a) { return Math.floor(a - b) }
}
function times(b) {
  return function(a) { return Math.floor(a * b) }
}
function dividedBy(b) {
  return function(a) { return Math.floor(a / b) }
}
Collapse
aspittel profile image
Ali Spittel Author

Wednesday

Write a program to reverse the digits of a positive integer but without converting it to a string.

Collapse
aspittel profile image
Ali Spittel Author

My Python solution:

def reverse_number(num, running_value=0):
    if num == 0: 
        return running_value // 10
    quotient, remainder = divmod(num, 10)
    running_value += remainder
    return reverse_number(quotient, running_value * 10)

print(reverse_number(123456))
print(reverse_number(5))
Collapse
dance2die profile image
Sung M. Kim

And now this is... 😮

Thread Thread
tux0r profile image
tux0r

... broken.

Collapse
tux0r profile image
tux0r
>>> print(reverse_number(1234567890))
987654321

You did not pass.

Thread Thread
dance2die profile image
Sung M. Kim

987654321 is how I expect it to work though without the 0 in the beginning as you should return a positive integer.

Thread Thread
tux0r profile image
tux0r

That was not a part of the question, so I would say that the result should still start with a 0.

Thread Thread
aspittel profile image
Ali Spittel Author

the positive integer shouldn't have a leading zero I don't think. It's at least up to interpretation.

Collapse
kspeakman profile image
Kasey Speakman

F#

let rec loop rev i =
    if i = 0 then rev
    else loop (rev * 10 + (i % 10)) (i / 10)

// usage, returns 987654321
let reversed = loop 0 123456789
  • Uses a recursive loop. (F# will TCO to a while loop on compile)
  • i % 10 gets the right-most digit of i
  • rev * 10 shifts the numbers left, with right-most zero
  • i / 10 shifts the numbers right, dropping right-most digit

I happened to remember these little number tricks from a previous challenge. This is basically using integers as digit stacks.

Collapse
choroba profile image
E. Choroba
#! /usr/bin/perl
use warnings;
use strict;

sub rev {
    my ($x) = @_;
    my $r = my $z = 0;
    my $start = 1;
    while ($x) {
        ! ($r *= 10) and $z += $start or undef $start;
        $r += $x % 10;
        $x = ($x - $x % 10) / 10;
    }
    return '0' x ($z - 1) . $r
}

use Test::More tests => 4;
is rev(3), 3;
is rev(123456789), 987654321;
is rev(4444), 4444;
is rev(1000), '0001';
Collapse
dance2die profile image
Sung M. Kim

Thank you, Ali.
This has been one of the most fun challenges.

Took me awhile but here is the C# version.

The gist is that, remainder is calculated for each digit, stored in a stack (LIFO - last in first out) to reverse the remainder.

Lastly the total is reconstructed from the stack.

Runnable code on .NET Fiddle

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        var a = new int[] {123456, 5, 654321, 1234567890};

        foreach (var n in a) {
            Console.WriteLine($"Reversed = {Reverse(n)}");  
        }
    }

    private static int Reverse(int input) {
        var stack = BuildStack(input);
        return ConvertStackToNumber(stack);
    }

    private static Stack<int> BuildStack(int input) {
        var power = 0;
        var stack = new Stack<int>();

        while (true) {
            power++;
            var modBy = (int) Math.Pow(10, power);
            var divisior = (int) Math.Pow(10, power - 1);

            var remainder = (input % modBy) / divisior;
            if (remainder == 0 && power != 1) break;

            stack.Push(remainder);
        }
        return stack;
    }

    private static int ConvertStackToNumber(Stack<int> stack) {
        var total = 0;
        var power = 0;
        while (stack.Count > 0) {
            var current = stack.Pop();
            total += current * (int)Math.Pow(10, power++);
        }
        return total;
    }
}
Collapse
aspittel profile image
Ali Spittel Author

Oh that's a really cool approach!

Collapse
clandau profile image
Courtney

probably not the best solution but it works. (unless you want leading zeros...but I'm assuming that's not the case since it wants a number).

function reverseNum(n) {
    const divisor = 10;
    let reversed = 0;
    let holder = [];
    while(n > 0) {
        holder.push(n % divisor);
        n = (Math.floor(n / divisor));
    }
    let place = Math.pow(10, holder.length-1);
    for(let i = 0; i < holder.length; i++) {
        reversed += (holder[i] * place);
        place /= 10;
    }
    return reversed;
}
Collapse
tux0r profile image
tux0r

As nothing in the question says that the result must still be an integer, why not make it an array instead? That would also elegantly solve the problem that an input that ends with a "0" would be chopped... or, even better, don't use any return value. After all, you did not ask for one.

#include <stdio.h>

void reverse_int(int in) {
    while (in > 0) {
        printf("%d", in % 10); /* modulo 10 ... */
        in /= 10; /* ... and move one digit. */
    }
}

/* PoC: */
int main(void) {
    reverse_int(1234567890);

    return 0;
}

Output:

0987654321
Collapse
aspittel profile image
Ali Spittel Author

Friday

Bathroom Stalls (Code Jam):

A certain bathroom has N + 2 stalls in a single row; the stalls on the left and right ends are permanently occupied by the bathroom guards. The other N stalls are for users.

link

Collapse
aspittel profile image
Ali Spittel Author

Python solution!

from math import floor, ceil

def clean_input_file(file_name):
    inp = open(file_name)
    inp = inp.read()
    inp = inp.split('\n')
    cases = int(inp[0])
    inp.pop(0)
    inp.pop()
    return inp, cases


def find_min_stall(stalls, people):
    nth_powers = []
    n = 0
    while sum(nth_powers) < people:
        nth_powers.append(2**n)
        n+=1

    sum_powers = sum(nth_powers)
    remaining_n = stalls - sum_powers
    key_power = nth_powers[-1]

    remaining_people = people - key_power
    rem = remaining_n % key_power
    div = (stalls / key_power) - 1

    product = div * rem
    remainder = remaining_n - product
    people_needed = key_power - rem

    if remaining_people > rem:
        sol = float(remainder / people_needed)
    else:
        sol = float(div)

    _max = int(ceil(sol/2))
    _min = int(floor(sol/2))
    return '{} {}'.format(_max, _min)


input_file, cases = clean_input_file('C-large-practice.in')

write_file = open('solution.txt', 'w+')
for idx, n in enumerate(input_file):
    n = n.split(' ')
    write_file.write("Case #{}: {}\n".format(idx + 1, find_min_stall(int(n[0]), int(n[1]))))
Collapse
cynary profile image
Rodrigo Toste Gomes

So I was curious since this solution didn't seem correct, and tried to run this through the codejam grader, and it seems like it isn't correct.

I had some fun with this problem, though (it entertained some part of a plane ride), and came up with a nice concise solution:

#!/usr/bin/python
from collections import defaultdict


def left_range(x):
    return x//2 - (1 if x%2 == 0 else 0)


def right_range(x):
    return x//2


def best_toilet(n, k):
    assert n >= 1
    assert 1 <= k <= n

    k -= 1
    ranges = defaultdict(lambda: 0)
    ranges[n] = 1
    while True:
        r = max(ranges.keys())
        quant = ranges[r]
        if k >= quant:
            k -= quant
            del ranges[r]
            ranges[left_range(r)] += quant
            ranges[right_range(r)] += quant
        else:
            break

    m = max(ranges.keys())
    return (left_range(m), right_range(m))


def main():
    t = int(input().strip())
    for i in range(t):
        n, k = (int(val) for val in input().strip().split(' '))
        min_dist, max_dist = best_toilet(n, k)
        print("Case #%d: %d %d" % (i+1, max_dist, min_dist))


if __name__ == "__main__":
    main()

A few insights here:

  1. When picking a stall, instead of considering two pieces, Rs, Ls, of state, all you need to know is the size of groups of free stalls. You always pick the middle stall of the largest group of sequential free stalls (in case of ties, you pick the leftmost group, in case the size is even, you pick the half-left stall).
  2. Order doesn't matter - the problem doesn't ask for which stall the Kth person is going to pick, it asks indirectly for the size of the group (given the size of the group you can easily compute max(Ls, Rs) and min(Ls, Rs).
  3. You can group stall groups by size - so this is a little trickier, but you can consider the choices of stalls as a binary tree (the solution above seemed to be going in that direction). Each choice corresponds to a group of stalls. At each level of the binary tree, you'll have a lot of repeated group sizes. In particular, each level of the binary tree has at most 2 different group sizes (I'll leave this as an exercise for you to prove). So, instead of splitting each group one at a time, since order doesn't matter, we can split all groups of the same time in one step, and just add groups for the next level.

At the end you get a nice concise O(log(K)) runtime and O(1) space solution.

Here's an example of how this works by manually solving N=1000 and K=100:

You start with a group of size 1000 for free stalls, so your group size -> number of groups maps looks like this:

Step 1:
1000 -> 1
k = 100

You split 1000 into two groups, one of 499, and one of size 500, and this represents the choice of 1 person, since there is 1 group of size 1000. So now our state looks like:

Step 2:
500 -> 1
499 -> 1
k = 99

Now you split 500 into 249 and 250:

Step 3:
499 -> 1
249 -> 1
250 -> 1
k = 98

Now I'll just draw the next steps, without explaining:

Step 4: 250 -> 1, 249 -> 3, k = 97
Step 5: 249 -> 3, 125 -> 1, 124 -> 1, k = 96
Step 6: 125 -> 1, 124 -> 7, k = 93
Step 7: 124 -> 7, 62 -> 2, k = 91
Step 8: 62 -> 9, 61 -> 7, k = 84
Step 9: 61 -> 7, 31 -> 9, 30 -> 9, k = 75
Step 10: 31 -> 9, 30 -> 23, k = 68
Step 11: 30 -> 23, 15 -> 18, k = 59
Step 12: 15 -> 41, 14 -> 23, k = 36

Now things get special, because there are 41 groups of 15 free stalls, but only 36 people left to choose a stall. Therefore, the last person will choose the middle stall of a group of 15 free stalls, and thus Ls = 7 and Rs = 7!

Thread Thread
aspittel profile image
Ali Spittel Author

Ah -- I must have introduced an issue while refactoring -- it passed the tests during the competition. But then I refactored, should have checked again!

Collapse
aspittel profile image
Ali Spittel Author

Meta

Discussion on how I should format this post!

Collapse
rrampage profile image
Raunak Ramakrishnan

I think you should add the problems to the post itself. Otherwise, the later problems will get lost in the comment thread. It will be even better to create a separate post per problem and embed them in the weekly post. That way, discussion will be more focused.

Collapse
aspittel profile image
Ali Spittel Author

yeah -- the only thing that makes me nervous about that is it seeming spammy to post one every day?

Collapse
tux0r profile image
tux0r

Meta-meta: Discussion on how you ignore all the replies!

Collapse
aspittel profile image
Ali Spittel Author

Haha there are worse problems out there

Collapse
thejessleigh profile image
jess unrein

You've got me on a go kick, and now I'm going back and doing previous exercises you've posted! (Sorry for the large volume of comments on your posts today.