v/programming: We need more programming challenges. We should start off small: First non-repeating character of a string. Any language you like.

greaseBTC · 2016-04-15T09:42:04Z

Example input yellow tooth Example output y h Pro tip: Add four extra indents to your code for formatting.

6 u/RayLomas 15 Apr 2016 12:01

Goddamnit... I should be working, and I'm writing a bash one liner...

Doesn't match the input precisely, but it's easy to adjust

bash-4.2$ echo "qwertyqwer" | fold -w 1 | nl | tr -s ' ' | sort --key 2 | uniq -c  -f 1 | grep -F '    1 ' | cut -c 8- | sort --numeric | head -n 1 | cut -f 2
t
bash-4.2$ echo "qwertywert" | fold -w 1 | nl | tr -s ' ' | sort --key 2 | uniq -c  -f 1 | grep -F '    1 ' | cut -c 8- | sort --numeric | head -n 1 | cut -f 2
q
bash-4.2$ echo "yellow" | fold -w 1 | nl | tr -s ' ' | sort --key 2 | uniq -c  -f 1 | grep -F '    1 ' | cut -c 8- | sort --numeric | head -n 1 | cut -f 2
y
bash-4.2$ echo "tooth" | fold -w 1 | nl | tr -s ' ' | sort --key 2 | uniq -c  -f 1 | grep -F '    1 ' | cut -c 8- | sort --numeric | head -n 1 | cut -f 2
h

6 u/VxMxPx 15 Apr 2016 12:49

No PHP? Here's one liner.

<?php
for ($i=0 or $var=fread(STDIN, 8192); $i<strlen($var); (substr_count($var, $var[$i]) === 1) ? exit($var[$i]) : $i++);

Edit: modified from two, to one line.

1 u/RayLomas 15 Apr 2016 15:35

This one takes the cake. Beauty of for ($i=0 or $var=fread(STDIN, 8192); is astonishing. I'm 100% serious.

0 u/VxMxPx 15 Apr 2016 22:01

Ha! Thank you. I knew I'll have to be a little bit creative if I'll go with PHP. ;)

3 u/djdevin 15 Apr 2016 16:17

different approach

<?php
print (key(array_filter(array_count_values(str_split(fread(STDIN, 8192))), function($y) {return $y<2;})));

1 u/VxMxPx 15 Apr 2016 22:02

This is wonderful, I was actually thinking about functional approach.

0 u/djdevin 17 Apr 2016 06:47

thanks, I call it the "lazy" approach

1 u/eqi397 16 Apr 2016 00:18

thats not really a one liner, more like 5 lines crammed into one

0 u/VxMxPx 16 Apr 2016 03:06

I'm pretty much sure that's the definition of one liners. But of course, this particular example is not something anyone should be using in production, for obvious reasons.

6 u/sir_hanselot 15 Apr 2016 15:41

Less Python:

def non_repeat(some_string):
    return [char for char in some_string if some_string.count(char) < 2][0]

2 u/i_am_triggered 15 Apr 2016 23:23

If you would use generator expression instead of list comprehension and next() instead of [0] it would stop on first match instead of going through whole string. Only difference would be IterationStop exception instead of IndexError when no match.

I didn't test it, but I'm pretty sure I'm right :)

5 u/main_gi 15 Apr 2016 13:42

Python

def fnrc(x): #First non-repeating character
    temp = x
    while len(temp) != 0:
        if temp.count(str(temp[0]), 0, len(temp)) == 1:
            return temp[0]
        else:
            temp = temp.replace(str(temp[0]), "")
    return "No nrc found"

I love syntax errors. >_>

5 u/i_am_triggered 15 Apr 2016 23:20

This is not Python code, this is C code written in Python :P

3 u/main_gi 16 Apr 2016 04:43

Considering I don't know C, I estimate I will only get this joke 10 years later. @_@

1 u/TheBookWasBetter 16 Apr 2016 08:05

Python is an interpreted language built on C. Everything you write in python is viewed as C by your computer.

1 u/Tommstein 16 Apr 2016 09:10

Pretty sure that's not what he meant. Not least of which because your computer doesn't execute C either.

0 u/SelfReferenceParadox 17 Apr 2016 06:56

If we're going that route, isn't C just viewed as Assembly?

3 u/SelfReferenceParadox 17 Apr 2016 06:57

What he means is that the code is written the way you'd write it in C. In Python the preferred method would probably be more functional.

4 u/MadCamel 16 Apr 2016 07:20

Perl:

#!/usr/bin/perl -n
s/(.)(\1)+//; printf("%s\n", (split(//))[0]);

C. Pointer math is fun.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main() {
  char buf[512], *p, fc;
  while (read(0, &buf, 512) > 0) {
    for (p=buf, fc = *p; *p == fc && *p != 0; p++);
    if (p-1 == buf) // Single character edge-case
      printf("%c\n", fc);
    else
      printf("%c\n", *p);
  }
}

2 u/svipbo 16 Apr 2016 13:54

C version fails for input aba. The code here prints a even though a is a duplicate.

For aabbc, it thinks the answer is b.

1 u/MadCamel 16 Apr 2016 15:20

Thanks for giving it a try! I thought I was completely buried down here. That's proper behaviour given the specification as I understand it.

If I were asked to re-phrase the specification: Print the first character that isn't a repeat of the last.

AAAAABC - A is repeated, B is first non-repeating char
ABA - A doesn't repeat, B is first non-repeating char
ABBBBBBBBC - A doesn't repeat. B is the first non-repeating char
A - A doesn't repeat..

1 u/svipbo 16 Apr 2016 15:26

I thought something like that, but tooth is supposed to be h. It isn't t, because t appears twice, even though the two t's aren't next to each other. I think it means the first character that doesn't appear in the string twice.

3 u/RevanProdigalKnight 15 Apr 2016 13:31

JavaScript (ES6):

word => [...word].filter(letter => word.lastIndexOf(letter) === word.indexOf(letter))[0];

Written in plainer JavaScript (ES5) with comments:

function(word) {
  var i, array = [];
  // Spread the letters of `word` into an array. This was done by `[...word]` in the ES6 version
  for (i = 0; i < word.length; i++) {
    array.push(word[i]);
  }
  // Filter the array, returning only the letters of the word whose first occurrence is also their last occurrence
  return array.filter(function(letter) {
    return word.lastIndexOf(letter) === word.indexOf(letter);
  })[0]; // Return the first element of the resulting array
}

0 u/greaseBTC [OP] 28 Apr 2016 18:30

Couldn't you stop at the first occurence of lastIndexOf === indexOf

var result
array.some(function(letter) {
    if(word.lastIndexOf(letter) === word.indexOf(letter) {
        return result=letter;
    }
}
return result;

I suppose that wouldn't match your ES6 exactly.

0 u/RevanProdigalKnight 28 Apr 2016 22:23

Yeah, I was trying to match the ES6 precisely, though I noticed a few days after posting that I could have used arr = word.split('') instead of the manual loop.

2 u/greaseBTC [OP] 15 Apr 2016 09:45

#!/usr/bin/env node
var readline = require('linebyline');
var lo = require('lodash');
function readFirstNonRepeatingOfStream(input,cb) {
 readline(input).on('line',function(line) {
  var counts = lo.countBy(line);
  Object.keys(counts).some(function(char) {
   if(counts[char] === 1) {
    cb(char);
    return true; //Breaks out of the loop.
   }
  });
 });
}
readFirstNonRepeatingOfStream(process.stdin,function(char) {
 console.log(char);
});

2 u/smeezekitty 16 Apr 2016 03:30

Shitty C

#include <string.h>
int check_char(int i, char *str, char c){
    int j;
    int t = strlen(str);
    for(j = 0;j < t;j++){
        if(str[j] == c && j != i){
            return 0;
        }
    }
    return 1;
}
int main(){
    char input[256];
    gets(input);
    int i=0,t,j;
    t = strlen(input);
    for(;i < t;i++){
        char c = input[i];
            if(check_char(i, input, c)){
                putchar(c);
                return 0;
            }
    }
    return -1;
}

and a bit golfed

main(){char n[99],j,i,f;gets(n);for(i=0;n[i];i++){for(f=j=0;n[j];j++)f+=n[j]==n[i]&j!=i;if(!f){putchar(n[i]);break;}}}

1 u/svipbo 16 Apr 2016 13:32

Here's my shitty C:

char
first_non_repeating (char *s)
{
        char *p;
        int dup;
           characters with '0'. */
        for (; *s; s++) {
                if (*s == '0') {
                        continue;
                }
                dup = 0; 
                for (p = s + 1; *p; p++) {
                        if (*p == *s) {
                                *p = '0';
                                dup = 1;
                        }
                }
                if (!dup) {
                        return *s;
                }
        }
        return 0;
}
int
main ()
{
        char strings[] = "yellow\0tooth";
        char *s;
        for (s = strings; s < strings + sizeof (strings);
             s += strlen (s), s++) {
                printf ("%s ", s);
                printf ("%c\n", first_non_repeating (s));
        }
}

2 u/Tommstein 16 Apr 2016 06:14

In linear time, because you little bastards are performance-challenged:

#!/usr/bin/env python
word = 'yellow'
locs = {}
for i, letter in enumerate(word):
    if letter not in locs:
        locs[letter] = i 
    else:
        locs[letter] = None
print(word[min(i for letter, i in locs.items() if i is not None)])

Linear assuming the locs dictionary doesn't fuck shit up. Let's call it linearish. I'm not sure how Python dictionaries are implemented, but even the most retarded implementation on the planet should still only result in the quadratic time that you gits love so much.

2 u/TheBookWasBetter 16 Apr 2016 08:06

Can someone please write this in functional Scala?

1 u/Vladar 15 Apr 2016 11:33

Nim

while true:
  var input = readLine stdin
  if input.len < 1: break
  var once: seq[char] = @[]
  for ch in input:
    if once.contains ch: once.delete once.find ch
    else: once.add ch
  echo once[0]

0 u/Vladar 15 Apr 2016 14:10

Nim using strutils

import strutils
while true:
  var input = readLine stdin
  if input.len < 1: break
  for ch in input:
    if input.count(ch) == 1:
      echo ch
      break

1 u/Owoc 15 Apr 2016 13:15

Java:

public static char findFirstNonRepeatingCharacter(String s) {
    if (s.isEmpty()) {
        throw new IllegalArgumentException();
    }
    LinkedHashMap<Character, Integer> occurrences = new LinkedHashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (occurrences.containsKey(c)) {
            occurrences.put(c, occurrences.get(c) + 1);
        } else {
            occurrences.put(c, 1);
        }
    }
    for (Character c : occurrences.keySet()) {
        if (occurrences.get(c) == 1) {
            return c.charValue();
        }
    }
    throw new RuntimeException();
}

4 u/Tommstein 16 Apr 2016 05:32

And this is why nobody likes Java.

2 u/Owoc 16 Apr 2016 13:21

It could alternatively be written like MrKequc's snippet to be much more concise, but slower:

public static char firstNonRepeatingCharacter (String s) {
    for (char c : s.toCharArray()) {
        if (s.indexOf(c) == s.lastIndexOf(c)) {
            return c;
        }
    }
    throw new IllegalArgumentException();
}

1 u/Tommstein 16 Apr 2016 19:35

Yeah, I actually like your original algorithm, linear time I believe instead of all the quadratic BS that dominates the solutions here, the Java implementation just made me throw up in my mouth.

1 u/effusive_ermine 15 Apr 2016 17:57

#!/usr/bin/awk
{
    split("", c);
    for(i=1; i<=length($0); ++i)
        c[substr($0, i, 1)]++
    for(i=1; i<=length($0); ++i)
        if(c[substr($0, i, 1)]==1) {
           print substr($0, i, 1)
           break
        }
}

1 u/rwbj 15 Apr 2016 20:55

C# without LINQ

void Foo(string s)
{
    foreach( var c in s)
      if(s.IndexOf(c) == s.LastIndexOf(c))
      {
        Console.WriteLine(c);
        return;
      }
}

1 u/irl_badass_here 17 Apr 2016 06:38

In K:

  f:{*x@&1=+/x=/:x}

Example output:

  f "yellow"
"y"
  f "tooth"
"h"

1 u/greaseBTC [OP] 28 Apr 2016 18:38

I think you won at code golf.

1 u/SelfReferenceParadox 17 Apr 2016 06:54

In Haskell:

nonRepeat s = head $ filter (\c -> 1 == length (filter (==c) s )) s

0 u/thefloodcontrol 15 Apr 2016 13:40

Copied from /tech/ ?

0 u/pushthis 16 Apr 2016 00:16

program that uses infographics to describe cannabis profits per resale price based on purchase price and resale portion size.

0 u/dizzydog 20 Apr 2016 22:05

Recursive Java:

public class FnrC
{
    public static void main(String[] args) {
        if (args.length > 0) {
            System.out.println(fnrc(args[0], args[0].length()));
        } else {
            System.out.println("no args");
        }
    }
    static char fnrc(String str, int len) {
        if (str.length() == 1) {
            return str.charAt(0);
        } else {
            String subStr = str.substring(Math.abs(len - str.length()));
            String inStr = str.replace(subStr, "");
            if (subStr.indexOf(subStr.charAt(0), 1) < 0) {
                if (inStr.indexOf(subStr.charAt(0)) < 0) {
                    if (subStr.length() + inStr.length() != str.length()) {
                        return 0;
                    } else {
                        return subStr.charAt(0);
                    }
                }
                return fnrc(str, len - 1);
            } else {
                return fnrc(str, len - 1);
            }
        }
    }
}

0 u/whisky_cat 24 Apr 2016 11:30

fuck indents, especially four of them

0 u/greaseBTC [OP] 28 Apr 2016 18:38

It's that or two spaces at the end of every line.

ctrl-h \n \n[4 spaces]

We need more programming challenges. We should start off small: First non-repeating character of a string. Any language you like.

52 comments